Поиск пути A*

php

Ищет путь по карте алгоритмом A*: учитывает проходимость клеток и их «цену» — по дороге существо идёт охотнее, через болото неохотнее. Цену клетки задают в редакторе карт Tiled.

Пример использования — механика движения к цели в игре The Mana World: events/move/walk/to.php.

Устройство

Поиск пути A* с binary heap:

  • Open list использует BinaryHeap (extractBest O(log n)) вместо линейного поиска.
  • Closed list — NodeHashTable (O(1) lookup по id).

DomainLogic адаптирует A* к карте Map2D:

  • getAdjacentNodes — соседи из графа Map2D (8 направлений, tunneling prevention);
  • calculateRealCost — вес ребра из графа (1.0 ортогональ, 1.41 диагональ, умножается на cost тайла);
  • calculateEstimatedCost — Euclidean distance.

Веса местности (cost)

Дизайнер ставит property cost на SizeTile в Tiled (float, множитель, по умолчанию 1.0). Примеры: дорога cost=0.5 (быстрее), болото cost=3.0 (медленнее), лава cost=999 (почти непроходима).

Cost попадает через мету набора графики → sandbox terrain → граф Map2D → DomainLogic::calculateRealCost(). Формула: realCost = baseCost (1.0 или 1.41) * targetTile.cost.

Что нужно игре

Пока описанием — объявления зависимостей у библиотек ещё нет:

  • фреймворк с Map2D (матрица проходимости целиком — terrain, проверка общей связной области sameArea), Position (разделитель координат), PHP (журнал), Perfomance (замер).

Связь односторонняя: при первом поиске библиотека берёт у фреймворка матрицу проходимости (Map2D::terrain) и сама зовёт DomainLogic::init. Фреймворк о библиотеке не знает: без неё карта поднимается, недоступным остаётся только движение к цели.

Бесплатно

Войти и получить Git-репозиторий
Используется в играх