Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
I'm pretty sure you would need to generate nodes. –  The Communist Duck Dec 23 '10 at 17:37
    
Can this be generated automatically? –  Shawn Mclean Dec 23 '10 at 17:46
    
I think so. Or at least, a lot of procedural stuff wouldn't be able to do it any other way. –  The Communist Duck Dec 23 '10 at 19:10
add comment

2 Answers

up vote 4 down vote accepted

Consider navigation meshes. There is a good overview article here:

http://www.ai-blog.net/archives/000152.html

share|improve this answer
add comment

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.

share|improve this answer
    
Thanks. I'm going to try navigation meshes along with checking out recast library –  Shawn Mclean Dec 23 '10 at 23:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.