A* pathfinding example !

[Abened]

I've managed to write a very simple A* pathfinding program using delphiX that works well thaks to a tut on GameDev.net : A* Pathfinig for beginners by Patrick Lester !
I'm quite proud of myself and to help and have some feedback i'm posting a link to it here (delphiX needed)

The A* algo (whith sources & exe) (http://perso.club-internet.fr/jbe/pathfinding.zip)

Waiting for some feedback, Abened

PS : To move start point, move your mouse while pressing shift.
To move destination, move your mouse holding Control
To place walls, clik & move ! (to remove, right clik)

[J9850s]

ss

[J9850s]

source comment...

first of all: nottings wrong with your program.

your way of programming is with the mind.
you must program 'recursive'>>the way that the computer must use his head(cpu).

analyse:

there are 4 ways the 'person' can go.
starts in a point and ends in a point.
the grid has a max x&y value.


for example a procedure:



PathFinding(thisPiont,EndPoint:TPoint;Matrix:grid) ;

var . .. . ;
begin

//ending.
if thisPoint=EndPoint then
Solution(Matrax)
else
//moving to all 4 places. (left, right, top, bottom)
for i:=0 to 3 do
//check if that place if free.
if OK(thisPoint,i,Matrix) then
begin
// everything went fine, mark the place where you are (thisPoint) and move on.
//mark
Matrix[thisPoint.x,thisPoint.y]:=False;
//move on
newPoint:=thisPoint;
case i of
1:Dec(newPoint.x);
2:Inc(newPoint.x);
3:Dec(newPoint.y);
4:Inc(newPoint.y);
end;
PathFinding&#40;newPoint,endPoint,Matrix&#41;;//<<< this is recursive.
//unmark
Matrix&#91;thisPoint.x,thisPoint.y&#93;&#58;=True;
end;
end;


now there are 2 other procedures to write.
Solution(Matrix:grid);

and
OK(thisPoint,i,Matrix);

the solution procedure is simple this is calling when the computer found A way to the end, <<ps. there is often more then one!!!!

the OK procedure is the ai for the computer.
return false when:
1:the newPoint is already taken.
2:there was already found a shorter way.
etc. ect.
otherwise return true.

the second point i recommend is not nessesery. but slows the computer down. becauce the Matrix that was found is not the Matrix where we are looking for.

the more false returning in the OK procedure the smatrer the computer.

this way of programming is called 'BACKTRACKING'.

[holybyte]

thank you Abened ! A* is really tricky so i enjoyed the help of your work. It is exactly what i was looking for.

I have just ported it to freepascal. It works fine with only minor changes (static Arrays). Using Console output it can be compiled by any existing pascal compiler.
:pirate:
THANKS!

[EugenioEnko]

It is just what I was searching.
Thanks, soon post a coment. :lol:

[Lazo]

What is the max size of the nodes in X and Y Whit this technique?

[cairnswm]

There is an article on A* pathfinding in the Tools and Tutorials forum that I wrote a few years ago - it includes example code on how the algorithm works.

[JernejL]

There is an article on A* pathfinding in the Tools and Tutorials forum that I wrote a few years ago - it includes example code on how the algorithm works.

is that anywhere to download?

[cairnswm]

I've updated the tutorial with the links.

The example code can be downloaded from http://www.cairnsgames.co.za/files/astar1.zip - This is the final code - I do not have theintermediate example available any more.

[JernejL]

interesting stuff, is it okay to use in any apps or a under specific license?

[cairnswm]

My standard license: Free for any use :)

[JernejL]

nice, thanks, ill probably make some modifications and post them here :)

EDIT: as promised:

http://www.gtatools.com/temp/pathfinder.jpg

https://github.com/JernejL/astar

added:
colored cubes, actual path finding that finds the shortest path between the nodes, and some fun stuff ;)

EDIT:

I modified some of the algorythm internals now, for start - i replaced the sorted Tlistbox with a dynamic array instead, and instead of sorting the array i just find the lowest item in the array - which is MUCH faster than sorting the whole list for every added item no matter which sorting algorythm you use, the deletion of item from array is also optimized with using memory MOVE routine.

and i added a cleanup menu button to clear the path searching results.

i also commented most of the new code i added so it should be easy to understand.

[czar]

Nice one Delpfi

Thanks for posting

[cairnswm]

Some more things that can be added

