# Collision detection against large arbitrarily shaped textures

What is the most effecient way to do collision detection on strangely shaped textures in XNA? Here is an example texture:

As you can see, it is far from a perfect square. I want the player to collide with the brown parts and pass through the transparent ones.

How do I create a bounding box that wraps around irregular terrain? Should I create many smaller bounding boxes instead?

• @BogdanMarginean do you mind sharing a link? – Battle_Pasture Mar 17 '13 at 18:57
• convert your surface to polygon and build quadtree. Per-pixel collision does not make sense, if your objects are larger than 1 pixel. – Ivan Kuckir Mar 17 '13 at 19:00

Don't be discouraged, what you're trying to do is very possible and has been used in several shipped games; I haven't tried such an approach myself, but I know at least two people who have managed to get such a system working.

This paper describes how to get smooth well-behaved collision information (penetration depth and surface normal) from bitmap data. http://imrtechnology.ngemu.com/downloads/tutorial.pdf

Alternately, you could generate/calculate a distance field texture which gives, for each pixel, the distance to the closest point on the surface of the solid. Once you have a distance field, you can very easily collide circles against it. This thread covers some ways to generate distance fields: How can I generate signed distance fields (2D) in real time, fast?

Look at spatial hierarchies like quadtrees or binary space partitioning (BSP) trees.

These data structures are independent of C#/XNA. The basic idea is like what you mentioned: They involve many small bounding boxes. However, you don't have just a list of small bounding boxes, but instead build a tree structure where every node of the tree represents a bounding box and every branch of that node represents even smaller bounding boxes.

For example, a quad tree works like this: Start out with one giant bounding box. Insert your objects (for example your pixels) into it. After a certain treshold it will split into 4 smaller bounding boxes. And this continues on. The wikipedia article demonstrates it well.

Instead of checking, say, the bounding box of your character, against each pixel in your texture you check it against the biggest bounding box for your image, then the smaller ones contained by it and so on, until you finally you will arrive at a node in your tree that contains only a few pixels to check against, which you can do efficiently.