Page 1 of 1
Eller's maze generator
Posted: Mon Apr 11, 2016 3:48 pm
by zsolt
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 370 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
Re: Eller's maze generator
Posted: Mon Apr 11, 2016 10:22 pm
by dr beep
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.
Re: Eller's maze generator
Posted: Sun May 01, 2016 1:55 pm
by zsolt
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 284 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
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.
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?.
Re: Eller's maze generator
Posted: Sun May 01, 2016 3:52 pm
by berk
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?
Re: Eller's maze generator
Posted: Mon May 02, 2016 11:22 am
by zsolt
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?
Re: Eller's maze generator
Posted: Mon May 02, 2016 11:47 am
by berk
Sorry for my English
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
Posted: Mon May 02, 2016 9:28 pm
by dr beep
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
Posted: Mon May 02, 2016 10:30 pm
by dr beep
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
Posted: Wed May 04, 2016 1:51 pm
by zsolt
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).
- see the "walkig parts" of the 1st post
- EMG81_walk.png (27.77 KiB) Viewed 6573 times
dr beep wrote:The algorithm I use:
Code: Select all
set all field unused
.
.
;maze ready
Thanks, i will try it
Zsolt
Re: Eller's maze generator
Posted: Wed May 04, 2016 8:50 pm
by berk
I think it depends only on the random number generator - sometimes it gives quite difficult maze (more branches).
Great!