Re: [Rails-devel] Tile Database API & route calculation

[Dave M. <da...@mi...>]

A couple more comments on my implementation...

On 7/7/2006 11:47 PM, Dave Mitton wrote:
>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.

Actually, having an array of edge connectivity vectors per hex (a bit 
matrix) led to some interesting capabilities.
To match a tile to the map, you do an matrix rotation on the array.
When rotated, a canidate tile must preserve the existing 
connectivity, so the new tile's bit vector must be a superset of on 
the existing map hex.  AND'ing the tile's matrix against the hex, 
should yield the hex's matrix.



...
Dave.