next »

[dspencer]

Hi guys!

I'm trying to do a game with a bunch of enemies that all use pathfinding and i'm not sure how to do it. At all. In fact, I have no idea where to start! Can anyone give me suggestions of literature or an idea of an algorithm I might use? I'm using A* for my static pathfinding as is, unsurprisingly.

Ok, I lied, I had one idea - Just use static pathfinding, and allow enemies to push one another around a little bit. Enemies would need to confirm and potentially recalculate their paths at every collision, though, so this might not be optimal...

Anyway, any help would be great! 

Thanks so much!

[ThemsAllTook]

Depending on how many enemies you're dealing with, a flocking algorithm may be applicable.

[dspencer]

Well, the thing is I want to have scripted enemy behavior. So the entities wouldn't all be going toward the same location, or be acting in the same way; so I think that would make a flocking algorithm not really applicable.

(I don't know too much about them, though, so correct me if I'm wrong!)

[Zaphos]

Hmm ... if they have really different goals, and there are tight passages to navigate, you may need to worry about annoying deadlock-style problems; like if two enemies are on opposite sides of a narrow hall and both want to traverse it, they need to decide which goes first and make the other wait for it.  If they all had roughly the same goal (like, get to the player) then simpler things (like your first idea, probably) will probably do something reasonable ...

edit: you can also try to still have different goals and avoid deadlock just by not scripting situations where deadlock would occur -- depending on the flexibility you need in your scripting, this may or may not be reasonable ...

[Sam]

Need more information please!

Particularly:
Are the agents always pathfinding to the same location as one-another (does that location change over time)?
Do agents have significant differences in how they move?
Do the agents collide with one-another?  If not, do you want to avoid them huddling up?
If they do collide, is the "two agents going down a very narrow corridor" situation liable to happen in your game?

If the agents share a common moving goal, I have had a positive experience performing the pathfinding in a shared space.  I generated a heat map such that hotter areas are nearer the target (taking into account the movement constraints of the level geometry.)  That is done just once, then each agent will just examine their local area of the heat map and simply move in whatever direction gives the greatest heat rise.  For a single agent, it's the world's least efficient pathfinding algorithm but it shows significant performance gains once you have large numbers of agents.  Some variety in agent movement can be produced by changing how they respond to the heat map.

I've some words and pictures about this from when I was implementing it.  I think I call it a height map in that, just to be inconsistent.

[shrimp]

Heh oops, didn't see this thread - I just posted a massive braindump on a similar subject in another thread:

http://forums.tigsource.com/index.php?topic=11286.msg345918#msg345918

Not exactly the same topic, but there's a big overlap. I totally agree with Zaphos and Salt's points. Great tutorial/write-up Mr Salt 
I tend to get too attached to stuff that I know, like A*, boids, and don't experiment enough with other stuff like the heightmap system.