Jump to content

  • Log In with Google      Sign In   
  • Create Account


[SDL] Efficient collision detection?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 MottMan   Members   -  Reputation: 100

Like
0Likes
Like

Posted 25 July 2011 - 08:33 AM

I have been using the following code to check for collision detection for the player and the wall:


void Player::move()
{
    player_outline.x += xVel;
    if (...check_collision(player_outline, wall_outline))
        player_outline.x -= xVel;

    player_outline.y += yVel;
    if (...check_collision(player_outline, wall_outline))
        player_outline.y -= yVel;
}


This works fine but if there are a lot of different walls, barrels, obstacles, then the if statement will become quite large and system hogging. Is there a more efficient way to determine what to check/how to check for collision? I'm sure there must be.
Thanks in advance.

Sponsor:

#2 0x3a   Members   -  Reputation: 109

Like
0Likes
Like

Posted 25 July 2011 - 08:47 AM

What you could do is write a general physics manager which you update every tick. When you create a new object ( a wall for example ) this is added to your list of physics objects and the physics manager calculates all the proper information in terms of collisions ( if there is any ), speed, acceleration, etc. This way you really only write gameplay and don't deal with physics inside the game itself, just an update call to your manager.

If that is too much work you can always go for a library to do this, if you work only in 2D I suggest using Box2D.
If I've helped you in any way please push the reputation button, thanks!

Abstraction is my choice of words.
Portfolio: http://www.0x3a.com/
Blog: http://blog.0x3a.com/

#3 MottMan   Members   -  Reputation: 100

Like
0Likes
Like

Posted 25 July 2011 - 08:54 AM

I'm more interested in writing it myself. Could you provide a link to an example?

I'm not worrying (or required to worry) about velocity, speed, or any other variables other than location. If you hit a wall, you should stop. I'm working with 2D strictly, yes.

#4 0x3a   Members   -  Reputation: 109

Like
1Likes
Like

Posted 25 July 2011 - 09:55 AM

Well. The simple example is Box2D, it is open source so just grab it ;)
If I've helped you in any way please push the reputation button, thanks!

Abstraction is my choice of words.
Portfolio: http://www.0x3a.com/
Blog: http://blog.0x3a.com/

#5 MottMan   Members   -  Reputation: 100

Like
0Likes
Like

Posted 25 July 2011 - 10:29 AM

Thanks Posted Image

Glancing at the source it seems overly complicated for what I need it for but should be helpful nonetheless.

#6 kdmiller3   Members   -  Reputation: 176

Like
0Likes
Like

Posted 25 July 2011 - 10:54 AM

What you want is a "spatial query", which allows you to ask what objects are in a particular area. There are a bunch of ways to do that depending on the size of your world and range of sizes of your objects. I'll throw out some terms for you to google: Spatial Hash (what Chipmunk uses), Sweep and Prune or Mark and Sweep (what Box2D used to use), and Bounding Volume Hierarchy (what Box2D uses now).

I'd look at how Chipmunk does it since its system is a lot simpler.

Spatial Hash divides the world into a grid and places objects into whatever grid cells they overlap. This works particularly well if your game is tile-based, since most objects will end up in at most one grid cell. When adding or removing an object, find what cells it covers and add it to or remove it from the hash table using the grid coordinates of those cells as keys. To find what objects are in an area, go through each cell that the area covers and return any objects you find. Depending on size and position, objects can cover more than one grid cell at a time so you need to mark objects so you don't return them more than once. Increment a counter every time you run a query, store that value into the object record when you visit it, and only return an object if the counter and the stored value don't match.

#7 MottMan   Members   -  Reputation: 100

Like
0Likes
Like

Posted 25 July 2011 - 11:05 AM

If I understand correctly there should be a piece of data in an obstacle and the player that identifies it's location on a grid (possibly an array) so that the collision detection function can see what obstacles are near the player and might be causing a collision?

#8 FlyingDutchman   Members   -  Reputation: 207

Like
0Likes
Like

Posted 25 September 2011 - 08:46 AM

If I understand correctly there should be a piece of data in an obstacle and the player that identifies it's location on a grid (possibly an array) so that the collision detection function can see what obstacles are near the player and might be causing a collision?


i just implemented a collision detection in my 2d Engine. You can take a look at the pictures on my blog how it works . Each tile has a bool value 0 or zero, which states if a tile is walkable or not.

then when i move the character, i scan all the tiles around the character (not all on the screen, because thats unnecessary) and if he collides i scan from which side. than i write everything in an char and go on..

here is the code

void AnimatedChar::collisionWithTile(WorldMap &current_map, u_int8_t &collision)

