rails-devel — List for discussion of Rails development

Re: [Rails-devel] Experimental version of revenue calculation

[Phil D. <de...@gm...>]

Further to this example...if you generate the B&M network in this
game, it gives you 60 as the routes, it won't count the offboard twice
for two separate trains even though as far as I'm aware that's valid
in this case.

Phil

On 13 April 2010 11:33, Phil Davies <de...@gm...> wrote:
> Stefan,
>
> A quick test on my currently running 18Kaas game threw up one thing
> for the algorithm and a vaguely related issue that certainly needs
> consideration for automatic revenue generation.
>
> I generated the network info for NYNH in the attached scenario,
> firstly, it ran one of the 2 trains by just counting the revenue for
> hex G10 on it's own.  In this case NYNH doesn't really have 3 legal
> runs for it's 3 trains so I understand why it did this.  It needs to
> be limited to not allow runs of only one station (unless there is a
> game out there that allows this that I am unaware of?).
>
> The second issue (and less of an algorithm problem) is that the Ruhr
> is listed as an income of 2.  This is simply how I assume we have
> chosen to represent the 'doubles cities' power of the Ruhr offboard.
> If revenue generation is to work for 18Kaas we will need to represent
> this differently.  Of course, that is a whole other discussion on it's
> own, as far as I can tell different gaming groups handle this rule
> totally differently so there may be some discussion as to what the
> official ruling is!
>
> Phil
>
> On 12 April 2010 18:50, Stefan Frey (web.de) <ste...@we...> wrote:
>> There is a first working version for revenue calculation in CVS.
>> The interface is minimal and added to the graph view:
>>
>> Thus in the ORWindow select Info => NetworkInfo and the
>> public company. Then the graph is displayed and the optimal revenue result and
>> the vertexes run for each train for the result.
>>
>> After this one can add additional trains and the optimization restarts.
>>
>> For available traintypes (currently default (including diesel), +, E and D
>> trains) check the addTrainByString method in RevenueAdapter.
>>
>> BE CAREFUL:
>> 1) It generates a lot of debug in the 18xx.log if the logging level is set to
>> DEBUG (as it is the default). If one tests complicated cases it can fill up
>> the hd quite quickly. Better have an own properties with debug level set to
>> INFO.
>>
>> 2) I cannot guarantee that it will not run into a deadlock, thus it can freeze
>> the UI and generate lots of debug output. Again see 1) and kill the program
>> after around 5 minutes latest.
>>
>> But for reasonable (up to moderate difficult) networks it will give results
>> nearly immediately.
>>
>> This is still not the algorithm of Alex, which has pretty amazing running
>> times, but a simple brute force algorithm on the current (moderately
>> optimized) network graph.
>>
>> Stefan
>>
>>
>> ------------------------------------------------------------------------------
>> Download Intel&#174; Parallel Studio Eval
>> Try the new software tools for yourself. Speed compiling, find bugs
>> proactively, and fine-tune applications for parallel performance.
>> See why Intel Parallel Studio got high marks during beta.
>> http://p.sf.net/sfu/intel-sw-dev
>> _______________________________________________
>> Rails-devel mailing list
>> Rai...@li...
>> https://lists.sourceforge.net/lists/listinfo/rails-devel
>>
>

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

Hi Stefan,

Don't worry about embarrassing errors! I have one somewhere and I don't  
even know where :) - I don't know why my algorithm doesn't find the  
optimal solution you've mentioned - it's supposed to, it's completely  
brute force and it should check every combination, but apparently it  
doesn't. I suspect I have a bug in my new 2-phased code where I determine  
which segments connecting cities are mutually exclusive.

I wonder, how do you plan to do the "best route estimates" in general.  
When the various train and bonus rules are added ("free" towns, express  
trains, doubling trains, East-West runs, bonuses for connecting pairs of  
cities etc...) evaluating what should be in the optimal route is going to  
be rather complex. It's also important to figure out how to quickly find  
pretty good set of routes, thus cutting off a lot of the search tree.

The times start to look promising, even the complete run finishing in 1-2  
minutes is pretty good. With one-phased algorithm it was taking ~40  
seconds on my machine to do complete search.

Thanks,
Alex.


On Tue, 13 Apr 2010 17:01:37 -0600, Stefan Frey (web.de)  
<ste...@we...> wrote:

> Hi Alex and all others...
> ... discussing revenue calculation. It seems to spur a lot of interest.
>
> Sorry for the long post (if one includes the text document), but I try to
> answer most of the asked and some of the not-yet asked questions.
> And it seems that the algorithms already improve from the fruitful  
> discussion.
>
> Some talk about the concepts are in the attached text document, that was
> easier to edit.
>
> This is the good thing of commit early and often. One of its  
> disadvantages are
> the embarrassing errors in the early releases. I list those at the end  
> of the
> attachment and hopefully it will clarify some of the problems you ran  
> into.
>
> Good news first:
>
> * Running Times
> After hunting them down and adding a new concept (the revenue prediction  
> - see
> attachment) evaluation time is now down to 1-2 seconds for a 8 and 10  
> train
> on the A scenario on my laptop. Without revenue prediction it runs for  
> 1-2
> minutes. Both runs have identical results.
>
> * Optimal Solution (?)
> The other thing is that my implementation suggests a (slightly)  
> different path
> than Alex' which results in an increase of revenue.
> The change is that the 8 train does not have the 10 - 30 - 30 (
> that is Alexandria and Baton Rouge in 1870, the right bottom in Alex  
> graph -
> it is rotated) in the end, but the 10 - 30 - 50 (that is Austin and  
> SouthWest
> on the map, the right top in Alex graph). Thus it runs for 20 more.
>
> It now pays off that we have independent algorithms running, that can  
> find
> flaws in each others (like you did for mine).
>
> Stefan


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

