Maze solution algorithm. Complex mazes

Question

I found several algorithms for solving mazes. Those that are simple enough are only suitable when the exit is at the outer boundary (Wall-follower, pledge ...).

Are there even more complex algorithms for cases where the shapes of the borders are random, the costs of unequal zones and output can be somewhere inside the maze? (btw, all elements are quadratic)

Refresh . In addition, we do not know a priori what the maze looks like and only a certain area can see it.

Answer 1

If you mean “normal” 2-dimensional mazes, similar to those found on paper, you can solve them using image analysis . However, if you somehow find yourself in a maze (2D / 3D) and need to find a way out, you should probably use the Machine Learning Technique . This works if you don’t know what the maze looks like, aka you just “see” part of it.

Update: In addition to the shortest family of path-finding algorithms, I can also refer to the so-called Trémaux algorithm, intended for human use inside the maze . It looks like a simple recursive backtracker and will find a solution for all the mazes.

Description:

As you walk down the corridor, draw a line behind you to mark your path. When you are at a standstill, turn around and come back as you came. When you meet a connection that you have not visited before, choose a new passage at random. If you are walking along a new aisle and encounter an intersection that you have visited before, treat it as a dead end and return to how you arrived so as not to walk in circles or missed aisles. If you are walking along the aisle that you visited before (that is, it is marked once) and you encounter an intersection, take any new passage if it is available, otherwise take the "old" one. Each passage will be either empty (if it has not yet been visited), marked once, or marked twice (if you were forced to retreat). When you reach a solution, paths that have been marked exactly once indicate a direct path to the beginning. If the labyrinth has no solution, you will again be at the beginning with all the passages marked twice.

Answer 2

The shortest path The algorithms find the shortest path to the exit, regardless of where the output is.

If the cost is - BFS , then otherwise you need something like dijkstra algorithm or A * algorithm [which is basically informed dijkstra] to find the shortest path.

To use these algorithms, you need to simulate your maze as a graph: G=(V,E) where V = { all moveable squares in the maze } and E = {(u,v) | you can move from u to v in a sinlgle step } E = {(u,v) | you can move from u to v in a sinlgle step }

If the squares have value, let it be cost(v) for each square, you will need a weighting function: w:E->R : define it as w(u,v) = cost(v)

Answer 3

The pledge algorithm is useful for the mazes you are talking about. It consists of:

The choice of direction, if you know the general direction to the goal, but an arbitrary direction. Say you choose North.

Go in this direction until you hit an obstacle.

Follow the obstacle, watching how hard you turn. For example, going north, you encounter an East-West wall. You turn east (90d) and follow the wall, turning south (180d), west (270d) and north again (360d). You do not stop following the wall until the amount you have converted becomes 0. So, you continue to follow, turning West (270d turned in the opposite direction), South (180d), East (90d) and finally North (0d), Now you can stop following.

Do this anytime you hit an obstacle. In the end, you will reach the northernmost part of the maze. If you still haven’t found the target because you have chosen the wrong direction, try again with the East or South or any other direction closest to the target.