Sign in to follow this  

Where collision detection belongs in a 2D tile-based game engine

This topic is 2490 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

I've got a very simple 2D game engine brewing and I've got my really simple game loop like such set up (pseudo code)

[code]
void gameLoop() {
// Calculate timing delta since last loop
makeGameControllerUpdateCurrentSceneWithDelta(delta);
render();
}
[/code]


Then, my function for updating the current scene (level), updates the positions of Entities (characters, either Human or Computer).
This game is really simple right now. The screen is fixed (and will remain that way, so all Entities are generally on screen at once) and also right now there is just one Human player, but I'm trying to design it with the eventual goal of having other players (networked… I'll cross that bridge later, I just want my engine to not make assumptions about how many Entities are Human).

[code]
void makeGameControllerUpdateCurrentSceneWithDelta(float delta) {
// Assume the scene is not paused; ie it's running. I do checks in my actual code

// I first call a function to update all the entities in the scene. This loops through each of them and calls their respective "updateWithDelta(float)"
updateAllEntitiesWithDelta(delta);

// other things

// should collision detection go here?
checkCollisionForAllEntitiesWithDelta(delta);
}
[/code]


My question is kind of in the code. Should my collision detection happen in the scene's update function, OR should it be part of each entity's updateWithDelta() call (ie, should each entity call the checking…. I'm thinking NO, because then it would have to know about all other entities, right? Seems like a bad design, but maybe I'm wrong).

