Skip to main content
gamedev.net
🔒 Locked

Multi Agent Pathfinding.

Started by Ultimape Jan 15, 2007 at 6:01 PM 10 replies 3.3k views
Original Post
Ultimape
Ultimape
I've been working on making my little simulation program a little more interactive, but I've come into some pretty peculiar logic problems having to do with unit movement. its a simple 2-d tile based game with "ants" and "doodlebugs", creating a sort of predator-prey simulation of population control, eventually I hope to make a sort of african sahvana simulation (Antelopes and (ant)Lions, etc) Right now, they just move in random directions, but I wanted to create a way for them to make more intelegent moves, as I am also going to be adding in rivers, mountain cliffs, and trees for them to avoid, and it would be stupid for a bunch of doodlebugs to die out simply because they couldn't find the land bridge to the grazing fields, etc. The problem I'm running into, is how to manage the movements of multiple entities at the same time. The current scenario is that i am iterating over the entire array and having each animal move, and then having the next one take into account that movement. But this creates some weird artifacts where they all kinda move diagonally because they are conflicting with each other in the order their moves are being called. It dosen't happen all the time, but i'd still like it to be a more realistic simulation, not restrained by certain little ai bugs (pun intended). The code is for high level movement on the tile grid and decision making/pathfinding, so I don't really want to implement steering behaviors or influence mapping until later on when I expand each tile down to a micro-simulation. Can you point me to some resources or have any ideas as to a better way to manage unit movement ordering? Also, any ideas on how to make units "predict" other units movement paths? I'm hopeing that some simple logic would create a sort of "pack" movement due to them predicting where all the others are going. I'd be neat to have the ants scatter in all directions away from the antlion.
KulSeran
KulSeran
you should have a "before" and "after" step. When you move each unit, it should update the "after" info from "before" info.
Then you make the "after" part the "before" of the next step. This way you dont have those artifacts from
move order. Everything happens at once, instead of one entity at a time.


the other question is twards "flocking" behaviours. they act like springs to all the units. where each unit
springy-ly drifts from a min to max dist from each other entity in the flock.
Ultimape
Ultimape
What about if two decide to move into the same area in the after?
KulSeran
KulSeran
You could put them both on the square, then do a post step where you push all overlaping entities onto a random ajacent
spot.
IADaveMark
IADaveMark
I would definately have to put in my vote for the flocking behaviors. However, the flock will need to have general direction ideas such as the land bridge you talked about. One idea is to have a hidden "leader" agent. The "cohesion" factor in the flocking behavior would be stronger to the leader agent. You pathfind or steer the leader and the pack tends to follow. However, if a herd gets attacked by a predator, the "flee" function should be such that there is the possibility that the herd splits somewhat if they are threatened closely. There's all sorts of different effects you can get by changing the weights in the flocking behaviors. (Flocking is well documented around here)
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit<
Ultimape
Ultimape
looking into flocking behavior, its essentially a form of steering, and isn't exactly what I want. Although it is more "organic" in form, that level of control would be for "sub cells". I need ideas on how to manage collision gracefully when directing units on a per-tile basis for the macro simulation. Units can only be on one tile at a time in the macro sim.

if unitA wants to move to the same tile at the same time as unitB, what is a good way to decide "who goes first", or should they take another approach like just to ignore that tile altogether. If one unit has to change direction, it often causes a sort of chain reaction, leading all previously moved units to be moved differently.

Artifacts arise because although each unit is supposed to be moving at the same time, they are processed in sequence. These artifacts are what I want to avoid.
Vorpy
Vorpy
Your movement issues have a very "unnatural" character for what appears to be a sort of naturalistic simulation. How are the entities deciding where they want to move? Entirely preplanned courses will probably never appear as natural as letting the entities wander around a bit. A valid solution for your problem could be to have the entities bump into each other. Their individual responses would depend on the type and state of the entity. Two ants bumping into each other might stop to think for a random amount of time, maybe even replotting their courses. Or maybe one just pushes the other away. Using a tile grid where only one entity can be on a grid cell at a time could even be limiting the possible solutions in undesirable ways.
Kylotan
Kylotan
The diagonal movement thing sounds like there are too few tiles per animal, so there's literally nowhere else to go. If so, you obviously can't solve that without a change in the design.