1. Find a way to make it a class that can easily be included in any game using squares. I have sort of done this in my Run-A-War game but every time I want to reuse the Pathfinding I am finding I need to make modifications.

2. Make weighted cells - so be able to add a river that costs three movement points to cross, or mountains, forests etc.

3. Optimise optimise optimise :)

Glad to see someone found the tutorial useful anyway :)

[JernejL]

I thought of making it a library with some simple callbacks, so you would call it and it would call your callback parameter of your routine that would just call you back for every cube that it wants to search and you would tell it if it is passable and A* weight... this would be very simple to use.

[jdarling]

Make sure that it is flexiable in its walking and passing schema. For example don't limit it to X, Y int coords. X, Y, Z Singles would be much better, with a step size passed back for each direction. That way if you have a "Warp" from one loc to another you can let the engine know about it.

[JernejL]

Added: fallback case: finds closest point to the goal if there is no direct path!

http://www.gtatools.com/temp/pathfinderfallback.jpg

Ok, i separated the path finding from the form unit, it works like i described - using callbacks, here is the new download:

http://www.gtatools.com/temp/astar1.rar

If you need older one for any reasons it is here:
http://www.gtatools.com/temp/astar1_old.rar

EDIT:

jdarling:

this is now all possible what you described, the map area field is dynamic, and you can also specify it to wrap worlds (it cannot go to negative coords, you need to enlarge the field you give to pathfinder and compensate for it in the callback routines)

im not sure if you could make warp areas, it could be done, just give the cube at the warp entrance much bigger priority if the warp exit is closer..

[tanffn]

How hard will it be to add ‘ground priorities’, meaning:
road penalty = 0.
dirt path penalty = 1.
Up hill penalty = 5
And so on.

[JernejL]

How hard will it be to add ‘ground priorities’, meaning:
road penalty = 0.
dirt path penalty = 1.
Up hill penalty = 5
And so on.

very easy.. just tell the pathfinder block cost in the callback.

[JernejL]

Now this is embarrasing, i forgot to include actual astar.pas into the rar file, i added it now :oops:

[paul_nicholls]

Now this is embarrasing, i forgot to include actual astar.pas into the rar file, i added it now :oops:

I don't suppose you could include a .zip version as well for download?
I don't have WinRAR on my machine and I wanted to look at it (I can't download WinRAR at the moment).

cheers,
Paul.

[JernejL]

can't winzip open rars? winrar is free aniway..

[paul_nicholls]

can't winzip open rars? winrar is free aniway..

WinZIP can open WinRAR files, but only by using WinRAR itself...

I have downloaded WinRAR...
cheers,
Paul.

[Firlefanz]

Hi!

I am just trying to add your AStar unit to my current 3D game project 'The Innominate'.

Thanks for your class and sample!

I'll sure get back here as soon as I run into first problems. :wink:

I understand this is done with a list of TPoints from the Start to the End, right?

I want to use this for 3D. So is there the possibility to really only store the next point I need without a block between it so I can always use the shortest way between the points? Understandable? Right now it only works in 45¬?, would be cool if it would work in 3D with shortest distance (and free angle) between the waypoint...

P.S.: Some problems with the sample:
So Astar.Grid stores the grid where I can set my blocks, right?
Astar.Grid[x,y]=0 means no block, Astar.Grid[x,y]=-1 means block right? What happens if I set 255 f.E.?
Astar.Path(i) is the next waypoint? Can I delete it after I reached it to get access to the next waypoint or what is the best way to step through them?

Firle

[JernejL]

Hi!

I am just trying to add your AStar unit to my current 3D game project 'The Innominate'.

Thanks for your class and sample!

I'll sure get back here as soon as I run into first problems. :wink:

I understand this is done with a list of TPoints from the Start to the End, right?

I want to use this for 3D. So is there the possibility to really only store the next point I need without a block between it so I can always use the shortest way between the points? Understandable? Right now it only works in 45¬?, would be cool if it would work in 3D with shortest distance (and free angle) between the waypoint...

P.S.: Some problems with the sample:
So Astar.Grid stores the grid where I can set my blocks, right?
Astar.Grid[x,y]=0 means no block, Astar.Grid[x,y]=-1 means block right? What happens if I set 255 f.E.?
Astar.Path(i) is the next waypoint? Can I delete it after I reached it to get access to the next waypoint or what is the best way to step through them?

