Sign in to follow this  
Shadeirou

2d Collision Detection on Moving Entities

Recommended Posts

Sigh... I can't believe that I can't figure out a simple solution to this one myself... I feel unbelievably stupid. I have been working on a 2d platforming game for the past 6 or 7 days. It seemed to be moving along at a great pace. In the first 2 days, I got the map and camera system up, set up a player class, created a somewhat efficient algorithm for checking collision on non-moving barriers, and even made a quick map editor so that I could visually create levels to test my new algorithm. Then, I figured that I would move on to creating moving entities, such as moving platforms, walking NPCs, etc. It seemed like a simple enough concept at the time. But now it's five days later and I can't seem to get this working the way I want it to work. Here's the general idea of what my collision detection system does as of now: - 1. When some entity moves, it moves on the horizontal axis first and then on the vertical. When it does this it creates a rectangle to simulate the path that it will take. - 2. It then checks for collision between that path rectangle and any non-moving barriers around it. If the path rectangle intersects a barrier, the rectangle is shortened so that, if the entity were to move along it, it would stop just touching the barrier. - 3. The same thing is then done for the moving entities instead of non-moving barriers, and it uses the same path rectangle from before. Step number three is where my problem occurs. Since my entities are stored in a list, they are updated one after another. What happens as a result of this is that, when entities check for collision against other entities that are ahead of them in the list, they are checking a position that the other entity may no longer be in come render time. I've been obsessed with this problem for the past few days. I want all entities in the list to check the other entity's render position regardless of where they are in the list. I've thought about getting the next position of the entities based on their velocities, but what if there is another entity in the way of the predicted next positions? I could predict the next position of that as well, but what if there's another entity in the way of that one too? And what if it's the one I wanted to originally move? Then A would have to wait on B to move and B on C and C on A creating an endless loop. I suppose that I could then add a method for checking to see if C was ultimately waiting on A by means of B, but then I would have to run through a loop of entities every time there was a collision and it would slow down collision detection... I feel like I'm thinking to far into this and making it harder than it needs to be.

Share this post


Link to post
Share on other sites
You are venturing into the realm of modern physics engines.

