Creating a graph from a string

Question

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.

AKX · Accepted Answer · 2021-02-04 17:36:32Z

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)}}

Collectives™ on Stack Overflow

Creating a graph from a string

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related