rails-devel — List for discussion of Rails development

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

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

Ok, after looking at Iain's code, I propose the following:

Extend the tile XML file to show additional exclusive track use and add 
necessary drawing data:

<Tile id="62" colour="green" category="NY">
    # position/rotation can be defaulted
    <Station id="1" type="City" slots="2" value="80" position="90,.4" rotation="0" />
    <Station id="2" type="City" slots="2" value="80" position="270,.4" rotation="0" />
    # gauge and level are defaulted, use shorter labels for size and parsing speed
    <Track from="1" to="A" />
    <Track from="1" to="F" />
    <Track from="2" to "E" />
    <Track from="2" to "D" />
</Tile>
<Tile id="Map-1841-Milano" colour="yellow" category="M">
    <Annotation text="Milano" size="12pt" position="270,.7" justify="b" rotation="0" />
    <Station id="1" type="City" slots="1" value="60" position="210,.6" />
    <Track from="1" to "A">
        <Excludes from="1" to "B" />
    </Track>
    <Track from="1" to "B">
        <Excludes from="1" to="A" />
    </Track>
</Tile>
<Tile id="23" colour="green">
    <Track from="A" to="D" />
    <Track from="D" to="B" />
</Tile>
<Tile id=16 colour="green">
    <Track from="A" to "C" level="0"/>
    <Track from="B" to "D" level="2"/>
</Tile>
<Tile id="Map-1830-Altoona" colour="fixed">
    <Station id="1" type="City" slots="1" value="10" reservedtoken="PRR" />
    <Track from="E" to="1" />
    <Track from="B" to="1" />
    <Track from="B" to="E">
	 <Draw from="E" to="[210,.25]" radius="-.25" />
	 <Draw from="[210,.25]" to="[300,.25]" radius=".25" />
	 <Draw from="[300,.25]" to="B" radius="-.25" />
    </Track>
</Tile> 

Tile code defaults to the id if it is numeric, otherwise it defaults to 
"", can be overriden with code="603" etc.

Note that for the #23 tile the excludes are automatically picked up 
since the edges overlap.  Since 90% of the gauge will be normal, it 
makes sense to default that attribute (as well as level, which is only 
needed for tiles with overpasses).  The Milano tile shows how extra 
excludes that wouldn't be known just from looking at the connectivity 
information are specified.  The last tile shows how you can specify how 
to draw a particular piece of track if the default choices won't work (a 
negative radius means curving away from the center of the tile, positive 
means curve towards the center; leaving radius out means a straight 
line).  If you are worried about intialization time (and automatically 
positioning elements that don't have a position specified is not a 
trivial task), this file could be built from a master file that contains 
all the tile definitions and filling in all the drawing and other 
defaulted information.  Once you do that, this needs to be considered a 
generated file, but that is a good thing since otherwise you will have 
multiple copies of the same tile data that have to be updated and we 
know that means they won't be exactly the same.

In addition to text annotations, we need to support other annotations as 
well, which would be used to show additional building costs or graphics 
added to the tile.  In my perl code, I just supply arbitrary postscript 
code for them, but that won't work here.  I suggest having something 
like <Annotation shape="xxx" position="a,r" scale="s"/> which references 
shape xxx defined elsewhere, either SVG to draw it or perhaps even 
custom code.

It will be a lot less work to add the excludes that can't be deduced 
automatically than to do all the splitting of junctions into junction 
exits, and the resulting datastructure will be simpler as well.

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

Re: [Rails-devel] Bug fixing

[brett l. <wak...@gm...>]

On 7/8/06, Erik Vos <eri...@hc...> wrote:
> > I've committed some changes that fix the bugs related to the
> > UpgradesPanel buttons.
> >
> > Now their behavior is more predictable and consistent. They're only
> > clickable during the proper subphases and the button text is now
> > consistent with the subphase, even after errors.
>
> A new bug: if you lay a tile and then rotate it, the list of tiles
> disappears,
> so that you no longer have the option to select another tile at this stage.
>
> No doubt the code has been simplified by removing the ability to "play with
> the map"
> when it is not your turn, i.e. try out which upgrades are available
> by clicking a hex (without being able to 'lay' the tile).
> But I consider it a loss.
>

