How did older games do collision detection with walls, floors and ceilings?

Question

I have been reading about collision detection in games on stackoverflow and other sites. A lot of them talk about BSPs, bounding elipses, integration etc. However, on the NES, they managed to do floor and wall collision detection in games and I find it hard to believe that they did many calculations to detect wall collisions.

I guess my question is, given a level made up of just tiles, how did they detect collisions with walls and floors in games like Mario and Megaman which had little processing power?

• Did they follow the path of motion and determine the closest connecting tile? (a bit of searching) (priori)
• Did they determine a collision with the floor and then figure out the best way of adjusting the character? (posteriori) This is risky with variable timesteps, you could jump through a tile if you were fast enough. Although I assume NES games timesteps were synced with the tv's refresh rate.
• Is gravity always affecting your character when you're on the ground? Or do you just 'turn it off' when you're determined to be walking on a tile? What about when you walk off an edge of the cliff? You'd need some sort of way of determining tiles underneath you otherwise.
• If you've collided with a tile, would you just find the edge of that tile and move your character to the side of it (depending on the direction of travel)?
• what about sloping tiles like in super metroid and mario?
• What about 'platforms' where you can jump through the bottom and land on top. How would you deal with collisions with these tiles if you were doing it 'posteriori'?

I have written some collision code that is basically 'priori' as it searches for the first tile you will hit in a certain direction. I'm just wondering if there's a better way. (just using after-the-fact collision detection instead maybe)

eg, code to check for tile collisions for moving downward (I check vert then horizontal movement):

  def tile_search_down(self, char, level):
        y_off = char.vert_speed
        assert y_off > 0

        # t_ are tile coordintes
        # must be int.. since we're adding to it.
        t_upper_edge_y = int( math.ceil((char.y+char.h) / self.tile_height ) ) #lowest edge
        while (t_upper_edge_y*self.tile_height) < (char.y+char.h+y_off): # lowest edge + offset

            t_upper_edge_x = int( math.floor(char.x/self.tile_width) )
            while (t_upper_edge_x*self.tile_width) < (char.x+char.w):

                t_x = t_upper_edge_x
                t_y = t_upper_edge_y 
                if self.is_tile_top_solid(t_x, t_y, plane):
                    char.y = t_y*self.tile_height - char.h
                    char.vert_speed = 0.0
                    char.on_ground = True
                    return

                t_upper_edge_x += 1
            t_upper_edge_y += 1

        char.y += y_off

Answer 1

For the types of NES-era games you're talking about, everything was 2D. That alone simplifies many things.

Some machines of that era (particularly ones with hardware sprites, like the Commodore 64) had hardware collision detection. Most games that weren't relying on hardware collision detection would either use a bounding box or a hit mask (1-bit bitmap of the sprite).

Either way, collision detection was usually done "a posteriori", except for special cases like the edges of the world. Some games actually did have bugs where moving too fast when you hit something could cause you to pass through it. (In fact, reviews of early 80's games would often comment on how precise the collision detection was.)

For platformers, you'd typically check to see if the character is "grounded" before applying gravity.

The one-way platforms thing isn't too hard to deal with after the fact since you know the sprite's velocity vector, so you can use that to determine whether or not the collision should register.