Python Maze

[Findlebot]

Okay, I need to write a maze solver for the maze in the text file (yes it is an assignment). I am not asking for a direct answer, I just want someone to propose ways of solving the maze( I also have to mark the paths taken in the maze). The problem is that I have learned nothing in the class the assignment is for because the professor tends to ramble on about anything from Star Trek jokes to WoW (seriously). As a result, I am completely lost on what to do on this assignment. The only code I have so far prints the maze:

def main():
    mazefile = open('Python Maze.txt','r+')

    
    for line in mazefile:
        line = line.strip()
        print line

    
    mazefile.close()

    
    

main()

[woooee]

I would assign a unique number to each character that makes up a maze. Then you can find S(tart) and proceed in whatever direction there is an space, keeping track of the path taken so you try different solutions. Also, you might want a variable that is set to True if there are two or more options within the path, so you can repeat with the other option.

[cmpgeek]

I am in this same dilemma(actually the exact same class it sounds like). I know how i want to solve it, i just do not know the syntax for what i want to do or how to get python to assign something like a coordinate to each character.

[Mathhax0r]

Without going into the full process, I would probably read every line into a list and break each line down into a list of characters. That way, you have a list such that list[2][3] refers to 2 rows down and 3 characters over in the maze. I would also have two variables that represent your current location in the maze clx and cly or anything you want to name them really. You should set your clx and cly to the indices of where the S is at in the maze. Then I would make a function that looks at the coordinates immeadiately next to where your current location is, and move your current location to anywhere there's a space.

Have you ever heard of the way to solve any maze by sticking to one side of it? That means you might wanna have direction, and only move forward when you have a space, and if the space in front of you is a #, then you should turn in a certain direction and check again.

[wowchick]

I need my program to print out every position of the maze! How do I do this???

OPEN, WALL, START, END, SEEN, GOOD = tuple(' #SE!0')

SAMPLE = """
####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##      ## ####  E
# ## #### ## #### ##
#    ####         ##
#S##################
"""
def main():
    maze = [list(x) for x in SAMPLE.splitlines() if x]
    solve(maze, 1, 9, len(maze[0]), len(maze))
    for line in maze:
        print "".join(line)

def solve(maze, posx, posy, sizex, sizey):
    found = 0
    if 0 <= posx < sizex and 0 <= posy < sizey:
        if maze[posy][posx] in (OPEN, START):
            if maze[posy][posx] == OPEN:
                maze[posy][posx] = SEEN
            if (solve(maze, posx+1, posy, sizex, sizey) or
                solve(maze, posx-1, posy, sizex, sizey) or
                solve(maze, posx, posy+1, sizex, sizey) or
                solve(maze, posx, posy-1, sizex, sizey)):
                if maze[posy][posx] == SEEN:
                    maze[posy][posx] = GOOD
                found = 1
        elif maze[posy][posx] == END:
            found = 1
    return found

if __name__ == "__main__":
    main()

[TrustyTony]

This maze program seems to work without the listing of all locations.

Nice hack to initialize many variables with chars this OPEN, WALL, START, END, SEEN, GOOD = tuple(' #SE!0') Here is alternative algorithm finding the road through maze. Actually it is originally logic to move ball in Lines game, but principle is exactly same.

make table (dict with (x,y) as key) with 
a) very_big_number-1 for every cell position which is empty or S, 
b) very_big_number for wall cell position, 
c) 0 for E cell position, remember the position of S

set changed True

while changed
    set changed to False

    for each cell in the dict
        if cell is not wall 
            check every neighbour cell finding smallest value there to minvalue
        if value of current cell is more than found minvalue+1:
              set changed True and
              set current cell position value to minvalue+1

## here we went through maze without changing value in any cell

starting from S position
go to neighbour cell with value (distance) one smaller than this cell and
mark it in maze with 'O'
until 
a) neighbour cell is E cell (ie value 0) or
b) there is not such cell for current cell and 
then the maze is unsolvable, write *Unsolvable maze*, print original problem and finish

We are ready with shortest solution marked with 'O'
write *Maze solved*
and print the maze with 'O's

[wowchick]

how would I put these changes in my code? could you change my program?

[TrustyTony]

I would just implement the pseudo code I wrote based on my Delphi Pascal programs pseudocode in Python. That is your part of job, I think, as I gave quite clear instructions. Maybe you want to check the algorithm for finding the neighbours of cell I gave in other thread. http://www.daniweb.com/forums/post1199135.html#post1199135.

[TrustyTony]

That program given in this thread is
http://labix.org/snippets/labsolver

[TrustyTony]

Unsolvable case in my ball moving algorith (I made it up myself, but surely somebody has done similar algorithm before) probably reduce to checking if Start cells distance is smaller than it is set in the beginning (I wrote the algorithm from memory). Good number for the very big number is m*n, where m and n are maze's dimensions.

If there is equal length solutions, the chosen road depends on the checking order of neighbour cells.

[TrustyTony]

I implemented the distance finding part and here is prove that it finds the distances from every part of labyrinth until the exit.
This is print of distances to exit from every part of labyrinth.

This is actually matrix by which lost person in labyrinth can go shortest way to E exit from anywhere in labyrinth.

####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##      ## ####  E
# ## #### ## #### ##
#    ####         ##
#S##################
. . . . . . . . . . . . . . . . . . . . .
--------------------
21 iterations


