(maze)
| 40 | return [[None for x in range(width)] for y in range(height)] |
| 41 | |
| 42 | def escape_route(maze): |
| 43 | final = [] |
| 44 | |
| 45 | # check if the maze has valid dimensions |
| 46 | height, width = get_maze_size(maze) |
| 47 | if height < 1 or width < 1: |
| 48 | return None |
| 49 | |
| 50 | # create status tracking lists |
| 51 | y, x = 0, 0 |
| 52 | parent = create_parent_grid(height, width) |
| 53 | unavailable = create_unavailable_grid(height, width) |
| 54 | |
| 55 | # initialise lists with current node |
| 56 | available = [ # the "open list" |
| 57 | [], # y positions |
| 58 | [] # x positions |
| 59 | ] |
| 60 | unavailable[y][x] = True |
| 61 | |
| 62 | # find a path to the exit |
| 63 | while not maze[y][x].exit: |
| 64 | # mark adjacent nodes as available |
| 65 | current = maze[y][x] |
| 66 | directions = [ |
| 67 | current.north, |
| 68 | current.east, |
| 69 | current.south, |
| 70 | current.west |
| 71 | ] |
| 72 | for index in range(4): |
| 73 | if directions[index]: |
| 74 | yo, xo = get_offset(index) |
| 75 | yn, xn = (y + yo), (x + xo) |
| 76 | if not unavailable[yn][xn]: |
| 77 | available[0].append(yn) |
| 78 | available[1].append(xn) |
| 79 | parent[yn][xn] = get_opposite_index(index) |
| 80 | |
| 81 | # mark the current node as unavailable |
| 82 | unavailable[y][x] = True |
| 83 | |
| 84 | # ran out of positions to move to |
| 85 | if len(available[0]) < 1 or len(available[1]) < 1: |
| 86 | return None |
| 87 | |
| 88 | # get the next available node |
| 89 | y, x = available[0].pop(0), available[1].pop(0) |
| 90 | |
| 91 | # backtrack current node to get the path |
| 92 | while parent[y][x] is not None: |
| 93 | index = get_opposite_index(parent[y][x]) |
| 94 | final.insert(0, get_direction(index)) |
| 95 | # reference the next parent |
| 96 | yo, xo = get_offset(parent[y][x]) |
| 97 | y, x = (y + yo), (x + xo) |
| 98 | |
| 99 | return final |
no test coverage detected