* Поиск пути работы с большим открытым списком

Я работаю над проектом, который требует использования алгоритма A *. В этом проекте вы выбираете своего игрока левым кликом и направляете его по карте правым кликом, как в геймплее тысячи стратегических игр. Графика 2D, немного похожа на игру Don’t Starve, и игра разработана с использованием SFML / C ++.

Мне нужно использовать A * для перемещения игрока, действительно, если на его дороге появляется препятствие, он должен избегать его. Но на данный момент я не знаю, как применить сетку к карте, я хочу разместить любое дерево / камни и другие вещи в любом месте, чтобы не видеть ячейки сетки. Пока открытый список состоит только из пикселей, что, я думаю, не очень хорошее решение ^^, алгоритм довольно медленный. Если у вас есть какое-либо решение для реалистичного рендеринга с сохранением быстрого алгоритма, я буду рад его услышать. 🙂

Заранее спасибо,

1

Решение

У тебя есть скриншот?

Сетка поиска пути и сетка рендеринга могут быть разными. Zelda использовала плитки разных размеров для перемещения и рендеринга.

Это может быть излишним для вашей структуры карты, но вы можете использовать сетку навигации.

введите описание изображения здесь , введите описание изображения здесь

редактировать: если вы еще не читали, у Амит есть отличный ресурс: http://theory.stanford.edu/~amitp/GameProgramming/

2

Другие решения

То, что вы ищете, это дискретизация. За этим непристойным названием стоит простой принцип: вы не можете иметь дело с бесконечным количеством данных.

Затем вам нужно выполнить преобразование в вашем мире: вместо того, чтобы позволить вашему персонажу / отряду перемещаться в любое место (x и y — действительные числа), вы можете разделить свой мир на какую-то сетку (это то, что является сеткой навигации и путевые точки делают), и позволяют вашему персонажу перемещаться только по этим ячейкам (или точкам, вы можете видеть их так, как хотите). Это дискретно: вы переходите от непрерывных значений (действительные координаты) к дискретным значениям (целочисленные координаты / точка). Чем точнее вы идете, тем приятнее будет выглядеть.

После этого достаточно просто распределить затраты на перемещение между ячейками / точками, а также выполнить A *.

0