Однако как-то прошел мимо меня алгоритм поиска пути в ширину, как бы знал о нем, но совершенно не интересовался, есть такой и ладно. А вот на днях заинтересовался, оказывается незаменимая вещь для игр жанра Tower Defense или даже для шутеров, везде где враги должны набегать на одинокую цель, или небольшое количество целей. И главное - простая. Причем, в силу своей простоты исполняется один раз, а дальше результатами может пользоваться куча юнитов, во всяком случае, пока цель не сдвинется с места. А ведь делал что-то подобное - генератор регионов для навигационных карт и даже не сообразил, вот что значит лень и отсутствие специализированного образования.
КДПВ:
Немного о том, что видно на картинке. Зеленая решетка - плейн, служащий для визуального отображения матрицы игрового поля, которое, как не трудно убедиться имеет размер 8х8. Размер этот в примере не особо изменяемый, надо в куче мест цифры поменять. Также должен сообщить, что я несколько лопухнулся с координатной сеткой, она неудобная. Еще лопухнулся с плавным движением мобов - оно иногда глючит, однако редко, а вот "резкое" движение работает как часы. В основном - предупредил. Белые блоки играют роль препятствий, они неподвижны. Красный ромб, это так изображена цель для всех мобов, которые изображены синими шестигранниками. И, наконец циферки отображают количество шагов из данной ячейки до цели.
Матрица, она же навигационная карта, является одномерным списком ячеек, что с одой стороны проще реализовать, с другой стороны неудобно для использования в больших по размеру картах. Ячейка представляет из себя список, в котором записаны, индекс ячейки в списке, координата "на местности", список соседних ячеек, проходимость и число шагов до цели. По умолчанию число шагов равно минус единице и все клетки проходимы. После создания карты случайным образом расставляются блоки - препятствия, после установки блока в клетку эта клетка становится непроходимой, то есть в ячейку по этому индексу записывается False. Закончив с блоками, опять же случайным образом выбирается ячейка для установки её как цели, когда скрипт удачно выберет ячейку, начинается расчет количества шагов до цели для каждой ячейки. Делается это так: создается "большой"список, в который вкладывается стартовый "малый" список, состоящий из количества шагов и индекса ячейки-цели. Далее этот "большой" список помещается в цикл, который извлекает вложенный список и по записанному в нем индексу обращается к ячейке в навигационной карте, проверяет её проходимость и если она свободна, то записывает в нее значение количества шагов, которое для стартовой клетки будет равно 0, и формирует новый список из увеличенного на 1 количества шагов и списка связанных ячеек, извлеченных из рассматриваемой. Затем этот, "малый" список помещается в "большой", и цикл повторяет все снова, пока не будут посещены все доступные клетки. Если же клетка не была посещена, то количество шагов в ней так и остается равным -1 и бот, находящийся в ней, может узнать, что цель для него недоступна, в примере такой моб кончает жизнь самоубийством. Бот, оказавшийся на любой клетке, проверяет количество шагов из нее и если остается жив, просматривает список соседних ячеек, выбирая первую попавшуюся, в которой количество шагов будет меньше чем в той, в которой он находится. Тогда он перемещается в выбранную и повторяет процесс, пока не придет к цели и там уже совершит самоубийство. Как оно выглядит в процессе, можно посмотреть на видео:
Управление - по нажатию пробела в случайную ячейку добавится еще один бот.
Скачать пример:
КДПВ:
Немного о том, что видно на картинке. Зеленая решетка - плейн, служащий для визуального отображения матрицы игрового поля, которое, как не трудно убедиться имеет размер 8х8. Размер этот в примере не особо изменяемый, надо в куче мест цифры поменять. Также должен сообщить, что я несколько лопухнулся с координатной сеткой, она неудобная. Еще лопухнулся с плавным движением мобов - оно иногда глючит, однако редко, а вот "резкое" движение работает как часы. В основном - предупредил. Белые блоки играют роль препятствий, они неподвижны. Красный ромб, это так изображена цель для всех мобов, которые изображены синими шестигранниками. И, наконец циферки отображают количество шагов из данной ячейки до цели.
Матрица, она же навигационная карта, является одномерным списком ячеек, что с одой стороны проще реализовать, с другой стороны неудобно для использования в больших по размеру картах. Ячейка представляет из себя список, в котором записаны, индекс ячейки в списке, координата "на местности", список соседних ячеек, проходимость и число шагов до цели. По умолчанию число шагов равно минус единице и все клетки проходимы. После создания карты случайным образом расставляются блоки - препятствия, после установки блока в клетку эта клетка становится непроходимой, то есть в ячейку по этому индексу записывается False. Закончив с блоками, опять же случайным образом выбирается ячейка для установки её как цели, когда скрипт удачно выберет ячейку, начинается расчет количества шагов до цели для каждой ячейки. Делается это так: создается "большой"список, в который вкладывается стартовый "малый" список, состоящий из количества шагов и индекса ячейки-цели. Далее этот "большой" список помещается в цикл, который извлекает вложенный список и по записанному в нем индексу обращается к ячейке в навигационной карте, проверяет её проходимость и если она свободна, то записывает в нее значение количества шагов, которое для стартовой клетки будет равно 0, и формирует новый список из увеличенного на 1 количества шагов и списка связанных ячеек, извлеченных из рассматриваемой. Затем этот, "малый" список помещается в "большой", и цикл повторяет все снова, пока не будут посещены все доступные клетки. Если же клетка не была посещена, то количество шагов в ней так и остается равным -1 и бот, находящийся в ней, может узнать, что цель для него недоступна, в примере такой моб кончает жизнь самоубийством. Бот, оказавшийся на любой клетке, проверяет количество шагов из нее и если остается жив, просматривает список соседних ячеек, выбирая первую попавшуюся, в которой количество шагов будет меньше чем в той, в которой он находится. Тогда он перемещается в выбранную и повторяет процесс, пока не придет к цели и там уже совершит самоубийство. Как оно выглядит в процессе, можно посмотреть на видео:
Управление - по нажатию пробела в случайную ячейку добавится еще один бот.
Скачать пример:
Комментариев нет:
Отправить комментарий