how they handle the circular collision issue is (really simplisticly.. it's more complex but this is the basic idea) they let things overlap, and when they overlap, they try to push them apart based on which one is heavier etc.

IE lighter objects get pushed away from a heavier object more than the heavy object is pushed away.

often times they'll do a couple iterations through resolving collisions in this way per frame since one iteration will probably not be enough.

also, since if you did say 6 iterations per frame, those 6 may not resolve all collisions either 100% of the way, but that's ok because next frame it gets 6 more iterations to resolve the collisions and after a few frames things should resolve.

PROBLEMS: my explanation is super simplified. the real process is a bit more complicated.

Also, there are different methods to do different parts of the process, and the different methods each have different issues / side effects so it's kind of a complex thing.

alternately, theres a way to put all collision info into a matrix and solve it as if it's a set of equations, but mostly people like to do the iterative process since it's simpler and cheaper to calculate.

I think the process goes like this...

#1 - move all objects, keeping track of their last frame's position
#2 - find all colliding objects as a list of collision pairs (lots of ways to detect collisions, the seperating axis theorem aka SAT is used a lot but there are others)
#3 - loop through each collision pair, find information about their collision and handle the collision / do collision response
#4 - do #3 some number of iterations per each frame
#5 - render the frame
#6 - goto 1

hope this helps, i know it's a ton of info...

basically maybe you should let things overlap and try to resolve all collisions each frame (realizing they might not all resolve well) and then let any unresolved collisions be handled more in future frames.

note: i am not a physics programmer though so if one replies, listen to him instead hehe

Share this post


Link to post
Share on other sites
good point, i reread your post and missed the point the first time around sorry :P

#1 - pick an object and see if moving it makes it collide with another moveable object.
#2 - if so, process that other moveable object first (ie goto 1 for that other object).

that way, if there is a dependency chain (ie this object should move before this one before this one before this one etc) it'll process objects in the right order.

A problem comes up like you hinted at that the dependency chain could be circular.

to prevent this, you can have a flag on each object for whether it's been processed yet. that way, if you hit circular dependency it might not look right at the end but at least it wont infinitely loop.

It's not a perfect solution but may give you good enough results in practice (:

Circular dependency is probably going to be pretty rare I'd bet

Share this post


Link to post
Share on other sites
I'd have to agree that circular dependency will be rare, but I like to cover all my bases =P. I actually have this method mostly implemented with a way to prevent circular dependency. I got about 80% of the way through coding it and thought to myself, "I'm making this way too complicated... there has to be a better way to do this."

I suppose it will have to do for now. It will let me continue on to the rest of the game until I can find a better way to do it.

Thanks for your responses.

Share this post


Link to post
Share on other sites
How often is entities overlapping actually a bad thing? In what situations do you want to restrict an object's movement based on other objects in the way, and could you just say "sod dependencies - if that platform wants to move over my player character, that means he's squished to death"?

Share this post


Link to post
Share on other sites
In my situation, entities overlapping is almost always a bad thing. It causes the player to be inside platforms that move up and causes hovering over platforms moving down if the platform is created after the player. I tried adding the velocities to the player's position, which worked for platforms created after the player, but screwed up platforms created before the player.

I really just want to know the render position of the entities regardless of where each is in the list. This is because I don't want it to matter when an entity is created so that my engine can be as dynamic as possible. But with moving entities, I have the problem of not knowing where they are going to be.

Share this post


Link to post
Share on other sites
Quote:
Original post by Shadeirou
In my situation, entities overlapping is almost always a bad thing. It causes the player to be inside platforms that move up and causes hovering over platforms moving down if the platform is created after the player. I tried adding the velocities to the player's position, which worked for platforms created after the player, but screwed up platforms created before the player.
I didn't mean all entities, just some of them. Eg, is it okay for moving platforms to overlap each other, or the tilemap?

Also, you want objects to handle collisions in different ways: the player should never be able to move into a platform, a platform should not have its movement restricted because the player's in the way (the player should be pushed by the platform) presumably? So it's not going to be a standard approach for all entities.

Quote:
I really just want to know the render position of the entities regardless of where each is in the list. This is because I don't want it to matter when an entity is created so that my engine can be as dynamic as possible. But with moving entities, I have the problem of not knowing where they are going to be.
There's more than one way to skin that cat. One of them is: update the movements of all the platforms first, then the player and other entities etc. One way to do that is keep them in separate lists. For an entity which is on a platform, keep a pointer to that platform and add that platform's movements to the entity.

Share this post


Link to post
Share on other sites
Quote:
I didn't mean all entities, just some of them. Eg, is it okay for moving platforms to overlap each other, or the tilemap?

Ah, I see. Yes, the platforms can overlap each other and the tilemap at the moment.
Quote:
Also, you want objects to handle collisions in different ways: the player should never be able to move into a platform, a platform should not have its movement restricted because the player's in the way (the player should be pushed by the platform) presumably? So it's not going to be a standard approach for all entities.

Yeah, my entities have collision flags associated with them and I have it so the platform's movements are not hindered by other entities and so that it registers as a collision for other entities, such as the player, so they cannot move through.
Quote:
There's more than one way to skin that cat. One of them is: update the movements of all the platforms first, then the player and other entities etc. One way to do that is keep them in separate lists.

You are 100% correct. I guess I'm just being stubborn =P.

...Also, I have a tendency to over think things...

Share this post


Link to post
Share on other sites
Yeah everyone is making it way too complex.

I just have a list for each type of object, and can then easily perform actions in response to collisions. If they collide into something in the tile list, they stop. They collide into something in the enemy list, then a "hit" notification is sent to the enemy he collided with and the player. If you want all the stuff to be in one big list for whatever reason, just have a way to distinguish them.

Remember things on a computer happen linearly, one way or another. Just move everything, then check for collisions between them. Simple. Don't try and make everything happen at once.

Share this post


Link to post
Share on other sites
I'm not quite at a point where I have many objects on screen, but the solution i'm planning to use is to compare future coordinates to future coordinates, and should a conflict or collision arise, have some hierarchy in place to decide who gets to move and who has to react.

a bit more complex than this, I've also added some rules based on vector math for deciding where an object should go if it can't go to it's original future point, say, i have a little circular object moving, and is trumped by a larger circle object, I concatenate a vector (perpendicular to the large circle) on the would be future point of the small circle object that "pushes" it just to the edge of the big circle. at this point i can see where multiple collision iterations would make sense, but hope this gives you an idea.

if I were making mario on a floating (up and down) platform, mario would always be "falling" (a velocity vector in the -y direction perhaps?), and would be held up by the platform, and thus rise and fall with the platform. Hope that makes sense, good luck

Share this post


Link to post
Share on other sites
I'm not entirely sure I know what you are asking, and I've never done a platform game, but here is what I will contribute since I recently created a game engine that handles interactions of two moving characters (on a top-down view instead of side scrolling):

- I use the deductive theory of collision (here is my sample code from my engine):

char SpritesCollide(BOUNDING_BOX box1, BOUNDING_BOX box2)
{
/* This function works to serve other functions in collision
detection between two sprites. It uses a deductive theory algorithm.*/
if(box1.bottom < box2.top)
return 0;

if(box1.top > box2.bottom)
return 0;

if(box1.right < box2.left)
return 0;

if(box1.left > box2.right)
return 0;

return 1; //It collides by default!
}

When implementing this code with two objects moving, you have to do a "collide check" every pass through your gameloop to ensure it's up to date. Then, if you encounter a collision, you can re-route to another game phase which will handle the even that has occured. Regardless of game style, this idea should work. I used real time fight scenes in my last game with each character throwing projectiles which are other items to keep track of and it still works.

If you have special needs like how mario has collapsable platforms, then i would recommend creating a matrix called a "solidity buffer" which holds the values of certain collidable surfaces and designate symbolic constants to define what is what. For instance, COLLAPSABLE_BRIDGE could define this. That way, if you encounter this particular item, you could reroute to a process that checks your Xpos, Ypos coords to validate that you're indeed above the bridge and then implement a brdige timer (1000 mS or such?) until either the hero moved or the bridge fell.

This is an example and I hope I explained myself well enough.

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