Jump to content
  • Advertisement
Sign in to follow this  
Seer

Collision Handling

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

https://www.gamedev.net/topic/686435-accessing-main-class-objects-list/

 

Following on from that thread, I have tried implementing collision handling in my game.

 

Here's the top level directory for the .java source files https://github.com/RustedBot/DesignTesting/tree/collision/core/src/com/observertest

The main files to look at are World.java, CollisionHandler.java, CollidableObject.java and Ship.java.

 

I have created a CollisionHandler that the World holds. The CollisionHandler checks every CollidableObject against every other CollidableObject in the method handleCollisions() to see if any of them collide. This is determined based on whether or not each objects Rectangles are intersecting. If they are, it calls CollidableObject.resolveCollision(CollidableObject). This methods implementation is left to each individual CollidableObject, so every object can react to collisions in a way that makes sense for it. The biggest problem that I can see with this is that it requires instanceof checking for every type the CollidableObject is interested in handling collisions with. I would rather not have that, but I can't see any other way as each object has to be able to react accordingly to different types.

 

I know that iterating over every object with every object is pretty much the least efficient way of detecting collisions, but it's the only way I know how and right now I'm just testing to see how collisions work.

 

That's the basic structure. The problem is that objects are not resolving their collisions correctly.

 

When two Ships collide, what I want to happen is for each Ships movement towards one another to cease. What currently happens is that the moving Ship pushes the other Ship away when moving into it. At least this is what happens when moving perfectly squarely from one side. If the two Ships y values are not perfectly aligned when moving along the x axis, then the Ships jerk away from one another diagonally. The same goes for when moving along the y axis.

 

I think that this behaviour can be fixed by handling collisions along one axis after movement along that axis and then handling collisions along the other axis after movement along that axis, but this is something that can only be done if handling collisions during each objects update phase. That kind of structure does not seem right to me. I feel like all objects should be able to update, and only once that is finished, should collision handling be performed.

 

How can I correct the collision resolution between objects?

What might be a better way to check for types than a set of if(CollidableObject instanceof Type) statements when resolving collisions?

Any other advice? I'm sure I'm doing plenty wrong, and there's probably a lot that I'm not seeing.

 

If anything is unclear I'll try to clarify. Thank you.

 

 

 

Share this post


Link to post
Share on other sites
Advertisement

Just use a lib, dude: http://www.jbox2d.org/

That is a port of Box2D to Java. Otherwise you got libGDX's bindings to the native lib, but that depends on libGDX (yuck!).

Physics get really complex really fast. You start with a square-square intersection test, and soon enough you're researching narrow phases, broad phases, continuous collision, all sort of trees, etc.

 

EDIT: Oh you're already using libGDX, um so why not use their Box2d integration? https://github.com/libgdx/libgdx/wiki/Box2d

Edited by TheChubu

Share this post


Link to post
Share on other sites

Thanks TheChubu, but collisions won't be more complicated than AABB collisions for what I'm planning and I would rather not have to learn Box2D for this. I would like to be able to get AABB collision handling working without a physics library.

Share this post


Link to post
Share on other sites

The first thing you have to do is decide what exactly is not working.

 

 

From the feature "I want collision handling", you have developed a solution in your head how to go about it (this is also often called 'algorithm').

From that solution, you coded the program.

 

If both steps are done correctly, you get the feature you wanted, and all is fine. Alas, this time, something went wrong. If the coded solution is wrong (that is, it does not do what you have in mind to happen), the code is wrong and must be fixed. If your developed solution is wrong, you can throw the code away, and go back to the drawing board to invent a better algorithm.

 

To decide which case you have, set a breakpoint in the code where a collision is detected. When it triggers, check all the variables, and reason what the solution in your head should do in that case. Then step through the program, and check what actually happens. If the code does something else than the algorithm says, the code is buggy.

If the code gives the right answer, your algorithm is likely broken (or maybe the code worked for this case, but not for another case you encounter later.)

 

 

What's tricky in these cases is getting a picture how the algorithm works if you move in time, computing a sequence of frames. Maybe the algorithm seems to work for a single frame, but all the frames together don't give the desired result.

Share this post


