Software‎ > ‎

Multi-point maze solver

This Java tool is a simple application of the Lee algorithm for (rectilinear) maze routing, applied to a non-grid space using Bresenham's line algorithm.
It was written as part of a course on VLSI algorithms, in Java. The Processing library (3.0.1) allowed quick development of a basic graphic interface. The user can draw a maze and define points within it that should be connected.

Screenshot of screen for editing maze

The Lee algorithm can then be used to find the shortest path (or an unusually long one, if desired).

Screenshot of maze with route between two points.

Altering the clearance required by the wires, paths through narrower openings can be enabled:
Route through maze passing through narrower gaps between barriers.

Large numbers of endpoints can be defined, and the router will attempt to connect each to an existing path.
Route connecting many endpoints in the maze.

Mazes can be imported and exported as segment-based text files, for storage and possible use in other systems.
Maze import/export screen with maze code.

A standalone archive for 32-bit windows is attached. The files in /source contain the original code, which can be executed in and exported for other operating systems with the Processing environment. Further development is possible if desired.
Martin Berka,
Jul 13, 2017, 8:24 PM