CODEWITHSUNDEEP
algorithmmaze
Sergey
Sergey

Reputation: 1208

Maze solving algorithm. Complex mazes

I found several algorithms to solve mazes. Those which are simple enough are suitable only in cases when exit is in outer boundary (Wall-follower, pledge...).

Is there some more sophisticated algorithms for cases when shapes of boundaries are random, costs of zones inequal and exit may be somewhere inside the maze? (btw, all elements are quadratic)

Update: Also, we don't know apriori how maze looks like and are able to see only certain area.

Upvotes: 4

Views: 9928

Answers (3)

Weux
Weux

Reputation: 11

The Pledge Algorithm is useful for the kind of mazes you are talking of. It consists of:

Picking a direction, if you know the general direction to goal good, but a random direction will do. Let say you pick North.

Go that direction until you hit an obstacle.

Follow the obstacle, keeping track of how much you turn. For instance, going North you run into an East-West wall. You turn East (90d), and follow the wall as it turns South (180d), West (270d), and North again (360d). You do not stop following the wall until the amount you have turned becomes 0. So you keep following as it turns West (270d it turned in the opposite direction), South (180d), East (90d), and finally North (0d). Now you can stop following.

Do that any time you hit an obstacle. You will get to the Northern most part of the maze eventually. If you still havent found the goal, because you picked the wrong direction, try again with East or South or whatever direction is closest to the goal.

Upvotes: 1

Stefan Marinov
Stefan Marinov

Reputation: 581

If you mean "normal" 2-dimensinal mazes like those one can find on paper, you can solve them using image analysis. However, if you are somehow located in the (2D/3D) maze itself and should find a way out, you should probably deploy some Machine learning techniques. This works if you don't have any idea what you maze exactly looks like, a.k.a. you only "see" part of it.

Update: Apart from the shortest path finder algorithm family, I can also relate to the so-called Trémaux's algorithm designed to be able to be used by a human inside of the maze. It's similar to a simple recursive backtracker and will find a solution for all mazes.

Description:

As you walk down a passage, draw a line behind you to mark your path. When you hit a dead end turn around and go back the way you came. When you encounter a junction you haven't visited before, pick a new passage at random. If you're walking down a new passage and encounter a junction you have visited before, treat it like a dead end and go back the way you came so that you won't go around in circles or missing passages. If walking down a passage you have visited before (i.e. marked once) and you encounter a junction, take any new passage if one is available, otherwise take an "old" one. Every passage will be either empty (if not visited yet), marked once, or marked twice (if you were forced to backtrack). When you reach the solution, the paths which were marked exactly once will indicate the direct way back to the start. If the maze has no solution, you'll find yourself back at the start with all passages marked twice.

Upvotes: 4

amit
amit

Reputation: 178521

Shortest path algorithms are finding shortest path to the exit, no matter where the exit is.

If the cost is equal - BFS will do - otherwise, you need something like dijkstra's algorithm or A* algorithm [which is basically an informed dijkstra] to find the shortest path.

To use these algorithms, you need to model 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 }

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

Upvotes: 2

Related Questions