I'll check it out.

---Brett

Re: [Rails-devel] Bug fixing

[Erik V. <eri...@hc...>]

> I've committed some changes that fix the bugs related to the
> UpgradesPanel buttons.
> 
> Now their behavior is more predictable and consistent. They're only
> clickable during the proper subphases and the button text is now
> consistent with the subphase, even after errors.
 
A new bug: if you lay a tile and then rotate it, the list of tiles
disappears,
so that you no longer have the option to select another tile at this stage.

No doubt the code has been simplified by removing the ability to "play with
the map" 
when it is not your turn, i.e. try out which upgrades are available
by clicking a hex (without being able to 'lay' the tile).
But I consider it a loss.

Erik.

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

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

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. 

[Rails-devel] Bug fixing

[brett l. <wak...@gm...>]

I've committed some changes that fix the bugs related to the
UpgradesPanel buttons.

Now their behavior is more predictable and consistent. They're only
clickable during the proper subphases and the button text is now
consistent with the subphase, even after errors.

I also caught an ArrayIndexOutOfBounds exception that was being thrown
if we try to place a token where there's no station.

---Brett.

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

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

Erik Vos wrote:

>I was under the impression, that your pseudocode would work with
>the track/junction objects themselves, without need for separate 
>structures (a.k.a. different connectivity graphs).
>Which would mean, that for different purposes you would have 
>different algorithms working with the same data structure
>(which indeed is how I would do it). 
>Did I misunderstand that?
>  
>
The pseudocode was just to illustrate the idea of the algorithm, not 
tied to any particular data structure.  The references to the 
connectivity graph is in connectionJunctionExit(junction,exit) which 
iterates over all the junction exits reachable from a particular 
junction exit.  It could do that by traversing pointers between objects 
or by looking at a bitvector, or indeed many other implementations.

Looking at Iain's code, there is a different way of solving the problem 
-- rather than splitting the junctions into a subgraph of nodes so you 
can track which connections to other junctions/edges share the same 
track, you can simply keep a list of which edges in the graph are 
mutually exclusive.  I will look at it some over the weekend to see if 
that will work better for our purposes.  It has the benefit of removing 
the subdivision of junctions, but adding another datastructure that has 
to be looked up during each route aggregation step.

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

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

[Erik V. <eri...@hc...>]

> >I guess it's mostly a matter of words.
> >To me, the Track, Junction and Station objects *are* the 
> connectivity graph.
> >Our difference then is, as it seems to me, that you restrict 
> the cloning 
> >to those Track, Junction and Station objects, not including 
> >the parent tile itself. Not much saving, I would think.
> >
> >Or does your graph consist of entirely different objects?
> >  
> >
> If you use them as the connectivity graph, then you wind up pointing 
> into Junction objects in other Tile objects, which means the Junction 
> objects have to have a reference the parent Station or Tile object 
> (which complicates a common superclass).  Another problem is 
> maintiaining multiple connectivity graphs -- as mentioned in 
> the first 
> message you really want to have different types of 
> connectivity graphs 
> for tile laying, token placement, and route calculations.  For the 
> latter, you also need to have different connectivity graphs for each 
> company.
> 
> What I am proposing is a triangular (since the edges are 
> bi-directional) 
> 2-D bitvector which encodes connectivity between all the 
> things you want 
> to care about.  That would be maintained totally outside the data 
> structure for the tiles, which would be immutable once loaded 
> from the 
> database.  You could have as many different connectivity 
> graphs as you 
> like without a problem.
> 
> Even if you don't want to do it with a bitvector, I think you 
> still want 
> to have the connectivity graph outside the tile data structure.

