Ответ: AI for RTS
Поиск пути можно сравнить с волнами на воде:
Камень - это объект который ищет путь.
А цель которую нужно достигнть - это точка на воде к которой вы хотите проложить путь.
Вы кидаете камень в воду и от него расходятся волны - эти волны огибают препятствия и проходы, постепенно удаляясь от камня. какая-то волна дойдет до намеченной точки (цели) быстрее, какая-то медленнее. Только вода это клетчатое пространство, поставили точку клетки который вокруг "обвели" (пометили клетки как единички) - это первая волна. Дальше обводим клетки которые вокруг единичек помечаем их двойками, но только пустые клетки, клетки которые уже заняты мы игнорируем, мы тут уже были - это вторая волна, потом так же идет третья которая обводит вторую, потом, четвертая, пятая, шестая, седьмая и т.д. Пока новая волна не коснется назначенной целевой точки.
Когда волна достигла точки назначения, идет обратный процесс, теперь уже двигаемся "по волнам" но в обратную сторону, от точки назначения к месту падения камня - переходим от последней волны к предыдущей: от девятой, к восьмой, от восьмой к седьмой и т.д. помечая путь (это и будет путь от точки падения камня в воду, до цели которую мы наметили), пока не достигнем точки из которой пошли волны.
|