Menu
▾
▴
Re: [Rails-devel] Tile Database API & route calculation
|
From: <ia...@co...> - 2006-07-07 07:37:29
|
> From: "John A. Tamplin" <ja...@ja...>
> Subject: [Rails-devel] Tile Database API & route calculation
>
> 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,
If keeping a single connectivity graph (which seems reasonable to me), you need to record which company occupies each token slot. At first glance your ideas are similar to those I proposed on the 18xx soft-dev mailing some aeons ago: if we both came up with a similar scheme independently, that suggests we're on the right track.
Did you look at my 18xx revenue calculator code at all (see http://www.cosgor.demon.co.uk/Perlbits/revenue.html)? It's eight year old Perl code, but it did brute-force on a typcial 1830 mid-game in what I consider to be a reasonable time. I don't have time right now to compare your algorithm with mine, nor unfortunately can I promise that I will.
All,
Congratulations on getting something out.
Iain.
|
