Lemma Soft Forums

Code: Select all

# 0 is walkable, 1 is wall, 2 is goal.
# you can have multiple number 2 goals if you want, it will try to find the one closest to you.
define graph = [
    [0, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 2, 1],
    [0, 0, 0, 1]
]

init python:

    import queue

    class Node:
        def __init__(self, val, pos):
            self.val = val
            self.pos = pos
            self.visited = False
        def __repr__(self):
            return repr(self.pos)

    def bfs(graph, start):
        fringe = [[start]]
        if start.val == 'g':
            return [start]
        start.visited = True
        width = len(graph[0])
        height = len(graph)
        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while fringe:
            path = fringe.pop(0)
            node = path[-1]
            pos = node.pos
            for move in moves:
                if not (0 <= pos[0] + move[0] < height and 0 <= pos[1] + move[1] < width):
                    continue
                neighbor = graph[pos[0] + move[0]][pos[1] + move[1]]
                if neighbor.val == 'g':
                    return path + [neighbor]
                elif neighbor.val == 'o' and not neighbor.visited:
                    neighbor.visited = True
                    fringe.append(path + [neighbor])  # creates copy of list
        raise Exception('Path not found!')

label findShortestPath:

    $ TRANSLATE = {0: 'o', 1: 'x', 2: 'g'}
    $ graph = [[Node(TRANSLATE[x], (i, j)) for j, x in enumerate(row)] for i, row in enumerate(graph)]
    $ path = bfs(graph, graph[1][1])

     #output shortest path to see result in renpy
    "[path]"