Looking for detailed pathfinding examples

Question

I am currently working on a 2D-TopDown game. Now I was looking for pathfinding algorithms. I read and understood A* and Dijkstra. But there are still some questions I have. So I am looking for examples which cover the following topics when it comes to pathfinding:

1. Collision (Pathfinding should consider obstacles)
2. How are those algorithms implemented properly in game's AI? I mean do I have to calculate all possible paths? That could be an performance issue?!
3. I am not using tiles on my maps so how do I get the single nodes for a wighted graph (Dijkstra)?

I would be very pleased if somebody could point me in the right direction.

Thanks in advance!

Answer 1

I don't have any example in mind at the moment, but I'll try clearing your doubts.

Pathfinding algorithms work on graph structures (connection of nodes). A grid is an example of a graph, but it's not the only graph structure available for pathfinding. Basically, any kind of "set of nodes" will do.

If you don't have a tiled map, don't worry, you can still have nodes where you desire. A common thing to do is create a navigation mesh (nav mesh), a human-designed or procedurally-generated graph that places nodes in parts of your map you can walk into.

The above picture is a navigation mesh from World of Warcraft. The green nodes are used for pathfinding, and the polygons created by connecting those nodes sample the walkable space. This should clarify questions 1 and 3.

Another common practice is creating many grids on top of your current level architecture, every one more precise than the previous one, in order to speed up pathfinding.

Performance can be an issue, but you can be smart about it. If you don't need every single actor to find its own path, you could use influence maps or breadth-first search to crate a global map the actors will follow.

Check this video out: http://www.youtube.com/watch?v=DusL7kXSJlc

The goal (in this case the player), generates an influence map around him, and what the enemies do is simply move from areas with less influence to areas with more influence, no pathfinding involved on their part. You can generate multiple influence maps if you have more goals (for example, more "factions" battling each other in a RTS).

Pathfinding is a complex subject, but there are many resources you can find by googling. Let me know if you still have doubts.

Answer 2

Collision happens during graph traversal, "can I move from this node to the next?" is a collision check. Or in algorithm space, the cost to move from this node to the next is temporarily infinite if it is blocked.

You are using weighted nodes with costs associated with moving from one node to the next, right? Proper weighting fixes all sorts of stupid looking pathing =)

You never calculate all possible paths, you only need one best path, that's what all the methods you mention do. If you are working with multiple units then you either weight against spots already on a used path for subsequent queries or use some sort of flocking behavior to move the group along the one path.

If you don't have "tiles" then you must generate them yourself from the geometry of your levels. Please note that A* is not restricted to working on a square grid, many people make this mistake.

If you are using some kind of 3D geometry I have used this method successfully before: find all the faces that are within 45deg of flat (i.e. no walking up walls); then build the weighted graph from center-points of these faces based on adjacency. A standard depth first search will get your path.

Answer 3

A* and Dijkstra are quite a bit slow when you use it for a huge amount of units at the same time. You could use some simpler algorithms as robust trace and improve their found solution. The solutions from robust trace (which in a simple ways finds a way around obstacles) can be improved by checking at each position of the found path if it can walk the direct line of sight to any later position on the path. You should also improve robust trace by comparing the way "left" and "right" around an obstacle and take the shorter path. The algorithm with these optimizations should always find a way to a target (if it exists), even in a complex maze. The difference of the found solution compared to the optimal path is negligible in most cases.

You can reduce your collision problems by calculating the paths one by one by a global path planner, which keeps track of which position on the map is already planed to be blocked at a certain point in time. The unit will then either need to walk around the other unit or wait a bit, till it moved on. While this can cause performance issues, you can stick to a simple algorithm, that just plans a static route using the currently blocked fields on the map. While executing the plan a unit will eventually see it's planned path blocked. In such a case, let the unit execute its planned route for some more time (if possible) and observe if this special point on the map is still blocked. If it gets "unblocked", continue ... if does not get "unblocked" for a continuous time span (of e.g. for 3 seconds) the unit should plan a new route.

These algorithms will be have a well performance even on slow computers. I implemented them about 10 years ago on a PDA using a V30MZ processor (33MHz, 16-bit) to route about 200 units of a real-time strategy game. It worked very fluently ...