Maze-solving algorithm - Revision history

174.29.218.91 at 20:33, 16 April 2025

2025-04-16T20:33:12Z

← Previous revision		Revision as of 20:33, 16 April 2025
Line 79:		Line 79:
	maze = generateMaze(); // Create Maze (false = path, true = wall)		maze = generateMaze(); // Create Maze (false = path, true = wall)

	// Below assignment to false is redundant as Java assigns array elements to false by default, but it is included because other languages may not behave the same ~~behavior~~.		// Below assignment to false is redundant as Java assigns array elements to false by default, but it is included because other languages may not behave the same.
	for (int row = 0; row < maze.length; row++)		for (int row = 0; row < maze.length; row++)
	// Sets boolean Arrays to default values		// Sets boolean Arrays to default values

174.29.218.91 at 20:32, 16 April 2025

2025-04-16T20:32:25Z

← Previous revision		Revision as of 20:32, 16 April 2025
Line 79:		Line 79:
	maze = generateMaze(); // Create Maze (false = path, true = wall)		maze = generateMaze(); // Create Maze (false = path, true = wall)

	// Below assignment to false is redundant as Java assigns array elements to false by default		// Below assignment to false is redundant as Java assigns array elements to false by default, but it is included because other languages may not behave the same behavior.
	for (int row = 0; row < maze.length; row++)		for (int row = 0; row < maze.length; row++)
	// Sets boolean Arrays to default values		// Sets boolean Arrays to default values

Edit7hesadparts: Fixed redirecting link

2025-04-08T13:24:56Z

Fixed redirecting link

← Previous revision		Revision as of 13:24, 8 April 2025
Line 9:		Line 9:

	== Hand On Wall Rule ==		== Hand On Wall Rule ==
	[[File:maze01-02.svg\|left\|thumb\|164px\|Traversal using ''right-hand rule'' ([[:~~media:maze01~~-02.svg\|animation]])]]		[[File:maze01-02.svg\|left\|thumb\|164px\|Traversal using ''right-hand rule'' ([[Media:Maze01-02.svg\|animation]])]]
	One effective rule for traversing mazes is the ''Hand On Wall Rule'', also known as either the ''left-hand rule'' or the ''right-hand rule''. If the maze is [[Simply connected space\|''simply connected'']], that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the solver is guaranteed not to get lost and will reach a different exit if there is one; otherwise, the algorithm will return to the entrance having traversed every corridor next to that connected section of walls at least once. The algorithm is a depth-first in-order [[tree traversal]].		One effective rule for traversing mazes is the ''Hand On Wall Rule'', also known as either the ''left-hand rule'' or the ''right-hand rule''. If the maze is [[Simply connected space\|''simply connected'']], that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the solver is guaranteed not to get lost and will reach a different exit if there is one; otherwise, the algorithm will return to the entrance having traversed every corridor next to that connected section of walls at least once. The algorithm is a depth-first in-order [[tree traversal]].

Line 152:		Line 152:

	==See also==		==See also==
	* [[~~Mazes~~]]		* [[Maze]]
	* [[Maze generation algorithm]]		* [[Maze generation algorithm]]

TamaMcGlinn: /* Trémaux's algorithm */ Add to rule 2; only if all entrances are marked. Otherwise, it contradicts the execution shown, and Tremaux's original formulation.

2025-02-12T18:10:41Z

Trémaux's algorithm: Add to rule 2; only if all entrances are marked. Otherwise, it contradicts the execution shown, and Tremaux's original formulation.

