AI Pathfinding Algorithms

Question

I am looking to create a special kind of pathfinding system. At this point, the geometry is still flexible, but this pathfinding is integral to the project.

The goals I have are this:

1. I will have a number of entities seeking paths.
2. Each entity will have a memory of certain paths.
3. The memory will be based on landmarks. Landmarks will be objects or entities on the map that can be or have been seen by the entity.
4. When an entity generates a path, it's only doing it based on what it can see, and what it has memory of. Anything else has to be guessed, it can't use unknown information.

5. The system has to be able to handle a updating paths for a lot of entities at once, but it never has to find the best path, especially not on the first try.

6. It doesn't need to find a path to it's destination in a single frame, just be able to make progress, and reach the target eventually if possible.

7. Entities might be able to share partial or full path information.

I'm thinking this is best served by some modified D* algorithm, but I was wondering if anyone had any other suggestions for something to do this, or challenges that I'd expect to face.

One thing I'm cognizant of for instance is that if I'm using landmarks to confirm the path, that I'll be able to quickly look up nearby landmarks. If I have thousands of landmarks in a list and need to iterate through them and calculate distance to the player this is going to cause trouble. If I'm going to define regions, like a convex hull, I might be able to share that calculation across entities when they need it since I might be able to say anyone inside this poly should be able to see everything within this poly.

Answer 1

At first blush, I'd try to use Hierarchical Pathfinding for what you describe. The main reason why is that it seems that you're talking about Landmarks as the main element that represents the map at a high-level, and that should map well to a hierarchy of two levels.

So you'd have two maps. For the high-level map, each node is a Landmark, and you have a web of connections representing Landmarks contiguous to other Landmarks. This should address your concern with iterating through a list of Landmarks, although you'll probably still require some kind of spatial structure to find the Landmark closest to your start point and your destination. A simple, coarse, grid might work well, or you could build a tree structure, like a KD-Tree, or a Quadtree.

The low-level map would contain the actual geometry and navigation information. It would be grouped by Landmark. The way to divide the geometry will depend on what you end up using. If you use navigation meshes, you could literally cut out areas around a Landmark and have the polygons follow the borders. If you use a grid, then you could have a mask for what squares are linked to each Landmark.

As the characters learn about new Landmarks, you'd allow them to use those Landmarks in the high-level pathfinding (they'd become "unblocked"). The low-level pathfinding only needs to be done as a character prepares to enter the area around a new Landmark, and we only need to calculate how to get to the next area, which should be fast.

If you want to share paths, you could cache paths per Landmark, to go from one of the neighboring Landmarks to another.

The main sticking point with Hierarchical Pathfinding (especially compared to a general algorithm like D*) is that because you're not doing a global search, it's possible that the path might look a bit unnatural. Think of a path using navigation meshes without the optimization step. You can solve that by carefully designing the areas that will be attached to Landmarks, and using tricks like looking ahead one Landmark (which is pretty effective).