Breadth First Search Grid Based Pathfinding w/Walls (Find shortest distance between grid points)

A place for Ren'Py tutorials and reusable Ren'Py code.
Forum rules
Do not post questions here!

This forum is for example code you want to show other people. Ren'Py questions should be asked in the Ren'Py Questions and Announcements forum.
Post Reply
Message
Author
henvu50
Veteran
Posts: 337
Joined: Wed Aug 22, 2018 1:22 am
Contact:

Breadth First Search Grid Based Pathfinding w/Walls (Find shortest distance between grid points)

#1 Post by henvu50 »

Here is code to find the shortest distance between a specified grid point and the number 2 on the following grid. The grid can be expanded if you want. You can do whatever you want with it.

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


Post Reply

Who is online

Users browsing this forum: No registered users