Maze generation algorithm - Revision history

Goodram: /* Cellular automaton algorithms */ update LifeWiki ref URL

2025-04-22T11:38:30Z

Cellular automaton algorithms: update LifeWiki ref URL

← Previous revision		Revision as of 11:38, 22 April 2025
Line 176:		Line 176:

	== Cellular automaton algorithms ==		== Cellular automaton algorithms ==
	Certain types of [[cellular automata]] can be used to generate mazes.<ref name=ca>{{cite web\|url=~~http~~://~~www.~~conwaylife.com/wiki/~~index.php?title=~~Maze\|title=Maze ~~- LifeWiki~~ \|author=Nathaniel Johnston\|date=21 August 2010 \|publisher=LifeWiki \|accessdate=1 ~~March~~ ~~2011~~\|display-authors=etal}}</ref> Two well-known such cellular automata, Maze and Mazectric, have rulestrings B3/S12345 and B3/S1234.<ref name=ca /> In the former, this means that cells survive from one generation to the next if they have at least one and at most five [[Moore neighbourhood\|neighbours]]. In the latter, this means that cells survive if they have one to four neighbours. If a cell has exactly three neighbours, it is born. It is similar to [[Conway's Game of Life]] in that patterns that do not have a living cell adjacent to 1, 4, or 5 other living cells in any generation will behave identically to it.<ref name=ca /> However, for large patterns, it behaves very differently from Life.<ref name=ca />		Certain types of [[cellular automata]] can be used to generate mazes.<ref name=ca>{{cite web\|url=https://conwaylife.com/wiki/OCA:Maze\|title=Maze \|author=Nathaniel Johnston\|date=21 August 2010 \|publisher=LifeWiki \|accessdate=22 April 2025\|display-authors=etal}}</ref> Two well-known such cellular automata, Maze and Mazectric, have rulestrings B3/S12345 and B3/S1234.<ref name=ca /> In the former, this means that cells survive from one generation to the next if they have at least one and at most five [[Moore neighbourhood\|neighbours]]. In the latter, this means that cells survive if they have one to four neighbours. If a cell has exactly three neighbours, it is born. It is similar to [[Conway's Game of Life]] in that patterns that do not have a living cell adjacent to 1, 4, or 5 other living cells in any generation will behave identically to it.<ref name=ca /> However, for large patterns, it behaves very differently from Life.<ref name=ca />

	For a random starting pattern, these maze-generating cellular automata will evolve into complex mazes with well-defined walls outlining corridors. Mazecetric, which has the rule B3/S1234 has a tendency to generate longer and straighter corridors compared with Maze, with the rule B3/S12345.<ref name=ca /> Since these cellular automaton rules are [[deterministic]], each maze generated is uniquely determined by its random starting pattern. This is a significant drawback since the mazes tend to be relatively predictable.		For a random starting pattern, these maze-generating cellular automata will evolve into complex mazes with well-defined walls outlining corridors. Mazecetric, which has the rule B3/S1234 has a tendency to generate longer and straighter corridors compared with Maze, with the rule B3/S12345.<ref name=ca /> Since these cellular automaton rules are [[deterministic]], each maze generated is uniquely determined by its random starting pattern. This is a significant drawback since the mazes tend to be relatively predictable.

DynamicField: Fix a typo "o" -> "of"

2025-04-16T09:47:54Z

Fix a typo "o" -> "of"

← Previous revision		Revision as of 09:47, 16 April 2025
Line 2:		Line 2:
	{{more citations needed\|date=March 2018}}		{{more citations needed\|date=March 2018}}
	[[Image:Prim Maze.svg\|thumb\|A maze generated by a modified version of [[Prim's algorithm]]]]		[[Image:Prim Maze.svg\|thumb\|A maze generated by a modified version of [[Prim's algorithm]]]]
	'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation f [[maze]]s.		'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation of [[maze]]s.

	== Graph theory based methods ==		== Graph theory based methods ==

41.233.197.251 at 21:25, 15 April 2025

2025-04-15T21:25:05Z

← Previous revision		Revision as of 21:25, 15 April 2025
Line 2:		Line 2:
	{{more citations needed\|date=March 2018}}		{{more citations needed\|date=March 2018}}
	[[Image:Prim Maze.svg\|thumb\|A maze generated by a modified version of [[Prim's algorithm]]]]		[[Image:Prim Maze.svg\|thumb\|A maze generated by a modified version of [[Prim's algorithm]]]]
	'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation of [[maze]]s.		'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation f [[maze]]s.

	== Graph theory based methods ==		== Graph theory based methods ==

Belbury: /* top */ MOS:ORDER

2025-02-18T16:07:31Z

top: MOS:ORDER

← Previous revision		Revision as of 16:07, 18 February 2025
Line 1:		Line 1:
	{{short description\|Automated methods for the creation of mazes}}		{{short description\|Automated methods for the creation of mazes}}
	{{more citations needed\|date=March 2018}}		{{more citations needed\|date=March 2018}}
		⚫	[[Image:Prim Maze.svg\|thumb\|A maze generated by a modified version of [[Prim's algorithm]]]]
	'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation of [[maze]]s.		'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation of [[maze]]s.

⚫	[[Image:Prim Maze.svg\|~~right~~\|~~frame\|This~~ maze ~~was~~ generated by a modified version of [[Prim's algorithm]]~~, below.~~]]

	== Graph theory based methods ==		== Graph theory based methods ==

Cedar101: /* Simple algorithms */ {{sxhl}}

2025-01-22T10:01:20Z

Simple algorithms: {{sxhl}}

← Previous revision		Revision as of 10:01, 22 January 2025
Line 173:		Line 173:
	Most maze generation algorithms require maintaining relationships between cells within it, to ensure the result will be solvable. Valid simply connected mazes can however be generated by focusing on each cell independently. A binary tree maze is a standard orthogonal maze where each cell always has a passage leading up or leading left, but never both. To create a binary tree maze, for each cell flip a coin to decide whether to add a passage leading up or left. Always pick the same direction for cells on the boundary, and the result will be a valid simply connected maze that looks like a [[binary tree]], with the upper left corner its root. As with Sidewinder, the binary tree maze has no dead ends in the directions of bias.		Most maze generation algorithms require maintaining relationships between cells within it, to ensure the result will be solvable. Valid simply connected mazes can however be generated by focusing on each cell independently. A binary tree maze is a standard orthogonal maze where each cell always has a passage leading up or leading left, but never both. To create a binary tree maze, for each cell flip a coin to decide whether to add a passage leading up or left. Always pick the same direction for cells on the boundary, and the result will be a valid simply connected maze that looks like a [[binary tree]], with the upper left corner its root. As with Sidewinder, the binary tree maze has no dead ends in the directions of bias.

	[[File:Commodore 64 maze.png\|thumb\|upright=1.3\|Maze generated in Commodore 64 BASIC, using the code ~~<code>~~10 PRINT CHR$(205.5+RND(1)); : GOTO 10~~</code>~~]]		[[File:Commodore 64 maze.png\|thumb\|upright=1.3\|Maze generated in Commodore 64 BASIC, using the code {{sxhl\|10 PRINT CHR$(205.5+RND(1)); : GOTO 10\|cbmbas}}]]
	A related form of flipping a coin for each cell is to create an image using a random mix of forward slash and backslash characters. This doesn't generate a valid simply connected maze, but rather a selection of closed loops and unicursal passages. The manual for the [[Commodore 64]] presents a BASIC program using this algorithm, using [[PETSCII]] diagonal line graphic characters instead for a smoother graphic appearance.		A related form of flipping a coin for each cell is to create an image using a random mix of forward slash and backslash characters. This doesn't generate a valid simply connected maze, but rather a selection of closed loops and unicursal passages. The manual for the [[Commodore 64]] presents a BASIC program using this algorithm, using [[PETSCII]] diagonal line graphic characters instead for a smoother graphic appearance.

174.34.4.52: /* Iterative implementation (with stack) */

2024-10-23T15:51:53Z

Iterative implementation (with stack)

← Previous revision		Revision as of 15:51, 23 October 2024
Line 55:		Line 55:

	# Choose the initial cell, mark it as visited and push it to the stack		# Choose the initial cell, mark it as visited and push it to the stack
	# While the stack is not ~~emptyaaaaaaa~~		# While the stack is not empty
	## Pop a cell from the stack and make it a current cell		## Pop a cell from the stack and make it a current cell
	## If the current cell has any neighbours which have not been visited		## If the current cell has any neighbours which have not been visited

174.34.4.52: /* Iterative implementation (with stack) */

2024-10-23T15:51:42Z

Iterative implementation (with stack)

← Previous revision		Revision as of 15:51, 23 October 2024
Line 55:		Line 55:

	# Choose the initial cell, mark it as visited and push it to the stack		# Choose the initial cell, mark it as visited and push it to the stack
	# While the stack is not ~~empty~~		# While the stack is not emptyaaaaaaa
	## Pop a cell from the stack and make it a current cell		## Pop a cell from the stack and make it a current cell
	## If the current cell has any neighbours which have not been visited		## If the current cell has any neighbours which have not been visited

JalenBarks: Reverted edits by 2A02:842B:8332:2401:A7A3:2B4C:1050:6C7C (talk) (HG) (3.4.12)

2024-07-06T16:36:28Z

Reverted edits by 2A02:842B:8332:2401:A7A3:2B4C:1050:6C7C (talk) (HG) (3.4.12)

← Previous revision		Revision as of 16:36, 6 July 2024
Line 36:		Line 36:
	[[File:Horizontally Influenced Depth-First Search Generated Maze.png\|thumb\|right\|Horizontal Passage Bias]]		[[File:Horizontally Influenced Depth-First Search Generated Maze.png\|thumb\|right\|Horizontal Passage Bias]]

	Mazes generated with a depth-first search have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before backtracking~~. To avoid that, just add, before, some "stop cells": if you arrive on it, stop this track, and loop back~~.		Mazes generated with a depth-first search have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before backtracking.

	==== Recursive implementation ====		==== Recursive implementation ====

2A02:842B:8332:2401:A7A3:2B4C:1050:6C7C: /* Randomized depth-first search */ To avoid that, just add, before, some "stop cells": if you arrive on it, stop this track, and loop back.

2024-07-06T16:35:59Z

Randomized depth-first search: To avoid that, just add, before, some "stop cells": if you arrive on it, stop this track, and loop back.

← Previous revision		Revision as of 16:35, 6 July 2024
Line 36:		Line 36:
	[[File:Horizontally Influenced Depth-First Search Generated Maze.png\|thumb\|right\|Horizontal Passage Bias]]		[[File:Horizontally Influenced Depth-First Search Generated Maze.png\|thumb\|right\|Horizontal Passage Bias]]

	Mazes generated with a depth-first search have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before backtracking.		Mazes generated with a depth-first search have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before backtracking. To avoid that, just add, before, some "stop cells": if you arrive on it, stop this track, and loop back.

	==== Recursive implementation ====		==== Recursive implementation ====

Maxeto0910 at 19:51, 12 June 2024

2024-06-12T19:51:26Z

← Previous revision		Revision as of 19:51, 12 June 2024
Line 3:		Line 3:
	'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation of [[maze]]s.		'''Maze generation algorithms''' are [[algorithm\|automated methods]] for the creation of [[maze]]s.

	[[Image:Prim Maze.svg\|right\|frame\|This maze generated by modified version of [[Prim's algorithm]], below.]]		[[Image:Prim Maze.svg\|right\|frame\|This maze was generated by a modified version of [[Prim's algorithm]], below.]]

	== Graph theory based methods ==		== Graph theory based methods ==