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

100

Author

February 18, 2011 02:40 AM

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)



void gameLoop() {

	// Calculate timing delta since last loop

	makeGameControllerUpdateCurrentSceneWithDelta(delta);

	render();

}

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



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

}

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



if (rectIntersection(entityARect, entityBRect)) {

	entityA.collidedWithEntity(entityB);

	entityB.collidedWithEntity(entityA);

	// Or would just one of these be sufficient?

}

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!

kdmiller3

178

February 18, 2011 05:27 AM

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.

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

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: bounding volume hierarchy (what Box2D uses), sweep-and-prune (what Box2D used to use), spatial hash (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.

jbrennan

100

Author

February 18, 2011 11:06 PM

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?



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); ?

}

Thanks again for the help!

Buckeye

10,754

February 18, 2011 11:14 PM

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.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

simpler

927

February 18, 2011 11:50 PM

I'm also bumping in to similiar issues.

[color="#1C2837"]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.

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:



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

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,

[color="#1C2837"]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.
[/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?

My homepage, twitter and github

jbrennan

100

Author

February 19, 2011 12:04 AM

When their collision objects collide. Is there a reason you need to know about a collision before it occurs?

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 enemyPlayer.wasHitOnHeadByEntity(fallingEntity); 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.

Buckeye

10,754

February 19, 2011 02:59 AM

[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?

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 enemyPlayer.wasHitOnHeadByEntity(fallingEntity); 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.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

simpler

927

February 19, 2011 09:02 AM

Buckeye that's some really good advices you posted in the previous post.

EDIT: sorry for hijacking

My homepage, twitter and github

Buckeye

10,754

February 19, 2011 04:30 PM

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

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

jbrennan

100

Author

February 19, 2011 10:16 PM

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 .

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

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines