2
\$\begingroup\$

I am new in game development and for simple games bounding box collision is fine. However, let's say you have a shape or bitmap like this:

enter image description here

This is just an example but if you had more elaborate curves or even a whole shape which was more complex than a simple polygon or rectangle-like shape, how would you do precise collision detection? I am strictly speaking in 2D here. I just want to know the concept behind how you would do this.

\$\endgroup\$
  • \$\begingroup\$ If you need something more complex, it can always be composed by many less complex things. In your case for example many short lines . \$\endgroup\$ – wondra Aug 31 '14 at 12:15
1
\$\begingroup\$

I'm going to assume you're representing your world as geometric primitives (points, lines, curves, polygons, etc.) rather than sprites. If you're using sprites and per-pixel collision detection, there's nothing special about odd-shaped objects. See this question for some ideas.

Using geometric primitives, the first step is to use a broad-phase algorithm to narrow down the possible pairs of objects that might intersect. See this Stack Overflow question. Checking for collisions between each candidate pair is called the narrow phase, and you have a couple of options.

The simplest solution is to just approximate your curve using a series of line segments. If the curve is a standalone object, you'd just treat the segments as you would any other line segments in the world. If the curve is the edge of some larger object, then as a pre-processing step you'd split the larger object into smaller convex shapes using a process similar to the trapezoid rule from basic calculus. The general term for this process is "convex decomposition", and computing an optimal decomposition of arbitrary polygons is NP-complete, but a good-enough or hand-crafted decomposition will work just fine. The smaller convex subparts can be easily checked for collisions using any of a number of algorithms.

A more difficult solution is to write a custom collision algorithm for collisions between each kind of geometric primitive you want to support. Assuming you already support collisions between points, line segments, rectangles, circles, and convex polygons, adding a curve like your example would require coding a custom algorithm for the following pairs:

  • Point - sine curve
  • Line segment - sine curve
  • Rectangle - sine curve
  • Circle - sine curve
  • Convex polygon - sine curve
  • Sine curve - sine curve

I wouldn't recommend this approach because it's complex and ends up being a lot of work. However, if you can figure out a way to represent your objects using only convex shapes, then the generalized GJK algorithm will work, even if your objects have curves.

\$\endgroup\$
  • \$\begingroup\$ I want to know with sprites though.. what do you mean it's nothing special? How do you detect non-alpha pixels in the bitmap? \$\endgroup\$ – user3843164 Aug 31 '14 at 19:07
  • \$\begingroup\$ The details would depend on the pixel format used in your bitmaps, but there is a way to read the alpha channel for each pixel. Google "per-pixel collision detection sdl", replacing sdl with whatever library you're using. \$\endgroup\$ – Sam Sep 1 '14 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.