• 1

• 145.5k
• 22
• 190
• 478

• 41
• 1

I've written an AI (well... it's not really that intelligent) that plays the board game Ticket to Ride. In that game, cities are essentially nodes of a graph, linked together by train tracks (the edges of the graph). The goal is form routes between cities, but it doesn't matter how circuitous or direct a route is as long as it's unbroken.

The set of potential locations for tracks is limited, and different tracks have different costs. To assist my AI in deciding where to place tracks, I wrote the following modified version of Dijkstra's shortest path algorithm. The difference between it and the "normal" Dijkstra is that it accounts for cities that are already connected to each other, similar to what was described in this Programmers SE question. Groups of connected cities in between the "target" cities are treated similarly.

protected Stack<City> getShortestPath(Set<City> startSubgraph, Set<City> endSubgraph) {
 List<DijkstraCity> unvisited = new LinkedList<DijkstraCity>();
 EnumMap<City, DijkstraCity> dijkstraCities = new EnumMap<City, DijkstraCity>(City.class);
 initializeDijkstra(unvisited, dijkstraCities);
 initializeDijkstraDistances(dijkstraCities, startSubgraph);
 while (continueDijkstra(unvisited, endSubgraph)) {
 Collections.sort(unvisited);
 DijkstraCity currentDc = unvisited.get(0); // Depends on unvisited being sorted
 City currentName = currentDc.name;
 CityNode currentCn = board.getCityByName(currentName);
 // For each neighbor: see if unvisited and path available
 // If so, calculate tentative distance
 // If tentative distance less than current best, save as new best
 Set<City> neighbors = currentCn.getNeighbors();
 int currentBaseDist = currentDc.tentativeDist;
 for (City neighbor : neighbors) {
 // Has the city already been visited?
 DijkstraCity neighborDc = dijkstraCities.get(neighbor);
 if (!unvisited.contains(neighborDc))
 continue;
 // Is a path/route to the city even open to this player?
 if (board.getRoutesForPlayer(currentName, neighbor, this) == null)
 continue;
 // At this point, city is unvisited and route is available
 // Calculate distance
 int distFromCurrent = currentBaseDist + currentCn.getLengthToNeighbor(neighbor);
 if (distFromCurrent < neighborDc.tentativeDist) {
 neighborDc.tentativeDist = distFromCurrent;
 neighborDc.previous = currentDc;
 }
 // Since it's possible for the player to already own routes
 // between the start and endpoints, add an extra check
 DijkstraCity connectedDc = null;
 for (Set<City> cityGroup : connectedCities) {
 if (cityGroup.contains(neighbor)) {
 for (City connectedCity : cityGroup) {
 connectedDc = dijkstraCities.get(connectedCity);
 if (connectedDc.tentativeDist > neighborDc.tentativeDist) {
 connectedDc.tentativeDist = neighborDc.tentativeDist;
 connectedDc.previous = neighborDc; // This can cause the returned path to include non-adjacent cities!
 }
 }
 }
 }
 }
 // If all unvisited cities are at MAX_VALUE after the neighbors of
 // the current city have been checked, the destination is
 // unreachable, and we should abort
 if (currentDc.tentativeDist == Integer.MAX_VALUE)
 return null;
 // Mark the city we just completed as visited before next loop
 unvisited.remove(currentDc);
 }
 // Leaving the above loop = all necessary cities visited
 // Almost done, we just need to determine where the end is now...
 int lowestPathToEnd = Integer.MAX_VALUE;
 DijkstraCity endCity = null;
 for (City endCandidate : endSubgraph) {
 DijkstraCity endCandidateDc = dijkstraCities.get(endCandidate);
 if (endCandidateDc.tentativeDist < lowestPathToEnd) {
 lowestPathToEnd = endCandidateDc.tentativeDist;
 endCity = endCandidateDc;
 }
 }
 // ...and finally follow the path back to the start.
 Stack<City> shortestPath = new Stack<City>();
 do {
 shortestPath.push(endCity.name);
 endCity = endCity.previous;
 } while (endCity != null);
 return shortestPath;
}

Here are the two helper methods used at the beginning, and the loop condition:

private void initializeDijkstra(List<DijkstraCity> unvisited, EnumMap<City, DijkstraCity> dijkstraMap) {
 DijkstraCity van = new DijkstraCity(VANCOUVER);
 DijkstraCity sea = new DijkstraCity(SEATTLE);
 // and so on for the other cities on the board; cut just to save space
 unvisited.add(van);
 unvisited.add(sea);
 // and so on for the other cities on the board; cut just to save space
 dijkstraMap.put(VANCOUVER, van);
 dijkstraMap.put(SEATTLE, sea);
 // and so on for the other cities on the board; cut just to save space
}
private void initializeDijkstraDistances(EnumMap<City, DijkstraCity> dijkstraCities, Set<City> startCityNames) {
 for (City city : startCityNames)
 dijkstraCities.get(city).tentativeDist = 0;
}
/**
 * Technically, we only have to run until all of the cities in "unvisited"
 * are also in "endSubgraph," but checking for that would be a pain, so
 * we'll save that micro-optimization for later.
 */
private boolean continueDijkstra(List<DijkstraCity> unvisited, Set<City> endSubgraph) {
 return !unvisited.isEmpty();
}

This is the helper class referenced by the method above

public class DijkstraCity implements Comparable<DijkstraCity> {
 public City name;
 public int tentativeDist;
 public DijkstraCity previous;
 
 public DijkstraCity(City name) {
 this.name = name;
 tentativeDist = Integer.MAX_VALUE;
 previous = null;
 }
 @Override
 public int compareTo(DijkstraCity otherCity) {
 return tentativeDist - otherCity.tentativeDist;
 }
 
 @Override
 public String toString() {
 return name.toString();
 }
}

The Dijkstra method and its helpers are located within an abstract Player class. City is an Enum that just lists the cities in the game (VANCOUVER, SEATTLE, etc.). All the collections used are the "standard" versions found in java.util.

I'm mostly interested in how I could have done this in a more efficient or elegant way.