Eller's maze generator
Eller's maze generator
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.
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
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.
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)]
Re: Eller's maze generator
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.
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.
Re: Eller's maze generator
Hi,
Here comes the first version of the Maze Race'81 - you have 3:33 to:
I made a little video too.
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?.
Here comes the first version of the Maze Race'81 - you have 3:33 to:
I made a little video too.
It is interesting i found a site, where the maze creator algorithms are compared, and the "hunt and kill" seems 5 (7) times slower than the "Eller". Share your solution, please.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.
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?.
ZX81 (8K), ENTERPRISE 128, [ZX SPECTRUM (48K,+,+128K,+2,+2A), TS1000, TS1500, TS2068, Cambridge Z88, PRIMO A64 (red)]
Re: Eller's maze generator
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?
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?
Re: Eller's maze generator
Hi,
Sorry for my poor english, but how to understand your question?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?
ZX81 (8K), ENTERPRISE 128, [ZX SPECTRUM (48K,+,+128K,+2,+2A), TS1000, TS1500, TS2068, Cambridge Z88, PRIMO A64 (red)]
Re: Eller's maze generator
Sorry for my English
In my opinion path from start to finish is often too direct. Should be little more complex with more branches.
In my opinion path from start to finish is often too direct. Should be little more complex with more branches.
Re: Eller's maze generator
zsolt wrote:
It is interesting i found a site, where the maze creator algorithms are compared, and the "hunt and kill" seems 5 (7) times slower than the "Eller". 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.
Re: Eller's maze generator
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
Re: Eller's maze generator
Hi,
Zsolt
I think it depends only on the random number generator - sometimes it gives quite difficult maze (more branches).berk wrote:In my opinion path from start to finish is often too direct. Should be little more complex with more branches.
Thanks, i will try itdr beep wrote:The algorithm I use:Code: Select all
set all field unused . . ;maze ready
Zsolt
ZX81 (8K), ENTERPRISE 128, [ZX SPECTRUM (48K,+,+128K,+2,+2A), TS1000, TS1500, TS2068, Cambridge Z88, PRIMO A64 (red)]
Re: Eller's maze generator
Great!I think it depends only on the random number generator - sometimes it gives quite difficult maze (more branches).