Pathfinding algorithms?

[Stormy]

What's the general algorithm behind AI pathfinding? At the moment I am moving my pawn and then checking if the path to his goal won't collide in the next frame. If he is going to collide he stops. Then I send him in an arbitrary unblocked direction until he can move towards his goal again.

But this isn't pathfinding. This is bumping into shit until you find a clear path. I want to have this little guy plan his trip before he does it, which means I have to cast rays and check them in a single frame, which is the bit that confuses me. I can't see how this won't turn into a complete monkey shit fight, with rays being cast between every pixel on the screen to check collision.

So what's the basic idea? Do you put logic markers everywhere and have the pawn move between them? Do you assign the ai to an invisible grid so you can limit the places you have to cast rays from? Do you just make a metric fuckload of raycasts from every possible point along the calculated path? This isn't source specific, at the moment I am trying to get my head around it in simple 2d, and later I am going to fiddle with UDK.

[Armageddon]

Most people use A* http://www.policyalmanac.org/games/aStarTutorial.htm

[stoopdapoop]

There's no general algorithm for pathfinding because pathfinding isn't a general problem. The algorithm changes depending on how big your data is (can it all fit in ram? will the worst case take a million years to evalute?), how its laid out (grid? sparse tree? dense tree? nav mesh? are nodes weighted? are edges weighted?, are there even edges?), and what kind of path you want it to return (shortest path? safest path? least expensive path? a path that will deviate slightly to grabs goodies?, A path looks natural but is still efficient?).

What we call "path finding" happens to be a very well studied problem in computer science called graph/tree traversal and if you take a discrete mathematics course then you'll probably cover some of it in detail. We can really use any traversal algorithms on your maps to achieve different goals.

For example, if you have a few points on a map and you want to find the cheapest path that connects all of them, you can use one of the spanning tree algorithms like prims (very simple to implement) or warshall's. You'll have to read about the properties of each algorithm to see if they'll be useful to you or not.

And no matter what algorithm you chose, you're going to want to find ways to accelerate it as distances grow.

Arma is mostly right though. People use A* when their endpoint is known (as in, take me to cell 5,5) and they want the absolute cheapest path (or close to it). People use Dijkstra's algorithm when their endpoint isn't known (as in, find me the shortest path to the nearest healthkit). But dijkstra's can get out of hand very quickly if what it's looking for is distant. How you elect to place the nodes is up to you, if you're on a grid then you're able to take some shortcuts, but you end up wasting a ton of space.

You want to avoid Raycasts during the actual path finding. Though many people use rays once a path is found to shorten it. One way to do this is to check the next nodes in the path to see if they're reachable from the pawns current position, then move directly to the node that's the farthest forward. How often you do this check is up to you. Another way to is to do similar checks from each node, and just remove nodes that aren't needed, this has a constant cost because you only need to do the casts once to get your path from the algorithm

So how is your "map" laid out? is it a grid? how can your unit move, is he constrained to a grid, or can he move freely? If he can move freely then this can complicate things slightly, because the optimum path might require your pawn to squeeze through a crack under a door or something impossible.

I didn't actually look at the pathfinding code in source, so this might be false or have mistakes in it. I'm just making assumptions based on the different debugging and scripting options valve has provided for us. In source they seem solve this problem by creating different graphs for each AI_HULL size, The nodes are placed by the player in hammer and shared between all the graphs. connections are only made if the given hull size can walk from one node to the other without intersections. I've simplified this a little, but that's all you need to know for now. Then at runtime, the AI units query the graph for their own given hull size. As the unit walks, rays are cast forward that only collide with dynamic objects, if it bumps into one, then it raymarches along a ray perpendicular to the unit's path and from the end of that ray, it casts another ray to a point further along on the original path (or maybe to the next node, I don't remember). If the cast yields a hit, then the AI follows the "go around" path that consists of the two new rays. If no go around path is find, then it triggers the "I can't reach target" event, and it gets handled however the AI is scripted to handle it.

The cool thing about these search algorithms is that you can use them for things other than path finding. You can use them to help the AI make decisions by creating a decision tree and "searching" for an optimal path to an endpoint from their current position(s).

If you wanna get real freaky deaky, then you can something else entirely. Maybe create a vector flow field where obstacles "push" objects around themselves. The paths would be very suboptimal, but they'd look cool and the results might make it appear that pawn is relying on his own senses to find a path. (just a thought though, I haven't tried anything like this myself)

Damnit, this post ended up just being a brain dump, but I hope it was useful. Your question was pretty open ended so I'll pretend like that's the reason why my post is so scattered

[Stormy]

Maaaaaaaan thanks for that diatribe of information. Very interesting. I thought this was a very open ended subject, and just needed a jumping off point. My 'map' has a hexagon grid, and I think A* is just right for it. It seems to require large array lists though, to keep all the relevant information. I might try to simplify it a bit based on the map, although my map only has about 50 nodes so it's not a phenomenal amount of data.

I'll post it up if I ever finish it, otherwise it will go into my ever growing jsfiddles folder.

[zombie@computer]

http://www.valvesoftware.com/publicatio ... _booth.pdf

(interesting overview, just flip through if you are interested)

Oh, and for A*, Wikipedia has a pseudocode example. Just rewrite and done. Its quite easy.

[Stormy]

Starting off with a hexagon map was probably a bad idea. And I really only loosely followed A* on this one. I'm moving onto a square grid and following A* as close as I can so I'm abandoning the hex grid for now. Once I get the hang of it on squares I'll go back to hex. Here's the abomination if anyone wants to have a look and critique:

http://www.modelsforthemasses.com/jsfiddles/hexpath/hexpath.html

[Gary]

Haha, the little guy tried getting to his destination by circling the grid constantly. But sadly he never made it.

http://db.tt/do3ZhKqQ

[Stormy]

Dafuq? I can't replicate that.