Dave, I'm using similar approach to the one you've described (with minor  
differences). "Splat" tiles are represented by all possible connectivity  
links (so the graph representation is the same as it would be to the  
"traditional" equivalent of "splat" tile. Unlike your approach I don't  
have separate city entities in the graph - they're simply attached to the  
vertices. So, for example, in 1861 yellow Moscow tile there will be 3  
cities attached to NW,NE and S vertices.

As far as text coordinates go I like "compass" identification - it seems  
most intuitive.


On Tue, 13 Apr 2010 11:04:54 -0600, Dave Mitton <da...@mi...> wrote:

> I'm not sure what each person has done here, but I'll insert my approach.
>
> For a given tile edge entrance, you have to be able to figure out what it
> connects to.
>
> It could be another edge, or a city (of some type). More complex tiles  
> have
> several cities on them.
>
> This is the connectivity of the tile/hex expressed by the track graphic  
> and must
> be encoded for the game.
>
> Note that this didn't take into account the various "splat" like tiles  
> in some
> later games.
>
> These could be handled with a $0 no-token, no-stop city in the middle,  
> if that
> helps the graphic representation.
>
> For 1830 style tiles I ended up with a system of "locations" that were  
> basically
> the 6 edges and two internal cities.
>
> That probably was not enough for some games, but it worked for me.
>
> I flattened the tile connectivity input down into a bit vector for each  
> edge,
> that could be rotated as the tile was placed,
>
> and then wrote a simple function for connection exploration that given  
> an edge
> in, produced a list of "edges" out.
>
> After a comparison to see if we've been there already by another route,  
> then the
> edge "out"s where pushed to the adjacent tile edges to be evaluated.
>
> Also note that using a bit vector allowed me to produce a tile lay rule  
> where
> the AND of the existing tile connectivity and the canidate tile
>
> had to be the same as the existing tile bit vector.
>
> So, I like your graph data structure, but there must be a sense of  
> direction in
> connections or keep a representation of the edge vertex.
>
> I think that would preserve the correct connectivity.
>
> Another key issues is how to represent these "coordinates". If you can  
> do this,
> then you can print out lists of a route for logging and recording.
>
> I went with something like <hexcoord>{<edge a-f>|<city x,y>} e.g. A23d
>
> and if the city had a name a function could bring that up too.
>
> Well, enough rambling...
>
> Keep up the good work.
>
> Dave.
>
>
> Apr 13, 2010 11:17:48 AM, rai...@li... wrote:
>
> On Tue, Apr 13, 2010 at 1:28 AM, alexti <al...@sh...> wrote:
>
> I avoid "switch" problem in a different way. My vertex definition is
> geographical - vertex id is its coordinates. Because of that I can check
> backtracking differently - my criterion is that two consecutive edges  
> from
> the same hex are only allowed if they are joined at the center. This can
> not be derived from the graph definition formally. Essentially I have
> additional information in the graph that is encoded in the vertex
> identifiers.
>
>
> If I understand you correctly, this will fail for some games with  
> complicated
> tiles -- also, how does it handle multiple cities per tile?
>
>


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

On Tue, 13 Apr 2010 09:17:13 -0600, John A. Tamplin <ja...@ja...> wrote:

> On Tue, Apr 13, 2010 at 1:28 AM, alexti <al...@sh...> wrote:
>
>> I avoid "switch" problem in a different way. My vertex definition is
>> geographical - vertex id is its coordinates. Because of that I can check
>> backtracking differently - my criterion is that two consecutive edges  
>> from
>> the same hex are only allowed if they are joined at the center. This can
>> not be derived from the graph definition formally. Essentially I have
>> additional information in the graph that is encoded in the vertex
>> identifiers.
>>
>
> If I understand you correctly, this will fail for some games with
> complicated tiles -- also, how does it handle multiple cities per tile?

That's possible. This method makes several assumptions I thought would  
cover all existing tiles, but there are plenty of games I am not familiar  
with. There are two main assumptions: (1) every rail track that leaves the  
tile always crosses the tile edge in the middle of the edge and does so at  
the right angle. (2) Every tile can be represented as 7-vertex graph.  
Consequently, there would be a limit of 7 separate cities per tile.  
Multiple cities (by that I mean tiles like "OO" or Toronto tile) are  
handled by assigning different cities to different vertices. There's also  
a boolean option indicating whether the train is allowed to visit  
different cities on the same tile or not (I believe this rule is different  
in different games).

Do you have any tiles in mind that wouldn't fit into these assumptions?

Re: [Rails-devel] Automatic route calculation

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

On 4/13/2010 09:41 PM, brett lentz wrote:
>On Tue, Apr 13, 2010 at 6:15 PM, Dave Mitton <da...@mi...> wrote:
> > On 4/13/2010 03:22 PM, Erik Vos wrote:
> >
> >           Note that this didn't take into account the various "splat" like
> > tiles in some later games.These could be handled with a $0 
> no-token, no-stop
> > city in the middle, if that helps the graphic representation.
> >
> > This wouldn't work, as a city can be visited only once.
>
>
>This really depends on the game.
>
>Some games allow re-visiting cities as long as the route taken isn't
>using the same segment of track more than once.
>
>I believe 1830 has no restriction for visiting the same city multiple
>times, so long as track isn't duplicated.
>
>Also, there's OO cities where it's legal to hit different "sides" of
>the same city with the same train on a single run even if hitting the
>same city with the same train is otherwise forbidden.

In which case they shouldn't be considered the "same" city.
Consider that a hex can contain multiple cities.  Invent a 
nomenclature that works.

Here's the problem that drove me nuts;  How to keep track of which OO 
city is has the Erie home base token on it, given whatever rotation 
of the OO Green and then Brown tile is placed.  You will want to 
paint the token on the right one.

Hint: it comes back to the connectivity.   The city follows the prior 
connectivity of the hex/tile.

Dave.



>---Brett.
>
>------------------------------------------------------------------------------
>Download Intel&#174; Parallel Studio Eval
>Try the new software tools for yourself. Speed compiling, find bugs
>proactively, and fine-tune applications for parallel performance.
>See why Intel Parallel Studio got high marks during beta.
>http://p.sf.net/sfu/intel-sw-dev
>_______________________________________________
>Rails-devel mailing list
>Rai...@li...
>https://lists.sourceforge.net/lists/listinfo/rails-devel

Re: [Rails-devel] Automatic route calculation

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

On Tue, Apr 13, 2010 at 6:15 PM, Dave Mitton <da...@mi...> wrote:
> On 4/13/2010 03:22 PM, Erik Vos wrote:
>
>           Note that this didn't take into account the various "splat" like
> tiles in some later games.These could be handled with a $0 no-token, no-stop
> city in the middle, if that helps the graphic representation.
>
> This wouldn't work, as a city can be visited only once.


This really depends on the game.

Some games allow re-visiting cities as long as the route taken isn't
using the same segment of track more than once.

I believe 1830 has no restriction for visiting the same city multiple
times, so long as track isn't duplicated.

Also, there's OO cities where it's legal to hit different "sides" of
the same city with the same train on a single run even if hitting the
same city with the same train is otherwise forbidden.

---Brett.

Re: [Rails-devel] Automatic route calculation

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

<html>
<body>
On 4/13/2010 03:22 PM, Erik Vos wrote:<br>
<blockquote type=cite class=cite cite="">
<font face="Arial, Helvetica" size=2 color="#0000FF">
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </font>Note that
this didn't take into account the various &quot;splat&quot; like tiles in
some later games.These could be handled with a $0 no-token, no-stop city
in the middle, if that helps the graphic
representation.<font face="Arial, Helvetica" size=2 color="#0000FF">
<br>
</font>&nbsp;<br>
<font face="Arial, Helvetica" size=2 color="#0000FF">This wouldn't work,
as a city can be visited only once. </font></blockquote><br>
You're going to have to work on that for some types of trains.&nbsp; Like
those that ignore some types of cities.<br><br>
The point was to make it a vertex for connectivity sake.&nbsp; The
details would have to be worked out for the implementation.<br><br>
<blockquote type=cite class=cite cite="">&nbsp;<br>
<font face="Arial, Helvetica" size=2 color="#0000FF">In Rails, the
graphics and the</font>
<font face="Arial, Helvetica" size=2 color="#0000FF">graphs are
completely separate. The &quot;new&quot; tiles #81 etc, as in 18EU
(visually represented as 3 tracks meeting in the center), are internally
represented the same way as the &quot;old&quot; versions: with 3 separate
tracks connecting 3 edges. Same thing can be done with 4- and even 6-edge
connect-all tiles. So this is not really a problem.<br>
</font>&nbsp;<br>
<font face="Arial, Helvetica" size=2 color="#0000FF">Erik.</font>
</blockquote><br>
I've seen that in one of the examples, but I'm not sure that the
necessary only way to do that.&nbsp;&nbsp; In my implementation, the it
was possible to draw the route in a different color directly replacing
tile track.&nbsp;&nbsp; That simply required the route highlighting code
to call the track draw code on a per segment basis.<br><br>
My map and route code simply used the same UI routines to draw the
track.&nbsp; It's not hard if you have a unifying concept
underneath.<br><br>
FWIW:<br>
Dave.<br><br>
</body>
</html>

Re: [Rails-devel] Automatic route calculation

[Stefan F. (web.de) <ste...@we...>]

Hi Alex and all others...
... discussing revenue calculation. It seems to spur a lot of interest. 

Sorry for the long post (if one includes the text document), but I try to 
answer most of the asked and some of the not-yet asked questions.
And it seems that the algorithms already improve from the fruitful discussion.

Some talk about the concepts are in the attached text document, that was 
easier to edit.

This is the good thing of commit early and often. One of its disadvantages are 
the embarrassing errors in the early releases. I list those at the end of the 
attachment and hopefully it will clarify some of the problems you ran into.

Good news first:

* Running Times
After hunting them down and adding a new concept (the revenue prediction - see 
attachment) evaluation time is now down to 1-2 seconds for a 8 and 10 train 
on the A scenario on my laptop. Without revenue prediction it runs for 1-2 
minutes. Both runs have identical results.

* Optimal Solution (?)
The other thing is that my implementation suggests a (slightly) different path 
than Alex' which results in an increase of revenue. 
The change is that the 8 train does not have the 10 - 30 - 30 ( 
that is Alexandria and Baton Rouge in 1870, the right bottom in Alex graph - 
it is rotated) in the end, but the 10 - 30 - 50 (that is Austin and SouthWest 
on the map, the right top in Alex graph). Thus it runs for 20 more.

It now pays off that we have independent algorithms running, that can find 
flaws in each others (like you did for mine). 

Stefan

Re: [Rails-devel] Automatic route calculation

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

          Note that this didn't take into account the various "splat" like
tiles in some later games.These could be handled with a $0 no-token, no-stop
city in the middle, if that helps the graphic representation. 
 
This wouldn't work, as a city can be visited only once. 
 
In Rails, the graphics and the graphs are completely separate. The "new"
tiles #81 etc, as in 18EU (visually represented as 3 tracks meeting in the
center), are internally represented the same way as the "old" versions: with
3 separate tracks connecting 3 edges. Same thing can be done with 4- and
even 6-edge connect-all tiles. So this is not really a problem.
 
Erik.

Re: [Rails-devel] Automatic route calculation

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

I tried a 4-train and it backtracked on hex C8.

My simple and fast rule would be: if a route reaches a tile edge, then that
edge *must* be crossed.
If this simple rule does not fit well into graphs, I'd say: too bad for the
graphs, perhaps we need a different approach.

On debug logging: once a feature reaches stability, I usually cut down debug
logging to a sustainable level.

On reloading: yes, I think route detection should start after loading has
completed.

Erik.

-----Original Message-----
From: Stefan Frey (web.de) [mailto:ste...@we...] 
Sent: Monday 12 April 2010 23:49
To: Development list for Rails: an 18xx game
Subject: Re: [Rails-devel] Automatic route calculation

Hi Alex,

thanks for all the input below, it seems that there is really some more 
performance improvement possible. And without your proposals I would not
have 
started such an implementation at all.

Unfortunately I do not have that much time now, but maybe some additions
here 
are helpful, as I had some troubles understanding your approach first.

The major issue for me was how to get around the "switch" problem: A train
is  
not allowed to turn around at the end of the switch and you have to leave
the 
hex to the neighboring one. The major idea of my solution is the definition 
of a "greedy" edge: The "virtual" edges connecting the sides of the 
neighboring hexes force the traveller on their path, if they came 
in "non-greedy"  (those are the tracks inside the hex).

In the network graphs generated the non-greedy edges are those annotated
with 
asteriks. A nice property is that greedyness is dominating if one merges two

edges to eliminate a vertex with only two hexes. The new edge is greedy if
at 
least one of them was greedy. This implies after optimization most edges are

