Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

TLDR: I'm looking for an efficient way to detect collisions between irregular/small objects that are not a full tile size (like small cans) and a free-moving character in a 2D game.


I'm planning to design a 2D RPG-style game in XNA. It will be similar to the style of Chrono Trigger (pictured below) -- I will explain what that means. The main issue I have is how to properly design the collision detection.

enter image description here

First, a description of two of the main points of my game design:

  • Sprites are rectangular. So a character is two parts: lower-half (which collides with solid tiles) and upper half (which is "above" the lower half).
  • Free movement. Even though I use tiles, you don't move from tile to tile; you can move in any direction in a small increment (such as 8px).

Another important aspect of my design is that I don't (can't?) do any pre-processing on images to detect collision spaces. It must be either generic (eg. a 4px range outside of each tile), or cheaply calculatable. (This is to make it easier to develop by cutting down on the time needed to make sprites.)

My initial design for this (which I prototyped) was to use the (bottom half of the) character to collide with anything on the "ground" level. This works well with things that are full-tile covering (like walls), but not small objects (like cans). Pixel-level collision detection solved this, but can lead to irregularities, problems with granularity (eg. checking 4 pixels to either side), and of course, performance.

What I really want in this case is for the character to be able to move close to small or irregular objects. Is pixel-level collision detection the right answer? What about encapsulating it in a small polygon approximation (say a rectangle, even) and colliding with that area? I'm concerned that, even with spatial partitioning, the performance will be poor and the user perception of collision will be poor-quality.

How do other 2D games deal with this?

share|improve this question
    
Per pixel collision detection has pretty decent performance. At one point on Microsoft's own XNA site they had a per-pixel collision sample but I cannot seem to find it anymore. The gist of the method is first to check if the rectangles are overlapping with Rectangle.Contains(Rectangle) I believe, and then after that if they overlap you check to see if overlapping the textures changes any of the pixels color or alpha. You'll only check the lower half of your character sprites rectangles against the obstacles. –  Nic Foster Jan 22 '12 at 5:16
    
@NicFoster I have that already implemented efficiently using their sample as my starting point (it didn't rotate/scale too well). Cheers though. –  ashes999 Jan 22 '12 at 6:41
    
I implemented it as well a few years ago in a 2D shooter that I made, it worked perfectly. It should be pixel-perfect, so to speak, at any scale or rotation. What kind of issues were you having? –  Nic Foster Jan 22 '12 at 6:44
    
@NicFoster there was a hardcore bug I eventually solved where a scaled image, when you call GetPixelData or whatever its called, gives you non-scaled data. But I solved it eventually... having the tool of "I can do pixel collisions," I'm not sure where and how to successfully apply it. –  ashes999 Jan 22 '12 at 6:46
    
I guess it was a few years ago, I may have actually ran into a similar problem and solved it. Anyway, after the movement of a sprite I would compare it against other spites nearby immediately, and if it collides with one, I would undo the movement before rendering, and the user will never see the movement and they will see that they cannot move because of the obstacle. You could even handle this event with a response, for example in various games, like Zelda: A Link to the Past, for example, the character will animate as if they are struggling to push against the wall. –  Nic Foster Jan 22 '12 at 6:53
show 2 more comments

2 Answers

up vote 3 down vote accepted

I'm also working on a retro style RPG but rather than pixel perfect collision I am using circles and ellipses centered on the "feet" of my sprites. My world is made up of square environment tiles with some other shapes on top like tables, trees, and bookcases. These simple shapes are super cheap to collide, scale, and store and they give really nice "sliding" effects when they move against each other since the tangents and normals are trivial to compute and you can project your velocities along them.

In this kind of design the collision shapes are totally independent of the graphics and can move in any direction by any increment. You could take this further if you need more precision -- say you were throwing a hammer: if a bounding circle is not precise enough, use an ellipse or an object aligned bounding box. If that's too sloppy, compose the collision shape out of primitives, like a thin rectangle for the handle and a circle for the head.

Games are often more about smoke and mirrors than actual simulation, so do what's 1) cheap 2) looks reasonable 3) is fun

good luck!

share|improve this answer
    
Circles...is genius. Let me try that. –  ashes999 Jan 22 '12 at 11:53
add comment

My approach has always been to use rectangles and a simple version of SAT (Separating Axis Theorem) to resolve collisions.

Here's a sample python implementation (as my C# skills are lacking).

class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Rectangle(Vector):
    def __init__(self, x, y, w, h):
        self.x = x
        self.y = y
        self.w = w
        self.h = h

def intersect_rect(rect r1, rect r2)
    #r1.x1 < r2.x2; etc.
    return (r1.x - r1.w) < (r2.x + r2.w)
    and (r1.y - r1.h) < (r2.y + r2.h)
    and (r1.x + r1.w) > (r2.x - r2.w)
    and (r1.y + r1.h) > (r2.y - r2.h)


def overlap_rect(r1, r2):
    dx = r1.x - r2.x
    dy = r1.y - r2.y

    #Absolute value
    if dx < 0: dx *= -1
    if dy < 0: dy *= -1

    ovlx = (r1.w + r2.w) - dx
    ovly = (r1.h + r2.h) - dy

    if ovlx < ovly:
        ovly = 0
        if r2.x < r1.x: ovlx *= -1
    else:
        ovlx = 0
        if r2.y < r1.y: ovly *= -1

    return Vector(ovlx, ovly)

The overlap_rect function returns a vector that, if subtracted from r1's position will separate it from r2, or added to r2's position, will separate it from r1. If both move, then use half the separation vector. A very simple collision function looks like this:

class Body(Rectangle):
    def __init__(self):
    # I hope I did the super() correctly
        super(Body, self).__init__(0, 0, 0, 0)
        self.no_collide = False
        self.is_static = False

        #Function stubs
        self.pre_collide = None
        self.post_collide = None

    #in here goes integration stuff, materials etc

def collide(r1, r2)
    if intersect_rect(r1, r2):
        if r1.pre_collide:
            r1.pre_collide(r2)
        if r2.pre_collide:
            r2.pre_collide(r1)

        if not r1.no_collide and not r2.no_collide:
            if r1.is_static and not r2.is_static:
                v = overlap_rect(r1, r2)
                r2.x += v.x
                r2.y += v.y

            elif not r1.isStatic and r2.isStatic:
                v = overlap_rect(r1, r2)
                v.x *= -1
                v.y *= -1
                r1.x += v.x
                r1.y += v.y

            elif not (r1.isStatic and r2.isStatic):
                v = overlap_rect(r1, r2)
                v.x /= 2
                v.y /= 2

                r2.x += v.x
                r2.y += v.y

                r1.x -= v.x
                r1.y -= v.y
        if r1.post_collide:
            r1.post_collide(r2, v)
        if r2.post_collide:
            r2.post_collide(r1, v)

Though the broadphase in that is nearly non-existent, and neither does it take into account any form of momentum or restitution, it should be enough for something very simple.

share|improve this answer
    
My question is not how to detect collisions, but when to detect collisions. –  ashes999 Jan 22 '12 at 11:55
    
Oh, I thought that was your problem. The broadphase part of collision detection is something I know of, but not implementation details. I suggest looking into quadtrees, or simply only checking collisions between neighboring tiles. –  Quasiperfect Jan 23 '12 at 4:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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