path finding

[WiZz]

i dont knew where i need to post this topic so i posted it here. I am creating a small RPG game with standart delphi component, my hero is in image1, and enemies are in images2-3-4. this rpg will be turn based, so i have allready done the wallking system, bet with out path finding, if there is an enemy in heros's way he walk him through, how to avoid this?how to walk near enemy, not through?

P.S. sorry for my bad english

[TheLion]

There is an algorithm called A* that solves that problem... however I have never worked with it yet, so I have no idea how it works exactly, BUT I think we have a tutorial on that in the Tutorials & Articles forum...

check this:

http://terraqueous.f2o.org/dgdev/viewtopic.php?t=348


NOTE : I wouldn't use TImage objects to make a game, it's possible, but it's also a memory sucker! If you don't want to use OpenGL / DirectX use the Canvas, it gives you a lot more control over your characters and your game and it uses a lot less memory!

P.S. Your English is not bad btw!

[Harry Hunt]

One of the easiest path finding routine is the so called depth-search algorithm. It's not very fast, but it works very well.

In theory this is how it works: imagine you are in a labyrinth and have a piece of crayon that you can use to make markings on the wallks. While walking, always mark the walls with a straight line. Now if you reach a crossing, choose the path that has the least markings or if it has no markings, choose the one to the right (or left, makes no difference).

This can easily be implemented in delphi. If you have an array, simply have an Integer for every array field that you increment in your pathfinding routine.


A* is of course much faster, but also slightly harder to understand.

[WiZz]

hmmm :/ i am reading the material about this whole month. i don't understand anything could someone help me, to show some code example or something else.

[Harry Hunt]

This is an implementation of a depth-search algorithm. It won't find the shortest path, but it marks the fields in an array until it arrives at the destination.

0 is the code for the destination field.
Also, this is by no means an optimal solution.

[pascal]
procedure TForm1.FindPath;
var
CurrentX, CurrentY: Integer;
CostN, CostE, CostS, CostW: Integer;
OldX, OldY: Integer;

function Smallest(A, B, C, D: Integer): Boolean;
begin
if (A <= B) and (A <= C) and (A <= D) then
Result := true
else
Result := false;
end;

begin
CurrentX := StartX;
CurrentY := StartY;

repeat
Maze[CurrentX, CurrentY] := Maze[CurrentX, CurrentY] + 1;

CostN := Maze[CurrentX, CurrentY - 1];
CostE := Maze[CurrentX + 1, CurrentY];
CostS := Maze[CurrentX, CurrentY + 1];
CostW := Maze[CurrentX - 1, CurrentY];

if Smallest(CostN, CostE, CostS, CostW) then
CurrentY := CurrentY - 1
else if Smallest(CostE, CostS, CostW, CostN) then
CurrentX := CurrentX + 1
else if Smallest(CostS, CostW, CostN, CostE) then
CurrentY := CurrentY + 1
else if Smallest(CostW, CostN, CostE, CostS) then
CurrentX := CurrentX - 1;
until Maze[CurrentX, CurrentY] = 0;
end;
[/pascal]

[Harry Hunt]

Some additional words on how this works:

You have an array (in this case "Maze") which represents your playfield. Now each field has an integer value which i like to call "cost". Passable fields have a low cost (in this example, 1) and walls have a very high cost (in my case 4000). You can also handle walls separately if you like. Now from your starting point, you check the surrounding fields to see which one has the lowest "cost" and move to that field. You increment the cost of the previous field basically to mark that you've been there already. The destination field has the cost "0" to make sure the routine is definitely going to choose that field over any other. When you moved to a field with the cost "0" you are at your destination.

[WiZz]

oh thank's now i am understanding something

[height]