Let’s consider a “maze” defined by a string, for example
''' ################ #******######### #*####*********# ##############*# #*****#*#***##F# #*###*###*#****# #S###*****###### ################ '''
The sign “#” denotes a wall and the sign “*” denotes the possible path. Moreover “S” is the starting point and “F” is the destination.
I would like to apply a path searching algorithm to solve this labyrinth for instance Breadth-First Search. I’ve read that that algorithm uses a graph to find the proper path. Here comes my question.
I would like to create a graph out of my path. I think it should look something like this:
graph = {
0: [],
...
17: [18],
18: [17, 19],
...
}
as the first node is a wall so it is not linked to any path and the seventeenth node is a path and it is linked to his neighbour and so on.
My first thought was to implement several function, different ones for the center of the maze and the sides.
For example I would like to check, for all nodes i inside the graph (by inside I mean nodes which are not on the sides) I would check whether they are linked to i-n_1, i-n_2, i-n_3, i-n_4, because we can only go downstairs, upstairs, left and right. n_j would depend on the size of the maze.
However I find that idea to be completely ineffective and ugly. I would appreciate any other ideas or tips.
Advertisement
Answer
It isn’t too hard to read a string like that into a graph.
The first function gets all the coordinates of non-wall cells, and the second function figures out which ones are neighbors of which.
import collections
def read_maze_string(maze_string):
start_coord = None
end_coord = None
non_walls = set()
for y, row in enumerate(maze_string.strip().splitlines()):
for x, c in enumerate(row):
if c == "#":
continue
non_walls.add((x, y))
if c == "S":
start_coord = (x, y)
if c == "F":
end_coord = (x, y)
return (non_walls, start_coord, end_coord)
def get_graph(non_walls):
neighbors = collections.defaultdict(set)
neighbor_deltas = [(-1, 0), (+1, 0), (0, -1), (0, +1)] # You could also add the diagonal deltas
for c in non_walls:
x, y = c
for dx, dy in neighbor_deltas:
nc = (x + dx, y + dy) # neighbor coordinate
if nc in non_walls:
neighbors[c].add(nc)
return dict(neighbors)
non_walls, start_coord, end_coord = read_maze_string(
"""
################
#******#########
#*####*********#
##############*#
#*****#*#***##F#
#*###*###*#****#
#S###*****######
################
"""
)
graph = get_graph(non_walls)
print(graph)
The output is e.g.
{(3, 4): {(4, 4), (2, 4)}, (14, 4): {(14, 3), (14, 5)}, (3, 1): {(4, 1), (2, 1)}, (5, 4): {(4, 4), (5, 5)}, (5, 1): {(6, 1), (4, 1)}, (9, 2): {(8, 2), (10, 2)}, (9, 5): {(9, 6), (9, 4)}, (11, 2): {(12, 2), (10, 2)}, (11, 5): {(12, 5), (11, 4)}, (8, 6): {(9, 6), (7, 6)}, (13, 2): {(14, 2), (12, 2)}, (1, 6): {(1, 5)}, (13, 5): {(12, 5), (14, 5)}, (6, 2): {(6, 1), (7, 2)}, (14, 3): {(14, 2), (14, 4)}, (5, 6): {(6, 6), (5, 5)}, (8, 2): {(9, 2), (7, 2)}, (11, 4): {(10, 4), (11, 5)}, (10, 2): {(11, 2), (9, 2)}, (9, 4): {(10, 4), (9, 5)}, (2, 4): {(3, 4), (1, 4)}, (1, 2): {(1, 1)}, (2, 1): {(3, 1), (1, 1)}, (1, 5): {(1, 6), (1, 4)}, (6, 1): {(6, 2), (5, 1)}, (7, 6): {(6, 6), (8, 6)}, (12, 2): {(13, 2), (11, 2)}, (12, 5): {(13, 5), (11, 5)}, (14, 2): {(13, 2), (14, 3)}, (4, 1): {(3, 1), (5, 1)}, (14, 5): {(13, 5), (14, 4)}, (4, 4): {(5, 4), (3, 4)}, (5, 5): {(5, 4), (5, 6)}, (10, 4): {(11, 4), (9, 4)}, (1, 1): {(1, 2), (2, 1)}, (9, 6): {(9, 5), (8, 6)}, (1, 4): {(2, 4), (1, 5)}, (7, 2): {(8, 2), (6, 2)}, (6, 6): {(7, 6), (5, 6)}}