Also, my checkCollisionForAllEntities() should be checking every single entity against EVERY other entity of the scene, right? When I do the check (let's assume just really simple rectangle intersection for now), and they do collide, then should I be calling some function on both entities of the collision? Like

[code]
if (rectIntersection(entityARect, entityBRect)) {
entityA.collidedWithEntity(entityB);
entityB.collidedWithEntity(entityA);
// Or would just one of these be sufficient?
}
[/code]

I think that's all I've got at this point, just trying to better my understanding of how to design this properly. Thanks in advance for any help!

Share this post


Link to post
Share on other sites
Separating it out like that ensures everything is in its final position when you check for intersection. If you did it inside the object update, some objects would be at their old locations and some at their new ones.

You want your program flow to work something like this, with the result from each stage cascading into the next.

[list=1][*]Input - collect player input[*]Control - update player and AI logic[*]Movement - move all objects to their desired locations[*]Collision - check for and resolve overlap[*]Render - render objects in your game world[*]Overlay - render interface elements[/list]
When using a physics library like Box2D or Chipmunk, movement works a bit differently since your applies forces or impulses to objects instead of moving them directly. The physics world then updates object velocities and positions, reporting and resolving any collisions along the way. After all that is complete, everything is in its final location for that simulation step.

By the way, you can avoid testing every pair of objects by using a broadphase test: [url="http://en.wikipedia.org/wiki/Bounding_volume_hierarchy"]bounding volume hierarchy[/url] (what Box2D uses), [url="http://en.wikipedia.org/wiki/Sweep_and_prune"]sweep-and-prune[/url] (what Box2D used to use), [url="http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/"]spatial hash[/url] (what Chipmunk uses), or--if your world is relatively small--a simple 2D grid. If your game doesn't have many objects, you can safely skip that.

Share this post


Link to post
Share on other sites
Excellent. This helps quite a bit. So I have a few followup questions too:

1. My game is a platformer, so the player can jump and land on platforms (not implemented yet) or also land on another player which will cause damage (also not implemented). My jumping/falling code happens in the "Movement" (step 3 of your list) stage and part of that method is the Entity object that is falling, asks the Game Scene for the highest possible Y value it can land on (right now I'm just making it return the floor height, so no platforming, but ideally it will be reading in my tile map and looking for which platforms it can collide with, eventually). So in my falling code, how would I detect if jumpingPlayer is going to land on enemyPlayer? Wouldn't this be repeating my collision detection?

OR should I do the updating, movement, etc. then do collision detection, and store away an "impending landing on an entity at position x, y"?

2. Also, more generally, when I do my collision detection, right now it's just a simple rectangle intersection, which is fine, but if I want to add more fine-grained detection INSIDE the rect intersection, should that be determined by the entity objects themselves? For example, if the collision happens, if they hit each other just on the sides then that's OK but if one entity was on top of another, then I'd want to do my "damage". Where would this belong?

[code]
if (rectIntersection(entityARect, entityBRect)) {
// do a further check to see if A was on TOP of B; or if B was on TOP of A?
// OR, should I just do something like:
// entityA.checkIfLandedOn(entityB); ?
}
[/code]


Thanks again for the help!



Share this post


Link to post
Share on other sites
[quote]how would I detect if jumpingPlayer is going to land on enemyPlayer?[/quote]
When their collision objects collide. Is there a reason you need to know about a collision before it occurs? EDIT: If you're anticipating something like the enemy trying to avoid being landed on, or looking up to see the player, you can include in the Input phase a routine to determine "Who sees who." That can be done by a routine in the physics engine that returns information about how far apart collision objects are, and the angles between them. I have a ray casting routine in my physics engine to do just that. With the information generated, you can check the "viewing cones" of each player to determine if the entity should be given the info. If an enemy is looking forward, he shouldn't see objects approaching from behind - that sort of thing.

With regard to collision detection, I would suggest you have a physics "engine" that does it all - it need not know about entities themselves, just the collision objects (rectangles, circles, etc.). Each of those collision objects will have some sort of information (maybe no more complex than a number) to pass back with the collision info.

Damage will result when an entity receives collision information - "A heavy object just hit you from above with such-and-such velocity, etc."

EDIT: In general, the physics engine need not and shouldn't "know" about entities, and entities need not and shouldn't know about collision objects. Obviously, there will have to be an interface that knows about both but that general approach will prevent undo complications with entities communicating with the physics engine, etc.

Share this post


Link to post
Share on other sites
I'm also bumping in to similiar issues.
[quote name='Buckeye' timestamp='1298070841' post='4776125']
[color="#1C2837"][size="2"]With regard to collision detection, I would suggest you have a physics "engine" that does it all - it need not know about entities themselves, just the collision objects (rectangles, circles, etc.). Each of those collision objects will have some sort of information (maybe no more complex than a number) to pass back with the collision info.[/size][/color]
[/quote]

So you suggest that each entity has a collision object, and then that object gets passed to the physic engine with parameters like weigth, speed, direction etc? The collision object in the entity gotta be a pointer right, so the engine can change to values directly?

Also I came up to this design solution for the engine:

[code]
Level has a ObjectManager // contains a list of all objects
ObjectManager has a CollisionManager // contains a list of collisions that occured
CollisionManager has a PhysicsManager // handles the collision in the collisionList in CollisionManager
[/code]

I didn't intend to steal this thread, just thought those questions fitted well here and the answer to them might help jbrennan as well ;)

EDIT:
I red through my previous post where you helped me Buckeye,

[quote]
[color="#1C2837"][size="2"]When a player/object is created, it tells the interface what collision objects* are needed (spheres, cylinders, etc.) which the interface then adds to the collision system. Those collision objects will have some sort of identifier. The collision system then generates a list of collision information for the collision objects and provides a list of collision information to the interface. That information includes the identifiers for the collision objects so the interface can provide appropriate update information back to the player/objects. Collision "objects" may include, in addition to the collision objects for the entities themselves, projectiles, laser sighting rays, explosion volumes, etc.[/size][/color]
[/quote]

Instead of a identifier isn't it a option to have the collision object as a pointer inside the entity like I mentioned above?

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298070841' post='4776125']
When their collision objects collide. Is there a reason you need to know about a collision before it occurs?
[/quote]

Nope, I think I might have just worded my question the wrong way (or wasn't thinking straight). I just wanted to make sure that as my player is falling, if he happens to land on another player that I can control what happens. What ideally would happen would be "landed on enemy, enemy damages/dies/whatever, then fallingPlayer should I guess bounce a bit or otherwise change to movement to indicate a hit has happened".

So I guess I was just confused of the order, but it should be

1. get input
2. move each entity one by one according to input
3. check for collision with other entities. When a collision happens from a jump, tell "fallingPlayer" that he hit an enemy on the head, and he should bounce up (or whatever) on the next frame through. In this step, if a "hit on the head" occurs, this is where I would say something like [code] enemyPlayer.wasHitOnHeadByEntity(fallingEntity); [/code] yeah?
4. render everything

I'm trying to avoid using a physics engine at this point because I just want to do something very simple for now with really basic physics (mostly as a learning experiment, without getting bogged down by a premade physics engine). But if I were, then @simpler's comment sounds logical.

Share this post


Link to post
Share on other sites
[quote name='jbrennan' timestamp='1298073840' post='4776152']
[quote name='Buckeye' timestamp='1298070841' post='4776125']
When their collision objects collide. Is there a reason you need to know about a collision before it occurs?
[/quote]

Nope, I think I might have just worded my question the wrong way (or wasn't thinking straight). I just wanted to make sure that as my player is falling, if he happens to land on another player that I can control what happens. What ideally would happen would be "landed on enemy, enemy damages/dies/whatever, then fallingPlayer should I guess bounce a bit or otherwise change to movement to indicate a hit has happened".

So I guess I was just confused of the order, but it should be

1. get input
2. move each entity one by one according to input
3. check for collision with other entities. When a collision happens from a jump, tell "fallingPlayer" that he hit an enemy on the head, and he should bounce up (or whatever) on the next frame through. In this step, if a "hit on the head" occurs, this is where I would say something like [code] enemyPlayer.wasHitOnHeadByEntity(fallingEntity); [/code] yeah?
4. render everything

I'm trying to avoid using a physics engine at this point because I just want to do something very simple for now with really basic physics (mostly as a learning experiment, without getting bogged down by a premade physics engine). But if I were, then @simpler's comment sounds logical.
[/quote]
Note: my comments are just suggestions which are intended to help you sort out what objects (players, enemies, collision engines and physics engines) need to "know" about each other.

With regard to your post above, I guess it all depends on what section of your program is going to move entities around. Making it a little clearer, there can be two parts to the physics engine: a physics engine (which calculates positions, velocities, etc.) for collision objects; and a second part, the collision engine (which determines if any 2 collision objects have collided and reports on the position, normals to the position at the collision point, etc.) of those collisions.

To expand your steps above, you might consider something like:
1. get input - user input: direction keys, rotation, etc. For non-human entities, if they have AI (artificial intelligence), similar input for wanting to move or rotate. As mentioned below, input may also result from the last go'round of collisions.
2. Add the input (in terms of direction or forces or however you're going to control collision objects) to the collision objects. The physics part of the engine then moves the collision objects around. That has the advantage of having a single location in your code for calculating positions and velocities, etc.
3. The collision engine part of your program then determines (based on the new positions of the collision objects) where collisions have occurred. It then generates a "report" (perhaps a std::vector of collision information structures) of all the collisions it detected.

At this point, I'll ask a question similar to the previous one - is there a need for the falling player to know that he hit an enemy on the head? If yes, that's fine, too. But, you could simply process the collision information for that particular event ("an entity landed on another entity's head') to "bounce" the falling entity's collision object (essentially "input" to be used the next time step 2 is processed) and just inform the other entity - "you were hit on the head. Take damage or die."

4. Render according to the new positions, perhaps with some enemies "exploding" or "puffing" out of existence due to getting hit on the head :) .

As simpler mentions above, you need to figure out how each entity (player or enemy) knows where it is to render correctly. One possibility is for each entity to have a copy of (or pointer to) information about its collision object. That information is kept up to date by the physics engine which has a pointer to that information also. Then, in step 4, each entity (if it hasn't been killed) can get it's own position from that information and be rendered appropriately.

Share this post


Link to post
Share on other sites
Buckeye that's some really good advices you posted in the previous post.

EDIT: sorry for hijacking [img]http://public.gamedev.net/public/style_emoticons/default/wink.gif[/img]

Share this post


Link to post
Share on other sites
@simpler - it's very bad form to hijack threads in forums. jbrennan had some questions and started a thread to get them answered. You should respect that. Your questions may be taking the progress of the thread in an entirely different direction than what jbrennan wants.

Share this post


Link to post
Share on other sites
[quote name='Buckeye' timestamp='1298084378' post='4776193']

To expand your steps above, you might consider something like:
1. get input - user input: direction keys, rotation, etc. For non-human entities, if they have AI (artificial intelligence), similar input for wanting to move or rotate. As mentioned below, input may also result from the last go'round of collisions.
2. Add the input (in terms of direction or forces or however you're going to control collision objects) to the collision objects. The physics part of the engine then moves the collision objects around. That has the advantage of having a single location in your code for calculating positions and velocities, etc.
3. The collision engine part of your program then determines (based on the new positions of the collision objects) where collisions have occurred. It then generates a "report" (perhaps a std::vector of collision information structures) of all the collisions it detected.

At this point, I'll ask a question similar to the previous one - is there a need for the falling player to know that he hit an enemy on the head? If yes, that's fine, too. But, you could simply process the collision information for that particular event ("an entity landed on another entity's head') to "bounce" the falling entity's collision object (essentially "input" to be used the next time step 2 is processed) and just inform the other entity - "you were hit on the head. Take damage or die."

4. Render according to the new positions, perhaps with some enemies "exploding" or "puffing" out of existence due to getting hit on the head :) .
[/quote]

Thanks so much Buckeye! You've been a tremendous help. I think it makes a lot of sense to me now!

Thanks everyone else as well. I'm sure I'll continue to post questions as I go along, but this is wonderful for now :)


Share this post


Link to post
Share on other sites

This topic is 2490 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this