Плиточное поле принято называть дискретным пространством.
В таком пространстве перемещение измеряется дискретными шагами, между которыми и может быть изменено.
Для поиска пути в таком дискретном пространстве стоит обратить внимание на алгоритмы поиска
в ширину и
в глубину.
Начать стоит с поиска в глубину. Его легко сделать и так же легко понять его неоптимальность. От поиска в глубину довольно легко перейти к поиску в ширину.
Алгоритмы поиска в ширину и в глубину дадут первичное понимание теории построения маршрута.
От поиска в ширину можно перейти к эвристическим алгоритмам поиска:
A* или поиску
по наилучшему совпадению.
На этом этапе еще полезно познакомиться с
алгоритмом JPS. Он может стать даже выгоднее обычного A*.
A* должен стать для тебя основным инструментом поиска в дискретном пространстве. Но у A* есть проблема большой сложности поиска прямого маршрута.
При поиске пути по прямой лучше всего использовать
алгоритм Брезенхама.
Этот алгоритм используется для рисования пиксельных примитивов. В частности - прямых.
И суть должна быть в том, чтобы сперва путь искать через Брезенхама по прямой от точки старта до точки финиша, а если Брезенхам наткнется на препятствие, то уже перейти к поиску через A*.
Для очень больших дискретных пространств есть варианты иерархического A*:
HPA* и HAA*. Они применяются на иерархических дискретных пространствах вида открытого мира. В освоении они являются самыми сложными и самыми интересными.
Простой
Простой
