on the future of the easter bunny maze #5829

New Issue

flux · 2023-12-26T03:39:06+01:00

flux commented

2023-12-26 03:39:06 +01:00

after dumping worldeditadditions, if we want to have more bunny mazes this year, we need to figure out a replacement maze generator. several mods exist already, but we may want to develop our own due to their limitations, or just try to extract the old generator as a stand-alone mod.

flux added the

1. kind/enhancement

4. step/discussion

labels 2023-12-26 03:39:06 +01:00

flux added this to the flux's TODO list project 2023-12-26 03:39:09 +01:00

flux self-assigned this 2023-12-26 03:39:20 +01:00

sixer commented

2023-12-26 19:59:01 +01:00

The maze was blocking direct access from spawn to harbor (you have to walk the long way around)
That was somewhat annoying.
I suggest the maze be modified so the direct route to harbor would be passable - i.e. the ground floor would be just a bunch of pillars where you could walk thru, with actual maze levels above and below it?

The maze was blocking direct access from spawn to harbor (you have to walk the long way around) That was somewhat annoying. I suggest the maze be modified so the direct route to harbor would be passable - i.e. the ground floor would be just a bunch of pillars where you could walk thru, with actual maze levels above and below it?

👍 6

flux commented

2024-02-12 05:26:55 +01:00

i'm pivoting to implementing something almost equivalent to the worldeditadditions maze in time for easter. i don't have any clear paths for fixing the reported bugs with spawnit or ballistics, and this should just take a day or so.

flux commented

2024-02-12 05:28:24 +01:00

The maze was blocking direct access from spawn to harbor (you have to walk the long way around)

i 100% agree that the maze should in the future let people walk from /spawn to the harbor unimpeded. that's pretty trivial if the other commands are parameterized.

> The maze was blocking direct access from spawn to harbor (you have to walk the long way around) i 100% agree that the maze should in the future let people walk from /spawn to the harbor unimpeded. that's pretty trivial if the other commands are parameterized.

👍 3

AliasAlreadyTaken commented

2024-02-12 09:45:58 +01:00

Sounds like a nice twist :)

flux commented

2024-02-13 06:13:22 +01:00

today, in pursuit of performance when generating mazes, i bonked my head on the limitations of lua. i wanted to use performant data structures when generating the maze, but lua 5.1 doesn't have a built-in way of hashing arbitrary tables, and also has no way to build efficient hash tables in pure lua (it lacks bitwise operators and shifts). tomorrow i'll just give up on efficiency and use O(n^2) algorithms. that should be enough for our immediate purposes.

flux added the

4. step/at work

label 2024-02-13 06:14:56 +01:00

flux commented

2024-02-13 06:16:35 +01:00

if anyone is curious, the algorithm i'm trying to implement is described here: https://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm

whosit commented

2024-02-13 07:30:58 +01:00

visits = { [cx, cy] => 0 }
for this you can just use minetest.hash_node_position(pos)
~~or just create an array of arrays visits[x][y]~~ (ah, you will need to re-create it each step...)

or... there's some other optimization you wanted to do?

```visits = { [cx, cy] => 0 }``` for this you can just use `minetest.hash_node_position(pos)` ~~or just create an array of arrays `visits[x][y]`~~ (ah, you will need to re-create it each step...) or... there's some other optimization you wanted to do?

whosit commented

2024-02-13 08:31:40 +01:00

Hm, that blog also has bunch of other (more efficient?) algorithms...

flux commented

2024-02-13 22:34:26 +01:00

https://github.com/fluxionary/minetest-we_maze

Hm, that blog also has bunch of other (more efficient?) algorithms...

so it does. wilson's sounded the best from wikipedia due to the "unbiased" property and ease of use. it doesn't seem to be too slow in practice. it produces nice-looking mazes:

i parameterized the code to allow for adding new algorithms in the future if we want.

https://github.com/fluxionary/minetest-we_maze > Hm, that blog also has bunch of other (more efficient?) algorithms... so it does. wilson's sounded the best from wikipedia due to the "unbiased" property and ease of use. it doesn't seem to be too slow in practice. it produces nice-looking mazes: ![image](/attachments/eaa15900-22bb-411f-b54e-849cbd0e7615) i parameterized the code to allow for adding new algorithms in the future if we want.

image.png

451 KiB

flux added

4. step/ready to QA test

and removed

4. step/at work

4. step/discussion

labels 2024-02-13 22:34:37 +01:00

flux commented

2024-02-13 23:03:24 +01:00

because the arguments to the //maze command are slightly different, the script will need to change to something like the following

