Xref: utzoo comp.sources.wanted:14508 alt.sources.d:1175 rec.games.misc:12841 rec.games.programmer:2693
Path: utzoo!utdoe!ontmoh!attcan!telly!problem!compus!lethe!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!mel.dit.csiro.au!yarra!melba.bby.oz.au!gnb
From: gnb@bby.oz.au (Gregory N. Bond)
Newsgroups: aus.games,comp.sources.wanted,alt.sources.d,rec.games.misc,rec.games.programmer
Subject: Re: Maze generation
Message-ID: <1990Dec13.230745.29321@melba.bby.oz.au>
Date: 13 Dec 90 23:07:45 GMT
References: <1215@syacus.acus.oz>
Sender: news@melba.bby.oz.au
Organization: Burdett, Buckeridge and Young Ltd.
Lines: 48
In-Reply-To: martins@syacus.acus.oz's message of 13 Dec 90 01:19:40 GMT

>>>>> On 13 Dec 90 01:19:40 GMT, martins@syacus.acus.oz (Martin Schwenke) said:

Martin> I am interested in software or algorithms for generating mazes with
Martin> unique solutions. I am also, but less, interested in maze solving
Martin> algorithms, and programs.

OK, build it by induction.

1) Select a start square.  This is a uniquely connected maze.

Induct: 
2) Given a uniquely connected maze of n squares, we can make a
   uniquely connected maze of n+1 squares by adding a new square
   adjacent to the existing maze and connecting it by removing wall
   only.

3) Choose arbitary start and end squares.  Guaranteed only 1 way
   through between any two squares.

However, this generates "choppy" mazes, with very few long runs.  Much
better looking mazes can be generated by slightly changing the
algorithm so that at point 2) instead of adding just one square, you
add a "corridor" that is straight say 80% of the time, and turns
randomly 20% of the time, and join that on to the existing maze at
only one point.  The length of the coridor can be limited (say, the
length of the short size fo the maze) or run untill it gets boxed in
by existing maze elements.

I experemented a lot with maze generation many years ago on a 64k Z80
system.  With fairly compact encoding (4 cells/byte) and a 60K TPA, I
was producing mazes approx 150 x 2000.  If I could read 8inch 1.2MB
CP/M disks, I'd send you the programs, but they don't fit in the Sun
tapedrive slot...

As for solving.....

With any uniquely connected maze it is possible to solve it by the
"right hand rule" - stick your right hand on the wall and keep
walking, always turning right at every opportunity.  The sunview maze
screenblanker does that.  (I once hacked it to leave a grey trail
where it had visited - most interesting graphical view of the
algorithm at work).

Greg.
--
Gregory Bond, Burdett Buckeridge & Young Ltd, Melbourne, Australia
Internet: gnb@melba.bby.oz.au    non-MX: gnb%melba.bby.oz@uunet.uu.net
Uucp: {uunet,pyramid,ubc-cs,ukc,mcvax,prlb2,nttlab...}!munnari!melba.bby.oz!gnb