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]"