Link to post
Share on other sites
I know that iterating over every object with every object is pretty much the least efficient way of detecting collisions, but it's the only way I know how and right now I'm just testing to see how collisions work.

 

That is time consuming.  If you have hundreds of objects it means tens of thousands or even hundreds of thousands of tests.  Generally you can eliminate nearly all of those time-consuming tests.

 

* Reduce the problem space first.  Instead of testing all-to-all, use a spatial grid. You still traverse the tree, but only need to test the few items that are in the same the spatial grid. Instead of testing hundreds-to-hundreds, typically the spatial grid comparison reduces it to a small number of pairwise tests. Generally items don't occupy the same spatial grid when you travel to the deepest level of the spatial hierarchy, so traversing the tree you only find a single item.  Only when you find two or more items in the cell do you need to test.

 

* Reduce the difficulty of the tests. Most systems have a broad phase and a narrow phase.  The first test is general and fast, such as testing a large bounding box/cube or a large bounding circle/sphere. If that test indicates a collision, then the more detailed collision test is run. Assuming you already store the center and the squared radius of each object, the first test can be done with a few multiplications and additions compared against the stored number.

 

 

 

The problem is that objects are not resolving their collisions correctly.   When two Ships collide, what I want to happen is for each Ships movement towards one another to cease. What currently happens is that the moving Ship pushes the other Ship away when moving into it. At least this is what happens when moving perfectly squarely from one side. If the two Ships y values are not perfectly aligned when moving along the x axis, then the Ships jerk away from one another diagonally. The same goes for when moving along the y axis. How can I correct the collision resolution between objects?

 

It could be you are operating on each axis independently as part of the math, but then accidentally using the combined vector or the total magnitude for other parts of the math.  For instance maybe the component X axis is 14 and the Y axis is 7, with a vector magnitude of about 22. You might be doing part of the math with the x axis value of 14, then at some point accidentally use the total magnitude of 22-ish.

 

Another possibility is that you're using the wrong axis at some step by accidentally swapping a sine or cosine. If you accidentally apply the wrong magnitude in a step, with the same numbers as above maybe when you thought you were applying a 7 you were actually applying a 14.  

 

Yet another possibility, when the two are exactly axis-aligned then the other axis value will have a zero magnitude, which might cause the error to multiply by zero and vanish on a perfectly-aligned comparison.

Share this post


Link to post
Share on other sites

First of all I would like to know, should collision handling be done only after every object has updated? In other words, after every object has moved, if it's going to move. Or, is it considered appropriate for collision handling to be performed during each objects update?

 

Thanks Alberth and Frob. Frob, I didn't understand anything you said after the second quote.

 

Did anyone have a look at the code?

Share this post


Link to post
Share on other sites

I had a quick look, and it seems you're testing and fixing at the same time, which seems a bit error-prone to me (If A detects collision with B, it moves. B will then not detect a collision with A later, as A already moved.)

However, maybe I am wrong in reading the code, or is this intended way of working for you.

 

 

Hence my suggestion to first check whether the code follows the algorithm.

 

 

As for "should be done", I never programmed anything like it, but there is usually only one final good/wrong criterium, it must work as you intend.

Share this post


Link to post
Share on other sites

I would like to know, should collision handling be done only after every object has updated?

 

Often (but not always) the collision processing takes place and the state changes are recorded, when they are all detected the events are broadcast to interested listeners so the code can respond appropriately.

 

Frob, I didn't understand anything you said after the second quote.

 

I was assuming you had a more real-world physics step based on your descriptions, rather than looking at the code. 

 

Looking over the code, the key parts are in Ship.java line 91, and  CollisionHandler.java line 30

 

 

hat I want to happen is for each Ships movement towards one another to cease. What currently happens is that the moving Ship pushes the other Ship away when moving into it.

 

What you describe seems to match the code.  CollisionHandler finds the first match and calls that object's resolve Collision.

 

Inside the ship's resolveCollision, if it collided with another Ship object the active ship moves its position. It does not modify its own speed or rotation, only the position.

 

