Творец. Мозг в коробке. Часть вторая

Сначала в классе наступила тишина, а потом все услышали шаги учителя. В класс зашёл Эйнштейн и сразу начал что-то писать на доске. «Алгоритмы поиска пути», – дружно стали все конспектировать в тетрадь. Урок начался.

На сцене – мозг в коробке
Конечно, продумать каждую деталь невозможно. Конечно, каждый игрок будет тыкать вас носом в то, что «на 22-м уровне на меня свалился невменяемый монстр, который сначала спокойно прошёл через все стенки, а потом покончил с собой». Но ведь все с чего-то начинали. Даже для шахмат… нет, плохой пример… Даже для… а, чёрт с ним, для «Дума-1» тоже пришлось писать AI, тут уж никуда не денешься.

По морям, по волнам…
Итак, сразу попробуем разработать общий алгоритм поиска пути. Понятно, что в зависимости от сложности и жанра игры, всё будет меняться. К примеру, в космосиме не требуется точный расчёт обхода статичес-ких препятствий, зато очень важно следить за динамическими объектами (представьте картину: летит эскадрилья кораблей, потом останавливается – и все корабли друг в друга методично врезаются).
Для любого алгоритма неизменно только одно: начальная и конечная координата пути. А вот как добираться – дело ваше.
Самый простой способ – это волновой алгоритм поиска. Идея следующая: имеется два массива: первый содержит в себе информацию о карте, а второй – вспомогательный. Из ячейки, где находится объект, начинаем во все стороны заносить во вспомогательный массив числа (пример визуализации – на скриншоте). В каждой следующей ячейке число увеличивается на единицу. Далее, мы узнаём текущую координату и координату искомую. Из текущей ячейки мы пытаемся перебраться в какую-нибудь соседнюю. Если у числа в одной из соседних ячеек разница с числом в текущей ячейке равна единице, то мы спокойно переходим в соседнюю ячейку. И так – пока не окажемся в искомой точке. Этот алгоритм идеально подходит для всякого рода «казуалок» типа Pacman’а и простеньких 2D-игр.

Идём в дебри
Ещё один алгоритм: поиск в глубину. Здесь используется очень вкусный метод программирования – рекурсия.
Есть вспомогательный булевый массив, в который заносим информацию о том, пройдена данная ячейка или нет. Общий принцип выглядит примерно так:

var
 WayTrue: array of Boolean;
 whatX, whatY: integer;
procedure Find(x,y:integer);
begin
 // мы находимся в некой ячейке,
 // а значит она уже пройдена
 WayTrue<x,y>:=true;
 if (x=WhatX) and (y=WhatY) then
  begin
  // Добрались до искомой точки,
  // сидим и радуемся жизни
  end;
 if WayTrue<x+1,y>=false
  then Find(x+1,y);
 if WayTrue<x,y+1>=false
  then Find(x,y+1);
 if WayTrue<x+1,y+1>=false
  then Find(x+1, y+1);
 if WayTrue<x-1,y-1>=false
  then Find(x-1, y-1);
 if WayTrue<x-1,y>=false
  then Find(x-1, y);
 if WayTrue<x,y-1>=false
  then Find(x, y-1);
end;

Из текущей координаты (x, y) мы высовываем нос во все стороны и узнаём, была ли уже пройдена интересующая нас координата. Если нет, то пытаем счастье на ней – а именно, вызываем процедуру Find с новыми координатами.
Я показал пример без проверки препятствий. Но всё решается просто, достаточно написать ещё одну функцию.

function check(x, y: integer): boolean;
begin
 if map<x,y><>0
  then check:=false
  else check:=true;
end;

Если в нужной нам координате стоит какое-то препятствие (любой символ, отличный от нуля), то функция возвратит значение false.
Теперь немного изменится и условие прохождения:

if (WayTrue<x+1,y>=false) and (check(x+1,y)=true)
 then Find(x+1,y);

Звёзды 3000
Алгоритмы, оставшиеся за кадром, – Дейкстры и А*(Астар). Это достаточно сложные алгоритмы – поэтому и остались за рамками «школьного курса», – но зато очень продуктивные (в том смысле, что оптимизированы и более надёжны).
Кстати, на заметку: как оказалось, для «Дума-1» был написан более простой AI, чем тот, который придётся писать мне для моего платформера. Дело в том, что заставить противников прыгать в правильном направлении и на правильную высоту очень непросто. И кстати, я не нашёл ещё ни одного «официального» алгоритма, который бы занимался прыжками. Это вам на будущее.

Для дальнейшего изучения данного вопроса, предлагаю такие ссылки:


Рекомендуем почитать: