a Maze generator program

Basic and Machine Language

Moderator: Moderators

nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

a Maze generator program

Post by nippur72 »

Here is a random maze generator program that I wrote. It draws a fully connected maze (with no islands).

The algorithm is quite simple: it does have a "drilling head" that is moved randomly as long as it can without going into an already existing tunnel. When the head can no longer be moved, it steps back finding another drilling point. When there are no more drilling points the maze is completed.

It is a slight different version from the classical algorithm because it doesn't use any stack; the maze itself serves as memory.

It's quite slow so VICE's Warp function is suggested.

Code: Select all

  basic start compact
      100 rem === inits ===     
      105 dim d(4,5)   
		110 for t=0 to 3
		120   for i=0 to 4
		130      read d(t,i)
		140   next
		150 next
		155 dim m(4):for t=0 to 3:m(t)=t:next
		160 rem === fill empty maze ===
		170 for t=0 to 512
		171   poke 7680+t,160
		172   poke 38400+t,3
		173 next
		188 rem nv=0:s=7680:goto270
		189 rem === starting point ===
		200 v = 7680+10*22+10
		205 s = 7680
		210 nv = 0		 
		220 rem === main loop ===
		225 poke v,22
		230 nv = nv + 1
		240 x = m(0):gosub 500:if n=0 then goto 300
		250 x = m(1):gosub 500:if n=0 then goto 300
		252 x = m(2):gosub 500:if n=0 then goto 300
		255 x = m(3):gosub 500:if n=0 then goto 300
		260 rem === find another drilling point ===
		260 poke v,32
		265 nv=nv-1
		266 if nv=0 then goto 295
		270 if peek(s)=22 then v=s:goto 240
		280 s = s + 1
		285 if s = 8192 then s = 7680  
		290 goto 270
		295 get a$:if a$="" then 295
		296 run
		300 rem === drills ===
		310 v = z 
		319 rem if rnd(1)< 0.20 then goto 280
	   320 if rnd(1)< 0.5 then goto 220
		321 t=int(rnd(1)*4)
	   322 i=int(rnd(1)*4)
      323 z=m(t):m(t)=m(i):m(i)=z
		330 goto 220
		500 rem === check drilling direction ====
		520 if x=0 then z = v - 22:goto 560
		530 if x=1 then z = v + 1 :goto 560
		540 if x=2 then z = v + 22:goto 560
		550 if x=3 then z = v - 1
		560 if z<7680 or z>8208 or peek(z)<>160 then n=5:return
		561 if int((z-7680)/22)=(z-7680)/22 then n=5:return
		565 n = 0
		570 for t=0 to 4
		580   if peek(z+d(x,t))<>160 then n=n+1
		590 next
		595 return 
		1000 rem === drilling head directions ===
		1005 data +1,-1,-23,-22,-21
		1010 data +22,-22,-21,+1,+23
		1020 data +1,-1,+21,+22,+23			
		1030 data +22,-22,-23,-1,+21					 	       
  basic end
User avatar
orion70
VICtalian
Posts: 4337
Joined: Thu Feb 02, 2006 4:45 am
Location: Piacenza, Italy
Occupation: Biologist

Post by orion70 »

Excellent program, very elegant design. :wink:

Line number 260 is repeated; the space between "data" and the numerical list and the "+" sign give syntax error. These things corrected. For those who want to download the routine saved on a d64, HERE is the link (or if you, Nippur, want to put it in your own website).

The screenshot reminds me of RTFK...
Image

:D
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Post by nippur72 »

orion70 wrote:Line number 260 is repeated;
oops... didn't realize. I wrote it in DASM+macro tool, where you can actually have repeated lines.
orion70 wrote:the space between "data" and the numerical list and the "+" sign give syntax error.
I don't understand why... if I type it, I get no errors. Did you type it on the VIC-20? Or have you used some tokenizer tool? If so, check it as it might be bugged. I say this because my own tokenizer tool had a bug in the DATA statement.
orion70 wrote:The screenshot reminds me of RTFK...
That's quite right, indeed I was trying to add an "infinite levels" feature to that game!

P.S. increase 0.5 to 0.95 (or more) in line 320 to get longer straight corridors.
Iltanen
Vic 20 Devotee
Posts: 200
Joined: Tue Jul 17, 2007 6:08 pm

Post by Iltanen »

Indeed a very bright idea. I hope you can add that to RTFK!
User avatar
Kweepa
Vic 20 Scientist
Posts: 1314
Joined: Fri Jan 04, 2008 5:11 pm
Location: Austin, Texas
Occupation: Game maker

Post by Kweepa »

You might be able to get some ideas for (size) optimization, if you need them, from this thread:
http://www.worldofspectrum.org/forums/s ... 16&page=34
Beware, there are nearly 1000 posts!
Here are some of the fruits:
http://reptonix.awardspace.co.uk/sinclair/oneliners/
See particularly the overhead map screenshots from the (3D!) maze games.

Just like yours, and unlike fort knox, there are no islands, so presumably you'd have to randomly (?) pick some points to drill through to connect up the maze a bit.
Last edited by Kweepa on Sat Jun 28, 2008 3:36 pm, edited 1 time in total.
User avatar
orion70
VICtalian
Posts: 4337
Joined: Thu Feb 02, 2006 4:45 am
Location: Piacenza, Italy
Occupation: Biologist

Post by orion70 »

