Back to the main site


Path-finding: a novice attempt

Posted on by Malcolm

It’s worth noting here that I’ve yet to actually study AI; I’ll be taking that module in the next year. However, for my end of year assessment in programming, we had to create a game based upon the classic Atari game Centipede and I was complimented by my peers on my centipede’s path-finding ability. So I think I’ll start this blog here.

Centipede 2.0 Title Screen

Centipede 2.0 Title Screen

One truism that you’ll find in programming is this: the more explicit you make your demands, the easier it is to code. This sounds like common sense but it’s very easy to get carried away, especially if you’re starting to get into the groove of programming, with the possibilities you can create at your fingertips.

 

For those who haven’t played Centipede, the centipede snakes its way down the game screen towards the player. If you shoot the centipede, then that segment of the centipede turns into a mushroom which the centipede cannot pass through. There’s also another object, which is a scorpion in the classic game and a Gundam in my version, which poisons the mushrooms it comes into contact with. When the centipede collides with a poisoned mushroom it drops to the bottom of the game screen. In addition the player movement is limited to the bottom third of the screen.

 

Now that we know just what the centipede actually does we can break it down this down into several steps:

Centipede 2.0 Gameplay Screenshot

Centipede 2.0 Gameplay Screenshot

All of the above demands are tied into one function called movecentipede() that is fired by a hard coded timer. This function is also a member function of the centipede class as the centipede should be responsible for its own movement since we’re programming this according to Object-Orientated design principles. It’s important to note that the centipede itself is a linked-list of elements and it “moves” by pushing and popping elements in the list. So, when we come to move it, it’s a case of where the next element should spawn as opposed to where should the elements be moved to. This made the path-finding incredibly easy to visualise for me. The movecentipede() function works in three easy steps:

  1. Move the centipede (this involves pushing an element into the linked-list and copying the data from the previous head to the current head).
  2. Check where the centipede is moving.
  3. Set the next direction.

The explicit behaviour of the centipede is this:

  1. If at the edge of the screen, move down (or up) and move in the horizontally opposite direction.
  2. If movement is blocked, move around it. If the centipede cannot move around it then behave like it’s the edge of the screen as in step 1.
  3. If movement is blocked by a poisoned mushroom; fall to the bottom of the screen.
  4. When the centipede hits the edge of the wall at the very bottom of the screen then start to move up and stay within the bounds of the player area.

For the first requirement the centipede has separate Boolean variables for whether it’s going left, right, up and down. It’s just a simple case of checking the centipede’s current position and the current state of its Boolean variables.

 

For the collision detection; a separate Boolean function has been created to check this which takes a direction as an argument and then operates on a switch-case statement to return true if there is a collision detected.

 

Back in movecentipede(), if there is a collision, then it will either try to move up or down (whether it moves up first or down first is determined by if it’s going up or down the game screen when it hits the edge of a screen) by checking collisions for the space to its top/bottom left or its top/bottom right. If it collisions are true for both the top and bottom then it just moves down and reverses its horizontal direction. The same methodology is used for when trying to move up and down.

 

Now we have to take into account the poisoned mushroom. Since the centipede ignores obstacles when falling we actually check this first in the movecentipede() function. This is controlled by a simple Boolean variable. When it is about to hit the bottom the next direction (going left or right) of the centipede is determined by what direction the centipede was going in before it hit the poisoned mushroom.

 

The last behaviour is pretty easy compared to what we’ve already made it do; the centipede also has a Boolean variable to determine whether it’s moving up which is set to true when it hits the bottom of the screen and is set to false when it hits the player area ceiling.

 

In summary, we have a centipede which already knows where it’s going to go. The movecentipede() function moves it first and then determines where it’s going to move next with the aid of a collision detection function when the function is next invoked. Simples!

This entry was posted in University Work and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>