How can I make individual paths acyclical while allowing multiple paths to traverse the same vertices?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By mfsgiant

I am recreating an old family favorite board game in Godot (Rail Baron). You roll dice and then move exactly that far along railroads (edges) from stop to stop (vertices). essentially it’s “exercises in graph theory: the game”.

The function I’ve written to find all vertices k moves away from a given vertex (returning all legal moves given a die roll i) doesn’t work because if a vertex has been visited before, the function won’t recur on that vertex, meaning each vertex can only be traversed once while looking for paths, and anywhere there is a vertex with more than 2 adjacent edges, legal paths will be missed.

I thought about just generating every possible path of length k, then doing a shortest path search from the last vertex of each of those paths back to the starting vertex to filter out the cyclical paths, but since the game is played with up to 3d6, it quickly becomes unfeasible to do that - a freeze while 18! computations are performed would not make for a very smooth user experience.

I have read some mathematical proofs that it’s possible to retrieve the set of vertices I want, but I’m struggling to even start converting them to usable code. Recursion is not my strong suit and neither are formal maths.

Here’s a pdf of the game board to help visualize the graph https://www.railgamefans.com/rbp/files/u21sm.pdf

and here is my pathfinding function. My graph is represented as an adjacency list.

var visited = []
func get_move_options(i, stop):
    var counter = i
    visited.append(stop)
    while counter > 0:
        counter -= 1
        for neighbor in adjList[stop]:
            if not neighbor.name in visited:
                get_move_options(counter, neighbor.name)
    var stopNodeHighlight = get_parent().get_node(stop).get_node('Highlight')
    if stopNodeHighlight:
        stopNodeHighlight.visible = true
:bust_in_silhouette: Reply From: Aeris130

If I understand this correctly then given a (potentially) cyclical graph, you want to find the shortest path to every node that’s K steps away from a given start node.

Run a BFS on your graph from your start position and tag each node that it traverses as visited, also store the node you visited it from (referred to as the parent). Keep track of how many nodes you’ve passed (the distance from start to the current node). Abort whenever you run into a node with only visited neighbors. This way each node only gets visited once, and since you’re doing a BFS you’re guaranteed to always find the shortest path to every node before any longer path runs into it.

Stop traversing whenever you reach a node at the target distance and store it as a potential move candidate. If a node only has previously visited neighbors and your current distance is less than your target distance then abort since no valid movement target exists from here.

Once you have all valid candidates (if any), pick whichever one you like and traverse the nodes backwards by moving from node A to the parent of A until you reach the start. Store the nodes you traverse along the way to get your path.