← Previous revision		Revision as of 18:10, 12 February 2025
Line 42:		Line 42:
	* When you are at a junction, use the first applicable rule below to pick an entrance to exit through:		* When you are at a junction, use the first applicable rule below to pick an entrance to exit through:
	*# If only the entrance you just came from is marked, pick an arbitrary unmarked entrance, if any. This rule also applies if you're just starting in the middle of the maze and there are no marked entrances at all.		*# If only the entrance you just came from is marked, pick an arbitrary unmarked entrance, if any. This rule also applies if you're just starting in the middle of the maze and there are no marked entrances at all.
	*# ~~Pick~~ the entrance you just came from, unless it is marked twice. This rule will apply whenever you reach a dead end.		*# If all entrances are marked, go back through the entrance you just came from, unless it is marked twice. This rule will apply whenever you reach a dead end.
	*# Pick any entrance with the fewest marks (zero if possible, else one).		*# Pick any entrance with the fewest marks (zero if possible, else one).

Grufo: /* Hand On Wall Rule */ png -> svg

2024-12-16T15:09:26Z

Hand On Wall Rule: png -> svg

← Previous revision		Revision as of 15:09, 16 December 2024
Line 9:		Line 9:

	== Hand On Wall Rule ==		== Hand On Wall Rule ==
	[[File:maze01-02.~~png~~\|left\|~~frame~~\|Traversal using ''right-hand rule'']]		[[File:maze01-02.svg\|left\|thumb\|164px\|Traversal using ''right-hand rule'' ([[:media:maze01-02.svg\|animation]])]]
	One effective rule for traversing mazes is the ''Hand On Wall Rule'', also known as either the ''left-hand rule'' or the ''right-hand rule''. If the maze is [[Simply connected space\|''simply connected'']], that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the solver is guaranteed not to get lost and will reach a different exit if there is one; otherwise, the algorithm will return to the entrance having traversed every corridor next to that connected section of walls at least once. The algorithm is a depth-first in-order [[tree traversal]].		One effective rule for traversing mazes is the ''Hand On Wall Rule'', also known as either the ''left-hand rule'' or the ''right-hand rule''. If the maze is [[Simply connected space\|''simply connected'']], that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the solver is guaranteed not to get lost and will reach a different exit if there is one; otherwise, the algorithm will return to the entrance having traversed every corridor next to that connected section of walls at least once. The algorithm is a depth-first in-order [[tree traversal]].

156.249.14.68: I added a link to a project that generates the maze and shows the algorithm working.

2024-07-23T05:39:20Z

I added a link to a project that generates the maze and shows the algorithm working.

← Previous revision		Revision as of 05:39, 23 July 2024
Line 19:		Line 19:

	Wall-following can be done in 3D or higher-dimensional mazes if its higher-dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead Northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can apply. However, unlike in 2D, this requires that the current orientation is known, to determine which direction is the first on the left or right.		Wall-following can be done in 3D or higher-dimensional mazes if its higher-dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead Northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can apply. However, unlike in 2D, this requires that the current orientation is known, to determine which direction is the first on the left or right.

			A simulation of this algorithm working can be found [https://scratch.mit.edu/projects/1049044916/ here].

	== Pledge algorithm ==		== Pledge algorithm ==

JCW-CleanerBot: /* Multi-agent maze-solving */task, removed: : An International Journal (2)

2024-07-08T21:25:41Z

Multi-agent maze-solving: task, removed: : An International Journal (2)

← Previous revision		Revision as of 21:25, 8 July 2024
Line 147:		Line 147:
	== Multi-agent maze-solving ==		== Multi-agent maze-solving ==
	Collective exploration refers to the exploration of an unknown environment by multiple mobile agents that move at the same speed. This model was introduced		Collective exploration refers to the exploration of an unknown environment by multiple mobile agents that move at the same speed. This model was introduced
	to study the [[Parallel computing \|paralellizability]] of maze-solving,<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks~~: An International Journal~~ \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref> especially in the case of [[Tree (graph theory)\|trees]]. The study depends on the model of communication between the agents. In the centralized communication model, the agents are allowed to communicate at all times with one another. In the [[Distributed computing \| distributed]] communication model, the agents can communicate only by reading and writing on the walls of the maze. For trees with <math>n</math> nodes and depth <math>D</math>, with <math>k</math> robots, the current-best algorithm is in <math>O\left(\frac{n}{k} + kD\right)</math> in the centralized communication model and in <math>O\left(\frac{n}{\log k} + D\right)</math> in the distributed communication model.<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/~~net.20127 }}</ref~~>		to study the [[Parallel computing\|paralellizability]] of maze-solving,<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks\| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref> especially in the case of [[Tree (graph theory)\|trees]]. The study depends on the model of communication between the agents. In the centralized communication model, the agents are allowed to communicate at all times with one another. In the [[Distributed computing\|distributed]] communication model, the agents can communicate only by reading and writing on the walls of the maze. For trees with <math>n</math> nodes and depth <math>D</math>, with <math>k</math> robots, the current-best algorithm is in <math>O\left(\frac{n}{k} + kD\right)</math> in the centralized communication model and in <math>O\left(\frac{n}{\log k} + D\right)</math> in the distributed communication model.<ref name="Fraigniaud2006"/>

	==See also==		==See also==

WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2024-05-28T06:20:18Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 06:20, 28 May 2024
Line 6:		Line 6:

	== Random mouse algorithm ==		== Random mouse algorithm ==
	This simple method can be implemented by a very unintelligent [[robot]] or perhaps a mouse, because it does not require any memory. The robot proceeds following the current passage until a junction is reached, and then makes a random decision about the next direction to follow. Although such a method would always [[Las Vegas algorithm\|eventually find the right solution]], the algorithm can be very slow<ref name="Aleliunas1979">{{cite conference \| last1=Aleliunas \| first1=Romas \| last2=Karp \| first2=Richard M \| last3=Lipton \| first3=Richard J \| last4=Lovász \| first4=László \| last5=Rackoff \| first5=Charles \| title=Random walks, universal traversal sequences, and the complexity of maze problems \| book-title=20th Annual Symposium on Foundations of Computer Science (sfcs 1979) \| pages=218–223 \| year=1979 \| publisher=IEEE Computer Society }}</ref>.		This simple method can be implemented by a very unintelligent [[robot]] or perhaps a mouse, because it does not require any memory. The robot proceeds following the current passage until a junction is reached, and then makes a random decision about the next direction to follow. Although such a method would always [[Las Vegas algorithm\|eventually find the right solution]], the algorithm can be very slow.<ref name="Aleliunas1979">{{cite conference \| last1=Aleliunas \| first1=Romas \| last2=Karp \| first2=Richard M \| last3=Lipton \| first3=Richard J \| last4=Lovász \| first4=László \| last5=Rackoff \| first5=Charles \| title=Random walks, universal traversal sequences, and the complexity of maze problems \| book-title=20th Annual Symposium on Foundations of Computer Science (sfcs 1979) \| pages=218–223 \| year=1979 \| publisher=IEEE Computer Society }}</ref>

	== Hand On Wall Rule ==		== Hand On Wall Rule ==
Line 147:		Line 147:
	== Multi-agent maze-solving ==		== Multi-agent maze-solving ==
	Collective exploration refers to the exploration of an unknown environment by multiple mobile agents that move at the same speed. This model was introduced		Collective exploration refers to the exploration of an unknown environment by multiple mobile agents that move at the same speed. This model was introduced
	to study the [[Parallel computing \|paralellizability]] of maze-solving<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref>, especially in the case of [[Tree (graph theory)\|trees]]. The study depends on the model of communication between the agents. In the centralized communication model, the agents are allowed to communicate at all times with one another. In the [[Distributed computing \| distributed]] communication model, the agents can communicate only by reading and writing on the walls of the maze. For trees with <math>n</math> nodes and depth <math>D</math>, with <math>k</math> robots, the current-best algorithm is in <math>O\left(\frac{n}{k} + kD\right)</math> in the centralized communication model and in <math>O\left(\frac{n}{\log k} + D\right)</math> in the distributed communication model<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref>.		to study the [[Parallel computing \|paralellizability]] of maze-solving,<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref> especially in the case of [[Tree (graph theory)\|trees]]. The study depends on the model of communication between the agents. In the centralized communication model, the agents are allowed to communicate at all times with one another. In the [[Distributed computing \| distributed]] communication model, the agents can communicate only by reading and writing on the walls of the maze. For trees with <math>n</math> nodes and depth <math>D</math>, with <math>k</math> robots, the current-best algorithm is in <math>O\left(\frac{n}{k} + kD\right)</math> in the centralized communication model and in <math>O\left(\frac{n}{\log k} + D\right)</math> in the distributed communication model.<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref>

	==See also==		==See also==