non-greedy, usually only the brown non-station tiles will be left. This and 
the dead-end elimination creates the optimized graphs in Rails.

I have attached the scenario (scenario A) that you talked below for
reference 
for all others, with the rails save file (does only work with the CVS
version 
due to the map corrections), a screenshot of the map and the optimized 
network graph.

Stefan

PS: I would like to compare the results and the performance of the two 
implementations (to know how much improvement is possible ...)

I did not use the exact specification I suggested (due to technical
reasons):
There is only one token in E12 and I run an 8 and 10 train.

My solution run finished 12 minutes on my 4 year old laptop. Interestingly
it 
found already 560 after 1 second, 570 after 1 minute and then 580 after 8 
minutes.

Revenue Value:580
Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE, 
D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1], 
10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE, 
L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]}

On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote:
> Hi all,
>
> Sorry about my disappearance after raising this question couple of weeks
> ago. Things weren't standing still; I was in contact with Stefan, but
> unfortunately circumstances prevented quicker progress. Stefan has added
> some new functionality to Rails to lay some background framework and to
> simplify creation of "test problems". He has created few testing scenarios
> too. My original algorithm has proved to be marginal - on a relatively
> complex example the time was around 40 seconds. We've discussed various
> optimizations and I believe we have found good approach. The basic idea is
> to use two-phased process that runs on two different graphs. The first
> graph (let's call it primary graph) is built from the tiles and
> essentially follows one tile - 7 vertices principle (I've described this
> approach before and after some discussion with Stefan we've concluded that
> it's identical to the approach he had in mind). Essentially, one vertex is
> in the center of the tile and there are 6 vertices, one per tile edge. I
> was envisioning them inside of the tile, on the line connecting the center
> of the tile edge to the center of the tile (in fact, that's how I was
> visualizing them in my program) while Stefan was seeing the center of the
> tile's edge as such vertex (so adjacent tiles would have their vertices on
> the same spot and those vertices would be connected by [invisible] edge).
> This obviously describes exactly the same graph and the difference is only
> in how it can be thought of visually (or displayed).
>
> This primary graph is then used to generate secondary "coarse" graph. The
> only vertices coarse graph has corresponds to the nodes with some value
> (usually cities and towns). The edges of the coarse graph (I will call
> also them segments) are defined by possible distinct routes between its
> vertices. Thus there might be more than one edge connecting the same pair
> of vertices. This edges are built by running my original algorithm on the
> primary graph with the constraint requiring every route to contains
> exactly two nodes (vertices with value) - one at the start and another at
> the end. Essentially the list of these edges is the list of all possible
> two city/town routes. Each segment of this graph has additional
> characteristic - list of segments mutually exclusive with it. There are
> two types of exclusions - one forbids use of the related segment by any
> route and another forbids its use only by the same route. The first type
> of exclusion happens when two segments share some edge of the primary
> graph and the second type happens when only some vertex of the primary
> graph is shared (here we only consider non-terminating vertices - ones
> that are inside of the segment route, those vertices will have no value).
> This information forms coarse graph. There are multiple advantages in
> choosing this approach. The value of any route only depends on the nodes
> (vertices with values) visited, not the intermediate vertices. This
> considerably reduces number of possibilities to scan and it also allows to
> optimize the process by using "pre-packed" segment routes between the
> nodes. The coarse graph is company-independent - it has no token
> information and can be used to do route computations for any company. The
> coarse graph can be built incrementally. The most expensive part of
> building this graph is the search for all possible routes between every
> pair of nodes. This time can be saved if the coarse graph is updated
> incrementally when new tiles are laid (or upgraded). We only need to track
> the routes containing the newly added edges. All remaining routes are
> unaffected. On the "realistic" 1870 scenario we've used for testing it is
> taking 2-3 seconds to build coarse graph from scratch (on my rather
> average computer). If it's built incrementally, this time will virtually
> disappear. Of course, this leaves a question of game reloading (perhaps it
> makes more sense to rebuild it non-incrementally when the game is
> reloaded, or even save the coarse graph itself).
>
> The second phase of the process is to run optimal route search on the
> coarse graph. I am just running my original algorithm on this graph. This
> part takes care of source stations, hostile station blocking, visiting the
> same city twice and similar rules (as well as various bonus application).
> On the example described above this was taking 2-3 seconds. This phase has
> to be re-run every time on "Run trains" step of the operating round, but
> this response time seems acceptable. The run times I've mentioned are from
> my quickly put together implementation of this new approach, so I would
> imagine it's possible to do better just by refining the implementation and
> we haven't looked closely at possible algorithmic optimizations of phase
2.
>
> There are few possibly optimizations that can be applied to the primary
> graph too. Stefan has suggested "asterisk-edge" optimization. This is to
> simplify verification preventing backtracking. Idea is to mark all edges
> that are within the same tile with "asterisk" and then the rule preventing
> backtracking becomes very simple: two "asterisk" edges can be traveled
> consequently only if they're connected at the tile's center. This should
> help in phase 1 generation. There's some difficulty now though, because
> I'm using "transient vertex" optimization which can eliminate some edges
> and thus change adjacency of "asterisk" and "non-asterisk" edges. The
> transient vertex optimization works in the case when there's a vertex
> (without value) connected to exactly two other vertices (for example
> vertex B in A-B-C example). In this case vertex B can be removed and edges
> (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,
> because realistic track build normally has large amount of such vertices.
> Another (obvious) optimization is dead-end elimination (if vertex has no
> value and it is connected with one other vertex only it can be
> eliminated). This optimization should not be used when tracking validity
> of track lay (for obvious reasons).
>
> There were some other ideas, such as caching results of the optimal route
> search and trying to eliminate some possibilities based on the values of
> the cities/towns on the map, but we have no concrete approach to exploit
> them.
>
> Hopefully, I haven't forgotten anything important. Stefan, please free to
> add whatever I've missed.
>
> Thanks,
> Alex.
>
>
---------------------------------------------------------------------------
>--- Download Intel® Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel

Re: [Rails-devel] Automatic route calculation

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

<html><HEAD><LINK rel=stylesheet type=text/css href="/webmail/static/deg/css/wysiwyg-3451203449.css" media=all>
<META name=GENERATOR content="MSHTML 8.00.6001.18904"></HEAD>
<BODY>
<DIV>I'm not sure what each person has done here, but I'll insert my approach.</DIV>
<DIV>&nbsp;</DIV>
<DIV>For a given tile edge entrance, you have to be able to figure out what it connects to.</DIV>
<DIV>It could be another edge, or a city (of some type).&nbsp;&nbsp; More complex tiles have several cities on them.</DIV>
<DIV>This is the connectivity of the tile/hex expressed by the track graphic and must be encoded for the game.</DIV>
<DIV>Note that this didn't take into account the various "splat" like tiles in some later games.</DIV>
<DIV>These could be handled with a $0 no-token, no-stop city in the middle, if that helps the graphic representation.</DIV>
<DIV>&nbsp;</DIV>
<DIV>For 1830 style tiles I ended up with a system of "locations" that were basically the 6 edges and two internal cities.</DIV>
<DIV>That probably was not enough for some games, but it worked for me.</DIV>
<DIV>I flattened the tile connectivity input down into a bit vector for each edge, that could be rotated as the tile was placed, </DIV>
<DIV>and then wrote a simple function&nbsp;&nbsp;for connection exploration that given an edge in, produced a list of "edges" out.</DIV>
<DIV>
<DIV>After a comparison to see if we've been there already by another route, then&nbsp;the edge "out"s where pushed to the adjacent tile edges to be evaluated.</DIV>
<DIV>&nbsp;</DIV></DIV>
<DIV>Also note that using a bit vector allowed me to produce a tile lay rule where the AND of the existing tile connectivity and the canidate tile </DIV>
<DIV>had to be the same as the existing tile bit vector.</DIV>
<DIV>&nbsp;</DIV>
<DIV>So, I like your graph data structure, but there must be a sense of direction in connections or keep a representation of the edge vertex.</DIV>
<DIV>I think that would preserve the correct connectivity.&nbsp; </DIV>
<DIV>&nbsp;</DIV>
<DIV>Another key issues is how to represent these "coordinates".&nbsp; If you can do this, then you can print out lists of a route for logging and recording.</DIV>
<DIV>&nbsp;</DIV>
<DIV>I went with something like&nbsp; &lt;hexcoord&gt;{&lt;edge a-f&gt;|&lt;city x,y&gt;}&nbsp;&nbsp;&nbsp;&nbsp;e.g.&nbsp;&nbsp; A23d</DIV>
<DIV>&nbsp;</DIV>
<DIV>&nbsp;and if the city had a name a function could bring that up too.</DIV>
<DIV>&nbsp;</DIV>
<DIV>Well, enough rambling...</DIV>
<DIV>Keep up the good work.</DIV>
<DIV>Dave.</DIV>
<DIV>&nbsp;</DIV>
<DIV><BR>Apr 13, 2010 11:17:48 AM, <A class=parsedEmail href="mailto:rai...@li..." target=_blank>rai...@li...</A> wrote:<BR></DIV>
<BLOCKQUOTE style="BORDER-LEFT: rgb(102,153,204) 3px solid">
<DIV class=gmail_quote>On Tue, Apr 13, 2010 at 1:28 AM, alexti <SPAN dir=ltr>&lt;<A class=" parsedEmail parsedEmail" href="mailto:al...@sh..." target=_blank>al...@sh...</A>&gt;</SPAN> wrote:<BR>
<BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=gmail_quote>I avoid "switch" problem in a different way. My vertex definition is<BR>geographical - vertex id is its coordinates. Because of that I can check<BR>backtracking differently - my criterion is that two consecutive edges from<BR>the same hex are only allowed if they are joined at the center. This can<BR>not be derived from the graph definition formally. Essentially I have<BR>additional information in the graph that is encoded in the vertex<BR>identifiers.<BR></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV>If I understand you correctly, this will fail for some games with complicated tiles -- also, how does it handle multiple cities per tile?</DIV>
<DIV><BR></DIV></DIV>-- <BR>John A. Tamplin<BR><BR>
<HR SIZE=1>
<BR>------------------------------------------------------------------------------<BR>Download Intel® Parallel Studio Eval<BR>Try the new software tools for yourself. Speed compiling, find bugs<BR>proactively, and fine-tune applications for parallel performance.<BR>See why Intel Parallel Studio got high marks during beta.<BR><A class=parsedLink href="http://p.sf.net/sfu/intel-sw-dev" target=_blank>http://p.sf.net/sfu/intel-sw-dev</A><BR>
<HR SIZE=1>
<BR>_______________________________________________<BR>Rails-devel mailing list<BR><A class="parsedEmail parsedEmail" href="mailto:Rai...@li..." target=_blank>Rai...@li...</A><BR><A class=parsedLink href="https://lists.sourceforge.net/lists/listinfo/rails-devel" target=_blank>https://lists.sourceforge.net/lists/listinfo/rails-devel</A><BR></BLOCKQUOTE></BODY></html>

Re: [Rails-devel] Automatic route calculation

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

On Tue, Apr 13, 2010 at 1:28 AM, alexti <al...@sh...> wrote:

> I avoid "switch" problem in a different way. My vertex definition is
> geographical - vertex id is its coordinates. Because of that I can check
> backtracking differently - my criterion is that two consecutive edges from
> the same hex are only allowed if they are joined at the center. This can
> not be derived from the graph definition formally. Essentially I have
> additional information in the graph that is encoded in the vertex
> identifiers.
>

If I understand you correctly, this will fail for some games with
complicated tiles -- also, how does it handle multiple cities per tile?

-- 
John A. Tamplin

Re: [Rails-devel] Experimental version of revenue calculation

[Phil D. <de...@gm...>]

Stefan,

A quick test on my currently running 18Kaas game threw up one thing
for the algorithm and a vaguely related issue that certainly needs
consideration for automatic revenue generation.

I generated the network info for NYNH in the attached scenario,
firstly, it ran one of the 2 trains by just counting the revenue for
hex G10 on it's own.  In this case NYNH doesn't really have 3 legal
runs for it's 3 trains so I understand why it did this.  It needs to
be limited to not allow runs of only one station (unless there is a
game out there that allows this that I am unaware of?).

The second issue (and less of an algorithm problem) is that the Ruhr
is listed as an income of 2.  This is simply how I assume we have
chosen to represent the 'doubles cities' power of the Ruhr offboard.
If revenue generation is to work for 18Kaas we will need to represent
this differently.  Of course, that is a whole other discussion on it's
own, as far as I can tell different gaming groups handle this rule
totally differently so there may be some discussion as to what the
official ruling is!

Phil

On 12 April 2010 18:50, Stefan Frey (web.de) <ste...@we...> wrote:
> There is a first working version for revenue calculation in CVS.
> The interface is minimal and added to the graph view:
>
> Thus in the ORWindow select Info => NetworkInfo and the
> public company. Then the graph is displayed and the optimal revenue result and
> the vertexes run for each train for the result.
>
> After this one can add additional trains and the optimization restarts.
>
> For available traintypes (currently default (including diesel), +, E and D
> trains) check the addTrainByString method in RevenueAdapter.
>
> BE CAREFUL:
> 1) It generates a lot of debug in the 18xx.log if the logging level is set to
> DEBUG (as it is the default). If one tests complicated cases it can fill up
> the hd quite quickly. Better have an own properties with debug level set to
> INFO.
>
> 2) I cannot guarantee that it will not run into a deadlock, thus it can freeze
> the UI and generate lots of debug output. Again see 1) and kill the program
> after around 5 minutes latest.
>
> But for reasonable (up to moderate difficult) networks it will give results
> nearly immediately.
>
> This is still not the algorithm of Alex, which has pretty amazing running
> times, but a simple brute force algorithm on the current (moderately
> optimized) network graph.
>
> Stefan
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel
>

Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

