# Cell based game and collisions in discrete space

This topic is 1071 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi.

I am wondering about this. I was not satisfied with my previous system for doing this, which seemed kind of ugly or limited, and I was wondering what would be the most efficient and elegant solution.

What I have is a cell-based, turn-based game with a discrete game world, that is, it's a raster of tiles, not a space with (approximately) continuous (floating point) coordinates, with each object in one time. And I was wondering how you deal with collisions. In particular, each object can move but it can, obviously, only move from tile to tile, never be in between two tiles.

This means that when we get collisions, we have a number of cases to consider, and I'd preferably like something better than a casewise approach. Moving one cell at a time, we could have, e.g. that two objects move at each other, their coordinates would change by 1 cell each in opposing directions, causing them to swap places if they were right next to each other. They'd go through each other, so that should be a collision. Another way a collision can occur is that two objects try to rush each other for the same cell. A situation that might look like it would be a collision, but isn't, is two objects moving in the same direction, in the same line, one just behind the other. If you look at only the one in behind, one could think it will collide with the one ahead unless you also look to see which way that is moving, which adds more complicated, tricky programming to make it work on a computer. Things are further complicated by that some objects may move different velocities, crossing multiple squares in a turn (like a shot arrow).

Almost all the collision-handling stuff I've seen deals with continuous space and (approximate) continuous time, e.g. checking overlap, etc. and so does not seem obvious how to apply to a discrete space and maybe also discrete time.

One way I thought to handle it would be to just use a continuous simulation space which is "rounded" to discrete, but then we get a computationally-intensive simulation, as it seems that given the discrete character of the world space, we should be able to simplify/optimize things considerably.

What do you do?

##### Share on other sites
Simple.
Make one pass to mark objects that want to move as no longer being on the space where they are (calling them “hovering”).
This leaves the space open and others can move into it.

The only problem is that a piece that is hovering may not be able to go where it wants to go, yet can’t land back on its square because it has been stolen.
This is easy to solve, though it involves a small amount of recursion.

When a piece wants to move to a square, if the square is empty (and all other rules obeyed), FinalizeMove(ThatPiece) (remove hovering flag, piece is finalized on the new square, is done processing for that frame, cannot be looked up by the following routines).
If the square, however, has a piece hovering over it, recursively evaluate the piece that is hovering. You terminate the recursion when a piece can move to a square or when you reach any of the pieces that are currently being checked in this recursive call.
This means the pieces rely on each other, and all moves they are trying to make are valid. In this case FinalizeMove() on each piece in the recursive call.
In other words, if any fail, don’t move any of the pieces.
If they all pass, move them all.

L. Spiro

##### Share on other sites

Simple.
Make one pass to mark objects that want to move as no longer being on the space where they are (calling them “hovering”).
This leaves the space open and others can move into it.

The only problem is that a piece that is hovering may not be able to go where it wants to go, yet can’t land back on its square because it has been stolen.
This is easy to solve, though it involves a small amount of recursion.

When a piece wants to move to a square, if the square is empty (and all other rules obeyed), FinalizeMove(ThatPiece) (remove hovering flag, piece is finalized on the new square, is done processing for that frame, cannot be looked up by the following routines).
If the square, however, has a piece hovering over it, recursively evaluate the piece that is hovering. You terminate the recursion when a piece can move to a square or when you reach any of the pieces that are currently being checked in this recursive call.
This means the pieces rely on each other, and all moves they are trying to make are valid. In this case FinalizeMove() on each piece in the recursive call.
In other words, if any fail, don’t move any of the pieces.
If they all pass, move them all.

L. Spiro

Thanks -- a nice "KISS" method for doing this. I had tried something similar, I believe, but did not use the flag grid, which seems better.

1. 1
2. 2
3. 3
Rutin
24
4. 4
5. 5
khawk
14

• 11
• 11
• 23
• 10
• 9
• ### Forum Statistics

• Total Topics
633651
• Total Posts
3013128
×