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

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?

• I'm pretty sure you would need to generate nodes. Commented Dec 23, 2010 at 17:37
• Can this be generated automatically? Commented Dec 23, 2010 at 17:46
• I think so. Or at least, a lot of procedural stuff wouldn't be able to do it any other way. Commented Dec 23, 2010 at 19:10

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.