Intermediate: check if connection to other edge is possible.End: Terminate possibleRoute, add it to the found list.Three things can be encountered: an end, intermediate or a split. Add a route to check (possibleRoute) for every end, and for every two edges + one vertex combination found (3, since degree is 3) at every split.Make a list of ends (vertices where degree=1) and splits (vertices where degree=3).Derive a graph from the main graph using all edges from a player, adding the vertices of the main graph connected to the edges.# otherwise, add the new paths to the queue Ruby pseudocode (assumes an get_neighbors function for each node) def explode nĮxploded = n.get_neighbors # get all neighborsĮlect! Assume all nodes with cities that do not belong to the current player automatically deactivated always.IMPORTANT NOTE, thanks to Cameron MacFarland Note that this is slightly inefficient, but if performance doesn't matter, then this would work :) The maximum you have now is your longest road length, for the given player. Add all exploded paths, if any, back into the queue.Īfter you do this once, move onto the next activated node and start the process all over again.If greater than it, it is the new maximum. If there are no valid "explosions" of the previous path, then compare that length of that path to the known maximum.Deactivate all nodes stepped to during the last step.By "valid", the next node must be connected to the last one by a road, and it also must be activated. Pop the first path out of the queue and "explode" it - that is, find all valid paths that are the the path + 1 more step in a valid direction.Add a path containing only the initial dead-end node to the queue.If there are no paths from this initial node, or more than one path, mark it deactivated and skip it.How can this be implemented? Here's one possible breadth-first algorithm that can be used: The catch: Once a node has been traversed to, it is "deactivated" for the all searches left in that turn. Skip if it has zero or more than one connected neighbors and find all of the player's paths starting from it in a breadth-first manner. Whenever you need to backtrack, because there are no more branches, take a note of the current length, and if it is longer than the "previous maximum", store the new length as the maximum.ĭo this for all the sets, and you should have your longest road. This will allow the algorithm to stop when it "eats its own tail". Always mark road segments as well, and don't branch into segments already marked. Now, from the segment you picked, do a recursive branching out depth-first search, keeping track of the length of the current road you've found so far. If you can't do that, then the whole set is looping (one or more), so pick a random segment in this case.Pick a random road segment in the set that has only one connected road segment out from it (ie.This gives you one or more sets, each containing one or more road segments. You can ignore those other segments as though they weren't even on the map. Note, in the above, and following, steps, only consider the current players segments. You need to detect this and not branch past the settlement.
Note: As per the official Catan Rules, a road can be broken if another play builds a settlement on a joint between two segments. If there's unmarked segments left, they're part of a new set, pick a random one and start back at 1 with another set.Keep going from new segments until you cannot find any more unmarked segments that are connected to those currently in the set.If found road segment is not already in the set, add it, and mark it.follow connected segments in both directions that aren't marked (if they're marked, we've already been here) Pick a random road segment, add it to a set, and mark it.There's various methods on doing this, but here's one: To begin with, separate out the roads into distinct sets, where all the road segments in each set are somehow connected. This should be a rather easy algorithm to implement.
0 kommentar(er)