Firle

well, you can use any type of structures you want, in the callback, you will be asked to do your own processing and tell pathfinder if the area is accesible from previous point. it works with 90¬? and 45¬? angles, just pass it right parameter.

[Firlefanz]

Okay, 45¬? and 90¬? of course, understood.

But it would be cool to have a feature that points directly beneath the previous point are not in list, only points where I have to walk around a block.

So I can tell my unit to move with the angle that is lying between this point and the next point to have angles other than only 45¬? and so on.

Understood or should I make a drawing?

And I didn't quite get the callback stuff, I will look at it again, thanks.

Firle

[Firlefanz]

To make it clear:

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

I don't want all points like this:

http://www.ericbehme.de/bilder/temp/Path1.JPG

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

http://www.ericbehme.de/bilder/temp/Path2.JPG

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

Thanks,
Firle

[WILL]

I had a great chapter on A* in a book I bought 'AI for Game Developers'.

Not wanting to step on toes, but I'll see if I can retell it in a seperate thread. It was amazingly clear to me the way he did it. It's not the only way to do A*, but it's certanly an easy way to learn it for the first time. (It used heavy illustrations aswell.)

If it is well received then I'll write up an article for PGD.

EDIT: Wow, I just looked back to the first post... this is an OLD thread. :) No toe stepping at this point then I guess huh? ;)

[JernejL]

Firlefanz: you can't do that, path finders don't do that, you must do that in your engine, with raycasting the points, i guess.


I had a great chapter on A* in a book I bought 'AI for Game Developers'.

Not wanting to step on toes, but I'll see if I can retell it in a seperate thread. It was amazingly clear to me the way he did it. It's not the only way to do A*, but it's certanly an easy way to learn it for the first time. (It used heavy illustrations aswell.)

If it is well received then I'll write up an article for PGD.

EDIT: Wow, I just looked back to the first post... this is an OLD thread. :) No toe stepping at this point then I guess huh? ;)

At least it is getting updates and posts :D aniway, any article about A* be great!

[Firlefanz]

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

[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! :wink:

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! :wink:

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:

http://www.ericbehme.de/bilder/temp/Path1.JPG

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

http://www.ericbehme.de/bilder/temp/Path2.JPG

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/GameProgramming/Heuristics.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&#58;= -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&#40;WayPath,length&#40;path&#41;&#41;;
for i&#58;=0 to length&#40;path&#41; do waypath&#91;i&#93;&#58;=path&#91;i&#93;;


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! :D

Firle

[JernejL]

Hi!

Two more questions please:

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



setlength&#40;WayPath,length&#40;path&#41;&#41;;
for i&#58;=0 to length&#40;path&#41; do waypath&#91;i&#93;&#58;=path&#91;i&#93;;


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! :D

Firle

you could try:


setlength&#40;WayPath,length&#40;path&#41;&#41;;

move&#40;waypath&#91;0&#93;, path&#91;0&#93;, sizeof&#40;whatever_point_you_use_in_path&#41; * length&#40;path&#41;&#41;;


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&#40;X, Y, Fx, Fy&#58; integer&#41;&#58; integer;
begin
result&#58;= -1; // if it isnt anything else - it is wall
if level&#91;x,y&#93;=255 then result&#58;=round&#40;&#40;&#40;ABS&#40;FX-X&#41; + ABS&#40;FY - Y&#41;&#41; * 3&#41;/3&#41;
else if level&#91;x,y&#93;=0 then result&#58;= &#40;&#40;ABS&#40;FX-X&#41; + ABS&#40;FY - Y&#41;&#41; * 3&#41;;
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

[Firlefanz]

Found a bug:

Set a block around the startpoinht so there is no way out!

Then start Pathfinding, you will get an exception!

Could you please fix that?

I understood it now and if you don't mind I may use your Astar.pas as pathfinding for my game in progress?

Thanks a lot!

Firle

[JernejL]

Found a bug:

Set a block around the startpoinht so there is no way out!

Then start Pathfinding, you will get an exception!

Could you please fix that?

I understood it now and if you don't mind I may use your Astar.pas as pathfinding for my game in progress?

Thanks a lot!

Firle

hmm, you mean like walls all around the start point? i'll check out that later.

no, i don't mind at all, it isn't really mine, i just made come changed to it, cairnswm wrote it (see page 1), he said: "My standard license: Free for any use :)".

[Firlefanz]

Hi delfi,

could you pleeease fix it? I am getting exceptions often because my unit is locked just like I described..this should not raise an exception.

Thanks a lot,
Firle

[JernejL]

Hi delfi,

could you pleeease fix it? I am getting exceptions often because my unit is locked just like I described..this should not raise an exception.

Thanks a lot,
Firle

this seems really weird, does your game really have that much lock situations? i'm sure the problem is in searching the array for closest item, it should be rather easy for you to fix it.

[Firlefanz]

It is not often, but possible! And should never raise an exception then!

The Player can itself build stuff into the level. If it happens he looks a unit then, I get an exception...

Okay, I will fix it myself. I only thought you would like to do so yourself, because you made such a nice topic here, and when you later make improvements to your version and I want to have them, my bugfixing is lost. Perhaps I try to fix it and post the new unit here.

Firle

[cairnswm]

This sounds like it should throw a custom exception from within the code that other programs can catch. So if you just catch enay exception for now the final fix (custom exception) should work as well.

[Firlefanz]

I would prefer the bool variable if path is found is set to false and the list is empty. Or if the unit has space to move it would be cool if it patrols this area then :)

