maze_solver/maze_solver.py at master · SherryFeng123/maze_solver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#Starting positions
ORIGIN_X = -200
ORIGIN_Y = 200
side = 10
begin_x = ORIGIN_X - 10
begin_y = ORIGIN_Y

def readMaze(filename):
    matrix = []
    f = open(filename,'r')
    lines = f.readlines()

    for x in lines:
        my_list = []
        for y in x:
            if y == "#":
                y = 1
                my_list.append(y)
            elif y == " ":
                y = 0
                my_list.append(y)
        matrix.append(my_list)

    return matrix

def drawSquare(x,y,side, t, col = "black"):
    t.penup()
    t.goto(x+ORIGIN_X,y+ORIGIN_Y)
    t.color(col)
    t.begin_fill()
    t.pendown()

    for i in range(0,4):
        t.forward(side)
        t.left(90)
    t.end_fill()

def drawMaze(maze,t,col):
    t.color(col)
    for index in range(0,len(maze)):
        for j in range(0,len(maze[0])):
            if maze[index][j] == 1:
                drawSquare(side*j, side*-index, side, t,"black")

wall = 1

def followLeftWall(maze,t,col):
    t.color(col)
    i = 1
    j = 0
    currDirection = "East"
    drawSquare(side*j,side*-i, side,t,col = "yellow")

    while i != len(maze)-2 or j != len(maze[0])-1:
        print("I went", currDirection)
        currDirection = nextMove(maze,i,j,currDirection)
        t.penup()
        t.goto(begin_x,begin_y)
        t.pendown()

        if currDirection == "East":
            j = j+1
        elif currDirection == "North":
            i = i-1
        elif currDirection == "South":
            i = i+1
        elif currDirection == "West":
            j = j-1
        drawSquare(10*j,10*-i, 10,t,col = "yellow")


def nextMove(maze,i,j,currDirection):

    #checkEast
    if currDirection == "East":
        if maze[i-1][j] != wall:
            return "North"
        elif maze[i][j+1]  != wall:
            return "East"
        elif maze[i+1][j] != wall:
            return "South"
        elif maze[i][j-1] != wall:
            return "West"

    #checkNorth
    if currDirection == "North":
        if maze[i][j-1]  != wall:
            return "West"
        elif maze[i-1][j] != wall:
            return "North"
        elif maze[i][j+1]  != wall:
            return "East"
        elif maze[i+1][j]  != wall:
            return "South"


    #checkSouth
    if currDirection == "West":
        if maze[i+1][j]  != wall:
            return "South"
        elif maze[i][j-1] != wall:
            return "West"
        elif maze[i-1][j] != wall:
            return "North"
        elif maze[i][j+1]  != wall:
            return "East"

    #checkWest
    if currDirection == "South":
        if maze[i][j+1]  != wall:
            return "East"
        elif maze[i+1][j]  != wall:
            return "South"
        elif maze[i][j-1]  != wall:
            return "West"
        elif maze[i-1][j]  != wall:
            return "North"

def main(filename,algorithm):
    import turtle
    t = turtle.Turtle()
    screen = turtle.Screen()
    maze = readMaze(filename)
    screen.tracer(0)
    drawMaze(maze,t,"black")
    screen.update()
    screen.tracer(10)
    if algorithm == "followLeftWall":
        followLeftWall(maze,t,"yellow")

main("testMaze3.txt","followLeftWall")