2/29/08

Java Maze Solver

Java Maze Solver

Maze solver started


Maze solver running Best FS

Maze solver finished A*

DESCRIPTION

Maze solver is a simple application you can use to solve mazes.
You can load a maze file with a specific form and then select an algorithm and find the exit.
The maze file is a text file you can write using any text editor you like(e.g. notepad++). Maze solver ignores all the lines in the file since it reads a line with only the word "start". At the next lines you can have any characters. You can define the start with the letter 'S'. End with the letter 'E' , walls with the letter 'X' and paths with space ' '. Any other character will be considered as a wall. If you write more than one 'S' and 'E' only the first read will count. The rest will be walls. At the end you must write the word "end". Be careful. All the lines must be the same length. If you want spaces at the end you must write them.

Implemented in Java 1.6 but uses some Deprecated functions (suspend(),resume()). Although there is no problem at all because there is no use of locks.
The package contains seven classes.
The idea is that a "man" (thread) is trying to find the exit. The user selects from five algorithms which one to use.
Available option are :
DFS non recursive
DFS recursive
BFS
BestFS
A*

HOW TO START

There are two options.
1) Double click MazeSolver.bat (only windows)
2) Using command line
Linux users:
a) Open console and follow steps b and c for windows

Windows users:
a) Start - Run - write " cmd " - enter.
b) Using cd command go to the directory where compiled code is.
c) Run
java Gui
where
filename : A file containing a maze at the format descriped above
algorithm number : Which Algorithm to use. Specifically:
1 : Non Recursive DFS
2 : Recirsive DFS
3 : BFS
4 : BestFS
5 : A*

If you don't select an algorithm then you just load the maze file.
Else if you entered a valid value the algorithm will start immediately.
Of course you must have java installed at your computer.

MENU OPTIONS

1) File - Open : Load a maze file
2) File - Exit : Exit application
3) Help - Help : A little help
4) Help - About : About the application


BUTTONS

Start/Pause : Start / Pause algorithm
Step : Another step is shown
Open File : Load a maze file
Select Algorithm : Select which algorithm you want to run.
Slider : Using slider you can adjuct the delay between steps. Option available are from 50 miliseconds to 500 miliseconds.

COULOR CODE

White : Path
Black : Wall
Red : Solution path
Green : Search frontier
Blue : Closed set
Pink : Start
Orange: Exit


LOADING A MAZE FILE

Use the file - open file menu or the Open File button or just press CTRL + O
From the new window select the file you want and click open.
Sometime the file must be at the same directory with the code.


STARTING

After successful load select the algorithm you want form Select Algorithm list.
Step button will show a step. Start/Pause button starts and stops when the button is pressed again.
If you paused it you can run it again til the end by pressing Start/Pause. If you want to see step press Step.

EXITING

Select File - Exit or press CTRL + X or press the X button at the right up corner.


ADDITIONAL INFORMATION

While program runs you see some information at two linees up to the maze.
First line show the time since you started the algorithm til it finishes. If it finished successfuly you see next to it the real time in nanoseconds( 1 bilion nanoseconds = 1 second).
Second line shows:

Search frontier: X Y Closed set : Z Path: W
X : Current size of search frontier
Y : Max size of search frontier til now
Z : Current size of closed set
W : Path size in steps.
Last one is showed when solution is found.

If an algorithm is running you cannot load another maze file or start other algorithm. You have to wait until it finishes.

Maze solver can be downloaded from http://andpapad.googlepages.com or click here.
If you want the source code you can send me an e-mail at my email( andpapad@gmail.com ).

Del.icio.us

1 comment:

Anonymous said...

sip

Related Posts Plugin for WordPress, Blogger...