Что нужно для написания игр ?

[Andrew771]

Нашел детальную открытую переписку В.Медноногова по этому поводу: http://pmg.org.ru/ai/raypath.zip

Вкратце быстрый алгоритм поиска пути таков (кому лень читать многабукафф):
1. Идем по прямой к цели.
2. Если наткнулись на препятствие, то переходим на п.3, иначе на п.1.
3. Считаем по периметру препятствия по часовой и против часовой стрелки (в двух направлениях), где меньше клеток для обхода, и запоминаем эти клетки. Последними клетками обхода считаются те, из которых можно двигаться по прямой к цели (последующие возможные препятствия пока не считаются).
4. Обходим препятствие по клеткам с минимальным обходом.
5. Переходим на п.1.

Вспомнил вот, решил написать...
Когда в 2000 г. я начал писать для Спектрума RTS (надеюсь, напишу ее), то алгоритм поиска пути делал тоже без полного просчитывания пути, чтобы максимально сэкономить время просчета и память. Он еще быстрее медноноговского, но маршрут может быть хуже, если препятствия протяженные. Тем не менее, в итоге юнит придет в нужную точку. Вот такой он:

1. Идем по прямой к цели (обе координаты горизонтальная и вертикальная сближаются с целью), запоминаем последние 6 клеток, через которые прошли, в буфер.
2. Если наткнулись на препятствие, то идем на клетку, чтобы хотя бы одна координата - горизонтальная или вертикальная сближались с целью. При этом не заходя ни на одну из 6 последних запомненных клеток в буфере. Продолжаем запоминать 6 последних клеток в буфер.
3. Если невозможно идти в условии п.2, то идем на любую соседнюю случайную клетку, которой нет в буфере. Продолжаем запоминать 6 последних клеток в буфер.
4. Если невозможно идти в условии п.3, то идем на любую соседнюю случайную клетку, которая есть в буфере, кроме той, где были на прошлом ходу. При этом в буфере запомненных клеток удаляем клетки, из которых пришли на текущую клетку в прошлый раз.
5. Переходим на п.1, пока не достигли цели.

Проверял, работает. Правда, приходится для каждого юнита хранить буфер 6 клеток (можно не сами координаты клеток, а смещение до них от текущей в 2-3 битах). Буфер можно увеличить/уменьшить в зависимости от размера и изрезанности предполагаемых препятствий.