I was under the impression, that your pseudocode would work with
the track/junction objects themselves, without need for separate 
structures (a.k.a. different connectivity graphs).
Which would mean, that for different purposes you would have 
different algorithms working with the same data structure
(which indeed is how I would do it). 
Did I misunderstand that?

For the rest, I'm totally out of graph and bitvector theory,
so this way it'll have to be you who implements all this
(or someone of equal math education level). 
My study was chemistry....

Erik.

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

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

Erik Vos wrote:

>I guess it's mostly a matter of words.
>To me, the Track, Junction and Station objects *are* the connectivity graph.
>Our difference then is, as it seems to me, that you restrict the cloning 
>to those Track, Junction and Station objects, not including 
>the parent tile itself. Not much saving, I would think.
>
>Or does your graph consist of entirely different objects?
>  
>
If you use them as the connectivity graph, then you wind up pointing 
into Junction objects in other Tile objects, which means the Junction 
objects have to have a reference the parent Station or Tile object 
(which complicates a common superclass).  Another problem is 
maintiaining multiple connectivity graphs -- as mentioned in the first 
message you really want to have different types of connectivity graphs 
for tile laying, token placement, and route calculations.  For the 
latter, you also need to have different connectivity graphs for each 
company.

What I am proposing is a triangular (since the edges are bi-directional) 
2-D bitvector which encodes connectivity between all the things you want 
to care about.  That would be maintained totally outside the data 
structure for the tiles, which would be immutable once loaded from the 
database.  You could have as many different connectivity graphs as you 
like without a problem.

Even if you don't want to do it with a bitvector, I think you still want 
to have the connectivity graph outside the tile data structure.

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

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

[Erik V. <eri...@hc...>]

> >How would you then distinguish the tracks and cities of a 
> tile on one hex
> >from those on another similar tile placed on a different hex?
> >I suppose I'm missing some point here.
> >  
> >
> You ask the map what tile is placed on hex A17 (or whatever), and it 
> gives you a pointer ot the Tile object along with the 
> orientation it was 
> placed at.  The fact that it also returns the same Tile object for a 
> different hex (or even from the TileManifest object) is 
> irrelevant since 
> it doesn't store any context.
> 
> When you are building the connectivity graph, you would 
> obviously take 
> into account the location where the tile is placed -- the tile object 
> simple gives connectivity within that hex and to the hex edges.

I guess it's mostly a matter of words.
To me, the Track, Junction and Station objects *are* the connectivity graph.
Our difference then is, as it seems to me, that you restrict the cloning 
to those Track, Junction and Station objects, not including 
the parent tile itself. Not much saving, I would think.

Or does your graph consist of entirely different objects?
 
> I realize that the current design has a UI-specific things 
> tied to the 
> tile object, but I would like to keep the Java port of the tile 
> rendering code and eventually route-calculation useable separate from 
> Rails, which means not tying it to any particular UI code.

I think only the token slot coordinates are UI-tied.
The tile images (or SVG definitiona) are completely separate from 
the tile descriotions in Tiles.xml
(although both are derived from TileDesigner now).

Erik.

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

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

Erik Vos wrote:

>How would you then distinguish the tracks and cities of a tile on one hex
>from those on another similar tile placed on a different hex?
>I suppose I'm missing some point here.
>  
>
You ask the map what tile is placed on hex A17 (or whatever), and it 
gives you a pointer ot the Tile object along with the orientation it was 
placed at.  The fact that it also returns the same Tile object for a 
different hex (or even from the TileManifest object) is irrelevant since 
it doesn't store any context.

When you are building the connectivity graph, you would obviously take 
into account the location where the tile is placed -- the tile object 
simple gives connectivity within that hex and to the hex edges.

I realize that the current design has a UI-specific things tied to the 
tile object, but I would like to keep the Java port of the tile 
rendering code and eventually route-calculation useable separate from 
Rails, which means not tying it to any particular UI code.

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

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

[brett l. <wak...@gm...>]

On 7/7/06, Erik Vos <eri...@hc...> wrote:

> I have created tile files per game to keep the files smaller and load
> faster (XML parsing is not cheap). The Tiles.xml including all
> tiles could then be omitted from the published game.
> But it can of course also be done the other way around,
> at the expense of a noticeably longer initialisation time.
> IMO we are already near the edge of what I find tolerable. YMMV.

The way we're transcoding the SVG into a rendered image is really
really slow and clunky.

I've also noticed that we're incurring the cost of loading the tile
image more than once as we iterate through the tile list. Right now
we're not checking for an already loaded tile image, which is slowing
things down considerably.

Once we fix some of the image loading and rendering issues, the load
times will decrease immensely.

---Brett

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

[Erik V. <eri...@hc...>]

> >This looks good enough for 1830 and the like. 
> >My only quick remark is that hopsleft is not checked for 
> becoming zero.
> >
> >A more general algorithm should take into account the possibility
> >that certain junctions would not count against maxhops 
> >(e.g. villages and ports in 18EU). In that case searching should
> >continue until hopsleft would become -1. 
> >  
> >
> It actually needs to be different than that, because different trains 
> have different abilities:
> 
>     * plus-trains get either a fixed or unlimited number of towns that
>       are counted separately from the main number
>     * H-trains count hexes rather than stops
>     * Halts in 1860 and G-trains running to mines in 1824 pay to the
>       company treasury not the run value
>     * H-trains can't run to off-board areas in 1844
>     * 4D-trains in 18Mex double cities but not towns, towns 
> don't count
>       against the train limit
>     * Mountains/tunnels in 1844 have to keep track of when they are
>       activated
> 
> etc.  So, more generally, I think the object that gets passed 
> around has 
> to know about the train type being used for the run and would also 
> accumulate the value and other effects of the train operation.

Yes, of course.
 
> >I'm wary of bitmaps and would go for objects pointing to each other.
> >But that is more intuition than anything else.
> >Objects take more memory, but are we running short?
> >  
> >
> I have done a lot of work in chess (and other games) endgame 
> retrograde 
> analysis.  Bit vectors make the algorithms much cleaner, and I think 
> there may be room to use something similar here.  For 
> example, given a 
> set of positions which are won in n moves, to find the set of 
> predecessors you simply say bv2=Predecessor(bv1).  This could 
> definitely 
> be done for tracking connectivity for track laying and token 
> placement, 
> but I am not positive it is useful for the route building or not.
> 
> It also makes copying the connectivity graph much easier -- 
> deep copies 
> of a cyclic graph are not trivial and take a lot of time compared to 
> just copying a 2D array of bits.

OK. This is not a subject I know anything about, so I can't help here.

> >In the below I will use the terminology I have used 
> >so far in this project; I use "Station" for Junction
> >and will use "Junction" for the superclass of "Edge" and "Exit";
> >and what people often call Station or Token or Garrison or Railhead
> >I call a "BaseToken", which will (in the future) be one 
> >of the many subclasses of "Token".
> >
> >The tree will then, in my opinion, look like:
> >
> >Tile
> >|
> >+-- Station (value)
> >|   |        
> >|   +-- Slot (location)  <--> BaseToken <--> PublicCompany
> >|   |
> >|   +-- Exit   ------
> >|                    > Junction (superclass or interface)
> >+-- Edge (sidenr.) --    ^ ^  
> >|                        | |
> >+-- Track (gauge) <------+ |
> >                  <--------+
> >
> >A Track connects two Junctions, either of which can be an 
> Edge or an Exit.
> >Tiles obviously connect to each other via Edges.
> >  
> >
> Ok.  I used Junction as it is the terminology in TileDesigner and my 
> re-implementation of it.
> 
> >The <Tile> XML should specify all of the above 
> >(except of course BaseToken & Company)
> >
> >Comparing this with the current Tiles.xml contents,
> >Slots and Exits would be added, and the location would
> >move from Station to Slot (where we need it for token placement).
> >
> >(BTW the current location values are my encoding of the longer
> >location descriptions as used in TileDesigner. I suppose we will
> >need some sort of polar coordinates instead).
> >
> >The structure per tile will be created when the XML is parsed,
> >and we will need to clone tiles of which the quantity is >1
> >(this is not done yet for tiles; it is done for certificates).
> >  
> >
> I would prefer to have one database of tile defintions, and then when 
> the game is loaded the correct set (and upgrade paths) can be 
> pulled in 
> based on the game's tile manifest and orientation changes.  