But the main point is to get rid of the exception which terminates my project from time to time...

firle

[JernejL]

you are right, but the code was not supposed to make a exception and i did not predict such a case, i'll fix it, it will just return no path status.

edit:

actually the path finder tried to predict such a case, but the code is wrong:

change:
if high(astack) = 0 then begin patherror:= true; exit; end;

to:
if high(astack) = -1 then begin patherror:= true; exit; end;

and the path finder will tell you that there is no path:

astar.Found = false

edit: here is fix:

http://www.gtatools.com/temp/astar1.rar

[Firlefanz]

Thanks a lot!

if length(astack) = 0 then begin patherror:= true; exit; end;

I added this line to your bugfix position before,
now I just took your new astar.pas and test it, thanks a lot!

firle

[bigsofty]

Path squeezes between 2 diagonal boxes?

[JernejL]

Path squeezes between 2 diagonal boxes?

huh?

[bigsofty]

Currently...




SX
PXPPPPE
PX



Should be...




SX
PX PPE
PXP
P



X= WALL
S=START
E=END
P=PATH

The path should go around the lower X, instead is squeezes between the lower and middle X.

[JernejL]

there's a boolean parameter switch to turn this behavor on and off in code, tell the pathfinder not to use diagonals if that's bothering you, if it is something else, then you can specify the pathfinder it can't go there in the callback procedure.

[bigsofty]

there's a boolean parameter switch to turn this behavor on and off in code, tell the pathfinder not to use diagonals if that's bothering you, if it is something else, then you can specify the pathfinder it can't go there in the callback procedure.

Ah, cool, nice work ;)

[IlovePascal]

hey, i know this is not really meant to be here, because you guys r doin som great work thinkin (!).

I jst wanted to ask how you guys make the download link thing. If it's a PGD thing, then how do you upload? If it's from a blog that lets u upload, what blog is it?

Cheers ;)

[JernejL]

[quote="IlovePascal"]I jst wanted to ask how you guys make the download ]

you need a server to host the file.

[IlovePascal]

Damn! Isn't there another way??? :( :cry:

[WILL]

IlovePascal, make another topic in the Feedback forum to continue this discussion please. :)

[Firlefanz]

Hey folks,

right now I found some times to test my pathfinding based on this sample and source.

I just realized it is not doing what it should do.

I have my own blocktester:



function TForm1.blocktester&#40;X, Y, Fx, Fy&#58; integer&#41;&#58; integer;
begin
result&#58;= -1; // if it isnt anything else - it is wall
if &#40;level&#91;x,y&#93;=255&#41; then result&#58;=round&#40;&#40;&#40;ABS&#40;FX-X&#41; + ABS&#40;FY - Y&#41;&#41; * 3&#41;&#41;
else if &#40;level&#91;x,y&#93;=0&#41; or &#40;level&#91;x,y&#93; in &#91;51..55&#93;&#41; then result&#58;= &#40;&#40;ABS&#40;FX-X&#41; + ABS&#40;FY - Y&#41;&#41; * 3&#41;*32;
end;

Level=0 means there is nothing, 255 means it is a road, 51..55 is grass.

For my villagers I call it like this:



