Menu
▾
▴
Re: [Rails-devel] Tile Database API & route calculation
|
From: Dave M. <da...@mi...> - 2006-07-08 03:47:16
|
On 7/7/2006 12:17 AM, John A. Tamplin wrote:
>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
In my 1830 program, I just considered cities to be another "edge"
I created a bit vector for the edges in a hex/tile
To describe the tile, each edge had a vector of edges it was connected to.
I didn't deal with junctions (none in 1830 tiles), but I think the
idea is extensible.
>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.
Will need a token container somewhere.
>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.
Right, so for this application it's not necessary to build a "tree" or "graph".
For tile placement, you need a bool IsEdgeConnected(loc,edge) function.
>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).
I found this problem rather ugly. Dealing with screen hits means some sort of
location coord to city mapping.
>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 used a breadth first stack to build my "tree".
Each iteration followed the entrance edge to push all connected "exit" edges,
then pop next entrance.
Eventually all paths will lead to no connection, seen before, or blocked.
The stack has a predicable max, and no recursion is involved.
>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.
I never got to building a route finder, but think about how you want
to keep and use the info.
Note that even though you are following a logical tree, it doesn't
have to be stored as a linked list.
>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
All for now... lets see if I can get this one through.
Sourceforge doesn't like my provider's email setup.
Dave.
|
