Вот начали вы делать свою игру. Придумали и сделали юнитов, разные декорации, Главного героя. Юнитам велели идти к герою, они пошли - и уперлись лбом в стену. И стоят так, ибо сквозь стены ходить нельзя, или идут сквозь стену, если у вас плохо прописана физика.
Как же быть? вот для этого и существуют алгоритмы поиска путей. Как вы могли заметить, в моей игре танки лбом в стену не тыкаются. Сейчас я попробую рассказать, как они находят дорогу :)
Сначала объявим все необходимые типы и классы. класс для именно этой задачки нам понадобится всего один.
Как видите, карта флагов у меня объявлена как отдельный класс, что открывает изрядную широту возможностей.
Код
type
TFlagN = 1..250;
TFlagSet = set of TFlagN;
TFlag = record
{флаг используется компьютерно-управляемыми юнитами для навигации и поиска пути. содержит информацию о том, какие флаги доступны из этого, и собственные координаты.}
EnabledFlags: array of integer;
SizeEn: integer;
MainID: integer;
position: TPoint;
end;
TFWorkPath = record
{специфический тип данных, используемый для работы алгоритма поиска путей}
PathFlags: array of integer;
Dist: integer;
end;
TFlagsMap = class
{описание класса - карта флагов. по этой карте NPC находят путь.}
private
Flags: array of TFlag;
Size: integer;
public
Function QuatroDist(MainPos: TPoint; TgtPos: TPoint): integer;
procedure AddFlag(PosX: integer; PosY: integer; EnFlags: TPArray);
Function FlagPath(FlagA: integer; FlagB: integer): integer;
Function FlagUpdate(FlagID: integer; WP: TFWorkPath): TFWorkPath;
Function EndFlag(WP: TFWorkPath): integer;
Function PathDistance(WP: TFWorkPath): integer;
Function NextFlag(WP: TFWorkPath): integer;
Function Flagfind(Pos: TPoint): integer;
end;
Теперь методы класса TFlagsMap.
Код
function TFlagsMap.QuatroDist(MainPos: TPoint; TgtPos: TPoint): integer;
{сопоставляет эффективность движения по 4 разным направлениям для достижения указанной цели}
var
ax: integer;
ay: integer;
begin
ax:= abs(MainPos.X - TgtPos.X);
ay:= abs(MainPos.Y - TgtPos.Y);
If (Distance(MainPos,TgtPos) > 12.5) then
begin
If (ax > ay) then // x
begin
If (MainPos.X
begin
Result:= 3;
end
else begin
Result:= 1;
end;
end
else begin //y
If (MainPos.Y > TgtPos.Y) then
begin
Result:= 0;
end
else begin
Result:= 2;
end;
end;
end
else begin // мы уже приехали
Result:= -1;
end;
end;
procedure TFlagsMap.AddFlag(PosX: integer; PosY: integer; EnFlags: TPArray);
{добавление флага на карту, старая версия.}
var
a: integer;
Pos: TPoint;
b: integer;
c: integer;
begin
Pos.X:= PosX;
Pos.Y:= PosY;
a:= Length(Flags);
SetLength(Flags,a + 1);
Size:= a + 1;
b:= Length(EnFlags.P);
SetLength(Flags[a].EnabledFlags,b);
c:= 0;
while (c
begin
Flags[a].EnabledFlags[c]:= EnFlags.P[c];
c:= c + 1;
end;
Flags[a].SizeEn:= b;
Flags[a].MainID:= a;
Flags[a].position:= Pos;
end;
function TFlagsmap.FlagPath(FlagA: integer; FlagB: integer): integer;
{поиск пути из флага А к флагу Б. Возвращает номер ближайшего флага, к которому следует двигаться сейчас. Когда танк дойдет до этого флага, запрос повторится опять.}
var
WPS: array of TFWorkPath; // массив путей
FSA: TFlagSet; // список флагов, до которых пути уже найдены
a: boolean; // признак того, что путь в пункт Б НЕ найден.
b: integer; // счетчик путей
c: integer; // счетчик вариантов пути из последнего флага
f: integer; // номер последнего флага
fa: integer; // послесчетчик
fb: integer; // число вариантов путей из последнего флага
bn: integer; // число путей в начале цикла их рассмотрения
Rn: integer; // номер пути в массиве путей, который приводит к Б.
begin
//Form1.LogMsg('Flagsmap.Flagpath: ' + Inttostr(FlagA) + '; ' + Inttostr(FlagB));
// убираем обратные пути;
// убираем пути ведущие туда куда мы уже приходили
// проверяем все пути параллельно до тех пор пока один из них не приведет в пункт Б.
FSA:= [FlagA];
SetLength(WPS,1);
WPS[0]:= FlagUpdate(FlagA,WPS[0]);
a:= true;
while (a) do // а изменится в ходе цикла, когда будет найден путь к пункту Б.
//внимание! этот подход не годится если у вас на карте есть места, до которых нельзя добраться.
begin
b:= 0;
bn:= Length(WPS);
while (b
begin
c:= 0;
f:= EndFlag(WPS[b]);
fb:= Flags[f].SizeEn;
// рассматриваем флаг f
while (c
begin
If not (Flags[f].EnabledFlags[c] in FSA) then
// к такому еще не приходили
begin
FSA:= FSA + [Flags[f].EnabledFlags[c]];
SetLength(WPS,Length(WPS) + 1);
WPS[high(WPS)]:= FlagUpdate(Flags[f].EnabledFlags[c],WPS[b]);
// проверям, пришли ли мы к точке назначения
If (Flags[f].EnabledFlags[c] = FlagB) then a:= false;
end;
c:= c + 1;
end;
b:= b + 1;
end;
// список рассматриваемых путей обновлен
end;
fa:= 0;
bn:= Length(WPS);
Rn:= -1; // error
while (fa
begin
If (EndFlag(WPS[fa]) = FlagB) then Rn:= fa;
fa:= fa + 1;
end;
Result:= WPS[Rn].PathFlags[1];
end;
function TFlagsmap.Flagfind(Pos: TPoint): integer;
{функция находит и возвращает номер флага, ближайшего к произвольно указанной позиции.}
var
a: integer;
d: extended;
nd: extended;
r: integer;
begin
d:= distance(Flags[0].position,Pos);
r:= 0;
a:= 1;
while (a
begin
nd:= distance(flags[a].position,Pos);
If (nd
begin
d:= nd;
r:= a;
end;
a:= a + 1;
end;
Result:= r;
end;
function TFlagsMap.FlagUpdate(FlagID: integer; WP: TFWorkPath): TFWorkPath;
{функция добавляет флаг к указанному пути, возвращает обновленный вариант пути}
var
a: integer;
b: integer;
begin
a:= Length(WP.PathFlags);
b:= endFlag(WP);
SetLength(WP.PathFlags,a + 1);
WP.PathFlags[a]:= FlagID;
WP.Dist:= WP.Dist + Distance(Flags[a].position,Flags[b].position);
Result:= WP;
end;
Function TFlagsmap.EndFlag(WP: TFWorkPath): integer;
{функция возвращает номер последнего флага пути}
begin
If (Length(WP.PathFlags) = 0) then
begin
Result:= -1;
Exit;
end;
Result:= WP.PathFlags[Length(WP.PathFlags) - 1];
end;
Function TFlagsmap.PathDistance(WP: TFWorkPath): integer;
{функция возвращает длину пути. Не число флагов на нем, а именно длину.}
begin
Result:= WP.Dist;
end;
Function TFlagsmap.NextFlag(WP: TFWorkPath): integer;
{следующий флаг в пути}
begin
Result:= WP.PathFlags[0];
end;
С методами закончили. Что каждый из них делает, вобщем понятно по комментариям. Более детальные пояснения - чуть позже.
Чтобы пути можно было находить, необходимо иметь какие то данные о местности. Эти данные, в танкодроме задаются при старте игры.
На старте игры, карта декораций и флагов генерируется процедурами:
Код
Function TGameServer.AddFlagtoMap(EnabledFlags: TFlagSet; PosX: integer; posY: integer): integer;
var
R: TPArray;
a: integer;
Rs: integer;
begin
R:= ClearArray;
a:= 0;
while (a
begin
If (a in EnabledFlags) then R:= AddtoArray(R,a);
a:= a + 1;
end;
Rs:= Length(Flagsmap.Flags);
Flagsmap.AddFlag(PosX,PosY,R);
Result:= Rs;
end;
procedure TGameServer.Blocksmap(Q: integer);
var
R: TPArray;
begin
{генерация карты: один из вариантов}
R:= ClearArray;
Case Q of
1: begin
{расставляем по карте бетонные кубики}
BlockCreate(200,200,false);
BlockCreate(200,760,false);
BlockCreate(1080,200,false);
BlockCreate(1080,760,false);
BlockCreate(300,200,true);
BlockCreate(200,300,true);
BlockCreate(300,300,true);
BlockCreate(300,760,true);
BlockCreate(200,660,true);
BlockCreate(300,660,true);
BlockCreate(1080,300,true);
BlockCreate(980,200,true);
BlockCreate(980,300,true);
BlockCreate(1080,660,true);
BlockCreate(980,760,true);
BlockCreate(980,660,true);
BlockCreate(590,430,true);
BlockCreate(690,430,true);
BlockCreate(590,530,true);
BlockCreate(690,530,true);
{расставляем по карте флаги, на которые будут ориентироваться НПС при движении}
// flagmap: (# - кирпичи)
// 0 1 2 3
// # #
// 4 5 6 7 8 9
// ##
// 10 11 12 13 14 15
// ## ##
// 16 17 18 19
// FLAG 0
AddFlagtoMap([1,4],90,90);
// FLAG 1
AddFlagtoMap([0,2,5,6],400,90);
// FLAG 2
AddFlagtoMap([1,3,7,8],870,90);
// FLAG 3
Addflagtomap([2,9],1180,90);
// FLAG 4
Addflagtomap([0,5,10],90,400);
// FLAG 5
Addflagtomap([1,4,6,11,12],400,400);
// FLAG 6
Addflagtomap([5,7,11,12],480,320);
// FLAG 7
AddFlagtomap([6,8,13,14],790,320);
// FLAG 8
Addflagtomap([2,7,9,13,14],870,400);
// FLAG 9
Addflagtomap([3,8,15],1180,400);
// FLAG 10
Addflagtomap([4,11,16],90,550);
// FLAG 11
Addflagtomap([5,6,10,12,17],400,550);
// FLAG 12
Addflagtomap([5,6,11,13],480,630);
// FLAG 13
AddFlagtomap([7,8,12,14],790,630);
// FLAG 14
Addflagtomap([7,8,13,15,18],870,550);
// FLAG 15
Addflagtomap([9,14,19],1180,550);
// FLAG 16
Addflagtomap([10,17],90,860);
// FLAG 17
Addflagtomap([11,12,16,18],400,860);
// FLAG 18
Addflagtomap([13,14,17,19],870,860);
// FLAG 19
Addflagtomap([15,18],1180,860);
end;
2: begin {другой вариант карты}
BlockCreate(200,200,true);
BlockCreate(300,200,true);
BlockCreate(200,300,true);
BlockCreate(300,300,true);
BlockCreate(800,200,true);
BlockCreate(700,200,true);
BlockCreate(800,300,true);
BlockCreate(700,300,true);
BlockCreate(200,800,true);
BlockCreate(300,800,true);
BlockCreate(200,700,true);
BlockCreate(300,700,true);
BlockCreate(800,800,true);
BlockCreate(700,800,true);
BlockCreate(800,700,true);
BlockCreate(700,700,true);
{расставляем по карте флаги, на которые будут ориентироваться НПС при движении}
// flagmap: (# - кирпичи)
// 0 1 2 3
// # #
// 4 5 6 7
//
// 8 9 10 11
// ## ##
// 12 13 14 15
Addflagtomap([1,4],75,75); //0
Addflagtomap([0,2,5],375,75); //1
Addflagtomap([1,3,6],575,75); //2
Addflagtomap([2,7],875,75); //3
Addflagtomap([0,5,8],75,375); //4
Addflagtomap([1,4,6,9,10],375,375); //5
Addflagtomap([2,5,7,9,10],575,375); //6
Addflagtomap([3,6,11],875,375); //7
Addflagtomap([4,9,12],75,575); //8
Addflagtomap([5,6,8,10,13],375,575);//9
Addflagtomap([5,6,9,11,14],575,575);//10
Addflagtomap([7,10,15],875,575); //11
Addflagtomap([8,3],75,875); //12
Addflagtomap([9,12,14],375,875); //13
Addflagtomap([10,13,15],575,875); //14
Addflagtomap([11,14],875,875); //15
end;
end;
end;
Я пока не стану распространяться насчет класса TGameServer. Достаточно сказать, что он контролирует абсолютно все что происходит в игре со всеми ее объектами, видимыми или невидимыми. Это тема для отдельной статьи, и может быть я ее напишу, но в другой раз.
А сейчас вернемся к карте флагов. Я показал, как устроен ее класс, показал как на старте игры генерируется карта. Теперь стоит показать те методы, с помощью которых Танки - юниты - общаются с картой.
Сам класс танка выглядит так:
Код
TTank = class
{танк. ездит, стреляет, находит пути среди бетонных блоков.}
constructor Create(Clr: TCanColor; Pos: TPoint);
procedure Fire;
procedure Rotate(V: integer);
procedure Move(V: integer);
procedure Dead;
procedure Time;
procedure MoveInTarget;
procedure Motivator;
procedure AIMove;
procedure Visual;
private
public
status: integer;
FireTime: integer;
Color: TCanColor;
position: TPoint;
Target: TPoint;
AIKey: boolean;
Bonused: TBonusState;
Armor: integer;
ChaseKey: boolean;
MaxMoveTarget: TPoint; // глобальная цель движения
MinMoveTarget: TPoint; // локальная цель движения
Old: boolean; // показатель того, что прежняя глобальная цель совпадает с новой.
end;
Разбирать его весь нам сейчас не понадобится. Возьмем лишь то что относится к поиску пути и движению по нему.
Код
procedure TTank.AIMove;
begin
Move(GameServer.FlagsMap.QuatroDist(position,MinMoveTarget));
end;
procedure TTank.Motivator;
{эта процедура - основная процедура ИИ танка}
var
AF: integer;
AP: TPoint;
BF: integer;
BP: TPoint;
NF: integer;
begin
{сначала танк определяет глобальную цель - то место, куда он хочет попасть в результате своего движения.
при этом он учитывает, есть ли на карте бонусы, и есть ли противник, и как далеко все это от его нынешней позиции}
ChaseKey:= false;
If (Gameserver.BonusEn) then
begin
If (Distance(position,GameServer.Bonus.position)
begin
MaxMoveTarget:= GameServer.Bonus.position;
MaxMoveTarget.X:= Maxmovetarget.X - 25;
MaxmoveTarget.Y:= Maxmovetarget.Y - 25;
end
else begin
If (GameServer.TargetExist(0)) then
begin
MaxMoveTarget:= GameServer.Tanks[0].position;
end
else begin
MaxMoveTarget:= GameServer.Bonus.position;
MaxMoveTarget.X:= Maxmovetarget.X - 25;
MaxmoveTarget.Y:= Maxmovetarget.Y - 25;
end;
end;
end
else begin
If (GameServer.TargetExist(0)) then
begin
MaxMoveTarget:= GameServer.Tanks[0].position;
end
else begin
MaxMoveTarget:= position;
{если на карте нет ни бонусов, ни противника, танк никуда не хочет ехать.}
end;
end;
// глобальная цель определена;
If (Old) then Exit;
// ищем локальную;
If ((MaxMoveTarget.X = position.X) and (MaxMoveTarget.Y = position.Y)) then
begin
minMoveTarget:= position;
{оказалось что танк хотел попасть туда, где он и так находится. никуда не едем.}
end
else begin
AF:= GameServer.FlagsMap.Flagfind(position);
BF:= Gameserver.FlagsMap.Flagfind(MaxMoveTarget);
If (AF = BF) then
begin
{оказалось, что глобальная цель недалеко и до нее можно добраться без всяких флагов}
MinMoveTarget:= MaxMoveTarget;
If (GameServer.TargetExist(0)) then
begin
If ((MaxMoveTarget.X = GameServer.Tanks[0].position.X) and
(MaxMoveTarget.Y = GameServer.Tanks[0].position.Y)) then chaseKey:= true;
end;
end
else begin
{итак, цель не рядом, до нее надо как то добраться. Танк выясняет, как далеко от него находится ближайший флаг из сети флагов.}
AP:= GameServer.FlagsMap.Flags[AF].position;
If (Distance(position,AP) > 12) then
begin
MinMoveTarget:= AP;
{оказалось что ближайший флаг далеко. едем к нему}
end
else begin
NF:= GameServer.FlagsMap.FlagPath(AF,BF);
BP:= Gameserver.FlagsMap.Flags[NF].position;
MinMoveTarget:= BP;
{оказалось что ближайший флаг под корпусом танка. Тогда - выполняется поиск пути к тому флагу, координаты которого ближе всего к позиции глобальной цели.
функция FlagPath возвращает номер флага, к которому надо двигаться, выясняем его координаты - и можно двигаться.}
end;
end;
end;
Old:= true;
{фиксируем найденный путь. если это не сделать, танк "забудет" откуда он начал движение, и едва отойдя от первого флага, обнаружит что он удален от всех флагов, и решит двигаться к ближайшему.
А это будет тот самый флаг от которого он отправился}
end;
procedure TTank.Time;
{обработка событий, происходящих с танком со временем. Всю процедуру рассматривать необязательно, нам нужно лишь то что относится к движению.}
begin
if (FireTime > 0) then FireTime:= FireTime - 1;
If (bonused.bonusTime > 0) then
begin
bonused.bonusTime:= bonused.bonusTime - 1;
If (Bonused.bonusTime = 0) then
begin
bonused.FireTime:= 25;
bonused.Bulletspeed:= 16;
bonused.Movespeed:= 4;
bonused.WeaponX:= 0;
bonused.RapidX:= 0;
end;
end;
If (Bonused.RapidFire > 0) then Fire;
{AI Realisation}
If (AIKey) then
begin
AIMove; {танк двигается к ЛОКАЛЬНОЙ цели}
If (GameServer.TargetExist(0)) then
begin
Target:= GameServer.Tanks[0].position;
If (FireTime = 0) then Fire;
end
end;
end;
Думаю, многое стало ясно из комментариев в самом коде. На всякий случай, расскажу принцип действия еще раз.
Танк имеет две цели, локальную и глобальную. локальная - это та, к которой он едет напрямую, уверенный в том что не встретит на этом пути препятствий. и Глобальная - то место куда танк хочет попасть в итоге.
Стоит заметить, что обе эти цели не имеют ничего общего с тем, куда танк стреляет - но это уже другая история. Танк сравнивает для начала свою позицию с позицией глобальной цели.
Если цель близко, он двигается к ней напрямую. Если же дистанция существенная, то идет расчет пути с помощью флагов.
Для начала Танк выясняет, как далеко он от ближайшего флага. Танки ведь могут двигаться произвольно и находиться в любой точке карты. Если флаг не прямо под танком, он двигается к ближайшему флагу.
Приехав к нему, или обнаружив что и так на нем стоит, Танк делает запрос для расчета пути
Код
NF:= GameServer.FlagsMap.FlagPath(AF,BF);
Вот эта самая строчка. Он просит карту флагов рассчитать для него путь, указывая при этом номер флага в котором он сам находится (AF), и номер флага куда хочет попасть. (BF).
Карта флагов перебирает все возможные варианты путей из исходной позиции, отметая повторяющиеся флаги, постепенно увеличивая длину путей, до тех пор пока один из флагов, добавленных к очередному варианту пути,
не окажется тем самым куда хотел попасть танк. Тогда танку сообщается номер флага, оказавшегося в найденном пути вторым. (первый - исходная позиция). Танк выясняет координаты флага с таким номером и делает их своей ЛОКАЛЬНОЙ целью.
после этого автоматика процедуры TTank.Time, работающая по тикам таймера десятки раз в секунду, начнет двигать танк к его локальной цели. Собственно, она всегда его двигает, просто иногда локальная цель может совпадать с его позицией - это когда танк никуда ехать не желает.
Процедура Мотиватор являющаяся "мозгами" танка, и принимающая решения куда ехать, в танкодроме вызывалась отдельным таймером, работающим со скоростью всего 3 тика в секунду. Это чтобы у танков не было мгновенной реакции - если цель сместилась, или
на карте появился бонус, танк отреагирует на это лишь при следующем тике мотиватора.
На этом, пока все.
