A* pathfinding example !

[JernejL]

Hmmm. Does not sound very satisfiying, now I am at the beginning again. But thanks for the info. Any other pathfinding samples for Delphi around?

Thanks,
Firle

you don't understand, that's not pathfinder's work, it is your program's.

[Firlefanz]

I see, thanks for the info. I just thought somebody else using pathfinding for 3D must have had the same problem. I'll think about how to do it, thanks!

Firle

[JernejL]

I see, thanks for the info. I just thought somebody else using pathfinding for 3D must have had the same problem. I'll think about how to do it, thanks!

Firle

pathfinding in 3d is usually done with info nodes (half-life style) and raycasting the 3d world (gta3/vc/sa engine).

[tpascal]

To make it clear:

I don't wanna use 45¬? only, if possible.

I don't want all points like this:



I only want the points I need so I can set my angle to next point until I am there:



Is this possible somehow? Or is there an Other Sample / Algo
to do so?

Thanks,
Firle

Most those examples are for grided maps, and the Path scoring is computed using the "manhattan" method; which procedue a path like in your first pic; but there is more ways to compute the path scoring wich could produce different paterns in the line path.
check this interesting article about Heuristic scoring:

http://theory.stanford.edu/%7Eamitp/...euristics.html

But what you are asking in your 2th pic i thinkis called "Steering behavior",

(warning, PDF ]http://ducati.doc.ntu.ac.uk/uksim/uksim%2704/Papers/Simon%20Tomlinson-%2004-20/paper04-20%20CR.pdf[/url]

[Firlefanz]

Hello,

one more question regarding the included sample:

Is there a possibility to set 'preferable' tiles somehow?
I mean some tiles are a road, and the program should prefer that road tiles if possible before using 'grass' tiles...

Thanks,
Firle

[JernejL]

yes, you can send back terrain weights in the callbacks.

[Firlefanz]

The 'callback' you are talking about is the 'Blocktester' in the MainUnit, right?

this is the way how you get the array (or stringgrid in your case) into the pathfinding method, right?

It is this method I find a bit hard to understand:

// this function is called when path finder asks you weither it can process coordinate X,Y
// Fx, Fy are the coordinates from where the pathfinder is coming, you can use
// that to make some blocks only passable thru some sides and not all 4.

// you return -1 if you dont allow pathfinder to go to that block - like walls,
// this can be used to limit search area of the pathfinder as well.

// if you allow the pathfinder to go to that specific block, return a positive number,
// returning zero means you want to terminate path finding.

result:= -1; // if it isnt anything else - it is wall

So instead of the stringGrid I just use myArray[x,y] here for the asked tile. I want 0 walkable and >0 not walkable, and <0 is a road it is better walkable if possible.

if myArray[x,y]=0 then result:=:=((ABS(EndPoint.X-X) + ABS(EndPoint.Y - Y)) * 3); //for walkable, right?
else if myArray[x,y]>0 then result:=-1 //not walkable, right?
else result:=result:=((ABS(EndPoint.X-X) + ABS(EndPoint.Y - Y)) * 3)+myarray[x,y]; //for walkable with lower cost, because myArray is below zero, right? Must be cautious that it is>0 right? The lower the better then?


Thanks,
Firle

[Firlefanz]

Hi!

Two more questions please:

Is there a faster possibility to copy the path into my sprite class item than this:

setlength(WayPath,length(path));
for i:=0 to length(path) do waypath[i]:=path[i];

And if I step through the path, is there a fast method to delete the first waypoint of the path after I reached it or should I have a variable where the current step is saved and so step through the pathlist?

Thanks a lot for your infos and help!

Firle

[JernejL]

Hi!

Two more questions please:

Is there a faster possibility to copy the path into my sprite class item than this:

setlength(WayPath,length(path));
for i:=0 to length(path) do waypath[i]:=path[i];

And if I step through the path, is there a fast method to delete the first waypoint of the path after I reached it or should I have a variable where the current step is saved and so step through the pathlist?

Thanks a lot for your infos and help!

Firle

you could try:

setlength(WayPath,length(path));

move(waypath[0], path[0], sizeof(whatever_point_you_use_in_path) * length(path));

this will move the memory from one variable to another.

[Firlefanz]

Hi,

one more please:

Like I asked some questions ago:

The Blocktester is a bit hard to understand, did I make it right?

Right now my people still run 'through' the obastacles, don't know if it is a pathfinding or a movement bug.

Here my blocktester:

function TForm1.blocktester(X, Y, Fx, Fy: integer): integer;
begin
  result:= -1; // if it isnt anything else - it is wall
  if level[x,y]=255 then result:=round(((ABS(FX-X) + ABS(FY - Y)) * 3)/3)
  else if level[x,y]=0 then result:= ((ABS(FX-X) + ABS(FY - Y)) * 3);
end;

0 is no obstacle, 255 is a road, this is no obstacle but a way to prefer.
Is the result correct?

Thanks again,
Firle