Addition to the crash'n turn algorithm

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
             *######   *
            **######   *
           *###########*
           *###########*
            **#######**
              ******* 


Back to index page.

john@lis.pitt.edu