nippur72 wrote:I don't understand why... if I type it, I get no errors. Did you type it on the VIC-20? Or have you used some tokenizer tool? If so, check it as it might be bugged. I say this because my own tokenizer tool had a bug in the DATA statement.
Yep, you're right. It's TOK64 and I remember I had some issues with DATA statements with Evil Castle as well. :?
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Post by nippur72 »

orion70 wrote:Yep, you're right. It's TOK64 and I remember I had some issues with DATA statements with Evil Castle as well. :?
I guess it's because DATA and REM are special statements so that the text that follows has to be treated literally, without no token expansion.
carlsson
Class of '6502
Posts: 5516
Joined: Wed Mar 10, 2004 1:41 am

Post by carlsson »

Is tok64 better than petcat which comes with VICE? At least petcat is irregularly updated when bugs are found.
Anders Carlsson

Image Image Image Image Image
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Re: a Maze generator program

Post by nippur72 »

not related to VIC-20 or this post's program, but there is a nice discussion about generating mazes here:

http://journal.stuffwithstuff.com/2014/ ... and-mazes/

Interesting if you are going to write a maze based game.
User avatar
orion70
VICtalian
Posts: 4337
Joined: Thu Feb 02, 2006 4:45 am
Location: Piacenza, Italy
Occupation: Biologist

Re: a Maze generator program

Post by orion70 »

Very interesting, thank you! Maybe it was already discussed here, but I recall an excellent essay about mazes, their maths, early micros, and the dungeons in games. I've read it some time ago, and strongly suggest it: http://10print.org/
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Re: a Maze generator program

Post by nippur72 »

reviving this very old thread.... I am still thinking about a maze generator, now for a possible III episode of Raid On Fort Knox.

The maze generation has a restriction though: in ROFK the "guards" always move forward, turning left or right only when they bump into a wall (either a 90 deg curve or a "T"). So you have to make sure that all the corridors of the generated maze can be visited with no unreacheable zones.

I tried to reason about and derive some rules that can work in all cases, the only one I figured is that a new corridor must not create two facing T's:

Code: Select all

|       |     
+--- ---+     ; not allowed
|       |     

           |     
---+--- ---+     ; allowed
   |       |     
but it seems difficult to implement in assembly and do it quickly for a on-the-fly maze generation. Perhaps I should fall back to offline generated mazes, but due to memory constraints they can be limited in number (16 or 32 maybe). Maybe I can load them in blocks from tape/disk once the player advances to a new level?

Anyway my initial idea was to have 256 maze randomly generated as in "Pitfall", and cut the gameplay so that a single maze lasts shortly.

Any thoughts?
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: a Maze generator program

Post by Mike »

nippur72 wrote:Here is a random maze generator program that I wrote. It draws a fully connected maze (with no islands). [...]
The maze is guaranteed to have no islands (i.e. it does not contain any cycle), so wouldn't it be more sensible to improve the AI of the guards?
[...] in ROFK the "guards" always move forward, turning left or right only when they bump into a wall (either a 90 deg curve or a "T"). So you have to make sure that all the corridors of the generated maze can be visited with no unreacheable zones.

I tried to reason about and derive some rules that can work in all cases, the only one I figured is that a new corridor must not create two facing T's: [...]
I'd presume a guard (facing to the east like thus: >) would also miss out on an occasion like this:

Code: Select all

           |
           |  <-- unreachable corridor
           |
... --->---+-------
However, if you change the algorithm, so a guard always "keeps his right hand at the wall", he is guaranteed to visit all locations of a cycle-free maze. In the example above, the guard would pass upon entering the junction from the west, but he would turn into the formerly unreachable corridor, when returning from the east.

You could also have two types of guards, those that "keep their right hands at the wall" and those that "keep their left hands at the wall".
User avatar
Kweepa
Vic 20 Scientist
Posts: 1314
Joined: Fri Jan 04, 2008 5:11 pm
Location: Austin, Texas
Occupation: Game maker

Re: a Maze generator program

Post by Kweepa »

You want to have cycles so that you can evade the guards while still getting around.
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Re: a Maze generator program

Post by nippur72 »

Mike wrote: Tue Nov 03, 2020 2:55 pm I'd presume a guard (facing to the east like thus: >) would also miss out on an occasion like this:

Code: Select all

           |
           |  <-- unreachable corridor
           |
... --->---+-------
if the maze follows the rule I described, that corridor will be visited from North to South when the guard comes back from its route. I can't prove it mathematically, but by intuition since the N-S corridor is connected to a non facing T then a guard will bump into it and have chance to visit.

I would like to keep the original AI logic of the guards because it's peculiar to this game and also to make it consistent to a third episode of the chapter (I was thinking about something like "Escape from Fort Knox" or "Raid on Fort Knox: Escape").
Kweepa wrote: Tue Nov 03, 2020 2:55 pm You want to have cycles so that you can evade the guards while still getting around.
Yes but I need to generate them in a controlled way, so that the level isn't too easy. Another option is to add 1-character "inlets" on long corridors where the player can hide and wait.
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: a Maze generator program

Post by Mike »

nippur72 wrote:Yes but I need to generate them in a controlled way, so that the level isn't too easy. Another option is to add 1-character "inlets" on long corridors where the player can hide and wait.
One other idea is to mark the junctions with invisible characters. When a guard arrives at a junction, let him change the direction (preferably disallowing U-turns). This also ensures a guard can visit the entire maze (in the long run), even if the maze has cycles. This method has been used in Paradroid.
Post Reply