Crash'n turn algorithm

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.


Back to index page.

john@lis.pitt.edu