But as for prioritising entry to certain tiles, deciding who goes first shouldn't be too hard. The person furthest from their destination should go first, as if the person nearest goes first, they're going to stop once they get there and possibly block the others. If that distance is equal, just use some arbitrary tie-breaker that remains constant for any 2 animals.

As for communicating this, here's one naive method that may work.

Each update: - For each animal with a current path:   - determine next tile to enter   - if tile is not reserved for another animal OR we take priority over that animal:    - reserve that tile in our name, overwriting any previous reservation   - else:     - do nothing - For each reservation:   - Move the animal that reserved it to that tile - Clear reservation list
Ultimape
Ultimape
Quote:
Original post by Vorpy
Your movement issues have a very "unnatural" character for what appears to be a sort of naturalistic simulation. How are the entities deciding where they want to move? Entirely preplanned courses will probably never appear as natural as letting the entities wander around a bit. A valid solution for your problem could be to have the entities bump into each other. Their individual responses would depend on the type and state of the entity. Two ants bumping into each other might stop to think for a random amount of time, maybe even replotting their courses. Or maybe one just pushes the other away. Using a tile grid where only one entity can be on a grid cell at a time could even be limiting the possible solutions in undesirable ways.


Yes, it is very limiting. That is basically how i am doing it though, "pushing the other away"... but the problem lies in that each creature is logically moving at the same time, but the updates are run in sequence of creature order. Depending on the order, a sort of domino artifact happens where one creature pushes another creature which pushes another creature... causing weird patterns stemming from the upper left corner. Perhaps some sort of back-progagation needs to be run, re-calculating all creatures affected with the new position.



Quote:
Original post by Kylotan
But as for prioritising entry to certain tiles, deciding who goes first shouldn't be too hard. The person furthest from their destination should go first, as if the person nearest goes first, they're going to stop once they get there and possibly block the others. If that distance is equal, just use some arbitrary tie-breaker that remains constant for any 2 animals.


Hmm, yes, a priority Que, that makes sense. The problem is then that I have my priority based on the set order in the grid, where i should be doing it based on some other heuristic. I could work with that to cause a lot of neat things, like larger/faster animals needing/reservering more room to stop/turn, so they reserve tiles in a different manner. Dumber animals, would only look a few tiles ahead (and potentially getting trampled), whereas smarter ones might even look at surrounding tiles to perceive potential predators.
Sneftel
Sneftel
In the academic arena, there's been surprisingly little work on multiagent cooperative pathfinding. One gem, though, is this paper, which uses a "reservation table" to coordinate paths. Check it out.
Palidine
Palidine
[EDIT: gratz me for posting what I think is a new idea to the thread when in fact it's just a poor summary of the paper that Sneftel posted... =( ]

another (more complicated approach) I saw outlined goes something like this:

represent your tile map with 3D cells. 2 of the dimensions is the normal tile map. the 3rd dimension is time. let's path 2 agents

path agent 1 -> success
as you pathfind him, you push cells onto that 3rd dimension noting when agent A will occupy the cell

path agent 2:
now instead of just pathfinding through the 2D tile map, you're looking at the 3D representation. When you look at a cell you know at what time you will occupy it. look to see if someone else is planning on occupying it at that time -> if they are the it's an invalid tile for pathfinding.

I didn't see an actual implementation but that's the basic gist. you essentially push and pop stuff off of the A* search lists based on the time you'd occupy that tile.

With a lot of agents this can get quite expensive and i'm sure there are bad edge cases. you'd likely have to re-attempt pathfinding multiple times if several agents are already pathing. I don't remember what game it was that used this approach...

-me
Sneftel
Sneftel
Quote:
Original post by Palidine
[EDIT: gratz me for posting what I think is a new idea to the thread when in fact it's just a poor summary of the paper that Sneftel posted... =( ]

Ahhh... but you, unlike me, thought of it without having to read the paper. [smile]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.