Designing Collision Detection for 2D Rectangular Adventure/RPG

Question

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.

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?

Answer 1

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!

Answer 2

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.