|
overview
Rat is a maze solving library and os x application. the core of the maze solving code is contained in ratlib and a very simple and unintuitive gui is contained in ratapp. All source code and Xcode projects are available here as well.
howto
The os x application isn't terribly intuitive. These instructions detail how to use the application without becoming seriously frustrated. Hopefully.
To use your own maze image, convert it to a png file, name it maze.png and place the file at Rat.app/Contents/Resources/maze.png. You can navigate to this directory by right-clicking on Rat.app and selecting Show Package Contents.
After starting the application, position the START marker by pressing Apple+1 and clicking at the start location in the maze. Similarly, press Apple+2 and position the END marker. Finally, press Apple+G to try to find a solution. When a solution has been found or all possibilies have been explored, the maze will re-draw showing the explored area (in blue) and the solution (if any) as a red line.
To save the resulting solution, press Apple+S and it will be written to ~/Desktop/Solution.png. Yeah, no Save As dialog. Get over it.
algorithm
coming soon
todo
1. adjustable threshold for pixel_similar() which governs how much the "floor" color can vary
2. hole-in-the-wall detection that distinguishes between a turn and an unintentional gap
3. improved memory efficiency by tracking sets of contiguous pixels instead of each individual pixel
example code
Incorporating ratlib into your application is fairly simple. Before you can do so, however, you need to be able to get a byte array of the bitmap pixel data for the image in RGB form and no alpha channel.
// initialize the ratlib library. this only needs to be done once.
ratlib_init();
// create a new image with some image data.
ratlibimage_t *image = ratlib_image(pixel_data, 0, bytes_per_pixel, width, height);
// create a new session. ratlib supports multiple simultaneous sessions. each session
// has a single image associated with it. the image data is not modified and can be
// shared between multiple sessions
ratlibsession_t *session = ratlib_session(image);
// initialize begin and end points and configure the session with them
ratlibsession_setbeg(session, point_beg);
ratlibsession_setend(session, point_end);
// blocks until the solution process is complete
ratlibsession_solve(session);
// the solution, if any, is contained in the session and is in the form of a series of
// linked points. traverse the points to draw the solution.
ratlibpoint_t *point = session->solution;
do {
// do something with point->x, point->y
}
while (NULL != (point = point->prev));
example solutions
Below are three examples of the output of the program. In cases where the maze "leaks", it is necessary to edit the image to close those leaks - as has been done in the second example.
This first maze is an example of a pixel-perfect computer-generated maze. I don't mean that its creation was automated (it wasn't), but rather that it was created on a computer from scratch. There are no fuzzy lines. All right angles. It is perfect for a simple and very efficient maze solving algorithm that works with straight lines.
This second maze is much less precise than the first. To begin with, the start and end points of the maze are open and I had to edit the image to close them off. Additionally, the "walls" of the maze are themselves imprecise; and the "floor" color is not uniform (which necessitated that I start doing a pixel_similar() instead of a pixel_equals()). Thankfully, there are no holes in any of the walls, so it is still relatively simple. You may notice in the solution that there are little white dots near the black walls. This is something that could be controlled by adjusting the threshold of pixel_similar().
This third maze is another pixel-perfect, computer-generated maze which is solvable without any modifications.
browse
The code below includes the maze solving code from ratlib as well as the supporting code for lists, atomic operations, memory management, logging, threading, etc - that I use in many projects; it's good stuff - as well as the ratapp code, which isn't very important, unless you care about reading and writing images using CoreGraphics (which isn't necessarily done correctly).
< support code >
atomic.h
cobject.c
cobject.h
logger.h
memlock.c
memlock.h
opool.c
opool.h
semaphore.c
semaphore.h
slist.c
slist.h
thread.c
thread.h
< maze code >
ratlib.c
ratlib.h
ratlibgrid.c
ratlibgrid.h
ratlibimage.c
ratlibimage.h
ratlibpoint.c
ratlibpoint.h
ratlibsession.c
ratlibsession.h
< application code >
main.m
ratlib.h
AppController.m
AppController.h
MazeView.m
MazeView.h
RatAppDelegate.m
RatAppDelegate.h
download
ratlib-xcode-20091117-1.zip
ratapp-xcode-20091117-1.zip
ratapp-20091117-1.zip
| 
