Hey all, This problem is going to be difficult to articulate, so please be patient. :) I have a grid, let's say 5x5 for convenience sake, that has units moving across it in a linear path. When two or more units are going to share the same square, I'd like one unit to move, then the other, alternating directions. Think of it like an intersection on a street with stop signs. When four cars pull up, one goes, then another, then another, etc. I'm having trouble getting these intersections to be asynchronous, though. I loop through the intersections, pulling units into them. But the order that I loop through dictates what units end up moving. If three units are lined up next to each other, only the unit furthest down gets to move because the other intersections have already determined that the path is blocked. For example (o = open space, e = heading east): eeeo -> eeoe -> eoee -> oeee This happens because I'm looping left to right and the first two checks determine that the spot to the right is blocked, then the third check determines that it's safe to move. But had the first two known that the third was going to move, they all could of moved. I can't just add these special cases though because objects are going to be heading in all directions and each intersection needs to alternate where it pulls units from. For example (o = open space, e = heading east, n = heading north): eeo -> ene ono -> ooo That's my ideal resolution of this collision. Assuming you still understand what I'm babbling about, does anyone have any ideas how I can make each intersection seemingly operate independently of each other? Thanks.

I think you'll also need to incorporate some notion of movement or velocity into your algorithm, instead of just position. Going back to the car analogy, you determine how fast to drive based not only on how far in front of you the next car is, but also how fast they are driving. If your speed was based only on distance between vehicles, then traffic patterns would basically look like a giant spring :P

"Asynchronous" is probably not the right word to use in this case. "Order of operations" is.

Anyway, I think one approach to solve the problem with multiple cars moving in the same direction would to have a second grid which stores the "desired location next frame":

1. Clear the 'next' grid (do not start with the current state)

current: 1 2 3 _next:    _ _ _ _

2. For each entity that wants to move, update the 'next' grid with the location where it wants to move. If there are any collisions when attempting to write to the 'next' grid handle it at this point.

current: 1 2 3 _next:    _ 1 _ _  (after moving unit 1)next:    _ 1 2 _  (after moving unit 2)next:    _ 1 2 3  (after moving unit 3)It will also work the same if the iteration order is different:current: 3 1 2 _next:    _ _ 1 _next:    _ _ 1 2next:    _ 3 1 2 

3. Assuming you didn't run into any conflicts, you can now update all of the entities. If you run into a conflict, you could just force the car to stay in its current location.

current = next;

For the multi-directional resolution, you should have the intersection choose the car to move based on the car currently in the intersection. If an 'e' is in the intersection, move a 'n' if possible, otherwise move the next 'e'. After all intersections have tested this case, update all other cars that were not moved by an intersection.

i can think of maybe 3 ways to deal with this:

1) Don't move units by running though a loop. Go through the unit list and find potential movement conflicts first, then go back through and do the actual moving.

2) Assign units an "initiative" rating. Units with higher initiative move first. So you could then go through the unit list sorted by initiative. (this might also have interesting strategic elements to it)

3) Move in floating point units. This was an interesting solution to a problem that someone else devised. Instead of moving "2 square", have the unit move "2.23 squares" and another move "2.16 squares" (depending on some kind of speed variable or whatever you come up with). Now of course it always rounds down to 2.0 and you can never actual move a fraction of a square, but the extra fraction determines "who gets there first" and gets rid of the chance that multiple units will hit the same square at the same speed at the same time.

Another approach that might be easier is, instead of moving cars, move the gaps. If there are no gaps, then nobody can move (gridlock). For instance, if the car currently in the intersection cannot leave, nobody can enter.

To make it 'fair' at intersections, you might want to tack on some extra data for each car - a value that stores how many updates the car has been forced to stay in the same location. Then just pick the car with the highest wait value when deciding who to allow into the intersection. To implement a 'move the gaps' algorithm, cars will need to store their 'have I been moved yet?' variable anyway. Just change that to 'how many updates has it been since I've moved' instead. Moved cars will have this value set to 0 so you know not to try to move them.

If you want to implement "right of way" at intersections where two or more cars tie for the highest 'waited' time, then you should be able to do that, too.

Make the grid tiles capable of temporarily holding multiple units. Optimistically move everything forward, and then find squares with collisions, undo the movements of whatever is found there, and recursively check the squares that the objects move back to. (Objects which were stationary before, or have already had their movement undone, do not get pushed back in this process.)

if this is a turn-based game, you might also get away with this looks-good-but-don't-tell-anyone-how-it-works solution:

just randomize the unit list every turn ;-)

units = array of units;while ( gameloop not done ) {   units = randomize( units );   foreach ( units ) { unit->Move(); }   }