Jump to content
  • Advertisement
Sign in to follow this  
Shadeirou

2d Collision Detection on Moving Entities

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

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
Advertisement
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
Do you really think that it needs that complex a solution? Because I'm really not thinking about making a physics based game here, more a old-school, mario type platformer...

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
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!