Mass astar pathfinding

Я пытаюсь создать игру защиты башни в Javascript.Mass astar pathfinding

Это все идет хорошо кроме первопрохождения ..

Я использую код AStar с этого сайта: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript который использует бинарную кучу (который я считаю довольно оптимальным)

Проблема я Я хочу, чтобы люди блокировали путь «нападавших». Это означает, что каждый «атакующий» должен иметь возможность самостоятельно найти выход на выходе (поскольку кто-то может просто отключить одного «атакующего», и ему нужно будет найти свой путь к выходу). Теперь 5/6 злоумышленников могут обращаться в любой момент без проблем. Но скажите, что путь заблокирован для 10 + атакующих, все 10 из них должны будут запускать свой сценарий поиска пути одновременно, что просто уменьшает FPS примерно до 1/2 в секунду.

Это должно быть распространенной проблемой для тех, у кого есть много сущностей, которые ищут путь в любое время, поэтому я думаю, что должен быть лучший способ, чем мой подход.

Итак, мой вопрос: какой лучший способ реализовать алгоритм многоцелевого поиска для нескольких «ботов» наиболее эффективным способом.

Спасибо,

Джеймс

источник

2012-04-12 james

похоже 'findGraphNode' в этом коде занимает линейное время, в то время как оно должно принимать постоянное время (с хэш-таблицей), так что реализация далеко не оптимальна. –

Я посмотрю, смогу ли я немного ускорить его. Но я думаю, что даже при более эффективном поиске пути я все равно окажусь медленными кадрами, если попытаюсь найти путь к ботам. Я начинаю думать, что мой лучший выбор - это на самом деле поиск всей карты один раз за кадр, а затем установление направления на каждом проходимом блоке для последующих ботов. – james

@james, если это что-то вроде большинства защиты башни, с примерно экраном карты и без сложных сражений (т.е. боты не сталкиваются друг с другом или с другими движущимися объектами, или вы справляетесь с этим отдельно), тогда да, я думаю, что расчет путей для всей карты был бы лучше всего.На самом деле вам, вероятно, даже не придется пересчитывать всю карту в каждом кадре. Если вы будете осторожны при построении алгоритма, вы сможете определить, на какие узлы влияет изменение пользователя, и пересчитать только «вверх по течению» от этих узлов. Звучит интересно! – Tim

Использование Anti-объекты, это единственный способ получить дешевый поиск пути, AFAIK: http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

Anti-объект в основном означает, что вместо бот, имеющий индивидуальный ai, у вас будет один «рой ai», который привязан к вашей игровой карте.

p.s .: Вот еще одна ссылка о первопрохождения в целом (возможно, лучший онлайн справочник доступен): http://theory.stanford.edu/~amitp/GameProgramming/index.html

источник

2012-04-12 10:01:55 c69

спасибо за ресурс, я посмотрю чуть позже. Хотя только из того, что вы сказали, похоже, что имеет смысл проследить всю карту и, возможно, установить направление на каждом «блоке», за которым следуют боты .. hmmm – james

Просто кэшировать результат.

Сохраните путь как значение в хэш-таблице (объекте), дайте каждому узлу UUID, объедините UUID, чтобы сформировать уникальный ключ таблицы хэша и вставьте туда путь.

При извлечении путь обратно из хэш-таблицы, идти по пути, и посмотреть, если он по-прежнему в силе, если нет, пересчитывать и вставьте новый обратно.

Есть много оптимизации, которые вы можете делать :)

как C69 сказал роя AI или улей ум приходит на ум: P

источник

2013-10-28 03:54:31 Metalstorm

Mass astar pathfinding

ответ

Смежные вопросы