MazeSolver

FF 2008-05-02 Today I was looking if any maze solving algorithm existed on the wiki. I couldn't found any.

I only know the stupid recursive one and coded it in 9 lines.

How does a better (smarter) algorithm work?

 set maze_str {
    {##############################}
    {#..........#.................#}
    {##.#######.#.##.#######.####.#}
    {#.##.....#.#.#.......#.....#.#}
    {#....###.#.#.#######.#.###.#.#}
    {######...#...#.......#.#.#.###}
    {#......#.#.###.#######...###*#}
    {#.####.#.#.#.#.#...#.###.#.#.#}
    {#.#....#...#.....#...........#}
    {##############################}
 }
 set maze {} ; foreach r $maze_str {lappend maze [split $r {}]}
 set w [llength [lindex $maze 0]]
 set h [llength $maze]
 set v {}

 proc go {x y {p {}}} {
    if [info exists ::path] return
    if {0 <= [lsearch -exact  $::v $x,$y]} {return}
    set c [lindex [lindex $::maze $y] $x]
    if {$c == "*"} {set ::path $p ; return}
    if {$c == "#"} {return}
    lappend ::v $x,$y
    lappend p $x,$y
    foreach {dx dy} {1 0 0 1 -1 0 0 -1} {
        go [expr {$x+$dx}] [expr {$y+$dy}] $p
    }
 }

 go 1 1

# Display the result in a nice Tk Canvas:

 package require Tk
 set cs 10
 canvas .c -width [expr {$cs*$w}] -height [expr {$cs*$h}] -background white
 for {set y 0} {$y < $h} {incr y} {
    for {set x 0} {$x < $w} {incr x} {
        set c [lindex [lindex $::maze $y] $x]
        set color [string map {* red # black . white} $c]
        if {0 <= [lsearch -exact  $::v $x,$y]} {set color yellow}
        if {0 <= [lsearch -exact  $::path $x,$y]} {set color green}
        if {$x == 1 && $y == 1} {set color orange}
        .c create rectangle [expr {$cs*$x}] [expr {$cs*$y}] \
            [expr {$cs*(1+$x)}] [expr {$cs*(1+$y)}] \
            -fill $color -outline black
    }
 }
 pack .c

NEM 2008-05-02: Your solution does depth-first search. Various alternatives are possible. If you know some heuristic for how far a given node is from the exit (e.g. straight-line or Manhattan distance) then you could use A*, which is guaranteed to be optimal if the heuristic is admissable -- see Searching A Star In Space or Heuristic Searches.

DKF: Could also consider using breadth-first searching, which guarantees to find an optimal solution (assuming it exists). OTOH, it can require a lot of memory and it does not translate to real life (depth-first is like the wall-following algorithm).

NEM: Yes, in this case where the cost of each step is identical (i.e. cost of route = number of steps) then breadth-first search is the best you can do for uninformed search strategies: the first solution it finds will be optimal, but it may search a lot of the space finding it. The solution given, while DFS, does memorise previous states visited (essential if you want to avoid looping in DFS), so has the same worst-case memory requirements as BFS.

Jaf: I remember reading about a "Flood Algorithm" that goes approximately like this:

1. The starting point is "wet", count=0
2. Every point that touches (up, down,left,right) a "wet" point is set to "wet"
3. incr count,
4. set the points that changed to "wet" to count
5. Repeat 2) until the end point is "wet"
6. Starting at the end point find the neighbour with the lowest count, put in list
7. Move to last point in list, find next neighbour, append to list
8. repeat 7) until start point is reached

I think that it is the same as depth first, it just uses the maze itself as a "stack". Cheers.

Lars H: No, that's a breadth first search: at every step, visit every neighbour of the points that were visited in the step before. The "count" is the length of the shortest path from current point to the starting point.

DKF: The other thing to consider is whether the maze is a tree or a general graph (i.e. with loops). In the tree case, you can always generate a solution (even if non-optimal) by following a wall since you're guaranteed to encounter every location in the maze eventually. With a general graph, you don't have those guarantees at all and you need to store state in order to figure out where you've been. (Actually, this extends to the generalized searching required for model checking, except there you need more than one sort of mark for places that you've seen...)

KPV Well, 3D Maze will solve any maze it generates, but it cheats and uses information gleaned during the maze's construction. Still, its kind of a clever algorithm to be able to solve from anywhere inside the maze.