Home

Electronic Projects
  • Micromite Microcontroller
  • Micromite Plus
  • The Microbridge
  • DDS Signal Generator
  • Super Clock
  • Boat Computer MkII
  • Parking Assistant
  • Micromite LCD Backpack
  • ASCII Video Terminal
  • GPS Controlled Clock
  • GPS Tracker
  • Colour Maximite Computer
  • The Original Maximite
  • The mini Maximite
  • Intelligent Fan Controller
  • GPS Synchronised Clock
  • GPS Boat Computer
  • GPS Car Computer
  • Making the GPS Computer
  • Energy Meter Firmware
  • ISM Band Scanner
  • Utility Power Supply
  • Precise Voltage Reference
  • Game of Pong
  • Water Level Meter


  • General Articles
  • Problems in Open Source
  • The Maximite Story
  • Programming PIC Micros
  • MMBasic on the UBW32
  • The TFT Maximite
  • Surface Mount is Easy
  • Measuring Capacitor ESR
  • EM-408 GPS Module
  • SG12232A LCD Driver
  • Custom PC Boards
  • The Gerber Format


  • Reviews
  • Hantek DSO-2250 Scope
  • Rigol DS1000 Scope
  • PIC C Compilers
  • Brickbats


  • PC Software
  • Weather Station
  • Mazing


  • About

     

     

     

    This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Australia (CC BY-NC-SA 3.0)

    Mazeing

     

    Mazeing is a program that draws mazes for you to solve. Each maze is unique and only has one path from entrance to exit.

    Mazeing can draw them on your computer screen and you can trace your path through the maze using your mouse. Alternatively you can print the maze out and solve it with a pen. And, you can generate mazes of amazing (pun intended) complexity, although you will need a high resolution display or printer to show them.

    Mazeing was created over 14 years ago as an exercise in programming using Microsoft's then new Foundation Classes. Mazeing was a minor hit in its day and was available on the early Internet. It even found its way onto the "cover disks" (floppy disk) popular with computer magazines back then.

    The Program

    Mazeing is a very lightweight in terms of the computer resources it uses. There is no installation, it only consists of two files (the program and the help file) and all you do is just copy them onto your hard disk and double click on the executable (.exe) file to run it.

    The program was designed for Windows 3.1 and amazingly it also runs on everything from Windows 95 to Windows 7 (32 bit).   But, in the 64 bit versions of Windows Microsoft has removed support for 16 bit apps so Mazeing cannot run in that environment. It is a pity but I guess that Microsoft had to retire this technology sometime.

    Removing the program is as simple as deleting the files. So, why not give it a go?   The program is available for download below, as is the source code.

    The image on the left shows a typical maze of medium complexity and below you can see the same maze which has been solved.

    If you cannot find your way through a maze then you can always ask Mazeing to do it for you.

    Printing Mazes

    One of the great features of Mazeing is that it can automatically generate and print as many mazes as you wish. For each maze generated you can specify the number of normal copies to print (ie. without a solution) and the number of copies with a solution.

    Why is this good?

    To quote from the help file:

    You could have fun with your family. Print a number of mazes with one copy for each member, then have a competition to see who completes the most mazes first. Because you all have a copy of the same maze the competition is fair. You can also print one copy of the solution for each maze in case no one can work it out.

    Going on a long camping trip? You could print enough mazes to keep yourself occupied for weeks!

    The Algorithm

    The algorithm for generating a maze is amazingly (there is that word again) simple, it is the frills that has made it complicated.

    How to make a maze:

    1. Pick a cell on an existing path. Pick a cell at random next to it which is not already part of a path and remove the wall between the cells, move to the new cell and repeat this step. When you cannot proceed any further (all cells around the current cell are part of paths) then you have finished with that path. At random pick another cell on some path and repeat the whole process.
    2. You are finished generating the maze when you have tried starting a path from all cells which are part of a path (which will eventually be all cells in the matrix).
    3. To start you need to select one cell and declare that it is a path, from then on the algorithm will generate a maze with only one path from any cell to any other. All you do now is select at random an entrance and exit.

    Mazeing is based on this algorithm but to make the main path through the maze more complicated it (the main path) is generated first.

    This main path then becomes the seed for generating the rest of the maze.

    To generate the main path pick a cell at random at the top, this is the entrance. Generate a path, this is similar to generating a path as described above except that when you cannot proceed any further (all cells around the current cell are part of paths) you back out and try alternative routes until you hit the bottom margin which becomes the exit.

    Save the path as this is the solution.

    To make this algorithm more efficient a number of frills were added:

    1. If the main path is too simple (length is less that a specified fraction of the total cells) then abort the whole thing and start again.
    2. If while generating the main path there is too little progress (due to backing out of blind spots where all neighbours are already part of the path) then scan back through the path and pick the spot closest to bottom (exit) and restart the path generation from there. If you have done this a certain number of times then abort the whole thing and start from the entrance again.
    3. While generating the main path do not move to a cell which has been visited (in addition to already used) in previous recursions while generating this path.


    The source code is available for download below. It is written in an ancient version of Microsoft Visual C++ using the Microsoft Foundation Classes. As a result it will be almost impossible to duplicate the original development environment but the source is provided as the algorithm might be of interest to someone.

    Downloads

    Program and help file. Read the README.TXT for installation instructions. DOWNLOAD
    Source code DOWNLOAD