Eller's maze generator

Any discussions related to the creation of new hardware or software for the ZX80 or ZX81
Post Reply
User avatar
zsolt
Posts: 194
Joined: Wed Apr 20, 2011 11:43 am
Location: Fót, Hungary

Eller's maze generator

Post by zsolt » Mon Apr 11, 2016 3:48 pm

Dear All,

When I read about drBeep's latest project, then i decided to learn more about the maze generators. Here, in the forum, I found more topics (by Greg and Shaun) but these solutions were slow and/or they did not give real (perfect) mazes.
Then later I found this site (and more other in hungarian too) and typed the algorithm, using ZX Basic.
EMG81.ZIP
The speed was not hair-raising, so I rewrote it in machine code too.
(17.58 KiB) Downloaded 151 times
Contents of the EMG81.ZIP file:

ZX BASIC variants

EllerMaze1print.p - (15x11) using PRINT [< 1 min in FAST mode]
EllerMaze2plot.p - (31x21) using PLOT [> 8 min in FAST mode]
EllerMaze2print.p - (31x21) using PRINT [> 7 min in FAST mode]

machine code variants

EllerMaze1mc.p - (15x11) [~1sec]
EllerMaze2mc.p - (31x21) [~3sec]

EllerMaze1float.p - (16x12) [~1sec] - this shows a floating maze (black) and its shadow (gray) - there are no walls ;)

Folders

<src> - basic / mc source codes

<walk> - playable versions w. sources

In latter folder are (or can be) the first steps to MAZE RACE

Enjoy,
Zsolt
ZX81 (8K), ENTERPRISE 128, [ZX SPECTRUM (48K,+,+128K,+2,+2A), TS1000, TS1500, TS2068, Cambridge Z88, PRIMO A64 (red)]

dr beep
Posts: 1190
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Eller's maze generator

Post by dr beep » Mon Apr 11, 2016 10:22 pm

The maze in 2DMM needs long passages and walking around. The generator is quite easy now, but not derived from any known method.

As for a normal maze (like in 3D random maze) I use a generator that is mostly based on the hunt and kill algorithm
http://weblog.jamisbuck.org/2011/1/24/m ... -algorithm

Only alteration is that I will start a loop from left above to right under and test if a field has free unused fields in any direction if so go in a valid direction until locked in. Then do next field. Also easy to code in Basic and also quite fast for BASIC.

In MC I have a generator in app. 200 bytes and a maze sized 19x19 in 100 bytes.

User avatar
zsolt
Posts: 194
Joined: Wed Apr 20, 2011 11:43 am
Location: Fót, Hungary

Re: Eller's maze generator

Post by zsolt » Sun May 01, 2016 1:55 pm

Hi,

Here comes the first version of the Maze Race'81 - you have 3:33 to:
MazeRace333.p
solve the most possible maze
(1.46 KiB) Downloaded 104 times
I made a little video too.
dr beep wrote:As for a normal maze (like in 3D random maze) I use a generator that is mostly based on the hunt and kill algorithm
http://weblog.jamisbuck.org/2011/1/24/m ... -algorithm

Only alteration is that I will start a loop from left above to right under and test if a field has free unused fields in any direction if so go in a valid direction until locked in. Then do next field. Also easy to code in Basic and also quite fast for BASIC.
It is interesting :o i found a site, where the maze creator algorithms are compared, and the "hunt and kill" seems 5 (7) times slower than the "Eller". :shock: Share your solution, please.

Regards,
Zsolt

ps: I have an unfinished BBC Basic port (in very alpha state). I typed in the Basic variant of the algorithm - here is the result:
the BBC Basic (80) is ~4 times faster then ZX Basic?
. :cry:
ZX81 (8K), ENTERPRISE 128, [ZX SPECTRUM (48K,+,+128K,+2,+2A), TS1000, TS1500, TS2068, Cambridge Z88, PRIMO A64 (red)]

berk
Posts: 6
Joined: Sat Apr 16, 2016 11:49 pm

Re: Eller's maze generator

Post by berk » Sun May 01, 2016 3:52 pm

Hello Zsolt,

it is very nice game with interesting idea - thank you for post.

The only notice - it is too easy to solve maze. May be the reason is that paths are too direct - is there some option for create them little more short?

User avatar
zsolt
Posts: 194
Joined: Wed Apr 20, 2011 11:43 am
Location: Fót, Hungary

Re: Eller's maze generator

Post by zsolt » Mon May 02, 2016 11:22 am

Hi,
berk wrote:The only notice - it is too easy to solve maze. May be the reason is that paths are too direct - is there some option for create them little more short?
Sorry for my poor english, but how to understand your question? :shock:
ZX81 (8K), ENTERPRISE 128, [ZX SPECTRUM (48K,+,+128K,+2,+2A), TS1000, TS1500, TS2068, Cambridge Z88, PRIMO A64 (red)]

berk
Posts: 6
Joined: Sat Apr 16, 2016 11:49 pm

Re: Eller's maze generator

Post by berk » Mon May 02, 2016 11:47 am

Sorry for my English :-)

In my opinion path from start to finish is often too direct. Should be little more complex with more branches.

dr beep
Posts: 1190
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Eller's maze generator

Post by dr beep » Mon May 02, 2016 9:28 pm

zsolt wrote:
It is interesting :o i found a site, where the maze creator algorithms are compared, and the "hunt and kill" seems 5 (7) times slower than the "Eller". :shock: Share your solution, please.

Source of game 5.
http://sinclairzxworld.com/viewtopic.ph ... ack#p16917

I have it in a described version with all comments, but I can make it also a generic diagram.

dr beep
Posts: 1190
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Eller's maze generator

Post by dr beep » Mon May 02, 2016 10:30 pm

The algorithm I use:

Code: Select all

set all field unused
for x=1 to maxx
    for y = 1 to maxy
test_field:
        set track false
        save x and y
do_path:
        set field used
        set all directions unused
        do          
          save x and y again
          do random direction
          if next field unused
             break wall, set track true
             drop save, new x and y as start, go to do_path 
          end if
          get saved x and y; undo move to next field
        loop until all directions tested
        ; here all directions are tested, either path blocked or field is surrounded with used fields
        ; on stack still a previous x y position. 
        get saved x and y; original hunt position
        if track=true then goto test_field ; path created but ended somewhere so test again
    next
next
;maze ready

User avatar
zsolt
Posts: 194
Joined: Wed Apr 20, 2011 11:43 am
Location: Fót, Hungary

Re: Eller's maze generator

Post by zsolt » Wed May 04, 2016 1:51 pm

Hi,
berk wrote:In my opinion path from start to finish is often too direct. Should be little more complex with more branches.
I think it depends only on the random number generator - sometimes it gives quite difficult maze (more branches).
EMG81_walk.png
see the "walkig parts" of the 1st post
EMG81_walk.png (27.77 KiB) Viewed 2355 times
dr beep wrote:The algorithm I use:

Code: Select all

set all field unused
.
.
;maze ready
Thanks, i will try it
Zsolt
ZX81 (8K), ENTERPRISE 128, [ZX SPECTRUM (48K,+,+128K,+2,+2A), TS1000, TS1500, TS2068, Cambridge Z88, PRIMO A64 (red)]

berk
Posts: 6
Joined: Sat Apr 16, 2016 11:49 pm

Re: Eller's maze generator

Post by berk » Wed May 04, 2016 8:50 pm

I think it depends only on the random number generator - sometimes it gives quite difficult maze (more branches).
Great! 8-)

Post Reply