Hi Stefan,

You have made a lot of progress in implementing route calculation recently
:)

About the "greedy" edges: (I was calling this optimization "asterisk"
optimization in my previous post).

I avoid "switch" problem in a different way. My vertex definition is
geographical - vertex id is its coordinates. Because of that I can check
backtracking differently - my criterion is that two consecutive edges from
the same hex are only allowed if they are joined at the center. This can
not be derived from the graph definition formally. Essentially I have
additional information in the graph that is encoded in the vertex
identifiers.

When I look at the train routes in your example, the sequence [B11.1,
C10.NE, C10.W, C8.NE, D7.NE] doesn't look right to me - C10.W, C8.NE,
D7.NE looks like backtracking.

I've run the test with the setup similar identical to yours (same stations
and trains), it took ~7 seconds on my machine (which is probably somewhat
faster than yours, perhaps by factor of 2 or something like that - unless
your laptop was really high-end when new). 2.5 seconds to build a coarse
graph and 4.5 seconds to find the routes. My total was also 580 and I hope
it is valid. I'm actually finding it challenging to validate correctness.
Couple of times in my experiments I've seen this algorithm picking rather
strange looking routes (not what I would intuitively expected to be the
best), but no matter how I tried I couldn't beat them manually :)

I don't have any mechanism to output the routes in the text form, so I'm
attaching screenshot with those routes highlighted. On my screenshot the
picture is transposed, but it doesn't have any effect on the topology of
the problem. I do not have any timing indicating when these routes have
been found. In a way it doesn't matter right now, until we can somehow
tell that no better route is possible.

