title: How did older games do collision detection with walls, floors and ceilings?
body: <p>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.</p>
  
  <p>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?</p>
  
  <ul>
  <li>Did they follow the path of motion and determine the closest connecting tile? (a bit of searching) (priori)</li>
  <li>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.</li>
  <li>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.</li>
  <li>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)?</li>
  <li>what about sloping tiles like in super metroid and mario?</li>
  <li>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'?</li>
  </ul>
  
  <p>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)</p>
  
  <p>eg, code to check for tile collisions for moving downward (I check vert then horizontal movement):</p>
  
  <pre><code>  def tile_search_down(self, char, level):
          y_off = char.vert_speed
          assert y_off &gt; 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) &lt; (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) &lt; (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
  </code></pre>