Attention |
Topic was automatically imported from the old Question2Answer platform. | |

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
```