StartPoint &#58;= Point&#40;round&#40;x&#41;,round&#40;z&#41;&#41;;
EndPoint &#58;= Point&#40;round&#40;ntargetx&#41;,round&#40;ntargetz&#41;&#41;;
setlength&#40;Astack, 0&#41;;
patherror&#58;=false;
Astar.findpath&#40;StartPoint, EndPoint, point&#40;levelb-1,levelh-1&#41;,true, true, @blocktester&#41;;
setlength&#40;waypath,0&#41;;
setlength&#40;path,0&#41;;
setlength&#40;WayPath,length&#40;path&#41;&#41;;
nway&#58;=0;
if not patherror then begin
boolstand&#58;=false;
for i&#58;=0 to length&#40;path&#41;-1 do waypath&#91;i&#93;&#58;=path&#91;i&#93;;
end else form1.exceptionmsg&#40;'Kein Path gefunden'&#41;;


I tried to debug it and realized each time I get an patherror!
Levelb is the width and Levelh the height of my level (256x256).
It starts to step and no idea what causes the patherror, any idea?

PS: Merry XMas. :D

Thanks,
Firle *depressedonxmas*

[JernejL]

Sorry, but without more info i can't really help you anything unless you tell us where the code ends up in an error.

[Firlefanz]

Wow, that was fast!
Not only I hate XMas it seems :)

Any idea how I can find the error except debugging the Step method which is very often called?

Firle

[JernejL]

you can run to line with F4, and step thru the code with F7 and F8...

[Firlefanz]

*laughs*

Oh yes I already realized :wink:

I thought I might have did something gnerally wrong...

Okay then Ihave to debug that stuff....

[Firlefanz]

I think I just found it, my blocks (obstacles) we too large.
Still needs some testing...

Firle

[spyke00]

someone haves an example of path-finding more easy?!

i can't understand a lot of things in this code!

it's hard =P

Brothers! DelphiX is hard!
GLScene is easy and, i think is more powerfull! =D

A hug!

[JernejL]

someone haves an example of path-finding more easy?!

i can't understand a lot of things in this code!

it's hard =P

Brothers! DelphiX is hard!
GLScene is easy and, i think is more powerfull! =D

A hug!

dude, read some elementary pascal books, it is not hard, the code is very simple, and this has nothing to do with delphix or glscene.

[WILL]

I've been putting off writing my own A* tutorial for some time now... perhaps it's time to get on it. :)

So far my techniques (borrowed granted) have proven them selves in 2 of my recent game projects. I also believe that it's great for customization as in the first (Subject 33), my sole interest was to see what I could do with it to make my roaming robots seem 'smarter'. Which I guess is the whole point, right? ;)

[spyke00]

ya! but i can't read! the problem is: can't understand where start and finish the functions, why have?, for what?

look:
my map haves 16*16 blocks, total of 256 blocks
abened's code, is so confused, i don't know where him check the "tile"...
i don't know where him add +1 to see the next tile.
that things....

i hope u understand....

a easy code:

var
x,y&#58;integer;
begin
for x&#58;=0 to maxtilex do begin
for y&#58;=0 to maxtiley do begin
if tile&#91;x,y&#93;.wall = true then
//do something
end
else
if tile&#91;x,y&#93;.wall = true then
end;
end;
end;
end;

and...


Brothers! DelphiX is hard!
GLScene is easy and, i think is more powerfull! =D
it's just a comment...

a hug!

[jasonf]

I've just taken a look at this code and I have to agree with Delfi in some ways, the code is not hard or badly written.. the trouble is the subject is not trivial.

DelphiX is one of the easiest things on the planet. You can easily write a game in a weekend with it. There are a TON of tutorial on this site for DelphiX, but that's not what this thread is about.

I'm sure that abened's code could be tidied up a little to suit a different coding style, but most of the time it's all down to personal preference really.

The variable naming could be better in my personal opinion, but that's just my preference and certainly not a fault in the code and in no way a disrespect to abened's fine work with this topic.

[spyke00]

i'm nothing disrespecting... i'm just say, that him code is confused!

coz i need something easy, i hate CTRL+C and CTRL+V on source-codes!

that put trash(inutil things) on code, and... the credits is for another people!

a hug

[chronozphere]

Hi guys 8)

