Где-то примерно три или четыре года назад, когда количество написанного, стёртого и снова написанного мной кода, с одной стороны, вызывало у меня непреодолимое чувство гордости, а с другой (никак мне не видной), совсем не собиралось переходить в качество, появилась идея о реализации браузерной игры. Как всё проходило и почему ничего не получилось история отдельная, а вот тем, что я узнал об алгоритмах поиска пути и как это предполагалось применить на практике, я бы хотел с вами поделится.
Для начала, естественно была поставлена задача: в игре герой по миру должен перемещаться по тыку мыши в карту, с отображением построенного пути (аля Heroes of Might&Magic).
На тот момент, рынок браузерных игр был в разы… нет в РАЗЫ меньше и небольшое изучение этого рынка показало: достойной реализации карты перемещения героя по миру — нет (как минимум я не нашёл). И я отправился искать свой путь, точнее то, как бы этот путь реализовать.
После поиска информации о поиске пути и её изучения, как алгоритм реализации был выбран А* (А звёздочка).
Вот основные преимущества этого алгоритма:
Описать весь алгоритм в одной (да даже в двух) статьях просто не возможно, но, для заинтересованных, очень рекомендую вот этот перевод статьи Патрика Лестера, как вводный материал.
После того, как я посчитал, что достаточно знаю о А*, я взялся за дело настоящего программиста — стал искать, а не реализовал ли кто-нибудь нечто подобное, на нужной мне платформе. К моему не малому удивлению, удача таки повернулась нужным мне местом, и я нашёл то, что искал.
Заготовка, в виде js файла была препарирована, упразднена до нужных мне функций, оптимизирована, на сколько на тот момент хватало знаний и была приговорена к вечной службе сложному вопросу — куда пойти, куда податься. Посыпая голову пеплом, с прискорбием и сожалением сообщаю, что мной, увы, потеряны все данные о том кем была написана та, изначальная, версия js реализации А*,… ну не подумал я когда то, что это может ещё пригодится… всё, бейте меня семеро!
После того, как основная часть была сделана, остались частности — отрисовать найденный путь. На тот момент это было второстепенно и было реализовано первым же пришедшим в голову способом.
Перед тем, как показать, как же это всё выглядит, хочу обратить ваше внимание на то, что в то время, я понятия не имел о многих полезных вещах. Как например css спрайты. Так что не стоит ругать мой код, лучше по настольгируйте, вспоминая когда и вы писали робко и наивно, искренне радуясь, когда то, что написано, работает так, как задумано.
И так:
Вот как это выглядит
А тут всё это в запакованном виде
В данной конкретной реализации есть некоторая погрешность и при определённом выборе конечной точки находится не кратчайший путь, однако, поиск закономерности и решение этой проблемы было для меня не оправданным в соотношении польза/трудозатраты и баг так и остался не отловленным.
Кстати, когда-то был скриптик для рисования препятствий, но по всей видимости, он канул в лету.
P.S. На данный момент это работает под: FF 3, IE 7, Chrome и Safari 4 (всё под vista). Opera 9.64 работать отказывается, ну да цель не в этом.
Очень надеюсь, что хоть кому-то это может пригодиться или помочь, а для меня написание своей браузерной игры, не для заработка, а для души, наверное так и останется светлой мечтой, к которой всегда хочется стремится, но которую никак не достичь.
Для начала, естественно была поставлена задача: в игре герой по миру должен перемещаться по тыку мыши в карту, с отображением построенного пути (аля Heroes of Might&Magic).
На тот момент, рынок браузерных игр был в разы… нет в РАЗЫ меньше и небольшое изучение этого рынка показало: достойной реализации карты перемещения героя по миру — нет (как минимум я не нашёл). И я отправился искать свой путь, точнее то, как бы этот путь реализовать.
После поиска информации о поиске пути и её изучения, как алгоритм реализации был выбран А* (А звёздочка).
Вот основные преимущества этого алгоритма:
- Это один из самых быстрых алгоритмов поиска пути
- Можно легко манипулировать стоимостью прохода (т.е. по диагонали — это дальше, чем по прямой или 3 хода по болоту это хуже, чем 5 ходов по песку)
- Можно использовать не только квадратные ячейки карты, но и многоугольные
- Он достаточно легко трансформируется в алгоритм Дийкстры (без заданного вектора поиска), что делает его пригодным для поиска пути когда не известны координаты конечной точки.
Описать весь алгоритм в одной (да даже в двух) статьях просто не возможно, но, для заинтересованных, очень рекомендую вот этот перевод статьи Патрика Лестера, как вводный материал.
После того, как я посчитал, что достаточно знаю о А*, я взялся за дело настоящего программиста — стал искать, а не реализовал ли кто-нибудь нечто подобное, на нужной мне платформе. К моему не малому удивлению, удача таки повернулась нужным мне местом, и я нашёл то, что искал.
Заготовка, в виде js файла была препарирована, упразднена до нужных мне функций, оптимизирована, на сколько на тот момент хватало знаний и была приговорена к вечной службе сложному вопросу — куда пойти, куда податься. Посыпая голову пеплом, с прискорбием и сожалением сообщаю, что мной, увы, потеряны все данные о том кем была написана та, изначальная, версия js реализации А*,… ну не подумал я когда то, что это может ещё пригодится… всё, бейте меня семеро!
После того, как основная часть была сделана, остались частности — отрисовать найденный путь. На тот момент это было второстепенно и было реализовано первым же пришедшим в голову способом.
Перед тем, как показать, как же это всё выглядит, хочу обратить ваше внимание на то, что в то время, я понятия не имел о многих полезных вещах. Как например css спрайты. Так что не стоит ругать мой код, лучше по настольгируйте, вспоминая когда и вы писали робко и наивно, искренне радуясь, когда то, что написано, работает так, как задумано.
И так:
Вот как это выглядит
А тут всё это в запакованном виде
В данной конкретной реализации есть некоторая погрешность и при определённом выборе конечной точки находится не кратчайший путь, однако, поиск закономерности и решение этой проблемы было для меня не оправданным в соотношении польза/трудозатраты и баг так и остался не отловленным.
Кстати, когда-то был скриптик для рисования препятствий, но по всей видимости, он канул в лету.
P.S. На данный момент это работает под: FF 3, IE 7, Chrome и Safari 4 (всё под vista). Opera 9.64 работать отказывается, ну да цель не в этом.
Очень надеюсь, что хоть кому-то это может пригодиться или помочь, а для меня написание своей браузерной игры, не для заработка, а для души, наверное так и останется светлой мечтой, к которой всегда хочется стремится, но которую никак не достичь.
