• 11/02/11 06:00 AM
    Sign in to follow this  
    Followers 0

    Collision detection and bug detection

    General and Gameplay Programming

    ronenkre
    A Few months ago I decided it was about time I write my own Pacman clone. I had it all figured out except for the AI. I wanted to make a good AI, and started looking for one. Diving more and more into the Pacman's world, I became obsessed with the AI, and trust me the Pacman AI deserves an article of its own. But it was that obsession, which led me to a decision. I'm gonna to reverse engineer the original Pacman. Yes, I know. I got it real bad.

    So, there I was spending hours, late nights, trying to put the pieces together, placing break points, and playing tones of Pacman, where at one point I wanted to test something related to Pacman getting caught. I was running Pacman into ghosts, when suddenly; I just went through one of them.Skeptical, are you?! Look at the link from "The Pac-Man Dossier". It gives a pretty good explanation of the bug. I would like to elaborate a bit more, and put it in context of game programming and programming in general.

    But first let me finish my story (It took me months of work,you can spare a few seconds). At one point while going through the code I found the collision detection procedure, and a few hours later, I found, yet another collision detection procedure. Weird. Here we a have, not one, but two ways to detect collisions and yet, we have a collision detection bug.

    Let's look at the following game loop. I think it is pretty standard:

    Do {
    Get user input
    Move characters
    Detect collisions
    Render
    } While ( Player alive)

    Here is how the first collision detection works:

    For each ghost
    If ghost.MAZE_POS == pacman.MAZE_POS Then Return collision detected
    Next
    Return no collision detected

    The MAZE_POS are set at the [Move characters ] procedure, as follows
    CHARCTER.SCREEN_POS.X = CHARCTER.SCREEN_POS.X + DIRECTION HORIZONTAL DELTA
    CHARCTER.SCREEN_POS.Y = CHARCTER.SCREEN_POS.Y+DIRECTION VERTICAL DELTA
    CHARCTER .MAZE_POS.X = CHARCTER .SCREEN_POS.X / 8
    CHARCTER .MAZE_POS.Y = CHARCTER .SCREEN_POS.Y / 8

    Now let's look at the following scenario:
    PACMAN.SCREEN_POSITION.X = 100
    GHOST.SCREEN_POSITION.X = 100
    PACMAN.SCREEN_POSITION.Y = 7
    GHOST.SCREEN_POSITION.Y = 8
    PACMAN.DIRECTION = DOWN
    GHOST.DIRECTION = UP

    At the first iteration, the [Move characters ] will result
    PACMAN.MAZE_POSITION.X = PACMAN.SCREEN_POSITION.X/8 // 100/8 = 12
    PACMAN.MAZE_POSITION.Y = PACMAN.SCREEN_POSITION.Y/8 // 7/8 = 0
    GHOST.MAZE_POSITION.X =GHOST.SCREEN_POSITION.X/8 // 100/8 = 12
    GHOST.MAZE_POSITION.Y = GHOST.SCREEN_POSITION.Y/8 // 8/8 = 1

    And in the collision detection we get:
    PACMAN.MAZE_POSITION (12,0) != GHOST.MAZE_POSITION(12,1)
    At the next iteration, the [Move characters ] will result
    PACMAN. SCREEN_POSITION.X = PACMAN.SCREEN_POSITION.X +0 // stays 100
    PACMAN. SCREEN_POSITION.Y = PACMAN.SCREEN_POSITION.Y +1 // now it is 8
    GHOST. SCREEN_POSITION.X =GHOST.SCREEN_POSITION.X + 0 //stays 100
    GHOST. SCREEN_POSITION.Y = GHOST.SCREEN_POSITION.Y +(-1) // now it is 7
    PACMAN.MAZE_POSITION.X = PACMAN.SCREEN_POSITION.X/8 // 100/8 = 12
    PACMAN.MAZE_POSITION.Y = PACMAN.SCREEN_POSITION.Y/8 // 8/8 = 1
    GHOST.MAZE_POSITION.X =GHOST.SCREEN_POSITION.X/8 // 100/8 = 12
    GHOST.MAZE_POSITION.Y = GHOST.SCREEN_POSITION.Y/8 // 7/8 = 0

    And in the collision detection we get:
    PACMAN.MAZE_POSITION (12,1) != GHOST.MAZE_POSITION(12,0)
    D'oh!, indeed.

    In this case if the programmers used the bounding rectangle collision detection based on the screen position it would of worked, but notice that even that won't always work for 2D games. Picture an asteroid game, where your spaceship advances more than a pixel on each frame and so is the asteroids.

    Moreover, this is not the only bug in Pacman. One might even think that the Pacman's programmers were not such an elite coders. But when looking at the rest of the code, you get exactly the opposite impression. They were GREAT coders. So what exactly went wrong? How could they have missed that?

    If we look at it chronologically, they were inventing the game industry. There were games prior to Pacman, but I believe it was one of the firsts to have more software based code than hardware.

    Pong was, I think, mostly hardware. And the Atari games had a Hardware mechanism for detecting collisions. It does not mean that hardware programming is easier than software; in fact it is quite the opposite. But it does mean that there wasn't a lot of code to learn from. They were writing some of the first lines in computer games industry, so show some respect.

    But there is also a timeless reason, I think, that programmers and QA everywhere, can relate to.

    Think of a program you write that for some reason is simply hell to debug. You either cannot:

    (A)Run it in a debugger.
    Or (B) The bug occurs only at theclient site, and you are not allowed to halt the system.
    Or ( C ) In cases like this where you don't even have a line to place a breakpoint.

    You would have to look at the code and figure out the entire scenario. But there's more. If you wereQA-ing PacMan, what would you do? Would you spend most of your time escapingthe ghosts or trying to run into them?

    And that leads me to the second collision detection procedure. It had more testing based on screen position. It subtracts Pacman screen position from the ghost's and tests if the result is lesser than 4 (but it does not test if it greater than -4).

    Oh yea, one more thing. It does that ONLY when in scared mode, when Pacman IS chasing the ghosts.

    So this is only speculating, but it is based on real life experience.

    If the bug happens when you are running into ghosts, it would probably appear mainly when YOU chase the ghosts. Now this is, I think, classic.The first thing that comes to mind is "something is wrong in the scared mode,so let's add a scared mode collision detection patch!". If you programmed for long enough, you are probably nodding now.

    So a nice conclusion would be, when testing, try to test NOTalways what is an expected behavior, try to test sometimes the unexpected. But a nicer conclusion would be, if you missed that one bug, well, you can still sale millions of copies. ka-ching!
    0


    Sign in to follow this  
    Followers 0


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!


    Register a new account

    Sign in

    Already have an account? Sign in here.


    Sign In Now

    Ectara

    • 5
      
    0

    Share this review


    Link to review
    Dragonsoulj

    • 5
      
    0

    Share this review


    Link to review
    DangerDoom

    • 5
      
    0

    Share this review


    Link to review