Divide and conquer algorithm

Here is an algorithm mailed to me by sillywiz@wardrobe.demon.co.uk (Note: the title has nothing to do with Command & Conquer) :

Take the current position and the destination position. Draw a straight line between them. Take the mid point of the line. If it is on an obstacle, perturb the point in some way ( spiral out for example ) until it isn't. Set this as the new destination & iterate until you have a close enough destination to be able to simple move there.. ( in C&C and WarCraft this will be a grid-square or two away. )

This won't work on too cluttered terrain or one with long linear features, but for avoiding marshes/trees etc it seems to work quite well. It has the other advantage that time to generate next move is log2 of the final distance and you concentrate on bits near to you and ignore further away moves ( which could well have changed when you get there if you are, for example, bombing the forests.. )


Back to index page.

john@lis.pitt.edu