The upgrade paths can be different per game and should therefore
be part of the game tile set., as these currently are. 

I have created tile files per game to keep the files smaller and load
faster (XML parsing is not cheap). The Tiles.xml including all
tiles could then be omitted from the published game.
But it can of course also be done the other way around, 
at the expense of a noticeably longer initialisation time.
IMO we are already near the edge of what I find tolerable. YMMV.

> Any cloning 
> of the tile objects would take place that that point 
> (although I wonder 
> why the tile objects themselves need to be cloned -- why not 
> just have a 
> pointer to the tile and change the available count in the 
> tile manifest? 

How would you then distinguish the tracks and cities of a tile on one hex
from those on another similar tile placed on a different hex?
I suppose I'm missing some point here.

> -- the design of the Tile object I have been porting from my 
> perl code 
> has no knowledge of its location, so that context is passed 
> in much like 
> a flyweight object).

Erik.

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

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

Erik Vos wrote:

>This looks good enough for 1830 and the like. 
>My only quick remark is that hopsleft is not checked for becoming zero.
>
>A more general algorithm should take into account the possibility
>that certain junctions would not count against maxhops 
>(e.g. villages and ports in 18EU). In that case searching should
>continue until hopsleft would become -1. 
>  
>
It actually needs to be different than that, because different trains 
have different abilities:

    * plus-trains get either a fixed or unlimited number of towns that
      are counted separately from the main number
    * H-trains count hexes rather than stops
    * Halts in 1860 and G-trains running to mines in 1824 pay to the
      company treasury not the run value
    * H-trains can't run to off-board areas in 1844
    * 4D-trains in 18Mex double cities but not towns, towns don't count
      against the train limit
    * Mountains/tunnels in 1844 have to keep track of when they are
      activated

etc.  So, more generally, I think the object that gets passed around has 
to know about the train type being used for the run and would also 
accumulate the value and other effects of the train operation.

>I'm wary of bitmaps and would go for objects pointing to each other.
>But that is more intuition than anything else.
>Objects take more memory, but are we running short?
>  
>
I have done a lot of work in chess (and other games) endgame retrograde 
analysis.  Bit vectors make the algorithms much cleaner, and I think 
there may be room to use something similar here.  For example, given a 
set of positions which are won in n moves, to find the set of 
predecessors you simply say bv2=Predecessor(bv1).  This could definitely 
be done for tracking connectivity for track laying and token placement, 
but I am not positive it is useful for the route building or not.

It also makes copying the connectivity graph much easier -- deep copies 
of a cyclic graph are not trivial and take a lot of time compared to 
just copying a 2D array of bits.

>In the below I will use the terminology I have used 
>so far in this project; I use "Station" for Junction
>and will use "Junction" for the superclass of "Edge" and "Exit";
>and what people often call Station or Token or Garrison or Railhead
>I call a "BaseToken", which will (in the future) be one 
>of the many subclasses of "Token".
>
>The tree will then, in my opinion, look like:
>
>Tile
>|
>+-- Station (value)
>|   |        
>|   +-- Slot (location)  <--> BaseToken <--> PublicCompany
>|   |
>|   +-- Exit   ------
>|                    > Junction (superclass or interface)
>+-- Edge (sidenr.) --    ^ ^  
>|                        | |
>+-- Track (gauge) <------+ |
>                  <--------+
>
>A Track connects two Junctions, either of which can be an Edge or an Exit.
>Tiles obviously connect to each other via Edges.
>  
>
Ok.  I used Junction as it is the terminology in TileDesigner and my 
re-implementation of it.