200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 

200 200  32  33 200  23  22  21  20 200 200  17  16  17  18 200 200 200  24 200 

200 200  31 200  23 200 200 200  19  18  17  16  15 200  19  20  21  22  23 200 

200  29  30 200  22 200  20 200 200 200 200 200  14 200 200 200 200 200 200 200 

200  28 200 200  21 200  19  18  17  16 200 200  13 200   7   6   5   4 200 200 

200  27 200 200  20 200 200 200 200  15 200 200  12 200 200 200 200   3 200 200 

200  26 200 200  19  18  17  16  15  14 200 200  11 200 200 200 200   2   1   0 

200  25 200 200  20 200 200 200 200  13 200 200  10 200 200 200 200   3 200 200 

200  24  23  22  21 200 200 200 200  12  11  10   9   8   7   6   5   4 200 200 

200   S 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200
>>>

[0x69]

Or... use backtracking algorithm =>
http://en.wikipedia.org/wiki/Backtracking
Main idea-
Save each crossroad decision you take in the tuple form (COL, ROW, DIRECTION) . Such as after N iteratiions you will get list something like: [(1,2,UP),(4,5,DOWN),(6,8,LEFT),(10,14,RIGHT),...] . Fill this list until you get into blind alley OR no NEW crossroads are reachable. If so - return to last crossroad and choose next unvisited direction from that [1..4]. Repeat until you find exit.

[TrustyTony]

Anyway I completed the labyrinth algorithm by my distance algorithm. Here is one sample output for the other labyrinth. I left printing of steps of solution in.

For me this algorithm is very simple with no depths of recursion or back tracking.

The labyrinth
###############
S #     #   # #
# # ### ### # #
# # #       # #
# #   ### # # #
# # # #   # # E
#   # # # # # #
##### # # # # #
#     # # #   #
###############

The distance matrix

17 iterations


150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 

 S   29 150  21  20  19  18  17 150  15  14  13 150   5 150 

150  28 150  22 150 150 150  16 150 150 150  12 150   4 150 

150  27 150  21 150  17  16  15  14  13  12  11 150   3 150 

150  26 150  20  19  18 150 150 150  14 150  10 150   2 150 

150  25 150  21 150  19 150  17  16  15 150   9 150   1   0 

150  24  23  22 150  20 150  18 150  16 150   8 150   2 150 

150 150 150 150 150  21 150  19 150  17 150   7 150   3 150 

150  26  25  24  23  22 150  20 150  18 150   6   5   4 150 

150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 

The walking path (dist: (x,y) coordinates)
30: (1,0)	29: (1,1)	28: (2,1)	27: (3,1)	26: (4,1)	25: (5,1)	24: (6,1)	23: (6,2)	22: (6,3)	21: (5,3)	20: (4,3)	19: (4,4)	18: (4,5)	17: (3,5)	16: (3,6)	15: (3,7)	14: (3,8)	13: (3,9)	12: (3,10)	11: (3,11)	10: (4,11)	9: (5,11)	8: (6,11)	7: (7,11)	6: (8,11)	5: (8,12)	4: (8,13)	3: (7,13)	2: (6,13)	1: (5,13)	

The solved labyrinth
###############
OO#     #   # #
#O# ### ### # #
#O# #OOOOOOO# #
#O#OOO### #O# #
#O#O# #   #O#OO
#OOO# # # #O#O#
##### # # #O#O#
#     # # #OOO#
###############


Running time was 1.193 s
>>>

[TrustyTony]

Major part of program running time seems to be the printing. With only first and last printing enabled the running time changes dramatically:

The labyrinth
###############
S #     #   # #
# # ### ### # #
# # #       # #
# #   ### # # #
# # # #   # # E
#   # # # # # #
##### # # # # #
#     # # #   #
###############

17 iterations


The solved labyrinth
###############
OO#     #   # #
#O# ### ### # #
#O# #OOOOOOO# #
#O#OOO### #O# #
#O#O# #   #O#OO
#OOO# # # #O#O#
##### # # #O#O#
#     # # #OOO#
###############


Running time was 0.121 s
Enter to finish

[TrustyTony]

Update:
My solution seems to be quite same in speed as the other solution:

>>> 
####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##000000## ####00E
# ##0####0## ####0##
#0000####000000000##
#S##################
0.035
>>> ## My solution
>>> 
The solved labyrinth
####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##OOOOOO## ####OOO
# ##O####O## ####O##
#OOOO####OOOOOOOOO##
#O##################


Running time was 0.034 s
Enter to finish

But actually here the IDLE effect is huge.

Here the runs from double clicking:

Previous:

####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##000000## ####00E
# ##0####0## ####0##
#0000####000000000##
#S##################
0.001
Enter to finish

Mine:

The solved labyrinth
####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##OOOOOO## ####OOO
# ##O####O## ####O##
#OOOO####OOOOOOOOO##
#O##################


Running time was 0.016 s
Enter to finish

Here my solution is much slower, but it does give solution for all maze not just from start to end.

[hovestar]

A cheap way of doing this is because you know the maze you have to use just tell it the solution, effectively completing the maze. Or you could devise an AI to follow the left wall, a simple maze solving method. In any case please post the code you use.
Thanks,
Hovestar

[0x69]

Or you could devise an AI to follow the left wall

This doesn't works if maze has disconnected walls.