How to handle pathfinding on a non-grid/non-node terrain map

Question

I'm not sure if this is even path-finding. All I have is a 3D map that has hills, etc. I'd like the enemy to flock an object, but also walk around other objects. These blocking objects may be added after the path is calculated, which would cause a re-calculation of the path.

What algorithm am I looking at here?

Answer 1

You can use a variation on A* pathfinding using an "influence map" technique to vary node-node weights based on whether they go near to bad things or good things (but be careful because A* breaks if your heuristic ever over-estimates). So your heuristic needs to be based on "best case" i.e. the cheapest it can possibly be. In practice it works ok if your heuristic is stupid and you don't have negative-weight edges between adjacent nodes, or any edges between non-adjacent nodes (think teleporters etc).

So for example, if you want your AI characters to avoid climbing hills (because it is more expensive), you make edges which climb hills more expensive.

Or if you have some undesirable entity on the map (say an enemy watch tower or something) then you can make paths which go close to that proportionately more expensive, and have the algorithm automatically find routes which go around it.

Then the only problem is, what happens if conditions change while you're going there. Clearly you could take the "lazy" approach, and just have entities periodically recalculate their paths (although you can get into a loop where Bob tries path A for a while, then it looks a bit bad, and then changes to B, then that looks bad, so he goes back for path A).

Or you could have some threshold, where if the perceived "cost" of a path exceeds estimates by more than a certain amount, you recalculate. Or simply, if your entity hits an unexpected obstacle, he recalcs the path.

But in any case, what you really want to avoid is getting into a situation where large numbers of entities recalculate their paths every tick, which typically leads to a performance disaster.

So perhaps you need to put a minimum time limit on re-calculating a path, so that your entities won't keep repathing all the time.

Anyway, it's a tricky problem, good luck with it, I hope this helps.

---

EDIT: I am now going to try to answer your question.

Your map has no "grid" - but it doesn't matter, you can simply overlay an imaginary one on top of it. Provided you can query the height of a particular spot on the map, and its passability, if your grid has a high enough resolution, you can get a useful path out of it.

You need to be careful about "passability". If you make the grid too low resolution, then you can have a choke point which falls badly on the grid, and an entity of radius R won't notice that he can get through a gap of > 2R , because the way the grid falls on it, it looks like a completely blocked path.