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:
- I will have a number of entities seeking paths.
- Each entity will have a memory of certain paths.
- 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.
- 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.
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.
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.
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.