Jump to content
  • Advertisement
Sign in to follow this  
mike3

Cell based game and collisions in discrete space

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!