/fp set1 2023 8 1118
/fp set2 2059 35 1190
/param2 0

msg Service Basement

/fp set1 2023 8 1118
/fp set2 2059 11 1190
/maze yl_nether:med_crystal maptools:lightbulb 2

msg Service Basement Waterlayer

/fp set1 2023 8 1118
/fp set2 2059 8 1190
/r maptools:lightbulb default:water_source

msg Service Basement Ceiling

/fp set1 2023 12 1118
/fp set2 2059 12 1190
/s default:obsidian_glass

msg Service Lava

/fp set1 2023 13 1118
/fp set2 2059 13 1190
/s default:lava_source

msg Service Door Water

/fp set1 2023 8 1150
/fp set2 2023 8 1148
/s default:water_source

msg Service Door maptools:lightbulb

/fp set1 2023 9 1150
/fp set2 2023 10 1148
/s maptools:lightbulb

msg Service Wood

/fp set1 2023 15 1118
/fp set2 2059 19 1190
/s maptools:lightbulb

/fp set1 2023 20 1118
/fp set2 2059 20 1190
/s dirt_with_grass

/fp set1 2023 21 1118
/fp set2 2059 25 1190
/maze cblocks:wood_orange maptools:lightbulb 2

msg Service glass

/fp set1 2023 26 1118
/fp set2 2059 26 1190
/s maptools:white

/fp set1 2023 27 1118
/fp set2 2059 30 1190
/maze default:glass maptools:lightbulb 2

msg Service Invis

/fp set1 2023 31 1118
/fp set2 2059 31 1190
/s maptools:black

/fp set1 2023 32 1118
/fp set2 2059 35 1190
/maze maptools:fullclip maptools:lightbulb 2

/rst

because the arguments to the `//maze` command are slightly different, the script will need to change to something like the following ``` /fp set1 2023 8 1118 /fp set2 2059 35 1190 /param2 0 msg Service Basement /fp set1 2023 8 1118 /fp set2 2059 11 1190 /maze yl_nether:med_crystal maptools:lightbulb 2 msg Service Basement Waterlayer /fp set1 2023 8 1118 /fp set2 2059 8 1190 /r maptools:lightbulb default:water_source msg Service Basement Ceiling /fp set1 2023 12 1118 /fp set2 2059 12 1190 /s default:obsidian_glass msg Service Lava /fp set1 2023 13 1118 /fp set2 2059 13 1190 /s default:lava_source msg Service Door Water /fp set1 2023 8 1150 /fp set2 2023 8 1148 /s default:water_source msg Service Door maptools:lightbulb /fp set1 2023 9 1150 /fp set2 2023 10 1148 /s maptools:lightbulb msg Service Wood /fp set1 2023 15 1118 /fp set2 2059 19 1190 /s maptools:lightbulb /fp set1 2023 20 1118 /fp set2 2059 20 1190 /s dirt_with_grass /fp set1 2023 21 1118 /fp set2 2059 25 1190 /maze cblocks:wood_orange maptools:lightbulb 2 msg Service glass /fp set1 2023 26 1118 /fp set2 2059 26 1190 /s maptools:white /fp set1 2023 27 1118 /fp set2 2059 30 1190 /maze default:glass maptools:lightbulb 2 msg Service Invis /fp set1 2023 31 1118 /fp set2 2059 31 1190 /s maptools:black /fp set1 2023 32 1118 /fp set2 2059 35 1190 /maze maptools:fullclip maptools:lightbulb 2 /rst ```

flux commented

2024-02-14 00:17:24 +01:00

added a couple more algorithms:

backtrack (longer paths, fewer dead ends):

prim's (shorter paths, more dead ends):

added a couple more algorithms: backtrack (longer paths, fewer dead ends): ![image](/attachments/f6f236c8-488a-4a74-bb32-3a5ce26b55e4) prim's (shorter paths, more dead ends): ![image](/attachments/6d5be794-7945-4a55-a80e-bf7a28c06463)

image.png

673 KiB

image.png

496 KiB

AliasAlreadyTaken added this to the 1.1.123 milestone 2024-02-14 05:12:15 +01:00

AliasAlreadyTaken commented

2024-02-16 10:27:43 +01:00

QA

I checked whether the command given would generate a nice bunny maze. That works.

I did NOT check whether all parameters lead to reasonable mazes or have crash potential when giving funny values like 0, -1 or 3.415

QA I checked whether the command given would generate a nice bunny maze. That works. I did NOT check whether all parameters lead to reasonable mazes or have crash potential when giving funny values like 0, -1 or 3.415

