PDA

View Full Version : Using path finding algorithms effectively



CiNiMoDZA
16-07-2011, 12:35 AM
So Ive been playing around with the A* path finding algorithm, and its been working fine. My implementation of the algorithm seems to take just as long as any of the examples I can find online, but now I am stumped. I know that GameMaker uses this algorithm, but how does id do it so efficiently?

For it to work properly it would need to re-calculate the path every frame, and in XNA this is going to be happening 60 times a second. With the calculation taking up to 4 seconds, this is way too long to work effectively. Any reading material on how to implement this effectively??

SkinkLizzard
16-07-2011, 03:32 AM
I'd suggest doing two levels of pathing
a primary level using A* to avoid static objects like terrain and stuff (only calc once at the move command)
and a secondary pathing using a basic avoid behavior so that if something impassable is moved
into your path you only need to recalc the A* once.

as for taking 4 seconds per calc, what size grid are you using ? perhaps try increasing the cell sizes.

Necrolis
17-07-2011, 12:15 PM
you might find relics A* implementation (http://www.chrisjurney.com/) of use.

hawk
17-07-2011, 08:10 PM
Props to anyone that got an A* algorithim working!

I tried to code one this past semester for a game and it completely stumped me. Thank goodness I'm studying IT! :)

CiNiMoDZA
18-07-2011, 08:14 PM
I did it :D Thanks to Wikipedia and freaking trial and error, I got it working super effectively!! Ill be posting a Windows Phone tutorial on CodeProject soon :D

cairnswm
19-07-2011, 02:03 PM
When I have used A* pathfinding in my games i worked on two systems

1. Design and save a path
2. Pause and wait

Basically when a unit wanted to go somewhere it would do a complete path to the path. I found that heavily increasing the penalty of not moving toward the goal made it a lot faster to find the optimal path. This path would then be cached in memory for the unit to follow (1).

If the unit was following the path and suddenly it found it could not move forward it would stop, and after a short period (0.1sec) would try move again. If it could not move for a certain number of pause session (I actually made this 1), it would then re-search the path and cache a new path presuming its path got blocked due to something having been built in its way.