[Rails-devel] route calculation

[John A. T. <ja...@ja...>]

Ok, I have spent some time figuring out Iain's code and thinking about 
the different games that need to be implemented, and here is the basic 
algorithm I am working on:

Bitvectors are used to store connectivity between nodes and edges.  
Nodes can be various types of stations (cities, towns, off-board areas) 
or internal connectivity nodes (corresponding to junctions between 
hexes).  Edges are essentially track.  These connectivity bitvectors are 
incrementally maintained as tile is placed.

A RouteSet object stores a set of Routes, as well as a bitvector of all 
edges used in any routes.  Each Route knows the train type it is 
building a route for, a bitvector of nodes that have been used on the 
route, a list of nodes used (the bitvector is only used for speed, you 
could do it by simply searching the list repeatedly), an array of 
bitvectors keeping track of the nodes/edges left to be explored for each 
depth in the route, and the statistics of the route in question (the 
total value, how many stations of different types have been seen, etc).

Unlike Iain's code (which generated all possible routes, then tried all 
possible assignments of trains to routes), this algorithm will build 
them together.  I believe that this will be more efficient, but also it 
will be necessary to easily implement some of the constraints various 
games place on sets of routes.  The top level algorithm looks like this:

public void RouteSet.buildRoutes(RouteRecorder goodRoutes) {
	for(int train=0; train<numtrains; train++) {
		route[train].reset();
	}
	while(1) {
		int curtrain=0;
		while(curtrain<numtrains && route[curtrain].nextRoute()) {
			curtrain++;
		}
		if(curtrain>numtrains) break;
		if(isValid()) {
			goodRoutes.saveRouteSet(routes);
		}
	}
}

So basically, it goes through all the trains and for each train every 
possible route (including 0 or 1 nodes) that doesn't interfere with the 
routes of other trains.  For each one, if it is legal (which would 
include things like 1860's requirement that the runs of all a 
corporation's trains intersect), then it is saved for use by the caller.

The algorithm (in pseudo-Java, especially making up for lack of operator 
overloading) for iterating through all possible routes:

// returns true when no more possible routes
public boolean Route.nextRoute() {
	int depth=numNodes;
	boolean f;

	while(depth>=0) {
		while((v=next[depth].getNext())>=0) {
			// for depth=0, the next[] bitvector contains node numbers of stations reachable by the current company
			// for other depths, it contains edge numbers
			if(depth>0) {
				f=appendEdge(v);
			} else {
				f=appendNode(v);
			}
			// if node was acceptable, we have a new route
			if(f) return false;
		}
		// can't add more, so try removing one and going to the next possible node
		removeNode();
	}
	// nothing to remove, reset for next pass
	reset();
	return true;
}

BitVector.getNext() finds the next set bit, clears it, and returns its 
index or -1 if there are no more set bits.  When a node is appended, the 
possible candidates are loaded into the next level's bitvector, which is 
gradually depleted.  This could all be done without bitvectors and doing 
an exhaustive search through the list of nodes each time, keeping a list 
of edges per node, etc, but I think this is much cleaner and faster.

As an example, here is how simple appendNode/appendEdge/reset are:

public boolean Route.appendNode(int nodeIdx) {
	Node node=getNode(nodeIdx);
	// could check criteria related to total train length or types of nodes
	// a train may use
	if(notAcceptable(node)) return false;
	nodes[numNodes++]=node;
	// show that we have used this node and any mutually exclusive with it
	// (for example, on the same hex where not allowed)
	seenNodes|=node.mutexNodes;
	routeStats.add(node);
	// see if this is a node where we dead-end, or are blocked by tokens
	// can also query routeStats to handle things like 1860's ability to
	// run past a single token
	if(node.blocked(routeStats) || (numNodes>1 && node.deadend())) {
		// no possible extensions
		next[numNodes]=0;
	} else {
		// plausible edges to investigate are all the ones from this node, leaving out
		// ones already used, and with a track type compatible with current train
		next[numNodes]=(node.edges - seenEdges) & train.usableEdges;
	}
	return true;
}

public boolean Route.appendEdge(int edgeIdx) {
	assert(numNodes>0);
	Edge edge=getEdge(edgeIdx);
	Node node=edge.getOtherNode(nodes[numNodes-1]);
	seenEdges|=edge.mutexEdges;
	edgeUsed[numNodes]=edgeIdx;
	if(!appendNode(node.idx)) {
		seenEdges-=edge.mutexEdges;
		return false;
	}
	return true;
} 

public void Route.reset() {
	numNodes=0;
	// only plausible starting points are stations reachable by the current company
	// and those which the current train may use
	next[0]=company.reachableStations & train.usableNodes;
	routeStats.init();
}

node.mutexNodes is a bitvector of all nodes that should be marked used 
if the current node is used, likewise edge.mutexEdges.  
train.usableNodes and usableEdges are bitvectors of those nodes/edges 
that are usable by the current train.  There are analogous removeNode 
and removeEdge methods which basically undo what was done in the append* 
methods.  The other methods listed but not defined should be pretty 
self-explanatory.  A bit of housekeeping to avoid duplicate routes 
(since starting from either end gets the same route) and a few other 
details are needed.

I believe this will cover games with different types of track usable by 
different trains, games where certain trains may not run certain places 
or have different values for different trains (1844, 1889), games with 
specific requirements on how many stations of what types a train may use 
or may ignore (1826, 1835, etc).  It should also handle things like the 
double track in 18GL, by just having two edges between two nodes that 
are not marked as mutually exclusive.  It does not explicitly handle 
H-trains, although that should be feasible to handle by looking at the 
sequence of nodes in a route and counting the number of distinct hexes 
they are on in routeStats.add().  Constraints on the entire set of train 
routes being run are easily handled, and special rules about skipping 
tokens can be handled.  So, I believe this basic algorithm will cover 
most 18xx games currently in print.

See any problems with the basic approach?  Questions?

-- 
John A. Tamplin					ja...@ja...
770/436-5387 HOME				4116 Manson Ave
                		 		Smyrna, GA  30082-3723