-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|235|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> AI and Movement


 
mike_g
Created : 06 August 2007
Edited : 11 June 2008
Language : Blitz

A-Star Pathfinding



Heres some AI code for pathfinding. If you want to know a bit more about it, heres the tutorial i worked off to create this. Its a pretty good explanation.

 

Comments


Wednesday, 11 June 2008, 17:16
mike_g
The original code I posted for this was borked. I just edited it so it always finds the shortest path now.
Thursday, 12 June 2008, 08:46
HoboBen
Oh cool, I was just going to have a go at path-finding today!

Thanks Mike, this will be a great starting point for a Cobra version
Thursday, 12 June 2008, 11:13
mike_g
Cheers ben. If you want to learn for yourself how it works heres the tutorial I made my version off:
https://www.policyalmanac.org/games/aStarTutorial.htm

I also have a dijkstras version, which I'll post if I get around to untangling the code from a game I made. As with that pathfinding algo you don't need to know the target before you begin the search.
Thursday, 12 June 2008, 12:29
JL235
I recently learnt Dijkstras shortest path for a module on graphs. It's quite a simple algorithm and I can see it being more useful then for just games.
Thursday, 12 June 2008, 13:10
mike_g
Yeah, Dijksra's algo is also used by routing protocols and probably loads of other things. Its very similar to A*, the only difference is that it does not use a heuristic to optimise the pathfinding.
Thursday, 12 June 2008, 14:53
Jayenkai
I think I've used Pathfinding, probably once!
Most of the time I just try to avoid anything that needs it

But this could come in handy, if I ever find a need for it.
Thursday, 12 June 2008, 18:38
Orion Pax
You are so wonderful Mike! This will come in great for my game. I planned on putting AI in my game much later. And I still do plan on doing it much later. I might put 1 bot in now or something....maybe...dunno. But thanks either way!

I just realized that this is in 2d. I wonder how hard it would be to convert it to 3d?
Friday, 13 June 2008, 16:41
mike_g
Thanks guys. Orion, It shouldent be too hard to convert to 3d, but if its for your space game you might be able to get away with something much simpler/faster. As theres generally not a lot of obstacles in space.

Pathfinding can be quite intensive. In realtime games for objects off-screen you can generally get away with the mindless walk to point approach. The only problem with that is when you have enclaves that things can get stuck in.
Friday, 13 June 2008, 20:05
JL235
Mike_G Pathfinding can be quite intensive. In realtime games for objects off-screen you can generally get away with the mindless walk to point approach. The only problem with that is when you have enclaves that things can get stuck in.

Even if it's expensive I'd have imagined that in say an RTS it would only be needed to be calculated when a unit picks a new destination. Over time I could see this occurrence easily averaging to be far less then once a frame. For those moments when the player sends 10000 units to go somewhere you could have them all walk mindlessly and queue their path finding requests. The calculations for these could be run over the next few frames so say only 10 units paths are calculated per frame. This would help keep the frame rate consistent.
Saturday, 14 June 2008, 06:14
HoboBen
Another alternative, which I think is commonly used, is if you want to go for example from one end of the map to the other, you do it roughly with really large squares, and then you use the more accurate method to find a path to the next point along the rough path. As you reach each point on the rough path, you calculate the accurate path to the next point again.
Saturday, 14 June 2008, 13:56
mike_g
For those moments when the player sends 10000 units to go somewhere you could have them all walk mindlessly and queue their path finding requests.

The problem with that scenario is that the units are all moving and will get in one-anothers way. I heard that there are algos better suited for this type of thing than A*. I just dont know their names.

Another alternative, which I think is commonly used, is if you want to go for example from one end of the map to the other, you do it roughly with really large squares, and then you use the more accurate method to find a path to the next point along the rough path. As you reach each point on the rough path, you calculate the accurate path to the next point again.

Yeah, thats another option. It just requires a bit more coding. I look forward to seeing your cobra version
Tuesday, 17 June 2008, 14:10
Paul
"For those moments when the player sends 10000 units to go somewhere you could have them all walk mindlessly and queue their path finding requests."

One way to that could be th handle the units as a group.

And by the way, here is some pathfinding code i wrote a while ago. leeks memory as shit though
If anyone sees anything that might cause it, please tell me

Press 1 to generate a path from a random position to another
Press 2 to keep generating.
The memory usage goes up with every path that is created, and the speed goes down