Log In  

Cart [#23402#] | Code | 2016-06-21 | License: CC4-BY-NC-SA | Embed
4

A fun little toy/demo displaying some maze algorithms.

Note the mazes generated are perfect mazes, meaning they have exactly one path from any point to any other point inside the maze. They're not so useful for making games without some adaptation.

Algorithms:

Binary tree: at each cell, decides to go either down or right. Produces a bias towards diagonal movement and obvious lines at the bottom/right.

Sidewinder: goes along a run of cells horizontally, then adds one passage downwards. Tends towards vertical movement and obvious line at the bottom.

Aldous-Broder: random walk filling in cells as they're visited. Produces a totally unbiased maze (assuming rnd() is unbiased) but can be slow at the end.

If you're interested in the topic I recommend this book (that I got the idea/algorithms from): Mazes for Programmers.

P#23403 2016-06-21 15:39 ( Edited 2016-06-22 09:29)

:: Danjen

Does the Aldous-Broder guarantee that all edges are connected to a single tree of nodes?

P#23406 2016-06-21 16:21 ( Edited 2016-06-21 20:21)

Very nice collection

P#23408 2016-06-21 16:32 ( Edited 2016-06-21 20:32)
:: mrh

@Danjen: yes (unless I've made a mistake in the implementation) all nodes should be reachable from all others via a single unique path.

P#23410 2016-06-21 17:29 ( Edited 2016-06-21 21:29)

Very interesting, thank you!

P#23429 2016-06-22 05:29 ( Edited 2016-06-22 09:29)

[Please log in to post a comment]

About | Contact | Updates | Terms of Use
Follow Lexaloffle:        
Generated 2019-08-20 05:26 | 0.034s | 4194k | Q:31