文件列表:

MAZE.BAS (8584, 1998-08-01)
MAZE1.BAS (12430, 1998-08-02)
MAZE2.BAS (12579, 1998-08-02)

This package should contain four files. maze.bas maze1.bas maze2.bas readme.txt These programs demonstrate a path finder algorithm I came up with. Initially I originally wrote this as an RTS game path finder. It is always irratating to me when my orc takes the longest path to a point, and once or twice I've been tempted to write a RTS game. I wrote it in qbasic. (its a quick, easy, small language. a vc++ project to do this would be 3 megs of hard drive space). After I wrote it, I reallized that the algorithm would solve mazes, which is a program I had always meant to write, but never got around to. maze2.bas contains a maze generator too, which is pretty simple, but still makes an ok maze. To run the programs, just go to a dos prompt and type qbasic maze.bas press F5 to start the program break to stop early You may have to search for qbasic if its not in your path. If you have trouble email me at kristian@ou.edu, and I'll be happy to help. 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 X Next 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 X Maze.bas contains the algorithm to this point. The next step is to see if any straight lines connect the points already contained in the path. Points are checked from farthest apart to closest Actually, to find the optimal path, the entire algorithm should be repeated between every pair of points on the path, but that is to intensive for our little program, and takes to long for a rts game. Here is the completed path after 2 lines are added. 3 2 3 3 X 3 3 X 3 S 1 X 1 E X X X Maze1.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 kristian@ou.edu http://www.geocities.com/EnchantedForest/Tower/7178 http://www.angelfire.com/ok/fireshaker

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：