Fast Collision Detection

Question

I'm currently writing a android game and and am dealing with fast collision detections. I've come up with a solution, yet I'd like to know the most and preferred way to do this.

My solution: If we have a game object that moves 30 units a frame, we might go straight through another game object. So when I update I iterate the game object by 1 unit and run a collision detections until my wanted velocity is reached, and then I render.

This is a game object, that checks if the player's lasers or if the player itself has collided with it.

public void update(PlayerDroid[] holderPlayerDroid) {
            // Update the location
            //y = y + velocity;
            //stupidBadDroidPositionShape.setLocation(this.x, this.y);

            // Updates regarding interactions with the enemy out of the StupidBadDroids perspective, which is the PlayeDroid
            for(int numberOfPlayerDroid = 0; numberOfPlayerDroid < holderPlayerDroid.length; numberOfPlayerDroid++) {
                // Check if the StupidBadDroid got hit
                for(int iterations = 0; iterations < velocity; iterations++) {
                    y = y + 1;
                    stupidBadDroidPositionShape.setLocation(this.x, this.y);
                    // Check if StupidBadDroid collides with the enemy (which is the player)
                    if(Physics.shapeInShape(holderPlayerDroid[numberOfPlayerDroid].getPlayerPositionShape(), getPlayerPositionShape())) {
                        isDead = true;
                    }
                    for(int i = 0; i < holderPlayerDroid[numberOfPlayerDroid].amountOfVisibleLasers; i++) {
                        if(holderPlayerDroid[numberOfPlayerDroid].holderLaser[i].isDisposed() == false) {
                            if(Physics.shapeInShape(holderPlayerDroid[numberOfPlayerDroid].holderLaser[i].getLaserPositionShape(), getPlayerPositionShape())) {
                                isDead = true;
                                holderPlayerDroid[numberOfPlayerDroid].holderLaser[i].dispose();
                            }
                        }

                    }
                }



            }

    }

This way is very CPU demanding. Do you believe there are better solution I could apply?

why are you iterating over the velocity? I get most of your code, just not this one part — Denzil
– Denzil, Commented May 16, 2012 at 20:49
Hey Denzil, I do this so I can check if the laser really hits the enemy. The laser is small and sometimes just flies straight through the enemy. The method I used before was to check for any collisions each time the laser added 8 to its distance. Yet now I'm letting it travel 1 then check for collisions then again and again until it reaches 8 (which is its velocity) and then I render it. Does that make any sense? — Luke Taylor
– Luke Taylor, Commented May 17, 2012 at 14:06
You can always use geometric bounding boxes/shapes for your objects, and calculate the time/position at which a collision occurs. In order to go into more detail, more information about objects' shapes might be needed. — Casey Kuball
– Casey Kuball, Commented May 17, 2012 at 15:07
Just an FYI, if you have an object at (0, 0) moving right (v=12), and an object at (0, -3) moving up (v=12), your collision algorithm can create a false positive if the second object is called with update before the first. — Casey Kuball
– Casey Kuball, Commented May 17, 2012 at 15:11
what are these lines supposed to do then?: y = y + 1; stupidBadDroidPositionShape.setLocation(this.x, this.y); — Denzil
– Denzil, Commented May 17, 2012 at 17:14

Jeremy Scoggins · Accepted Answer · 2013-09-04 12:54:51Z

You are describing tunneling, and are attempting to do continuous collision detection. Your method is CPU intensive because you are attempting to brute-force the solution.

The more fidelity that you want, the more technical the solution. If you don't need much fidelity, you could assume that the path the objects take in each frame is linear, and "expand" your hitboxes to cover the entire distance the objects moved during the frame. So, for example, instead of moving each point a discrete distance at a time, you could simply expand the points to a line segment and see if they intersect. Your hitboxes are not going to be points, though, so just "stretch" them by the path length. This is a very low-fi solution - if multiple collisions on the same object happen, you won't always pick the collision that happened "first".

For very complex solutions, try -

http://www.bulletphysics.org/mediawiki-1.5.8/index.php/Collision_Detection_and_Physics_FAQ

Collectives™ on Stack Overflow

Fast Collision Detection

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related