>The <Tile> XML should specify all of the above 
>(except of course BaseToken & Company)
>
>Comparing this with the current Tiles.xml contents,
>Slots and Exits would be added, and the location would
>move from Station to Slot (where we need it for token placement).
>
>(BTW the current location values are my encoding of the longer
>location descriptions as used in TileDesigner. I suppose we will
>need some sort of polar coordinates instead).
>
>The structure per tile will be created when the XML is parsed,
>and we will need to clone tiles of which the quantity is >1
>(this is not done yet for tiles; it is done for certificates).
>  
>
I would prefer to have one database of tile defintions, and then when 
the game is loaded the correct set (and upgrade paths) can be pulled in 
based on the game's tile manifest and orientation changes.  Any cloning 
of the tile objects would take place that that point (although I wonder 
why the tile objects themselves need to be cloned -- why not just have a 
pointer to the tile and change the available count in the tile manifest? 
-- the design of the Tile object I have been porting from my perl code 
has no knowledge of its location, so that context is passed in much like 
a flyweight object).

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

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

[Erik V. <eri...@hc...>]

> 
> Comments?

This looks good enough for 1830 and the like. 
My only quick remark is that hopsleft is not checked for becoming zero.

A more general algorithm should take into account the possibility
that certain junctions would not count against maxhops 
(e.g. villages and ports in 18EU). In that case searching should
continue until hopsleft would become -1.
 
> 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.

I'm wary of bitmaps and would go for objects pointing to each other.
But that is more intuition than anything else.
Objects take more memory, but are we running short?

In the below I will use the terminology I have used 
so far in this project; I use "Station" for Junction
and will use "Junction" for the superclass of "Edge" and "Exit";
and what people often call Station or Token or Garrison or Railhead
I call a "BaseToken", which will (in the future) be one 
of the many subclasses of "Token".

The tree will then, in my opinion, look like:

Tile
|
+-- Station (value)
|   |        
|   +-- Slot (location)  <--> BaseToken <--> PublicCompany
|   |
|   +-- Exit   ------
|                    > Junction (superclass or interface)
+-- Edge (sidenr.) --    ^ ^  
|                        | |
+-- Track (gauge) <------+ |
                  <--------+

A Track connects two Junctions, either of which can be an Edge or an Exit.
Tiles obviously connect to each other via Edges.

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

The <Tile> XML should specify all of the above 
(except of course BaseToken & Company)

Comparing this with the current Tiles.xml contents,
Slots and Exits would be added, and the location would
move from Station to Slot (where we need it for token placement).

(BTW the current location values are my encoding of the longer
location descriptions as used in TileDesigner. I suppose we will
need some sort of polar coordinates instead).

The structure per tile will be created when the XML is parsed,
and we will need to clone tiles of which the quantity is >1
(this is not done yet for tiles; it is done for certificates).

At least, this is how I tend to look at it....

Erik.

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

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

ia...@co... wrote:

>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.
>  
>
Thanks for reminding me -- I remember looking at it long ago, but had 
forgotten it.  I will take a look at it again.

Briefly looking through the code, I don't see where it handles the issue 
of some connections to a junction sharing track and other connections 
not sharing track -- is that handled?

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

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

[<ia...@co...>]

> 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.

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

[brett l. <wak...@gm...>]

Hmmm...  Looks like you've covered everything I can think of. I've got
no complaint with the design.  I suspect that some of our existing Hex
code may even already store some of the data you're mentioning.

I think that it'll work for now, but when we get to implementing the
bigger games like 1844, we can use their implementation to examine
improvements in the route finding algorithm.

Without a use case to test against, it may be difficult to really
benchmark anything more involved than brute-forcing our way down the
connectivity tree.

---Brett

