🚀 go-pugleaf

In article <1992Aug6.225108.572@ccu1.aukuni.ac.nz> rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:
>    OK a slight extension to the question I asked.
>I also want every possible room to be connected ......
>And I don't want to enter the maze from one point and exit at another
>I just need it so that it generates a set of connections between all 
>rooms :(    it's a bit of a dog but it's something I need to solve.
>
>Can anyone help at all ??
>
>+-----------------------------------------+--------------------+
>| Name   : Ross Williamson                |Auckland University | 
>| E-Mail : rossw@ccu1.aukuni.ac.nz        |    New Zealand     |
>| Of course these opinions are my own and thank !! for that    |
>+--------------------------------------------------------------+
>"Oh Zaphod he's in his cabin signing photos of himself, 'To 
>myself with frank admiration" Arthur Dent - From the Hitchhikers
>Guide To The Galaxy.

There was a very good maze generating algorithm for my TI-99.  It sets
up an array, chooses a corner, then starts doing two-step random walks,
placing a direction marker at each step.  The random walk would avoid
any square that has already been stepped on, or any that are outside the
dimensions of the array.  If the program finds itself trapped in a
dead-end, where no more steps can be taken without stepping on a pre-
trampled square, then it would retrace its steps, using the directional
markers to guide it, and look for the first place where it can branch
out.  Then it would continue walking randomly off that branch, until it
again arrives at a dead-end, where the whole process repeats itself.
Remember when implementing this algorithm to always take two consecutive
steps in the same direction, even when back-tracking.

This algorithm fills up an array with passageways, and it guarantees
that there can only be one path from one point in the maze to another.
I've used it to generate huge 2D mazes, which I printed out and gave to
my siblings to solve.

Hope this helps.
Phat.

In article <1992Aug6.225108.572@ccu1.aukuni.ac.nz>, rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes...
>I also want every possible room to be connected ......
>And I don't want to enter the maze from one point and exit at another
>I just need it so that it generates a set of connections between all 
>rooms :(    it's a bit of a dog but it's something I need to solve.

Well, a decent algorithm for which I can take no credit follows.
	- Mark all of the squares in the maze as unused.
	- Start at any square in the maze.
	- Record all possible unused maze squares around the square (referred
		hereafter as possible next squares.)
	- While there are still unused maze squares:
		- Randomly choose one of the possible next squares.
		- Mark it used.
		- Connect it with the currently used squares next to it.
		- Add adjacent unconnected squares to the possible next square
			 list.

Different maze types can be generated by fiddling with the
connection target and possibly with the next random target.

While I've not gotten around to playing with this algorithm yet, I've
seen it used, and it works fine.
	
Credit for this algorithm goes to Scott Berry (FXSDB@acad3.alaska.edu) who
pointed it out to me when I thought I needed something similar.
Whether he had the genius to steal it from someone else, or just 
created it himself, I cannot say.
=============================================================================
-Mike Kienenberger                       SXMLK@ALASKA           (BITNet)
 University of Alaska Computer Network   SXMLK@acad3.alaska.edu (Internet)
 University of Alaska-Fairbanks

In article <1992Aug6.225108.572@ccu1.aukuni.ac.nz>, rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:
 >     OK a slight extension to the question I asked.
 > I also want every possible room to be connected ......
 > And I don't want to enter the maze from one point and exit at another
 > I just need it so that it generates a set of connections between all 
 > rooms :(    it's a bit of a dog but it's something I need to solve.
 > 
 > Can anyone help at all ??

I'll try:

Initializing:
1. start with an array sized sx, sy filled with walls.
   coordinates outside array return walls too.
   sx and sy are ODD numbers!
2. go to a random position (x,y) in range (1..sx, 1..sy)
   make sure the x and y of the position are EVEN numbers!
   set it to a corridor.

Start of loop:
3. choose a random direction that won't lead you outside the array in
   two steps.
   note: i'm talking primary directions N, S, W and E here.
4. move one step in the dir from 3) and set cell to a room
5. do it one more time
6. now for the timeconsuming part:
   repeat 
     select a random position
     same restrictions to x and y as in 2.
   until you're in a corridor (not in a wall)
7. goto 3 till no more space for corridors.
   the number of times you repeat this is of course dependant on sx and sy
   (sx*sy/4  +/- something)

This will make a labyrinth with walls as thick as a corridor (as in
wolf3d), no entrance or exit (but those can easily be placed).

Most important, all corridors are connected, due to point 6.

I'd like to hear from anyone about suggestions on the random corridor selection
generator in 6.

For completeness, this algorithm was spun from the bottom of my head, as I
remember Acorn User magazine used it in their 3D MAZE game for the BBC micro 
some years ago...

I even 'ported' this game to 8086 and CGA (using Turbo Pascal), so if anyone
is interested I could post it to the net.  Please tell me via e-mail.
I guess I won't break any laws, as the BBC BASIC source was available in the
very magazine.

As I was probably 12-13 years old at the time, I want no flames for coding
peculiarities... ;)

 > +-----------------------------------------+--------------------+
 > | Name   : Ross Williamson                |Auckland University | 
 > | E-Mail : rossw@ccu1.aukuni.ac.nz        |    New Zealand     |
 > | Of course these opinions are my own and thank !! for that    |
 > +--------------------------------------------------------------+
 > "Oh Zaphod he's in his cabin signing photos of himself, 'To 
 > myself with frank admiration" Arthur Dent - From the Hitchhikers
 > Guide To The Galaxy.

-- 
Cheers from Robert Schmidt, aka Ztiff Zox, aka Buuud (IRC).  E-mail to 
robert@solan.unit.no, snail-mail to Stud.techn. Robert Schmidt, Stud.post 170,
Norwegian Institute of Technology, 7034 Trondheim, NORWAY          

Warlords: Now do you think my .sig is boring enough?

robert@solan.unit.no (Robert Schmidt) writes:

>In article <1992Aug6.225108.572@ccu1.aukuni.ac.nz>, rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:
> >     OK a slight extension to the question I asked.
> > I also want every possible room to be connected ......
> > And I don't want to enter the maze from one point and exit at another
> > I just need it so that it generates a set of connections between all 
> > rooms :(    it's a bit of a dog but it's something I need to solve.
> > 
> > Can anyone help at all ??

[ deleted some stuff ]

>I even 'ported' this game to 8086 and CGA (using Turbo Pascal), so if anyone
>is interested I could post it to the net.  Please tell me via e-mail.
>I guess I won't break any laws, as the BBC BASIC source was available in the
>very magazine.

Yes, could you please post it to the net or e-mail it to me?

Thanks in advance,

-Conrad