CollisionHandler scans across the remaining objects, but because the first ship has already moved it does not detect a collision with the second ship.  So the first ship continues on its way, never knowing the collision took place.

 

 In your CollsionHandler's handleCollisions loop, instead of looping across all collideable objects once and then all collidable objects again (the square case) you only need to consider the comparisons you haven't handled before (the diagonal case).  You don't get to use the ranged for, but it results in half the work:

for( int a=0; a<collideableObjects.count-1; a++) {
  for( int b = a+1; b<collidableObjects.count; b++) {
    if(collidableObjects[a].collidesWith(collidableObjects[b]) {
      collidableObject[a].resolveCollision(collidableObject[b]);
      collidableObject[b].resolveCollision(collidableObject[a]);
...

 

It still has the problem that your code moves the objects rather than queues up a future response, so you can address that next:

 

Inside the Ship code, if there is a collision set a flag that says there is a collision and record the object it collided with.  If appropriate, set its speed back to zero.  Then on the next update() or similar event, resolve the problem of overlapping position. 

 

As an alternative, have the CollisionHandler record a collection of all the collisions in one pass, then call all the resolveCollision functions, being aware that one call you may have moved the objects already, so rectangle.intersection() may return an empty intersection test even though the collision happened.

 

In a more comprehensive system a collision would likely change direction, speed, and position, with each of the values changing based on physics properties like mass and velocity relative to each other. 

Share this post


Link to post
Share on other sites

Thanks Frob, but I don't quite understand.

 

If the first Ship resolves the collision with the second Ship by adjusting its position, shouldn't that be that? Why would the second Ship need to resolve collisions with the first Ship then?

 

To give a picture of how I see it:

I imagine the first Ship travelling from left to right along the X axis. In its update, it has moved such that its rectangle is now overlapping the second Ships rectangle. Fine, then the objects all finish updating. The CollisionHandler does its job and searches through every CollidableObject, checking for collisions. As collisions occur, they are resolved. In the case of the Ship, it is resolved by getting pushed back so that its rectangle is no longer overlapping the second Ships rectangle, but is instead only bordering it. If this happens, why would the second Ship need to resolve collisions with the first Ship? Why is this not a good setup?

 

Of course the resolution I think should occur is not what actually happens. I think it's my resolution implementation, in CollidableObject.resolveCollision(), that isn't working, rather than the process around checking and resolving, but I could be wrong. The reason I think that is because of my reasoning above and because the first Ship pushes the second Ship away, when it should instead come to a stop. That would be something to do with the resolution itself wouldn't it, rather than how the checking and resolving is structured currently?

 

Inside the ship's resolveCollision, if it collided with another Ship object the active ship moves its position. It does not modify its own speed or rotation, only the position.   CollisionHandler scans across the remaining objects, but because the first ship has already moved it does not detect a collision with the second ship.  So the first ship continues on its way, never knowing the collision took place.
 

Frob, I'm struggling to understand your reasoning. Should position not be adjusted to resolve the collision? Why does the first Ship continue without realising there was a collision?

 

I'm having a hard time getting my head around this.

Share this post


Link to post
Share on other sites

Did you check what really happens?

You can reason all you want, but until you verify what actually happens, it's all speculation. When you watch it, there are dozens of collisions happening, indeed it is hard to understand such a sequence.

 

Should position not be adjusted to resolve the collision?
Adjusting position is one way to resolve a collision. However, the next frame, the ship collides again, and is again moved back. If you also adjust speed or direction, different things may happen, a bit more like in real-life. That goal however depends on what you aim for in the game.

 

Why does the first Ship continue without realising there was a collision?
Not sure how to interpret that. You have one-sided collisions currently (since you resolve the collision completely on the first->second collision detection), so one of the ships will indeed never realize there is a collision (second->one would come later in the double iteration, but at time, the ships don't collide anymore as the first ship was moved).

From the post, it seems like "first ship" is wrong, the second ship would not see the collision at all.

 

If"first ship" is really intended, perhaps it is because the ship doesn't keep history, it hits the second ship with exactly the same speed as in the previous frame (and gets moved back equally hard).

 

 

Note: "!collidableObject.equals(this)" is overkill since you don't define an "equals" method, "collidableObject != this" does the job too.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!