Finding the longest road in a Settlers of Catan game algorithmically

Question

I'm writing a Settlers of Catan clone for a class. One of the extra credit features is automatically determining which player has the longest road. I've thought about it, and it seems like some slight variation on depth-first search could work, but I'm having trouble figuring out what to do with cycle detection, how to handle the joining of a player's two initial road networks, and a few other minutiae. How could I do this algorithmically?

For those unfamiliar with the game, I'll try to describe the problem concisely and abstractly: I need to find the longest possible path in an undirected cyclic graph.

Answer 1

This should be a rather easy algorithm to implement.

To begin with, separate out the roads into distinct sets, where all the road segments in each set are somehow connected. There's various methods on doing this, but here's one:

1. Pick a random road segment, add it to a set, and mark it
2. Branch out from this segment, ie. follow connected segments in both directions that aren't marked (if they're marked, we've already been here)
3. If found road segment is not already in the set, add it, and mark it
4. Keep going from new segments until you cannot find any more unmarked segments that are connected to those currently in the set
5. 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

Note: As per the official Catan Rules, a road can be broken if another play builds a settlement on a joint between two segments. You need to detect this and not branch past the settlement.

Note, in the above, and following, steps, only consider the current players segments. You can ignore those other segments as though they weren't even on the map.

This gives you one or more sets, each containing one or more road segments.

Ok, for each set, do the following:

1. Pick a random road segment in the set that has only one connected road segment out from it (ie. you pick an endpoint)
2. If you can't do that, then the whole set is looping (one or more), so pick a random segment in this case

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. Always mark road segments as well, and don't branch into segments already marked. This will allow the algorithm to stop when it "eats its own tail".

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.

Do this for all the sets, and you should have your longest road.

Answer 2

I would suggest a breadth-first search.

For each player:

• Set a default known maximum of 0

• Pick a starting node. 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. The catch: Once a node has been traversed to, it is "deactivated" for the all searches left in that turn. That is, it may no longer be traversed.

  How can this be implemented? Here's one possible breadth-first algorithm that can be used:

  1. If there are no paths from this initial node, or more than one path, mark it deactivated and skip it.
  2. Keep a queue of paths.
  3. Add a path containing only the initial dead-end node to the queue. Deactivate this node.
  4. 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. By "valid", the next node must be connected to the last one by a road, and it also must be activated.
  5. Deactivate all nodes stepped to during the last step.
  6. If there are no valid "explosions" of the previous path, then compare that length of that path to the known maximum. If greater than it, it is the new maximum.
  7. Add all exploded paths, if any, back into the queue.
  8. Repeat 4-7 until the queue is empty.

• After you do this once, move onto the next activated node and start the process all over again. Stop when all nodes are deactivated.

• The maximum you have now is your longest road length, for the given player.

Note that this is slightly inefficient, but if performance doesn't matter, then this would work :)

IMPORTANT NOTE, thanks to Cameron MacFarland

• Assume all nodes with cities that do not belong to the current player automatically deactivated always.

---

Ruby pseudocode (assumes an get_neighbors function for each node)

def explode n
  exploded = n.get_neighbors             # get all neighbors
  exploded.select! { |i| i.activated? }  # we only want activated ones
  exploded.select! { |i| i.is_connected_to(n) } # we only want road-connected ones
  return exploded
end

max = 0

nodes.each do |n|                 # for each node n
  next if not n.activated?        # skip if node is deactivated
  if explode(n).empty? or explode(n).size > 1
    n.deactivate                  # deactivate and skip if
    next                          # there are no neighbors or
  end                             # more than one

  paths = [ [n] ]                 # start queue

  until paths.empty?              # do this until the queue is empty

    curr_path = paths.pop         # pop a path from the queue
    exploded = explode(curr_path) # get all of the exploded valid paths

    exploded.each { |i| i.deactivate }  # deactivate all of the exploded valid points

    if exploded.empty?                  # if no exploded paths
      max = [max,curr_path.size].max    # this is the end of the road, so compare its length to
                                        # the max
    else
      exploded.each { |i| paths.unshift(curr_path.clone + i) }  
                                        # otherwise, add the new paths to the queue
    end

  end

end

puts max