[Rails-devel] Tile Database API & route calculation

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

Ok, it was more work than I thought it would be and I am not totally 
satisfied with it yet -- feel free to suggest improvements.

The route finding code (and other similar uses such as connectivity 
requirement for tile and token placement) needs to know the following:

    * which edges are connected to other edges
    * which junctions are connected to which edges
    * which junctions are connected to each other
    * the revenue value of each junction (possibly varying by phase)
    * the number of token slots for each junction (which may be zero for
      off-board areas or villages)
    * which connections interfere with which other connections (ie, only
      one train can be run on a given set of connections)

The connectivity within a tile will be modelled by breaking down a 
junction into multiple exits from it -- ie, if track from a given 
junction going to side A and going to side B share some track and can't 
be used together, that will be treated as one exit.  If they don't share 
track, they will be in two different exits.  Thus, we have the following 
connectivity tests:

    * edge - edge
    * edge - junction/exit
    * junction/exit - junction/exit

Based on where the tiles are placed an in what orientation, a 
connectivity graph of junctions to map hex edges can be kept up to 
date.  Each company will also have a list of junctions where there 
tokens are located, and a connectivity graph of other junctions 
reachable from each of those.  When a new tile or the company's own 
token is placed, additional edges will get added to the connectivity 
graph (and nodes as well if new junctions are added on new tiles).  When 
a foreign token is placed, edges may get removed if a city is full of 
tokens.

Tile placement for a company will find the union of reachable map hex 
edges from all of the company's tokens and highlight possible tile 
locations.  When one is selected, the possible tiles that connect to one 
of the reachable edges on that hex and which can be oriented such that 
they don't connect to a blocked hex edge (the blocked edge list will be 
created when the map is created, and not updated afterwards) will be 
shown as options, and only rotations which meet these criteria will be 
shown in the cycle of rotations.

For a token placement, it will simply find reachable junctions where the 
company doesn't already have a token and has an available slot (we still 
have to solve  mapping the junction token slot to a screen location).

For route calculation, it is more complicated.  In addition to the 
connectivity graph of junctions, junction exits have to be considered 
since a given junction exit may only be used by one train.  Imagine the 
following connectivity example:

Tile A: J1E1-1, J1E1-2, J1E2-4
Tile B: J1E1-1, J1E2-4
Tile C: J1E1-1
The company has a token in TAJ1, TA-1 is connected to TC-1, and TA-2 is 
connected to TB-4.

The connectivity graph for the company includes all three junctions 
(TAJ1, TBJ1, TCJ1).  However, only one train may be run and it may only 
include B or C, since connectivity between tile A and either B or C both 
use J1E1.  Pseudocode of a brute force algorithm for one train, 
extendible to multiple trains:

bestRoute=null route;
for each company token {
        junction=token.junction;
        junctionsSeen=empty bitmap;
        junctionsSeen.setSeen(junction);
        exitsSeen=empty bitmap;
        route=findRoute(junction,junctionsSeen,exitsSeen,maxhops);
        if(route && route.value>bestRoute.value) {
                bestRoute=route;         }
}

function findRoute(junction,junctionsSeen,exitsSeen,hopsleft) {
        bestTail=null route;         junctionsSeen.setSeen(junction);
        for each outexit on junction {
                // can't go out the same way we came in or go into another
                // junction on a path that has been used already
                next if(outexit==exit || exitsSeen.seen(junction,outexit));

                // find out where this exit connects to
                junexit=connectedJunctionExit(junction,outexit);
                // make sure it goes someplace that we can run to and
                // that hasn't been used
                next if(!junexit || junctionsSeen.seen(junexit.junction)
                   || exitsSeen.seen(junexit.junction,junexit.exit));

                // mark what we have used and recurse to find the best
                // remainder of a route
                exitsSeen.setSeen(junction,outexit);
                exitsSeen.setSeen(junexit.junction,junexit.exit);
                routeTail=findRoute(junexit.junction,junctionsSeen,exitsSeen,hopsleft-1);
                if(routeTail && routeTail.value>bestTail.value) {
                        bestTail=routeTail;
                }
                exitsSeen.clearSeen(junexit.junction,junexit.exit);
                exitsSeen.clearSeen(junction,exit);
        }
        junctionsSeen.clearSeen(junction);
        return bestTail.prepend(junction);      // also updates route value
}

I don't know if bruteforce will be acceptable even on modern hardware. A 
large map like 1844 will have 50 or more unique junction exits, and if 
many of them aren't full of tokens that could be a very large number of 
possible routes to consider, and that is multiplied by the number of 
trains to run. To extend this to multiple trains, each train would have 
to keep its own list of junctions visited, but share the exits visited 
bitmaps.  You would also have to add code trying all combinations of 
trains starting from each of the tokens (including order, since a short 
train might cut off a long train by visiting a junction first), but 
findRoute wouldn't change at all.

Comments?

If this is agreeable, what is the best way to represent the connectivity 
graph and the API to get the connectivity information from the tile 
object?  You really have a tree -- a tile contains 0 or more junctions, 
each of those contains 0 or more exits (so map hexes with no track are 
covered), and each of those exits connects to an arbitrary number of 
edges and other junction exits on the same tile.  The two obvious ways 
are a graph of nodes and a 2-d bit vector showing connectivity between 
everything.  The latter would need to be built ourselves using longs 
since arrays of booleans aren't packed.

How would you like to see the interface to the connectivity data in the 
tile?

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