[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

Re: [Rails-devel] Fixes

[brett l. <wak...@gm...>]

On 7/6/06, John A. Tamplin <ja...@ja...> wrote:
> brett lentz wrote:
>
> >Unfortunately, it doesn't list 1830.
> >
> >
> In the rules difference list, any game not listed goes under "Rest".
>
> --


Ahhh.... that makes lots more sense now.   :-)


---Brett.

Re: [Rails-devel] Fixes

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

brett lentz wrote:

>Unfortunately, it doesn't list 1830.
>  
>
In the rules difference list, any game not listed goes under "Rest".

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

Re: [Rails-devel] Fixes

[brett l. <wak...@gm...>]

On 7/6/06, Jonathan Ferro <jo...@ya...> wrote:
> --- brett lentz <wak...@gm...> wrote:
> > On 7/6/06, Erik Vos <eri...@hc...> wrote:
> > > This includes a problem I found, that if 3 players have
> > > each 20% of a company, with 40% in the Pool, the
> > > presidency could not be sold.
> > In this situation, my understanding of the rules is that you can't
> > sell the presidency, especially because there's no clear benefactor
> > to receive the presidency.
>
> http://www.fwtwr.com/18xx/rules_difference_list/11_3.htm
>
>

Unfortunately, it doesn't list 1830.

---Brett.

Re: [Rails-devel] Fixes

[Jonathan F. <jo...@ya...>]

--- brett lentz <wak...@gm...> wrote:
> On 7/6/06, Erik Vos <eri...@hc...> wrote:
> > This includes a problem I found, that if 3 players have
> > each 20% of a company, with 40% in the Pool, the
> > presidency could not be sold.
> In this situation, my understanding of the rules is that you can't
> sell the presidency, especially because there's no clear benefactor
> to receive the presidency.

http://www.fwtwr.com/18xx/rules_difference_list/11_3.htm

-- Jon

[Rails-devel] President

[Erik V. <eri...@hc...>]

The President is now marked with a 'P' in the Game status window.
This is one of Fred's requests (I could not find it in Sourceforge).

For some mysterious reason the P does not show up when the Presidency is
bought
for the first time, so there must be something wrong with the logic.
Will sort that out later.

Enough for today!

Erik 

Re: [Rails-devel] Fixes

[Erik V. <eri...@hc...>]

> > I don't have the 1830 rules in front of me, but at least 
> some other 18xx
> > games specifically say this is acceptable -- the president 
> is allowed to
> > sell one share, trading with the one who will receive the 
> president's
> > certificate in order to put one in the pool.  As far as who gets the
> > presidency, all games I know of say the next eligible 
> player among those
> > tied clockwise from the current president (or in 
> share-round order if it
> > allows variable order).
> >
> 
> I have a similar problem.  I don't have the rules in front of me, and
> haven't read them in quite a while, so I definitely could be wrong
> here.

I'm pretty sure that John is right.

Erik.

Re: [Rails-devel] Fixes

[brett l. <wak...@gm...>]

On 7/6/06, John A. Tamplin <ja...@ja...> wrote:
> brett lentz wrote:
>
> >On 7/6/06, Erik Vos <eri...@hc...> wrote:
> >
> >
> >>I have (hopefully) fixed the reported (and some more) bugs
> >>regarding share buying/selling and certificate counting.
> >>
> >>This includes a problem I found, that if 3 players have
> >>each 20% of a company, with 40% in the Pool, the
> >>presidency could not be sold.
> >>
> >In this situation, my understanding of the rules is that you can't
> >sell the presidency, especially because there's no clear benefactor to
> >receive the presidency.
> >
> >
> I don't have the 1830 rules in front of me, but at least some other 18xx
> games specifically say this is acceptable -- the president is allowed to
> sell one share, trading with the one who will receive the president's
> certificate in order to put one in the pool.  As far as who gets the
> presidency, all games I know of say the next eligible player among those
> tied clockwise from the current president (or in share-round order if it
> allows variable order).
>

I have a similar problem.  I don't have the rules in front of me, and
haven't read them in quite a while, so I definitely could be wrong
here.

---Brett