Collision handling for grid based games and simulations

Question

I'm trying to implement a grid based game where there are many creatures moving in the grid from square to square. I'm having a hard time handling collision with creatures in the grid (multiple creatures trying to move into the same square or cell). Where can I find information on how I should handle a game (or simulation) where multiple creatures in a grid want to move into the same cell but aren't allowed to? It's easy to handle 2 creatures, but handling n object collision is tough.

I'm looking for info on how to handle collision in a grid world. I don't expect a specific answer as much as resources or suggestions to find more info.

EDIT: To clarify, I'm looking for info on HOW TO HANDLE COLLISIONS BETWEEN MULTIPLE OBJECTS IN A GRID. In a grid world where multiple objects want to move into the same cell at the same time, how do I resolve this? Does one object get to move into the cell and the other objects remain stationary? Do I make each object push the other object out of its cell? These are the questions I want to answer.

An example of the problem I'm looking to answer: Consider a grid where there's 3 creatures who move from tile to tile. What do I do when two creatures, A and B, try moving into the same tile? Let's consider if I allow creature A to move into the tile but creature B remains stationary. What happens if a different creature C wanted to move into the tile that creature B was stuck in? Then creature C also wouldn't be able to move.

This would cause an issue if I would evaluate creature C's movement first, telling it that he can move into the tile that creature B is in (because creature B plans to move out) but then creature B ends up never moving out.

How do I determine which creatures to evaluate first? Also, how do I avoid this huge chain of creatures being forced to remain stationary (in this example, only 1/3 creatures were able to move).

Answer 1

Hard to say without knowing how movement is programmed. If your "simulation" is turn based you should be able to change the status of any tile. When the creature(s) move then have the creatures A.I query the status of what ever tile it wants to move to. It it's free the creature moved and changes the status of the tile it just left and the tile it just moved to. If It's not turn based the same method can be applied but it has to be separated out int it's component steps and done all together (I hate working with stacks!);

1: Query every creature and load their infomration into a stack

2: Query the tile each creature is standing on...into a stack

3: Change that status of each creatures current tile to free

4: Run each individual creatures movement A.I and update the new tiles

5: Move the creatures in the stack to their new tiles

Answer 2

If every entity in your game has a uniform movement speed or "initiative" ranking, then you don't want to give any particular entity priority over the others when a conflict is detected.

A really straight forward way to do this might be to do something like the following psuedocode:

// Loop over every entity and update their tile information, then move them
for (entity in entities) {
  entity.lastTile    = entity.currentTile
  entity.currentTile = entity.desiredTile
}

recheck:
collisionFlag = false

// Loop back over the entities and check for collisions with other entities
for (entity in entities) {
  // If this entity hasn't moved we can skip it
  if (entity.currentTile == entity.lastTile) continue

  for (other in entities) {
    if (entity.currentTile = other.currentTile) {
      // When a collision is detected, revert both entities' movement
      entity.currentTile = entity.lastTile
      other.currentTile  = other.lastTile
      // and flag for recheck
      collisionFlag = true
    }
  }
}

// Check the entities again if there was a collision to handle cascades
if (collisionFlag) goto recheck

If your entities have different speeds or "initiatives" then you might want to instead have them stay where they moved where slower creatures are returned to their previous tile.

Most implementations you'll find will simply employ a series of movement rules that determine when and where you can move and don't care too much about perfect movement resolution.