To run the programs, just go to a dos prompt and type:
The algorithm:
The first step of the algorithm is to draw a straight line from the
start location to the end. The initial straight line is seen as
dark blue in the programs. I use a slightly modified bresenhams (spelling)
algorithm to draw a virtual line in the map array. This is the initial
guess for the path. S is start, E is end, 1 is the first path guess,
and X is an obstacle.
X X S 1 1 1 1 X 1 1 1 1 E X X XNext each point on the path is checked for intersection with an obstacle. If an obstacle is reached, it is traced around completely, and all intersections between the original path and the tracing are determined. If no intersections are found, the goal is unreachable. If 1 or more intersections are found, the path is modified to include the shortest traced path to the closest intersection to the goal. 2 is the included section on the path.
2 2 X 2 2 X 2 S 1 1 1 1 X 1 1 1 1 E X X XMaze.bas contains the algorithm to this point.
3 2 3 3 X 3 3 X 3 S 1 X 1 E X X XMaze1.bas contains the algorithm to this point. For an rts game, this algorithm gives really good paths if it is repeated at each step, and seems to be pretty quick.
After I had gotten this far, I realized that this proceedure would solve any path, and I decided to apply it to a maze. I added a maze generator, and removed the stright line step (it is useles and slow for large paths through lots of objects.) the result is maze2.bas. There is a small bug in maze2.bas...if the path is two long you will get an undefined array cell accessed, and a crash. Just restart, and hope for a simpler maze. This is due to array size limits in qbasic. There are also a couple smaller bugs, but nothing unmanagable, or worth my time at this point.
Disclaimer:
This is my code. Most of it is just junk that I came up with killing
time some afternoon but... you can use it for your own personal use, but
please do not publish it, distribute it, or use it commercially, without
permission from myself (which in most cases will probably be easy to get).
Otherwise enjoy,
Kristian Olivero
Primary E-mail: drko@ba3d.com ;
kristian@ou.edu