Public Group

# Collision Detection

This topic is 3932 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi guys, I am close to the point of making collision detection algorithms and I came up with this question: First, imagine a typical RPG game (this will be obvious but bear with me). You have a character walking around, who may collide with ANY SOLID object in the game, like rocks and trees and other characters. Now how do I check for collision in GENERAL, not just with a particular object. That is, if I have a function like checkCollision(Sprite *A, Sprite *B), and lets say that A is my character. How would I decide which solid object (rock, tree, character, etc..) would go as a second parameter, since this object can be(but not limited to) any of above mentioned objects at any point in the game? This is what I mean by "collision in GENERAL".

##### Share on other sites
I'm not an expert at this but shouldn't you check for collision every time you move your character? Like ok, he's going at the coords x,y,z. Is there something already there ?

##### Share on other sites
Quote:
 Original post by DeepPurple25How would I decide which solid object (rock, tree, character, etc..) would go as a second parameter, since this object can be(but not limited to) any of above mentioned objects at any point in the game?

Good question. Many people run into this problem when beginning graphical programming. Typically, when learning collision detection, you have to pass everything into that second parameter to check that your character does not collide with anything. While this works for smaller games, you could imagine it would get out of hand very quickly.

The solution usually comes in the form of partitioning your game world. Once you have many, many partitions, all you need to do is check for collisions between other entities in that partition.

The way to actually partition your world is up to you, I'm sure you can find several sources through google. One method which may seem intuitive is using a Tree; the root node is your entire World, and each child node is a partition. Keep in mind that these partitions can be comprised of several smaller partitions.

Hope that sparked some thought!

##### Share on other sites
Quote:
 Original post by Alex PanaI'm not an expert at this but shouldn't you check for collision every time you move your character? Like ok, he's going at the coords x,y,z. Is there something already there ?

Yes, this will work if I am walking into something. But still, there is the problem that an object is on collision course with the character from a direction different from that in which the character is walking.

I came up with a way of finding the second parameter, please let me know what you think about it. OK, so I would have to check collision along all four edges of the bounding box. I can give all objects a type "solid", and during each frame(or tick) check whether there is a "solid" obj at a pixel's length in front of either of the four sides of the bounding box. So I get the pixels in front of an edge, and check the see if any of them belong to a "solid". If any do, then I use that "solid" object as a second parameter and check for collision.

Oh and I couldn't find anything useful on partitioning a game world. Id like to know what that is.

##### Share on other sites
You can store your "solid" objects in a separate container from the non-solid objects.

##### Share on other sites
Assuming we're talking 2D here:

Typically, in both RPG and side-scrolling platformers, you would use tile-based collision detection. You define a two-dimensional array of tiles that represents your world, where each (square) tile is an object that stores image information and a flag indicating whether the tile is walkable or not. In your main loop, the four edges of the character's bounding box are continuously mapped to an offset within the array. If one of the edges' offset corresponds to a tile that isn't walkable (or another moving entity), you calculate the penetration vector and offset the character's position accordingly.

This is a primitive form of spatial partitioning: it partitions the world into smaller entities (tiles), which enables you to exclude obstacles that are further away from the player. You could also potentially run more precise tests (i.e. separating axis theorem, per-pixel) if the tile-based collision succeeds. If you have a huge world, you might want to consider quadtrees (or their 3D counterpart, octrees), which prevent useless collision tests (for instance, if the player is located in a clearing).

Hope this helps.

##### Share on other sites
The partitioning idea looks good, I'll look into it. Thanks a lot guys.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633680
• Total Posts
3013304
×

## Important Information

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!