1612elphi: /* Hand On Wall Rule */ Fixed typo

2024-05-20T20:06:30Z

Hand On Wall Rule: Fixed typo

← Previous revision		Revision as of 20:06, 20 May 2024
Line 19:		Line 19:

	Wall-following can be done in 3D or higher-dimensional mazes if its higher-dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead Northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can apply. However, unlike in 2D, this requires that the current orientation is known, to determine which direction is the first on the left or right.		Wall-following can be done in 3D or higher-dimensional mazes if its higher-dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead Northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can apply. However, unlike in 2D, this requires that the current orientation is known, to determine which direction is the first on the left or right.
	cmd-->fswfv
	[pdegtg[]e]

	== Pledge algorithm ==		== Pledge algorithm ==

Citation bot: Added doi. | Use this bot. Report bugs. | Suggested by Jay8g | #UCB_toolbar

2024-05-20T18:35:36Z

Added doi. | Use this bot. Report bugs. | Suggested by Jay8g | #UCB_toolbar

← Previous revision		Revision as of 18:35, 20 May 2024
Line 149:		Line 149:
	== Multi-agent maze-solving ==		== Multi-agent maze-solving ==
	Collective exploration refers to the exploration of an unknown environment by multiple mobile agents that move at the same speed. This model was introduced		Collective exploration refers to the exploration of an unknown environment by multiple mobile agents that move at the same speed. This model was introduced
	to study the [[Parallel computing \|paralellizability]] of maze-solving<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library }}</ref>, especially in the case of [[Tree (graph theory)\|trees]]. The study depends on the model of communication between the agents. In the centralized communication model, the agents are allowed to communicate at all times with one another. In the [[Distributed computing \| distributed]] communication model, the agents can communicate only by reading and writing on the walls of the maze. For trees with <math>n</math> nodes and depth <math>D</math>, with <math>k</math> robots, the current-best algorithm is in <math>O\left(\frac{n}{k} + kD\right)</math> in the centralized communication model and in <math>O\left(\frac{n}{\log k} + D\right)</math> in the distributed communication model<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library }}</ref>.		to study the [[Parallel computing \|paralellizability]] of maze-solving<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref>, especially in the case of [[Tree (graph theory)\|trees]]. The study depends on the model of communication between the agents. In the centralized communication model, the agents are allowed to communicate at all times with one another. In the [[Distributed computing \| distributed]] communication model, the agents can communicate only by reading and writing on the walls of the maze. For trees with <math>n</math> nodes and depth <math>D</math>, with <math>k</math> robots, the current-best algorithm is in <math>O\left(\frac{n}{k} + kD\right)</math> in the centralized communication model and in <math>O\left(\frac{n}{\log k} + D\right)</math> in the distributed communication model<ref name="Fraigniaud2006">{{cite journal \| last1=Fraigniaud \| first1=Pierre \| last2=Gasieniec \| first2=Leszek \| last3=Kowalski \| first3=Dariusz R \| last4=Pelc \| first4=Andrzej \| title=Collective tree exploration \| journal=Networks: An International Journal \| volume=48 \| issue=3 \| pages=166–177 \| year=2006 \| publisher=Wiley Online Library \| doi=10.1002/net.20127 }}</ref>.

	==See also==		==See also==