{

    int m,n,i2,j2;

    

    Rect2D tempRect;

    

    tempRect.pos.y = this->rect.pos.y+this->rect.height/2;

    tempRect.pos.x = this->rect.pos.x;

    tempRect.width = this->rect.width;

    tempRect.height = this->rect.height/2;

    

    // starting points

    m = tempRect.pos.x / TILE_SIZE;

    n = tempRect.pos.y / TILE_SIZE;

    

    // end points

    i2 = ((tempRect.width+tempRect.pos.x)/ TILE_SIZE);

    j2 = ((tempRect.pos.y+tempRect.height)/TILE_SIZE);

    

    bool colup = false;

    bool coldown = false;

    bool colleft = false;

    bool colright = false;

    for (int i=m-2; i < i2+2; i++)

    {

        for (int j=n-1; j < j2+2; j++)

        {

            if (current_map.returnTileAt(i, j).isWalkable==false)

            {

                

                if (tempRect.pos.x + tempRect.width-CHARACTER_COLL_OFFSET < current_map.returnTileAt(i, j).x)

                    collision = NO_COLLISION;

                else if (tempRect.pos.x+CHARACTER_COLL_OFFSET > current_map.returnTileAt(i, j).x + TILE_SIZE)

                    collision = NO_COLLISION;

                else if (tempRect.pos.y + tempRect.height-CHARACTER_COLL_OFFSET+2 < current_map.returnTileAt(i, j).y)

                    collision = NO_COLLISION;

                else if (tempRect.pos.y+CHARACTER_COLL_OFFSET > current_map.returnTileAt(i, j).y + TILE_SIZE)

                    collision = NO_COLLISION;

                else

                {




                    // COLLISION

                    if (tempRect.pos.y + tempRect.height > current_map.returnTileAt(i, j).y && tempRect.pos.y < current_map.returnTileAt(i, j).y)

                    {

                        coldown = true;

                    }

                    if (tempRect.pos.x < current_map.returnTileAt(i, j).x + TILE_SIZE &&

                        tempRect.pos.x + tempRect.width > current_map.returnTileAt(i, j).x + TILE_SIZE)

                    {

                        colleft = true;

                    }

                    if (tempRect.pos.x + tempRect.width > current_map.returnTileAt(i, j).x &&

                        tempRect.pos.x < current_map.returnTileAt(i, j).x)

                    {

                        colright = true;

                    }

                    if (tempRect.pos.y < current_map.returnTileAt(i, j).y+TILE_SIZE && tempRect.pos.y + tempRect.height > current_map.returnTileAt(i, j).y + TILE_SIZE)

                    {

                        colup = true;

                    }




     

                }

            }

        }

    }

    // write all values in collision

    collision = (coldown<<3)|(colleft<<2)|(colright<<1)|colup;

}



Then i check when the character moves the following:

void AnimatedChar::update_position(WorldMap &current_map)

{

    if (this->isMoving)

    {

        if (this->rect.pos.x < 0)

        {

            this->rect.pos.x = 0;

        }

        else if (this->rect.pos.y < 0-this->rect.height/2)

        {

            this->rect.pos.y = 0-this->rect.height/2;

        }

        else if (this->rect.pos.x+this->rect.width > current_map.get_world_width())

        {

            this->rect.pos.x = current_map.get_world_width()-this->rect.width;

        }

        else if (this->rect.pos.y+this->rect.height > current_map.get_world_height())

        {

            this->rect.pos.y = current_map.get_world_height()-this->rect.height;

        }

        else 

        {

            Point2D temp;

            temp.x = rect.pos.x;

            temp.y = rect.pos.y;

            

            if (this->viewDirection==DOWN)

            {

               this->rect.pos.y += this->movingSpeed;

            }

            else if(this->viewDirection==LEFT)

            {

                this->rect.pos.x -= this->movingSpeed;

            }

            else if(this->viewDirection==RIGHT)

            {

                this->rect.pos.x += this->movingSpeed;

            }

            else if(this->viewDirection==UP)

            {

                this->rect.pos.y -= this->movingSpeed;

            }

            

            u_int8_t collision=0;

            this->collisionWithTile(current_map, collision);

            

            if (this->viewDirection==DOWN && collision>>3&0x1)

            {

                this->rect.pos.y = temp.y-6.0f;

                this->isMoving=false;

            }

            if (this->viewDirection==LEFT && collision>>2&0x1)

            {




                this->rect.pos.x = temp.x+1.0f;

                this->isMoving=false;

            }

            if (this->viewDirection==RIGHT && collision>>1&0x1)

            {




                this->rect.pos.x = temp.x-1.0f;

                this->isMoving=false;

            }

            if (this->viewDirection==UP && collision&0x1)

            {




                this->rect.pos.y = temp.y+1.0f;

                this->isMoving=false;

            }

            

        }

    }

}








maybe it helps u a little bit, if u have any questions feel free to ask.








I open sourced my C++/iOS OpenGL 2D RPG engine :-)


See my blog: (Tutorials and GameDev)

http://howtomakeitin....wordpress.com/


#9 _Zac_   Members   -  Reputation: 138

Like
0Likes
Like

Posted 25 September 2011 - 02:55 PM

Like what KDMiller3 said, you should create a function that will tell you if there is nothing taking space in the location you want to move to. So like if(areaAvailabe(<where player wants to move>)) returns true then proceed to move the player there. Though it's mostly the reverse of what you're doing now.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS