Old Content:

MazePath, in Java

April 14, 2009 by Kyle Brady
Tags: Code Samples, Full Code Release, Java
As required by the FTC, a Full Disclosure is available - this piece adheres to the Code of Ethics

---

This project is similar to ConnectedComponents and KnightJumps, except that the goal is to find the shortest path between a start and end point, according to directional preference (North-East is preferred over South-East, for example) and move weights (diagonals = sqrt(2), not 1).  There are walls, and you're allowed to move diagonally.  Example mazes can be found in the ProjectDescription, with solutions.

This uses Dijkstra's Algorithm to find the shortest path in reverse:  dijkstra() and checkNeighbors().  After this is completed, the path is traveled forwards in order to mark it:  findPath() and compareNeighbors().  However, this code only works on examples up to somewhere near 70x70 input mazes, as the findPath() was written using recursion and it runs out of memory past a certain point.  A more correct version would be to use a looping mechanism to handle large examples.

Finally, I used the Java PriorityQueue, and not myPriorityQueue.java that is mentioned, even though it's included with the source below for reference.

It was due at midnight tonight, and I was done earlier, so this is a scheduled post.

All code is now available via SVN, and a web browsing utility.

Note:  I am not advocating using this code in place of doing your own homework, or in any situation other than pure interest.  However, in the event that you do, I am not responsible for any resultant issues (legal, moral, or ethical) that may arise.  Finally, I am not presenting these as perfect cases, the best way to approach the problems, nor the fastest.  They are, simply, viable solutions.

Old Content posts are leftovers from a less structured, less civilzed era that are kept for posterity.
Kyle can be found on Twitter and MySpace, or reached via email.