Archived

This topic is now archived and is closed to further replies.

TAN's pathfinding is useless.......???

This topic is 5866 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello !!! I have implemented the pathfinding from the TAN''s book "Isometric game programming with dx7". During the implementation I used a map of size 20x20 for testing purposes,and the speed was ok......now that I finished,I changed the map size to 200x200, and it got TERRIBLY SLOW (PIII 500mhz). It is even VERY SLOW with the map size of 100x100, which I think is a minimun map size for a decent game. So, does this mean, that the algorithm is useless!!!????...or is there any way to speed it up???? Thanx in advance!! -- Uros Life lived unexplored is life not worth living !

Share this post


Link to post
Share on other sites
Hey!

Thanx for your reply, but as I am not a native english speaker,and allso quite new in game programming, I don''t know what the term "recursive" means.... Sorry!! Can you explain please ?

Have fun!
--
Uros

Share this post


Link to post
Share on other sites

Recursive: See recursive.

from the game dictionary:

For a computer programmer, this is when a function you''ve written has to call itself in order
to get a result. (The classic, textbook example is a routine which works out the factorial of a
number.) It can be very elegant if done right. It can also be a complete bastard to debug if
done wrong.

in other words a function is recursive if it calls itself like


void recursive()
{
...
if (!done) recursive()
else return;
...
}


it can be a mess to debug, and if it goes too far without returning it could overflow your stack, so you have to be carefull, I will take a look to TAN''s pathfinding to see if it is or not recursive.

Share this post


Link to post
Share on other sites
Nope, The function is not recursive is just ineficient in large maps, this because it has to set all tiles to -1 (or 255 for unwalkable) and then find the start and end, set the end to 0 and start filling the values of each tile with the costs, its a simple A* algorithm, however 20x20 = 400 asignments, thats ok, but 200x200 = 40000, perhaps too many computations, I see 2 solutions 1) check and assign only tiles that you now are closer to the start (if the start is to the north east, pay attention to the tiles north east of the end first) or 2) use the chase algorithm until you hit a wall then apply the pathfinding on a 20x20 area just to get past the obstacle, then go back to chase.

the secound one might make your unit, character go to a wall corner and then surround the wall, so it will not look too inteligent, but maybe you can use a threshold of 2 or 3 tiles ahead so you make it turn before it actually hits his head against the wall.

Share this post


Link to post
Share on other sites