Concerning your algorithm, do you do transient vertex optimization? It is
probably the most important optimization on the original (primary as I
called it) graph. And it should be easy to implement (because of
asterisk/greedy edge approach you'd need to make it somewhat less
aggressive so that the resulting edge can preserve correct "greediness".

The other big optimization is two-phased approach - it's essentially
reduced dimensionality of a problem by a big factor. Another big
optimization for me was in efficient memory management, but that could be
hard to implement in Java. I'm also not certain if it's that important
anymore (since I've switched to the two-phased approach). It would be
interesting to see how much change in times you can achieve by removing
transient vertices. Another interesting experiment would be to time how
long it would take your algorithm to find all possible routes for every
city/town pair (that's what is necessary for building coarse graph). I am
not sure how easy it would to modify your code to do that.

I really appreciate your effort in adding this functionality to Rails. Not
being Java specialist I can only help on the algorithmic side. I want to
look into how the second phase works now and what can be improved there
(algorithmically) so I can share these results. I could also take a look
at how to [efficiently] combine transient vertex optimization with the
asterisk edge approach. If we decide to go with two-phased approach (and I
think we definitely should) and build the coarse graph incrementally,
asterisk edge optimization becomes less important. Of course, your
implementation needs asterisk edges to check backtracking which
complicates things a bit. Would it be easy to be use "geographical"
checking? Or is this part of code comes in some library you can't modify?

Please let me know what direction you think we should put our efforts.

Thanks,
Alex.

P.S. Sorry, I am unable to reduce the size of the screenshot much more  
without making it too hard to read.



On Mon, 12 Apr 2010 15:49:14 -0600, Stefan Frey (web.de)
<ste...@we...> wrote:

> Hi Alex,
>
> thanks for all the input below, it seems that there is really some more
> performance improvement possible. And without your proposals I would not  
> have
> started such an implementation at all.
>
> Unfortunately I do not have that much time now, but maybe some additions  
> here
> are helpful, as I had some troubles understanding your approach first.
>
> The major issue for me was how to get around the "switch" problem: A  
> train is
> not allowed to turn around at the end of the switch and you have to  
> leave the
> hex to the neighboring one. The major idea of my solution is the  
> definition
> of a "greedy" edge: The "virtual" edges connecting the sides of the
> neighboring hexes force the traveller on their path, if they came
> in "non-greedy"  (those are the tracks inside the hex).
>
> In the network graphs generated the non-greedy edges are those annotated  
> with
> asteriks. A nice property is that greedyness is dominating if one merges  
> two
> edges to eliminate a vertex with only two hexes. The new edge is greedy  
> if at
> least one of them was greedy. This implies after optimization most edges  
> are
> non-greedy, usually only the brown non-station tiles will be left. This  
> and
> the dead-end elimination creates the optimized graphs in Rails.
>
> I have attached the scenario (scenario A) that you talked below for  
> reference
> for all others, with the rails save file (does only work with the CVS  
> version
> due to the map corrections), a screenshot of the map and the optimized
> network graph.
>
> Stefan
>
> PS: I would like to compare the results and the performance of the two
> implementations (to know how much improvement is possible ...)
>
> I did not use the exact specification I suggested (due to technical  
> reasons):
> There is only one token in E12 and I run an 8 and 10 train.
>
> My solution run finished 12 minutes on my 4 year old laptop.  
> Interestingly it
> found already 560 after 1 second, 570 after 1 minute and then 580 after 8
> minutes.
>
> Revenue Value:580
> Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE,
> D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1],
> 10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE,
> L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]}
>
> On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote:
>> Hi all,
>>
>> Sorry about my disappearance after raising this question couple of weeks
>> ago. Things weren't standing still; I was in contact with Stefan, but
>> unfortunately circumstances prevented quicker progress. Stefan has added
>> some new functionality to Rails to lay some background framework and to
>> simplify creation of "test problems". He has created few testing  
>> scenarios
>> too. My original algorithm has proved to be marginal - on a relatively
>> complex example the time was around 40 seconds. We've discussed various
>> optimizations and I believe we have found good approach. The basic idea  
>> is
>> to use two-phased process that runs on two different graphs. The first
>> graph (let's call it primary graph) is built from the tiles and
>> essentially follows one tile - 7 vertices principle (I've described this
>> approach before and after some discussion with Stefan we've concluded  
>> that
>> it's identical to the approach he had in mind). Essentially, one vertex  
>> is
>> in the center of the tile and there are 6 vertices, one per tile edge. I
>> was envisioning them inside of the tile, on the line connecting the  
>> center
>> of the tile edge to the center of the tile (in fact, that's how I was
>> visualizing them in my program) while Stefan was seeing the center of  
>> the
>> tile's edge as such vertex (so adjacent tiles would have their vertices  
>> on
>> the same spot and those vertices would be connected by [invisible]  
>> edge).
>> This obviously describes exactly the same graph and the difference is  
>> only
>> in how it can be thought of visually (or displayed).
>>
>> This primary graph is then used to generate secondary "coarse" graph.  
>> The
>> only vertices coarse graph has corresponds to the nodes with some value
>> (usually cities and towns). The edges of the coarse graph (I will call
>> also them segments) are defined by possible distinct routes between its
>> vertices. Thus there might be more than one edge connecting the same  
>> pair
>> of vertices. This edges are built by running my original algorithm on  
>> the
>> primary graph with the constraint requiring every route to contains
>> exactly two nodes (vertices with value) - one at the start and another  
>> at
>> the end. Essentially the list of these edges is the list of all possible
>> two city/town routes. Each segment of this graph has additional
>> characteristic - list of segments mutually exclusive with it. There are
>> two types of exclusions - one forbids use of the related segment by any
>> route and another forbids its use only by the same route. The first type
>> of exclusion happens when two segments share some edge of the primary
>> graph and the second type happens when only some vertex of the primary
>> graph is shared (here we only consider non-terminating vertices - ones
>> that are inside of the segment route, those vertices will have no  
>> value).
>> This information forms coarse graph. There are multiple advantages in
>> choosing this approach. The value of any route only depends on the nodes
>> (vertices with values) visited, not the intermediate vertices. This
>> considerably reduces number of possibilities to scan and it also allows  
>> to
>> optimize the process by using "pre-packed" segment routes between the
>> nodes. The coarse graph is company-independent - it has no token
>> information and can be used to do route computations for any company.  
>> The
>> coarse graph can be built incrementally. The most expensive part of
>> building this graph is the search for all possible routes between every
>> pair of nodes. This time can be saved if the coarse graph is updated
>> incrementally when new tiles are laid (or upgraded). We only need to  
>> track
>> the routes containing the newly added edges. All remaining routes are
>> unaffected. On the "realistic" 1870 scenario we've used for testing it  
>> is
>> taking 2-3 seconds to build coarse graph from scratch (on my rather
>> average computer). If it's built incrementally, this time will virtually
>> disappear. Of course, this leaves a question of game reloading (perhaps  
>> it
>> makes more sense to rebuild it non-incrementally when the game is
>> reloaded, or even save the coarse graph itself).
>>
>> The second phase of the process is to run optimal route search on the
>> coarse graph. I am just running my original algorithm on this graph.  
>> This
>> part takes care of source stations, hostile station blocking, visiting  
>> the
>> same city twice and similar rules (as well as various bonus  
>> application).
>> On the example described above this was taking 2-3 seconds. This phase  
>> has
>> to be re-run every time on "Run trains" step of the operating round, but
>> this response time seems acceptable. The run times I've mentioned are  
>> from
>> my quickly put together implementation of this new approach, so I would
>> imagine it's possible to do better just by refining the implementation  
>> and
>> we haven't looked closely at possible algorithmic optimizations of  
>> phase 2.
>>
>> There are few possibly optimizations that can be applied to the primary
>> graph too. Stefan has suggested "asterisk-edge" optimization. This is to
>> simplify verification preventing backtracking. Idea is to mark all edges
>> that are within the same tile with "asterisk" and then the rule  
>> preventing
>> backtracking becomes very simple: two "asterisk" edges can be traveled
>> consequently only if they're connected at the tile's center. This should
>> help in phase 1 generation. There's some difficulty now though, because
>> I'm using "transient vertex" optimization which can eliminate some edges
>> and thus change adjacency of "asterisk" and "non-asterisk" edges. The
>> transient vertex optimization works in the case when there's a vertex
>> (without value) connected to exactly two other vertices (for example
>> vertex B in A-B-C example). In this case vertex B can be removed and  
>> edges
>> (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,
>> because realistic track build normally has large amount of such  
>> vertices.
>> Another (obvious) optimization is dead-end elimination (if vertex has no
>> value and it is connected with one other vertex only it can be
>> eliminated). This optimization should not be used when tracking validity
>> of track lay (for obvious reasons).
>>
>> There were some other ideas, such as caching results of the optimal  
>> route
>> search and trying to eliminate some possibilities based on the values of
>> the cities/towns on the map, but we have no concrete approach to exploit
>> them.
>>
>> Hopefully, I haven't forgotten anything important. Stefan, please free  
>> to
>> add whatever I've missed.
>>
>> Thanks,
>> Alex.
>>
>> ---------------------------------------------------------------------------
>> --- Download Intel&#174; Parallel Studio Eval
>> Try the new software tools for yourself. Speed compiling, find bugs
>> proactively, and fine-tune applications for parallel performance.
>> See why Intel Parallel Studio got high marks during beta.
>> http://p.sf.net/sfu/intel-sw-dev
>> _______________________________________________
>> Rails-devel mailing list
>> Rai...@li...
>> https://lists.sourceforge.net/lists/listinfo/rails-devel
>
>


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: [Rails-devel] Automatic route calculation

[Stefan F. (web.de) <ste...@we...>]

Hi Alex,

thanks for all the input below, it seems that there is really some more 
performance improvement possible. And without your proposals I would not have 
started such an implementation at all.

Unfortunately I do not have that much time now, but maybe some additions here 
are helpful, as I had some troubles understanding your approach first.

The major issue for me was how to get around the "switch" problem: A train is  
not allowed to turn around at the end of the switch and you have to leave the 
hex to the neighboring one. The major idea of my solution is the definition 
of a "greedy" edge: The "virtual" edges connecting the sides of the 
neighboring hexes force the traveller on their path, if they came 
in "non-greedy"  (those are the tracks inside the hex).

In the network graphs generated the non-greedy edges are those annotated with 
asteriks. A nice property is that greedyness is dominating if one merges two 
edges to eliminate a vertex with only two hexes. The new edge is greedy if at 
least one of them was greedy. This implies after optimization most edges are 
non-greedy, usually only the brown non-station tiles will be left. This and 
the dead-end elimination creates the optimized graphs in Rails.

I have attached the scenario (scenario A) that you talked below for reference 
for all others, with the rails save file (does only work with the CVS version 
due to the map corrections), a screenshot of the map and the optimized 
network graph.

Stefan

PS: I would like to compare the results and the performance of the two 
implementations (to know how much improvement is possible ...)

I did not use the exact specification I suggested (due to technical reasons):
There is only one token in E12 and I run an 8 and 10 train.

My solution run finished 12 minutes on my 4 year old laptop. Interestingly it 
found already 560 after 1 second, 570 after 1 minute and then 580 after 8 
minutes.

Revenue Value:580
Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE, 
D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1], 
10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE, 
L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]}

