Я сейчас пишу 2D-игру в Javascript, используя HTML5 < холст > элемент. Это идет очень хорошо, но я столкнулся с проблемой.Что такое хороший алгоритм поиска путей на основе сетки 2D?
Дизайн уровня для моей игры - сетка (поэтому стоимость пути, перемещающаяся из одной ячейки в северную/южную/восточную/западную ячейку, равна 1) с различными препятствиями, занимающими различные местоположения в сетке – много похоже на лабиринт, но с гораздо большим количеством поворота. Каждый отдельный уровень составляет порядка 400 × 200 ячеек.
Я пытаюсь реализовать врага, который будет искать игрока независимо от того, где они могут быть, но у меня возникли проблемы с попыткой перевести один из различных алгоритмов поиска пути в соответствии с моей ситуацией. Большинство из тех, с которыми я сталкивался (например, A * и Dijkstra), по-видимому, лучше всего подходят для 3D или более сложных 2D-ситуаций. Мне было интересно, можно ли значительно упростить эти алгоритмы, чтобы лучше соответствовать моим целям или что-то вроде поиска по глубине было бы более эффективной альтернативой, учитывая размер уровня.
Вы не будете делать лучше, чем A *, не дав ему предварительного знания о возможных путях (например, деление карты на сегменты с известной связностью). Глубина сначала была бы намного (намного намного) медленнее, чем ширина в первую очередь. – Dave
На самом деле это не то, что Stackoverflow/Stack Exchange о; задайте вопрос с определенным ответом, а не вопросом для покупок. Во что бы то ни стало, используйте то, что предлагают люди, но возвращайтесь, когда вы сталкиваетесь с проблемой программирования. – Amelia
@Dave: Вы можете легко найти [лучше, чем простой-ol 'A \ *] (http://programmers.stackexchange.com/questions/197894), когда он привязан к сетке; но JPS + A \ * сложнее, чем просто A \ *, и обычно это не обязательно. –