Sign in to follow this  
generaltao

Game Collision - interesting problem

Recommended Posts

So when I began work on our first 2D game I implemented a loop whereby each entity checks against all other entities to see if there is a collision. If so, it moves the entity to resolve it. Now, the problem I have now is that I now have pushable objects, and when they are pushed they sometimes collide with something that already had a check for collision and thus it will not resolve the collision properly. The way it works now: For each entity --Check all other entities --found collision? ---move entity My very first proposed solution is that I might have to "re-run" the check if there is any collision detected. So say I push the box against the wall and then it goes into the wall. Problem I see is that if I make this recursive it might get trapped in an infinite recursion loop if it keeps colliding...no? I'm absolutely certain others have figured this problem out before :) Any words of wisdom?

Share this post


Link to post
Share on other sites
I just recently implemented a collision detection algorithm into my game, before this I was just using libraries already in place. At first I just thought about how it could work and couldn't think of a way that it could be efficient, I then proceeded to look it up and found a concept called 'sectors'.

Which is splitting the collidable objects into sectors (ie. lists) of a fixed width x height. Then when checking for collisions only check the sectors that need to be checked, depending on your object sizes. I believe I made my sectors 64x64 pixels and checked the 4 ones closest to the checking object. This may help efficiency if you haven't done it like this, I thought it was kinda cool :)

My collision algorithm checked if the moving object was colliding with an object, then checking which side it was colliding on, then moved the moving object as it was going until it collided, so there are no pixels in between them.

I don't have pushable objects in my game but if I was to add them I would do the following:
- Create a Pushable class so that it's easy to check what's pushable.
- When checking moving object collisions, if it's in contact with a pushable object (and desires to push it) add that logic of pushing and checking it inside the moving object check. The sectors method will help here so you don't have to check the whole room/scene again.

Share this post


Link to post
Share on other sites
For efficiency, I definitely have some ideas :) I already have it checking only entities on the layer you are on and only check for objects that have moved in the latest update.

However, maybe I should explain this more clearly and provide a new idea...I'm sure there has to be a good solutions to this. Current logic:

For each entity:
-move entity
-for each other entity
--check if there is a collision
--collision?
---resolve conflict

Reality check:
If the character is standing next to a box which is standing next to a wall, the physics should react as such:
-move character
-found collision in pushable box so push box.
-found collision in wall so push off the box.
-found collision in player so push player away. Done, the result is all three entities not colliding with each other.

So think of it as a chain reaction. I'm thinking of re-organizing my logic but can't think of a good way to do it without going into recursive style functions. Ideas?

Share this post


Link to post
Share on other sites
It doesn't sound that bad.

I guess a harder case would be where a character is squished between two moving blocks, although it should be solved by seeing that the character can't move away the second moving piece after being pushed by one.

Otherwise I don't see why you should get infinite recursion as everything might be just moved back to the initial state where there was no collision?

Share this post


Link to post
Share on other sites
I was getting trapped in recursion when I first tried it, but after thinking about it some more, I realised it was because my current loop of "check entities against all entities" actually moves the entities within there then checking right after. So doing that recursively actually constantly updates items and constantly creates more collisions.

This should be a better fit:

Loop over all entities
Move this entity
do while there are collisions: checkForCollision(thisEntity)
Next entity

That's more or less what I'm thinking. I'd have to completely restructure my code, but I'm finding that to be a pretty normal occurence as a game developer :)

I'll give this logic a shot and let you guys know how it went. Did anybody else have to do similar type of systems?

Share this post


Link to post
Share on other sites

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