Version 5 of MazeSolver

Updated 2008-05-02 14:40:10 by kpv

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} {0 1 1 0 -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.

---

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.

---