[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:

[http://freemove.it/main/fileadmin/maze.png]
----
 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.
----
!!!!!!
%| enter categories here |%
!!!!!!