AliasAlreadyTaken added the

4. step/QA OK

label 2024-02-16 10:27:51 +01:00

flux commented

2024-02-17 19:56:38 +01:00

I did NOT check whether all parameters lead to reasonable mazes or have crash potential when giving funny values like 0, -1 or 3.415

> I did NOT check whether all parameters lead to reasonable mazes or have crash potential when giving funny values like 0, -1 or 3.415 ![image](/attachments/e1a3f9b0-9d63-4ed6-8094-acac5fde6f0b)

image.png

61 KiB

Boot commented

2024-02-17 20:12:38 +01:00

If you want a nice 3D maze, I'm happy to build one:)

flux commented

2024-02-17 23:33:47 +01:00

If you want a nice 3D maze, I'm happy to build one:)

your maze was fantastic, but i expect it takes days to make it by hand, so not suitable for often-changed bunny-type mazes :)

i'd love to be able to expand the 2d maze code to make 3d mazes eventually. it's not that much more complicated, the fundamental algorithms are the same.

> If you want a nice 3D maze, I'm happy to build one:) your maze was fantastic, but i expect it takes days to make it by hand, so not suitable for often-changed bunny-type mazes :) i'd love to be able to expand the 2d maze code to make 3d mazes eventually. it's not that much more complicated, the fundamental algorithms are the same.

👍 1

AliasAlreadyTaken referenced this issue from a commit

2024-03-03 23:40:43 +01:00

your-land/bugtracker#5829 Add maze generator

MisterE123 commented

2024-03-06 02:02:18 +01:00

https://github.com/conorpp/3d-maze-generator/blob/master/maze.py

flux commented

2024-03-09 04:32:34 +01:00

https://github.com/conorpp/3d-maze-generator/blob/master/maze.py

the maze algorithms i used are abstractable - the only big things to do to make a 3d maze is to provide a different set of adjacent nodes, and to specify another building material for players to use to go up and down. there's a number of other important QOL things like a way to specify that players tend to be about 2 nodes tall, but that's just tedious, not complicated.

> https://github.com/conorpp/3d-maze-generator/blob/master/maze.py the maze algorithms i used are abstractable - the only big things to do to make a 3d maze is to provide a different set of adjacent nodes, and to specify another building material for players to use to go up and down. there's a number of other important QOL things like a way to specify that players tend to be about 2 nodes tall, but that's just tedious, not complicated.

flux commented

2024-03-09 04:35:58 +01:00

re: 3d mazes; it wouldn't be too much harder to create algorithms that would build a maze inside of a pyramid, or which included more loops. or even using ideas from e.g. https://www.youtube.com/watch?v=ZMQbHMgK2rw

Boot commented

2024-03-09 11:16:21 +01:00

I used it to construct my 3D-labyrinths: https://www.astrolog.org/labyrnth/daedalus.htm
Source code: https://github.com/CruiserOne/Daedalus
Forget everything else.

I used it to construct my 3D-labyrinths: https://www.astrolog.org/labyrnth/daedalus.htm Source code: https://github.com/CruiserOne/Daedalus Forget everything else.

flux commented

2024-03-10 06:57:03 +01:00

I used it to construct my 3D-labyrinths: https://www.astrolog.org/labyrnth/daedalus.htm
Source code: https://github.com/CruiserOne/Daedalus
Forget everything else.

that daedalus engine is impressive. but the algorithms i've implemented correspond to an important subset of the algorithms it implements, without a lot of irrelevant overhead. maze generating algorithms need not be too complicated, and there's lots of other descriptions of the problem. i mostly used documentation from a person who literally published a book about it, as mentioned above.

> I used it to construct my 3D-labyrinths: https://www.astrolog.org/labyrnth/daedalus.htm > Source code: https://github.com/CruiserOne/Daedalus > Forget everything else. that daedalus engine is impressive. but the algorithms i've implemented correspond to an important subset of the algorithms it implements, without a lot of irrelevant overhead. maze generating algorithms need not be too complicated, and there's lots of other descriptions of the problem. i mostly used documentation from a person who literally published a book about it, as mentioned above.

👍 1

flux added

5. result/fixed

and removed

4. step/ready to QA test

labels 2024-03-28 20:50:56 +01:00

flux removed this from the flux's TODO list project 2024-03-28 21:09:18 +01:00

flux removed their assignment 2024-03-28 21:09:20 +01:00

flux commented

2024-03-28 21:09:37 +01:00

this is live, looking forward to this year's bunny mazes :)

🎉 1