maze/BreadthFirstSearch.py at master · Audrey-Lee88/maze · 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
import queue
import time


def start(maze):
    # Find starting pos
    for x, pos in enumerate(maze[0]):
        if pos == "s":
            s = x
    return s


def valid(maze, moves, begin):
    i = begin
    j = 0
    for move in moves:
        # Move left, right, up, or down
        if move == "W":
            i -= 1
        elif move == "E":
            i += 1
        elif move == "N":
            j -= 1
        elif move == "S":
            j += 1

        # Check if in row length and column length
        if not (0 <= i < len(maze[0]) and 0 <= j < len(maze)):
            return False
        # Check if not in wall
        elif maze[j][i] == "0":
            return False

    return True


def find_end(maze, moves, begin):
    i = begin
    j = 0
    for move in moves:
        if move == "W":
            i -= 1
        elif move == "E":
            i += 1
        elif move == "N":
            j -= 1
        elif move == "S":
            j += 1

    if maze[j][i] == "e":
        print("Shortest Path Directions: " + moves)
        return True

    return False


def bfs(maze):
    # Audrey
    # breadth first search
    # uses a queue to visit cells in increasing distance order from the start
    # until the finish is reached
    q = queue.Queue()
    q.put("")
    add = ""
    beg = start(maze)
    t = time.clock()
    while not find_end(maze, add, beg):
        add = q.get()
        # print(add)
        for j in ["N", "S", "E", "W"]:
            if time.clock()-t > 5:
                print('nope',time.clock()-t)
                return False
            push = add + j
            if valid(maze, push, beg):
                # print(push)
                q.put(push)

if __name__ == "__main__":

    m = [["0", "0", "1", "1", "0", "s", "0", "1", "1"],
        ["0", "1", "1", "1", "1", "1", "1", "1", "0"],
        ["0", "1", "1", "1", "1", "1", "0", "1", "1"],
        ["0", "1", "1", "1", "1", "1", "0", "1", "0"],
        ["1", "1", "0", "1", "1", "1", "0", "1", "0"],
        ["1", "1", "0", "1", "1", "1", "1", "1", "1"],
        ["1", "1", "0", "1", "1", "1", "1", "0", "1"],
        ["1", "1", "0", "1", "1", "1", "1", "1", "1"],
        ["0", "1", "0", "1", "1", "1", "1", "1", "1"],
        ["0", "0", "0", "0", "1", "0", "1", "1", "e"]]

    for _ in range(10):
        bfs(m)
        t = time.clock()
        print(t)