On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote:
> Hi all,
>
> Sorry about my disappearance after raising this question couple of weeks
> ago. Things weren't standing still; I was in contact with Stefan, but
> unfortunately circumstances prevented quicker progress. Stefan has added
> some new functionality to Rails to lay some background framework and to
> simplify creation of "test problems". He has created few testing scenarios
> too. My original algorithm has proved to be marginal - on a relatively
> complex example the time was around 40 seconds. We've discussed various
> optimizations and I believe we have found good approach. The basic idea is
> to use two-phased process that runs on two different graphs. The first
> graph (let's call it primary graph) is built from the tiles and
> essentially follows one tile - 7 vertices principle (I've described this
> approach before and after some discussion with Stefan we've concluded that
> it's identical to the approach he had in mind). Essentially, one vertex is
> in the center of the tile and there are 6 vertices, one per tile edge. I
> was envisioning them inside of the tile, on the line connecting the center
> of the tile edge to the center of the tile (in fact, that's how I was
> visualizing them in my program) while Stefan was seeing the center of the
> tile's edge as such vertex (so adjacent tiles would have their vertices on
> the same spot and those vertices would be connected by [invisible] edge).
> This obviously describes exactly the same graph and the difference is only
> in how it can be thought of visually (or displayed).
>
> This primary graph is then used to generate secondary "coarse" graph. The
> only vertices coarse graph has corresponds to the nodes with some value
> (usually cities and towns). The edges of the coarse graph (I will call
> also them segments) are defined by possible distinct routes between its
> vertices. Thus there might be more than one edge connecting the same pair
> of vertices. This edges are built by running my original algorithm on the
> primary graph with the constraint requiring every route to contains
> exactly two nodes (vertices with value) - one at the start and another at
> the end. Essentially the list of these edges is the list of all possible
> two city/town routes. Each segment of this graph has additional
> characteristic - list of segments mutually exclusive with it. There are
> two types of exclusions - one forbids use of the related segment by any
> route and another forbids its use only by the same route. The first type
> of exclusion happens when two segments share some edge of the primary
> graph and the second type happens when only some vertex of the primary
> graph is shared (here we only consider non-terminating vertices - ones
> that are inside of the segment route, those vertices will have no value).
> This information forms coarse graph. There are multiple advantages in
> choosing this approach. The value of any route only depends on the nodes
> (vertices with values) visited, not the intermediate vertices. This
> considerably reduces number of possibilities to scan and it also allows to
> optimize the process by using "pre-packed" segment routes between the
> nodes. The coarse graph is company-independent - it has no token
> information and can be used to do route computations for any company. The
> coarse graph can be built incrementally. The most expensive part of
> building this graph is the search for all possible routes between every
> pair of nodes. This time can be saved if the coarse graph is updated
> incrementally when new tiles are laid (or upgraded). We only need to track
> the routes containing the newly added edges. All remaining routes are
> unaffected. On the "realistic" 1870 scenario we've used for testing it is
> taking 2-3 seconds to build coarse graph from scratch (on my rather
> average computer). If it's built incrementally, this time will virtually
> disappear. Of course, this leaves a question of game reloading (perhaps it
> makes more sense to rebuild it non-incrementally when the game is
> reloaded, or even save the coarse graph itself).
>
> The second phase of the process is to run optimal route search on the
> coarse graph. I am just running my original algorithm on this graph. This
> part takes care of source stations, hostile station blocking, visiting the
> same city twice and similar rules (as well as various bonus application).
> On the example described above this was taking 2-3 seconds. This phase has
> to be re-run every time on "Run trains" step of the operating round, but
> this response time seems acceptable. The run times I've mentioned are from
> my quickly put together implementation of this new approach, so I would
> imagine it's possible to do better just by refining the implementation and
> we haven't looked closely at possible algorithmic optimizations of phase 2.
>
> There are few possibly optimizations that can be applied to the primary
> graph too. Stefan has suggested "asterisk-edge" optimization. This is to
> simplify verification preventing backtracking. Idea is to mark all edges
> that are within the same tile with "asterisk" and then the rule preventing
> backtracking becomes very simple: two "asterisk" edges can be traveled
> consequently only if they're connected at the tile's center. This should
> help in phase 1 generation. There's some difficulty now though, because
> I'm using "transient vertex" optimization which can eliminate some edges
> and thus change adjacency of "asterisk" and "non-asterisk" edges. The
> transient vertex optimization works in the case when there's a vertex
> (without value) connected to exactly two other vertices (for example
> vertex B in A-B-C example). In this case vertex B can be removed and edges
> (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,
> because realistic track build normally has large amount of such vertices.
> Another (obvious) optimization is dead-end elimination (if vertex has no
> value and it is connected with one other vertex only it can be
> eliminated). This optimization should not be used when tracking validity
> of track lay (for obvious reasons).
>
> There were some other ideas, such as caching results of the optimal route
> search and trying to eliminate some possibilities based on the values of
> the cities/towns on the map, but we have no concrete approach to exploit
> them.
>
> Hopefully, I haven't forgotten anything important. Stefan, please free to
> add whatever I've missed.
>
> Thanks,
> Alex.
>
> ---------------------------------------------------------------------------
>--- Download Intel® Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel

Re: [Rails-devel] Experimental version of revenue calculation

[Phil D. <de...@gm...>]

I recall a discussion on this a couple of months back.  I think the
general consensus was that at the moment, debug logging doesn't
significantly impact runtime performance and doesn't cause enough data
to be a disk space issue.  The benefit in terms of making it easy for
users to submit bug reports with logging data was worth leaving it on.

I suspect as and when this change goes live we might want to revisit
that decision

As far as the changes go, sounds exciting, I'll load up my current
PBEM games and run them with this feature on and see what feedback we
can give

Phil

On 12 April 2010 19:09, Chris Shaffer <chr...@gm...> wrote:
> Since there are more non-programmer end-users running rails, shouldn't the
> default for logging be INFO?
>
> --
> Chris
>
> Please consider the environment before printing this e-mail.
>
>
> On Mon, Apr 12, 2010 at 10:50 AM, Stefan Frey (web.de) <ste...@we...>
> wrote:
>>
>> There is a first working version for revenue calculation in CVS.
>> The interface is minimal and added to the graph view:
>>
>> Thus in the ORWindow select Info => NetworkInfo and the
>> public company. Then the graph is displayed and the optimal revenue result
>> and
>> the vertexes run for each train for the result.
>>
>> After this one can add additional trains and the optimization restarts.
>>
>> For available traintypes (currently default (including diesel), +, E and D
>> trains) check the addTrainByString method in RevenueAdapter.
>>
>> BE CAREFUL:
>> 1) It generates a lot of debug in the 18xx.log if the logging level is set
>> to
>> DEBUG (as it is the default). If one tests complicated cases it can fill
>> up
>> the hd quite quickly. Better have an own properties with debug level set
>> to
>> INFO.
>>
>> 2) I cannot guarantee that it will not run into a deadlock, thus it can
>> freeze
>> the UI and generate lots of debug output. Again see 1) and kill the
>> program
>> after around 5 minutes latest.
>>
>> But for reasonable (up to moderate difficult) networks it will give
>> results
>> nearly immediately.
>>
>> This is still not the algorithm of Alex, which has pretty amazing running
>> times, but a simple brute force algorithm on the current (moderately
>> optimized) network graph.
>>
>> Stefan
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Download Intel&#174; Parallel Studio Eval
>> Try the new software tools for yourself. Speed compiling, find bugs
>> proactively, and fine-tune applications for parallel performance.
>> See why Intel Parallel Studio got high marks during beta.
>> http://p.sf.net/sfu/intel-sw-dev
>> _______________________________________________
>> Rails-devel mailing list
>> Rai...@li...
>> https://lists.sourceforge.net/lists/listinfo/rails-devel
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel
>
>

Re: [Rails-devel] Experimental version of revenue calculation

[Chris S. <chr...@gm...>]

Since there are more non-programmer end-users running rails, shouldn't the
default for logging be INFO?

--
Chris

Please consider the environment before printing this e-mail.


On Mon, Apr 12, 2010 at 10:50 AM, Stefan Frey (web.de)
<ste...@we...>wrote:

> There is a first working version for revenue calculation in CVS.
> The interface is minimal and added to the graph view:
>
> Thus in the ORWindow select Info => NetworkInfo and the
> public company. Then the graph is displayed and the optimal revenue result
> and
> the vertexes run for each train for the result.
>
> After this one can add additional trains and the optimization restarts.
>
> For available traintypes (currently default (including diesel), +, E and D
> trains) check the addTrainByString method in RevenueAdapter.
>
> BE CAREFUL:
> 1) It generates a lot of debug in the 18xx.log if the logging level is set
> to
> DEBUG (as it is the default). If one tests complicated cases it can fill up
> the hd quite quickly. Better have an own properties with debug level set to
> INFO.
>
> 2) I cannot guarantee that it will not run into a deadlock, thus it can
> freeze
> the UI and generate lots of debug output. Again see 1) and kill the program
> after around 5 minutes latest.
>
> But for reasonable (up to moderate difficult) networks it will give results
> nearly immediately.
>
> This is still not the algorithm of Alex, which has pretty amazing running
> times, but a simple brute force algorithm on the current (moderately
> optimized) network graph.
>
> Stefan
>
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel
>

[Rails-devel] Experimental version of revenue calculation

[Stefan F. (web.de) <ste...@we...>]

There is a first working version for revenue calculation in CVS.
The interface is minimal and added to the graph view:

Thus in the ORWindow select Info => NetworkInfo and the 
public company. Then the graph is displayed and the optimal revenue result and
the vertexes run for each train for the result. 

After this one can add additional trains and the optimization restarts.

For available traintypes (currently default (including diesel), +, E and D 
trains) check the addTrainByString method in RevenueAdapter.

BE CAREFUL:
1) It generates a lot of debug in the 18xx.log if the logging level is set to 
DEBUG (as it is the default). If one tests complicated cases it can fill up 
the hd quite quickly. Better have an own properties with debug level set to 
INFO.

2) I cannot guarantee that it will not run into a deadlock, thus it can freeze 
the UI and generate lots of debug output. Again see 1) and kill the program 
after around 5 minutes latest.

