0
\$\begingroup\$

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).

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thanks for the comment! However, what I'm most worried about is how to handle multiple creatures trying to enter the same tile. Let's say 3 creatures all want to enter the same tile, do I just let one of them enter and the other 2 stay stationary? But if I do that, your third step above suggests that I change the status of each creatures current tile to free, but the status of those two creatures' tiles shouldn't be free because they weren't able to move out. \$\endgroup\$ – OMGitzMidgar Sep 18 '16 at 15:03
  • \$\begingroup\$ But then let's say there are 4 more creatures trying to enter the same tile that one of those 2 previous creatures had to stay stationary in, then none of those 4 creatures can move? And then there's this chain effect of a large portion of the creatures not moving at all. I'm looking for some material or suggestions on how to handle n-body collisions in this grid world. \$\endgroup\$ – OMGitzMidgar Sep 18 '16 at 15:05
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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