maze solving
I'm wanting some help with regards to what is possible in java.
I'm writing a mouse than can solve a 2D maze, 16*16 cells. I'm wanting to make sure the mouse can explore the maze and then solve it based on all the routes its found. I figured I could use the faster flood algorithm once I have solved the maze since that would be allowed given I have aquired all the data. I was wondering if any one knew how I could get my mouse to explore the maze fully, recognise that fact and if it say could explore as far as it could make it follow a path back to the start of it finished search? I guess I'd have to use arrays and maybe stacks to implement this.
Any code snippets/ideas would help so I could visualise the actual code and how to start writing it.
[776 byte] By [
itendsnowa] at [2007-11-27 1:23:46]
# 1
I'm not sure I understood. How is this different from depth first search? In depth first search you would maintain a "bread crumb"-like trail to lead you back to the start. If you always choose the different forks as "take the left most road first, and on my way back, take the one to it's right next", then you'd definitely explore the maze fully.
# 2
Hmm, I'm also not clear as exactly what you want to figure out.
If you simply want the shortest path out of the maze, a simple breadth-first search should do. Read up on Breadth-First Searches here if you need to http://en.wikipedia.org/wiki/Breadth_first_search. BFSs are fairly easy to implement using a LinkedList. They usually run pretty fast, but use up a lot of memory.
If you want to figure out if the mouse can traverse the whole maze, you can use a flood-fill algorithm and compare the area traversed and the total area of the maze. http://en.wikipedia.org/wiki/Breadth_first_search for info on flood-fill algorithms. These are also fairly easy to implement if you use recursion.