But for reasonable (up to moderate difficult) networks it will give results 
nearly immediately.

This is still not the algorithm of Alex, which has pretty amazing running 
times, but a simple brute force algorithm on the current (moderately 
optimized) network graph.

Stefan

[Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

Hi all,

Sorry about my disappearance after raising this question couple of weeks  
ago. Things weren't standing still; I was in contact with Stefan, but  
unfortunately circumstances prevented quicker progress. Stefan has added  
some new functionality to Rails to lay some background framework and to  
simplify creation of "test problems". He has created few testing scenarios  
too. My original algorithm has proved to be marginal - on a relatively  
complex example the time was around 40 seconds. We've discussed various  
optimizations and I believe we have found good approach. The basic idea is  
to use two-phased process that runs on two different graphs. The first  
graph (let's call it primary graph) is built from the tiles and  
essentially follows one tile - 7 vertices principle (I've described this  
approach before and after some discussion with Stefan we've concluded that  
it's identical to the approach he had in mind). Essentially, one vertex is  
in the center of the tile and there are 6 vertices, one per tile edge. I  
was envisioning them inside of the tile, on the line connecting the center  
of the tile edge to the center of the tile (in fact, that's how I was  
visualizing them in my program) while Stefan was seeing the center of the  
tile's edge as such vertex (so adjacent tiles would have their vertices on  
the same spot and those vertices would be connected by [invisible] edge).  
This obviously describes exactly the same graph and the difference is only  
in how it can be thought of visually (or displayed).

This primary graph is then used to generate secondary "coarse" graph. The  
only vertices coarse graph has corresponds to the nodes with some value  
(usually cities and towns). The edges of the coarse graph (I will call  
also them segments) are defined by possible distinct routes between its  
vertices. Thus there might be more than one edge connecting the same pair  
of vertices. This edges are built by running my original algorithm on the  
primary graph with the constraint requiring every route to contains  
exactly two nodes (vertices with value) - one at the start and another at  
the end. Essentially the list of these edges is the list of all possible  
two city/town routes. Each segment of this graph has additional  
characteristic - list of segments mutually exclusive with it. There are  
two types of exclusions - one forbids use of the related segment by any  
route and another forbids its use only by the same route. The first type  
of exclusion happens when two segments share some edge of the primary  
graph and the second type happens when only some vertex of the primary  
graph is shared (here we only consider non-terminating vertices - ones  
that are inside of the segment route, those vertices will have no value).  
This information forms coarse graph. There are multiple advantages in  
choosing this approach. The value of any route only depends on the nodes  
(vertices with values) visited, not the intermediate vertices. This  
considerably reduces number of possibilities to scan and it also allows to  
optimize the process by using "pre-packed" segment routes between the  
nodes. The coarse graph is company-independent - it has no token  
information and can be used to do route computations for any company. The  
coarse graph can be built incrementally. The most expensive part of  
building this graph is the search for all possible routes between every  
pair of nodes. This time can be saved if the coarse graph is updated  
incrementally when new tiles are laid (or upgraded). We only need to track  
the routes containing the newly added edges. All remaining routes are  
unaffected. On the "realistic" 1870 scenario we've used for testing it is  
taking 2-3 seconds to build coarse graph from scratch (on my rather  
average computer). If it's built incrementally, this time will virtually  
disappear. Of course, this leaves a question of game reloading (perhaps it  
makes more sense to rebuild it non-incrementally when the game is  
reloaded, or even save the coarse graph itself).

The second phase of the process is to run optimal route search on the  
coarse graph. I am just running my original algorithm on this graph. This  
part takes care of source stations, hostile station blocking, visiting the  
same city twice and similar rules (as well as various bonus application).  
On the example described above this was taking 2-3 seconds. This phase has  
to be re-run every time on "Run trains" step of the operating round, but  
this response time seems acceptable. The run times I've mentioned are from  
my quickly put together implementation of this new approach, so I would  
imagine it's possible to do better just by refining the implementation and  
we haven't looked closely at possible algorithmic optimizations of phase 2.

There are few possibly optimizations that can be applied to the primary  
graph too. Stefan has suggested "asterisk-edge" optimization. This is to  
simplify verification preventing backtracking. Idea is to mark all edges  
that are within the same tile with "asterisk" and then the rule preventing  
backtracking becomes very simple: two "asterisk" edges can be traveled  
consequently only if they're connected at the tile's center. This should  
help in phase 1 generation. There's some difficulty now though, because  
I'm using "transient vertex" optimization which can eliminate some edges  
and thus change adjacency of "asterisk" and "non-asterisk" edges. The  
transient vertex optimization works in the case when there's a vertex  
(without value) connected to exactly two other vertices (for example  
vertex B in A-B-C example). In this case vertex B can be removed and edges  
(A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,  
because realistic track build normally has large amount of such vertices.  
Another (obvious) optimization is dead-end elimination (if vertex has no  
value and it is connected with one other vertex only it can be  
eliminated). This optimization should not be used when tracking validity  
of track lay (for obvious reasons).

There were some other ideas, such as caching results of the optimal route  
search and trying to eliminate some possibilities based on the values of  
the cities/towns on the map, but we have no concrete approach to exploit  
them.

Hopefully, I haven't forgotten anything important. Stefan, please free to  
add whatever I've missed.

Thanks,
Alex.

[Rails-devel] Automatic route calculation

[Alex T. <al...@sh...>]

Hi all,

Sorry about my disappearance after raising this question couple of weeks  
ago. Things weren't standing still; I was in contact with Stefan, but  
unfortunately circumstances prevented quicker progress. Stefan has added  
some new functionality to Rails to lay some background framework and to  
simplify creation of "test problems". He has created few testing scenarios  
too. My original algorithm has proved to be marginal - on a relatively  
complex example the time was around 40 seconds. We've discussed various  
optimizations and I believe we have found good approach. The basic idea is  
to use two-phased process that runs on two different graphs. The first  
graph (let's call it primary graph) is built from the tiles and  
essentially follows one tile - 7 vertices principle (I've described this  
approach before and after some discussion with Stefan we've concluded that  
it's identical to the approach he had in mind). Essentially, one vertex is  
in the center of the tile and there are 6 vertices, one per tile edge. I  
was envisioning them inside of the tile, on the line connecting the center  
of the tile edge to the center of the tile (in fact, that's how I was  
visualizing them in my program) while Stefan was seeing the center of the  
tile's edge as such vertex (so adjacent tiles would have their vertices on  
the same spot and those vertices would be connected by [invisible] edge).  
This obviously describes exactly the same graph and the difference is only  
in how it can be thought of visually (or displayed).

This primary graph is then used to generate secondary "coarse" graph. The  
only vertices coarse graph has corresponds to the nodes with some value  
(usually cities and towns). The edges of the coarse graph (I will call  
also them segments) are defined by possible distinct routes between its  
vertices. Thus there might be more than one edge connecting the same pair  
of vertices. This edges are built by running my original algorithm on the  
primary graph with the constraint requiring every route to contains  
exactly two nodes (vertices with value) - one at the start and another at  
the end. Essentially the list of these edges is the list of all possible  
two city/town routes. Each segment of this graph has additional  
characteristic - list of segments mutually exclusive with it. There are  
two types of exclusions - one forbids use of the related segment by any  
route and another forbids its use only by the same route. The first type  
of exclusion happens when two segments share some edge of the primary  
graph and the second type happens when only some vertex of the primary  
graph is shared (here we only consider non-terminating vertices - ones  
that are inside of the segment route, those vertices will have no value).  
This information forms coarse graph. There are multiple advantages in  
choosing this approach. The value of any route only depends on the nodes  
(vertices with values) visited, not the intermediate vertices. This  
considerably reduces number of possibilities to scan and it also allows to  
optimize the process by using "pre-packed" segment routes between the  
nodes. The coarse graph is company-independent - it has no token  
information and can be used to do route computations for any company. The  
coarse graph can be built incrementally. The most expensive part of  
building this graph is the search for all possible routes between every  
pair of nodes. This time can be saved if the coarse graph is updated  
incrementally when new tiles are laid (or upgraded). We only need to track  
the routes containing the newly added edges. All remaining routes are  
unaffected. On the "realistic" 1870 scenario we've used for testing it is  
taking 2-3 seconds to build coarse graph from scratch (on my rather  
average computer). If it's built incrementally, this time will virtually  
disappear. Of course, this leaves a question of game reloading (perhaps it  
makes more sense to rebuild it non-incrementally when the game is  
reloaded, or even save the coarse graph itself).

The second phase of the process is to run optimal route search on the  
coarse graph. I am just running my original algorithm on this graph. This  
part takes care of source stations, hostile station blocking, visiting the  
same city twice and similar rules (as well as various bonus application).  
On the example described above this was taking 2-3 seconds. This phase has  
to be re-run every time on "Run trains" step of the operating round, but  
this response time seems acceptable. The run times I've mentioned are from  
my quickly put together implementation of this new approach, so I would  
imagine it's possible to do better just by refining the implementation and  
we haven't looked closely at possible algorithmic optimizations of phase 2.

There are few possibly optimizations that can be applied to the primary  
graph too. Stefan has suggested "asterisk-edge" optimization. This is to  
simplify verification preventing backtracking. Idea is to mark all edges  
that are within the same tile with "asterisk" and then the rule preventing  
backtracking becomes very simple: two "asterisk" edges can be traveled  
consequently only if they're connected at the tile's center. This should  
help in phase 1 generation. There's some difficulty now though, because  
I'm using "transient vertex" optimization which can eliminate some edges  
and thus change adjacency of "asterisk" and "non-asterisk" edges. The  
transient vertex optimization works in the case when there's a vertex  
(without value) connected to exactly two other vertices (for example  
vertex B in A-B-C example). In this case vertex B can be removed and edges  
(A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,  
because realistic track build normally has large amount of such vertices.  
Another (obvious) optimization is dead-end elimination (if vertex has no  
value and it is connected with one other vertex only it can be  
eliminated). This optimization should not be used when tracking validity  
of track lay (for obvious reasons).

There were some other ideas, such as caching results of the optimal route  
search and trying to eliminate some possibilities based on the values of  
the cities/towns on the map, but we have no concrete approach to exploit  
them.

Hopefully, I haven't forgotten anything important. Stefan, please free to  
add whatever I've missed.

Thanks,
Alex.

Re: [Rails-devel] Tile and Token Lay GUI Hints

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

Thanks for the good point about the reserved hexes. 18EU also has it, but
there the rule is that other companies need the consent of the owner's
company president - that does complicate things. I'll think about it.

Hex blocking by privates was already done long ago.

Erik.

-----Original Message-----
From: John David Galt [mailto:jd...@di...] 
Sent: Sunday 11 April 2010 20:34
To: Development list for Rails: an 18xx game
Subject: Re: [Rails-devel] Tile and Token Lay GUI Hints

On 2010-04-11 08:06, Erik Vos wrote:
> Pending answers to the below questions, I have committed code that does
the
> following:
> - In cases where a company has a defined home city, other companies are
> prevented to lay tokens if there is no extra free space (be it never, as
in
> 1830 Boston/Baltimore, or temporarily, as in yellow/green 1830 NE New
York).
> - In cases where a company must choose its home city, other companies are
> prevented to lay any tokens until that home token has been laid. This
> applies to 1830 Erie and 1835 BA.
> - A special provision was needed for green 1835 Berlin, where the one free
> token slot can be used even if PR has not yet started.
> 
> If I have overlooked other special cases, please let me know.

This is a good general rule.  In 1856 I ask the other players, because many
play with the restriction even though it isn't written.

While you're at it, you might want to provide for cases where a hex is
"restricted" so only a certain company (or more than one) can lay tiles
there
even though it's not that company's starting hex.  1825, 1826, and (IIRC)
the
Deep Thought Midwest game (1846?) use this mechanism to protect companies'
exits from their starting cities, and if the code for it is flexible enough,
it can implement private companies (in 1830, 37, AL) and the zones of 1853.

----------------------------------------------------------------------------
--
Download Intel® Parallel Studio Eval
Try the new software tools for yourself. Speed compiling, find bugs
proactively, and fine-tune applications for parallel performance.
See why Intel Parallel Studio got high marks during beta.
http://p.sf.net/sfu/intel-sw-dev
_______________________________________________
Rails-devel mailing list
Rai...@li...
https://lists.sourceforge.net/lists/listinfo/rails-devel

Re: [Rails-devel] Tile and Token Lay GUI Hints

[John D. G. <jd...@di...>]

On 2010-04-11 08:06, Erik Vos wrote:
> Pending answers to the below questions, I have committed code that does the
> following:
> - In cases where a company has a defined home city, other companies are
> prevented to lay tokens if there is no extra free space (be it never, as in
> 1830 Boston/Baltimore, or temporarily, as in yellow/green 1830 NE New York).
> - In cases where a company must choose its home city, other companies are
> prevented to lay any tokens until that home token has been laid. This
> applies to 1830 Erie and 1835 BA.
> - A special provision was needed for green 1835 Berlin, where the one free
> token slot can be used even if PR has not yet started.
> 
> If I have overlooked other special cases, please let me know.

This is a good general rule.  In 1856 I ask the other players, because many
play with the restriction even though it isn't written.

While you're at it, you might want to provide for cases where a hex is
"restricted" so only a certain company (or more than one) can lay tiles there
even though it's not that company's starting hex.  1825, 1826, and (IIRC) the
Deep Thought Midwest game (1846?) use this mechanism to protect companies'
exits from their starting cities, and if the code for it is flexible enough,
it can implement private companies (in 1830, 37, AL) and the zones of 1853.

Re: [Rails-devel] Tile and Token Lay GUI Hints

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

Pending answers to the below questions, I have committed code that does the
following:
- In cases where a company has a defined home city, other companies are
prevented to lay tokens if there is no extra free space (be it never, as in
1830 Boston/Baltimore, or temporarily, as in yellow/green 1830 NE New York).
- In cases where a company must choose its home city, other companies are
prevented to lay any tokens until that home token has been laid. This
applies to 1830 Erie and 1835 BA.
- A special provision was needed for green 1835 Berlin, where the one free
token slot can be used even if PR has not yet started.

If I have overlooked other special cases, please let me know.

For now, these checks only apply during post-action validation. Once
Stefan's new route awareness feature is applied to the back-end code, these
checks can also be applied pre-action to prevent untokenable hexes to be
highlighted.

Erik.

-----Original Message-----
From: Erik Vos [mailto:eri...@xs...] 
Sent: Sunday 11 April 2010 15:25
To: 'Development list for Rails: an 18xx game'
Subject: RE: [Rails-devel] Tile and Token Lay GUI Hints


>Ultimately the list of allowed locations will have to be prepared in
OperatingRound and put into the LayTile/LayBaseToken actions (which are
already prepared to contain such lists). Doing that will also make it easier
to avoid disallowed lays, such as a NYNH token on Boston in 1830. Such
checks don't yet exist (even in post-laying action validation), and are on
my list to be implemented soon. 

On this matter: I have recently implemented the blocking of token lays on
Mannheim/Ludwigshafen (1835) if BA has not yet laid its home token on that
hex. As a similar rule also applies to 1830 Erie, I think I will create a
generic option that can be set in the XML. 

My question is: does this rule apply to all similar cases, i.e. where an
OO-style two-city hex has a yet unspecified home base? The only other case
I'm currently aware of is 1856 Hamilton, the home base of THB. The 1856
rules and all rule clarifications I have found are silent on this matter,
i.e. on the question if another company may lay a token there before the THB
does. So I would think that it is allowed in this case.

Also, am I right in concluding that in none of the cases mentioned other
companies are prohibited to lay the first *tile* on such a hex?

Erik.

Re: [Rails-devel] Tile and Token Lay GUI Hints

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

>Ultimately the list of allowed locations will have to be prepared in
OperatingRound and put into the LayTile/LayBaseToken actions (which are
already prepared to contain such lists). Doing that will also make it easier
to avoid disallowed lays, such as a NYNH token on Boston in 1830. Such
checks don't yet exist (even in post-laying action validation), and are on
my list to be implemented soon. 

On this matter: I have recently implemented the blocking of token lays on
Mannheim/Ludwigshafen (1835) if BA has not yet laid its home token on that
hex. As a similar rule also applies to 1830 Erie, I think I will create a
generic option that can be set in the XML. 

My question is: does this rule apply to all similar cases, i.e. where an
OO-style two-city hex has a yet unspecified home base? The only other case
I'm currently aware of is 1856 Hamilton, the home base of THB. The 1856
rules and all rule clarifications I have found are silent on this matter,
i.e. on the question if another company may lay a token there before the THB
does. So I would think that it is allowed in this case.

Also, am I right in concluding that in none of the cases mentioned other
companies are prohibited to lay the first *tile* on such a hex?

Erik.

Re: [Rails-devel] Tile and Token Lay GUI Hints

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

Seems to work fine, on first sight. Congratulations to have got this
working!

Ultimately the list of allowed locations will have to be prepared in
OperatingRound and put into the LayTile/LayBaseToken actions (which are
already prepared to contain such lists). Doing that will also make it easier
to avoid disallowed lays, such as a NYNH token on Boston in 1830. Such
checks don't yet exist (even in post-laying action validation), and are on
my list to be implemented soon. 

Erik.

-----Original Message-----
From: Stefan Frey [mailto:ste...@we...] 
Sent: Saturday 10 April 2010 09:13
To: Development list for Rails: an 18xx game
Subject: [Rails-devel] Tile and Token Lay GUI Hints

I checked in an experimental implementation that indicates possible hexes
for tile and token lay in CVS, based on the current implementation of
network graphs.

It takes into account possible tile upgrades and the current phase.
It is not perfect yet as it still might indicate some hexes which might not
be 
upgradable (due to other constraints). Still it should be a superset of the 
allowed tile upgrades, those no possible hex should be missed.
The same holds for the possible locations for token lay.

Those are only visual hints, the actual checks have not changed, thus
illegal 
tile and token lays are still allowed as before.

Stefan

----------------------------------------------------------------------------
--
Download Intel® Parallel Studio Eval
Try the new software tools for yourself. Speed compiling, find bugs
proactively, and fine-tune applications for parallel performance.
See why Intel Parallel Studio got high marks during beta.
http://p.sf.net/sfu/intel-sw-dev
_______________________________________________
Rails-devel mailing list
Rai...@li...
https://lists.sourceforge.net/lists/listinfo/rails-devel