Breadth First Search Graph Based Pathfinding (Find shortest distance between two graph 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 Graph Based Pathfinding (Find shortest distance between two graph points)

#1 Post by henvu50 »

Code to find the shortest distance between any of these two points. can be customized.
Image

Code: Select all


# look at image above. Now look at the graph below. 
# A leads to B, E, C... ........
# E leads to A, B, D.... and so on... now you know how to customize it to your liking
define graph = {'A': ['B', 'E', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F', 'G'],
        'D': ['B', 'E'],
        'E': ['A', 'B', 'D'],
        'F': ['C'],
        'G': ['C']}

init python:

    def BFS_SP(graph, start, goal):
        explored = []

        queue = [[start]]

        if start == goal:
            return

        while queue:
            path = queue.pop(0)
            node = path[-1]

            if node not in explored:
                neighbours = graph[node]

                for neighbour in neighbours:
                    new_path = list(path)
                    new_path.append(neighbour)
                    queue.append(new_path)

                    if neighbour == goal:
                        return new_path
                explored.append(node)


label findDistanceBetweenTwoGraphPoints:

    #how to use it
    $ test34 = BFS_SP(graph, 'A', 'D')
    $ test34 = "".join(test34)
     #output the shortest distance, it will show A B D	
    "[test34]"


Post Reply

Who is online

Users browsing this forum: No registered users