Home This Article Is Taken From The Game Programming MegaSite, A Definitive Resource For Game Developers!

Crash 'n Turn Pathfinding
By: john@lis.pitt.edu

This is probably the easiest one to implement and was the first one I implemented in my Prisoner of War project. This is an algorithm that evaluates the way one step at a time. Trying to move in a straight line to the endpoint direction and adjusting the rules as it goes. As most of you already know, this is not a good way of solving it. The unit will behave odd, choosing silly path's. Sometimes it will get locked up in a loop. Anyway, here is how I implemented it:

  1. Try to move in a straight line to the endpoint. Always remember the previous tile coordinates. (One brain-cell).
  2. If it collides with an obstacle (landscape or other unit) try the RIGHT_HAND rule. Rotating right until a free passage is found and then move to that tile.
  3. Repeat 1-2 until the goal is reached or a collision with the previous tile occurs.
  4. If we collided with our previous position (trying to go back to the last tile we came from) try changing to a LEFT_HAND rule instead. Then follow the same procedure above (using a LEFT_HAND rule instead of RIGHT_HAND).

The last point can be changed to say it should not be able to go back into it's previous tracks. This way it will continue using the RIGHT_HAND rule all the way.

The algorithm is not very good and gets easily locked up. Especially in the U-formed obstacle example.

The crash'n turn algorithm can be further enhanced to make the unit behave a bit more intelligent. I.e. look at the below example: 


      ########
    ###########  A
    ###########  
    ###########
    ###########
     #######

      B

Our unit wants to go from A to B. We can easily see the best way will be to use a LEFT_HAND rule to reach the goal. Our initial algorithm will always use a RIGHT_HAND rule first. This will look silly, as it will take the other way around the obstacle.

By modifying the algorithm a bit we can decide which rule we should start using. Imagine yourself wanting to go past the obstacle. You would probably think something like: Lets follow the edge until we reach the corner and then move towards the endpoint B. Okay, you naturally chose a LEFT_HAND rule.

This is what we do: Alternate between RIGHT_HAND and LEFT_HAND scanning on the first obstacle you meet. The first one that gives a free path tells you which rule to use. This way the routine will probably choose a smarter rule to start with based on it's angle to the destination point. It will of course fail on difficult terrain and the same loop problems are quite evident in this implementation also.

Here is another example, it will choose the LEFT_HAND rule because it saw that the left edge was free. It will choose the same path from B to A also: 


            ***********
         A**###########**B
            ###########  
            ###########
            ###########

On the example below it will fail to behave intelligently because the scanning found the right to be the first free path: 


              ######
          A***######   B
             *######   *
            **######   *
           *###########*
           *###########*
            **#######**
              *******



The Game Programming MegaSite - ⌐1996- Matt Reiferson.