Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Алгоритм поиска кратчайшего пути для больших локаций

Алгоритм поиска кратчайшего пути для больших локаций

BernsПостоялецwww22 фев. 201821:53#0
для всяких лабиринтов и простых 2Д игрушек алгоритмы волновой трассировки работают замечательно, но с огромными локациями, которые, к слову, не содержат особо сложных препятствий, начинаются танцы. поле 8000x8000 роняет производительность напрочь (0.05 сек) , а ведь еще нужно растеризовать коллизии от тысяч объектов. использую алгоритм Ли с некоторой отсебятиной, заполняю по окрестностям Мура, расчеты провожу на  попсовом amd athlon x3 460 в одном потоке. т.к задача требует плавного перемещения объекта и значения его поворота, планирую интерполировать значения между точками, а угол направления вычислять из вектора <объект-маркер пути>. к слову, точность 8k*8k так же неудовлетворительна, и в случае дальнейшего снижения точности для объектов невозможное становится возможным - а то и вовсе наоборот, например PNC не может выйти из здания состоящего из 3,5 стен. есть идеи как это решить? полагаю, тут нужны альтернативные офлайн-алгоритмы, либо модернизация существующего. пробовал делать перемещение по вектору с учетом столкновений, но тут мои идеи заканчиваются, а подвижный объект в некоторых случаях застревает
FireFenixПостоялецwww22 фев. 201822:37#1
генерация графа вейпоинтов + runtime поиск на navmesh от ближайшего вейпоинта
ryzedПостоялецwww23 фев. 201810:41#2
Подобные проблемы с размерами типично решаются введением иерархии.
Можешь вот тут почитать для начала: https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf

/ Форум / Программирование игр / Игровая логика и ИИ

2001—2018 © GameDev.ru — Разработка игр