Итак, я начал делать игрушку про боевых роботов. Сперва у меня была задумка весьма нетривиального игрового подхода, когда игрок выбирает ходы, которые должны сделать персонажи, компьютер выбирает ходы своих персонажей, а потом всё происходит одновременно. Однако, такой подход требовал больше подготовки, поэтому я решил его, пока что, пропустить и сделать игру пошаговой. У игрока есть один или несколько роботов, которые могут выполнять определённые действия, а именно: передвигаться и атаковать противника. Игроки действуют по-очереди. Каждое действие стоит какого-то количества очков движения (которые восполняются с наступлением нового хода). Ну и всё в таком духе.
Начало, если что, тут.
Новый вызов
Хотя порой и кажется, что игра - это просто про графику, на деле всё далеко не так просто: требуется большое количество различных вычислений, связанных с рассчётом возможностей действий. Самое простое - это рассчитать радиус движения, то есть подсветить клетки, на которые герой может шагнуть или зона, внутри которой будут видны противники.
Но следующий по сложности этап возник в момент написания ИИ противника (ну ИИ это сильно сказано конечно, так несложный конечный автомат, но, всё же, для большего пафоса буду использовать модные определения).
Итак, потребовалось найти способ прокладывания маршрута управляемого ИИ персонажа в сторону противника. А также потребовался обратный алгоритм - удержание расстояния от противника (бегство, проще говоря).
И тут сложность заключалась в том, что карта - неоднородна. Где-то можно пройти, где-то нельзя, а где-то количество шагов, требующихся для преодоления клетки - больше чем в других случаях.
Короче, мы пришли к задаче поиска кратчайшего пути в графе. Обычно, для этого используется алгоритм Дейкстры, однако у меня появились некоторые сомнения относительно него: карта может быть очень большой, а возможных маршрутов может быть очень много, т.к. условный граф карты, по сути, может оказаться просто решёткой. Иными словами, это может потратить либо слишком много времени на рассчёты, либо сожрать очень много памяти. А может быть этого и не случится. Короче, я решил проанализировать работу алгоритма для достаточно большой карты (с весьма большим количеством возможных маршрутов).
Первый пример
Для начала я написал некоторое подобие алгоритма Дейкстры. Некоторое подобие - потому, что хотя алгоритм и похож на него, но, по сути, отличается способом реализации (все прочие реализации, что я видел, выглядели сильно проще, но требовали определённую структуру данных).
Для нулевых точек вес перехода - 1, для 1 - 2. Тут надо уточнить, что у меня не было графа как такового; есть лишь поле, где каждая клетка имеет стоимость вхождения на неё, так что это всё надо перевести сперва в граф.
Немного пошаманил, добавил непроходимые точки (3) и путь начал выводиться так:
Не очень наглядно. И хотя работает быстро - массив крайне мал. Надо усложнить задачу.
Усложнение
Признаться, генерировать случайный файл 100 на 100 клеток мне не хотелось, т.к. непонятно, как со всем этим потом быть: путь, проложенный случайно среди хаоса, может вовсе не быть оптимальным. Решение появилось такое: нарисовать растровую картинку 100 на 100 и использовать цвета, как маркер веса. И поверх получившейся картинки нарисовать путь. Ну и замерить скорость работы заодно.
И, первая же попытка посчитать маршрут для карты 100 на 100 привела к тому, что кончилось адресуемое пространство массивов: заполнилось 112813858 записей. И это ещё на уровне преобразования таблицы в граф. Неприятненько. Надо подумать, что с этим можно сделать.
На каждом новом шаге количество соседних точек увеличивается примерно в 4 раза. В общем. очевидно, что хотя алгоритм Дейкстры отлично работает на небольшой карте, но на картах побольше он перестаёт работать как надо. И даже то небольшое количество точек, что было обработано - заняло примерно 2 минуты. Неприемлемо!
Я уже всерьёз собирался поискать другой алгоритм и даже нашёл его, но мне не давало покоя то невероятное количество вершин, которые добавляются на каждой итерации. Что-то не то.
Проанализировав вывод пришёл к выводу, что одна и та же вершина добавляется по нескольку раз (что не удивительно, т.к. смежные клетки-вершины обязательно будут иметь одни и те же смежные вершины). Короче говоря, проведя небольшую оптимизацию я добился впечатляющих результатов: 180 милисекунд и путь построен.
То, что закрашено зелёным - это пройденные точки, голубая линия - проложенный путь.
Однако триумф длился недолго. Стоило мне добавить чёрные элементы карты в разряд "проходимых", как маршрут сразу поменялся.
Но тут всё оказалось не так страшно. Просто алгоритм преобразования координат в индекс массива данных был немного наивен в своём желании объять необъятное.
Короче, проверка делалась с ошибкой. Но я сейчас всё поправлю.
Последний рассчёт выполнен всего за 132 миллисекунды. Очень неплохо.
Ради интереса я попробовал поиграть с весами и путь получался вполне себе приемлемым, любезно обходя препятствия и следуя по "наилегчайшему" пути.
Короче говоря, можно использовать в работе над игрой. Есть ещё простор для оптимизации - разбить вычисления на интервалы по 5 миллисекунд. Но это потом.
Посмотреть исходники можно тут (исходник библиотеки тут). А результат здесь.
P.S. кстати, в Firefox, уже не в первый раз не получилось всё сделать легко и просто. Причина оказалась тривиальной - иная цветопередача. Если быть точнее, то цвета канваса в Chrome отличаются от Firefox. Пришлось всё немного переделать.
Кстати, если будете экспериментировать в прокладывании пути - можете загрузить любую картинку 100 на 100 и все цвета на ней будут отсортированы по мере вхождения в картинку. Самые частые получат минимальный вес, самые редкие - максимальный. Как-то так.