I was wondering..is there a way to find a path for an object that occupies 4 or 9 blocks.
Let's say you want to create a game with soldiers and tanks in it, :)
Then you could make the tanks bigger so they only can move when there is enough space. And soldiers could benefit from the smaller holes when they have to flee. This can make a game more realistic. :razz:

I've tried to figure out how to do this but with no result so far. :(

What do you guys think about this?? is it worth implementing? How can it be implemented??

Thanks

[Firlefanz]

If you use this unit, there is a patherror when the target cannot be reached.

So findPath, then if patherror stand still else move along path.

Firle

[cairnswm]

This code came out of a step by step tutorial I wrote previously - start at the beginning and make it grow - it is not supposed to be cut and paste.

[Firlefanz]

Still one question:

My level is a 2 dim array of byte.
The findpath is a bit slow.

Sometimes my monsters get stuck. I think it is because they maybe larger than 1, and the pathfinding finds a path where only size<=1 can walk.

So how do I get it a bit faster and working with larger monsters?

I thought perhaps I make a new 2dim array, 140x140 (or smaller?) and copy the larger one into the smaller one with keeping all obstacles, then the found way may work for larger monsters and findpath is faster?

Is that understandable or any better ideas?

Thanks,
Firle

[JernejL]

in the callback, your app can return proper results depending on monster's size (use smaller grid resolution where monster can fit).

[Firlefanz]

Hi Delfi,

in the sample there is nothing done with the callback.

Could you please give a short sample how to change the callback?

And any idea why the findpath is a bit slow with a 2dim level of 0..280,0..280?

Right now my blocktester looks like this:


function TForm1.blocktester&#40;X, Y, Fx, Fy&#58; integer&#41;&#58; integer;
begin
result&#58;= -1; // if it isnt anything else - it is wall
if &#40;level&#91;x,y&#93;=255&#41; then result&#58;=round&#40;&#40;&#40;ABS&#40;FX-X&#41; + ABS&#40;FY - Y&#41;&#41; * 3&#41;&#41;
else if &#40;level&#91;x,y&#93;=0&#41; or &#40;level&#91;x,y&#93;=51&#41; then result&#58;= &#40;&#40;ABS&#40;FX-X&#41; + ABS&#40;FY - Y&#41;&#41; * 3&#41;*16;
end;

255 is a road (walk faster), 0 is empty and 51 is grass, also walkable.

My findpath looks like this:

Astar.findpath&#40;StartPoint, EndPoint, point&#40;levelb-1,levelh-1&#41;,true,true, @blocktester&#41;;

Levelb and Levelh contain my level width/height (280)

Is this correct?

Thanks a lot,
Firle

[JernejL]

when getting data for array you are now checking level[x,y], to do it on lower resolution for bigger monsters, just check accompanying blocks as well.

[Firlefanz]

Okay, so I'll just have to add that to my blocktester.
Thanks, I'll try that :D

Firle

[Firlefanz]

I think I got it working perfect now.

That Innominate monsters are really dangerous now, they kill all villagers then me in a short time because they don't get stuck at obstacles anymore :D

Great stuff!

Thanks a lot Delfi!!! :wink:

Firle

[WILL]

*gasp* You zombie sympathizer! :P

:hellspawn:

[JernejL]

will, some of topics like this one could be put under some section as very useful resources or something similar ;)

[Firlefanz]

Yes indeed, it was really very useful for me, thanks ;)

Or put it (code and sample) in the library?

Firle

[WILL]

I try. :)

[JC_]

http://rapidshare.com/files/61581654/astar.rar.html - here is modified code for FPC, maybe help to somebody

[Colin]

i'm looking for something to help my AI's avoid colliding, and find short paths to destination, would this be relavant, and where can i download it?

my game and engine is a birds-eye view camera, 2d movement controls.

-Colin

[JernejL]

This is the original file:

http://mathpudding.com/temp/astar1.rar

[Colin]

hi thanks, i will take a look at that as soon as i implement a physics engine. i'm kinda having problems implementing newton (everything coded looks correct, even in comparison with samples, but just does not work - does nothing, not even update any values)

[JC_]

Hi,

has anyone edited astar1.rar from Delfi ? links are dead

[AthenaOfDelphi]

Try them again, I just downloaded them without a problem.

[JernejL]

I wish to reupload astar1.rar since link has died again, what file storage do you recommend? i don't have a website currently.

EDIT: i just put it up onto github:

https://github.com/JernejL/astar