Re: [Rails-devel] Automatic route calculation

[Stefan F. <ste...@we...>]

Hi Alex,
on a first glance it makes a lot of sense and I would definitely like to see 
some route calculation support for example in 1870 or 1835 with Preussen.

And from your description you have already included a lot of additional game 
options. I am very curious about your solution for this important feature and
I assume this is true for anyone involved with the project.

Some quick questions and comments:

- I prefer your definition of the graph to the one in tiles.xml (inherited 
from the tiledesigner) as you only have to count edges and you do not have to 
consider that you are not allowed to visit the same side (a node/vertex in 
Rails) twice. Rails defines tile 25 (the green Y) with two edges that both 
start from the same side  (see tiles.xml), but only one of each edge can be 
used per revenue turn.

- Is your algorithm implemented in Java and what is the calculation time for 
standard hardware and a reasonable difficult setting? (Your text below seems 
to imply close to zero, if you can use it for AI).

- From your description I conjecture that  you already maintain a dictionary 
that maps tile ids to your vertix/edge defintions. In that case that would 
easy to add, if the data format is used can be converted to xml. Rails 
maintains a similar definition file in tiles/tiles.xml. 

Stefan


On Sunday 21 March 2010 06:43:31 alexti wrote:
> I am not completely sure if you were referring to the difficulties of the
> algorithm or the difficulties of the integration, but I assume it's former.
>
> Perhaps I should explain how the algorithm works to make things more
> clear. There are two parts to the algorithm - route selection and route
> evaluation. Route selection is performed on the abstract connectivity
> graph (which is a vector of edges and a associative map of vertices). Each
> edge is a pair of vertex coordinates on 2-D grid (I use specific encoding
> that allows to go between these vertices and hexes (or tiles) and back by
> simple arithmetics). Vertex information contains some basic data, such as
> whether there is a town at this vertex, if it's blocked [by station
> markers of other companies], current town/city value etc... The way this
> connectivity graph is defined takes care of handling use of track segments
> and visiting same cities. It would be easier to show he method on the
> picture, but I will try to describe it here. Let's say we have a hex
> oriented so that one side is facing north, another south and the other 4
> NW, SW, NE and SE. For each hex there will be 13 vertices. One in the
> center (#0), 6 vertices each in the middle of the hex edge (#1-#6, #1 is
> North, counting clockwise) and 6 more in the middle of the line connecting
> each of vertices #1-#6 to the center. Vertices #1-#6 will be shared with
> other adjacent hexes. Let's say we have green Y tile (two gently curving
> tracks from S to NW and from S to NE). Connectivity graph for such tile
> will be (2-8,8-10,10-4,6-12,12-10). 10-4 edge represents the bottom of "Y"
> and this ensures that only one of the track segments on this tile can be
> used. This definition method also takes care of defining tiles such as
> yellow and green Toronto from 1856 or Moscow from 1861.
>
> In general the search for optimal routes work by selecting a route,
> evaluating its value, removing the used edges from the graph and running
> the search again on the remaining graph (with remaining trains). Then
> choosing the "next" route and repeating the process, until the set of
> routes with the highest total value is found. In the route selection
> process there are 3 direction of iteration: "head", "tail" and "branch".
> "Head" and "tail" is extending (by one edge) from the head or from the
> tail (each route starts from the station) and "branch" is replacing last
> added edge with the possible alternative. This guarantees to iterate over
> every possible route (here by route I mean route in graph terms, it's not
> necessarily a valid route in 18xx terms). In practice, I'm using few
> optimizations to eliminate complete scan, but that's probably unimportant
> for non-AI use.
>
> The route evaluation part needs to be aware of the rules of the specific
> games. Route evaluation logic gets a proposed route as a vector of
> vertices it visits. As a result it gives a value and the vector of
> vertices it has used (this is used for optimization by skipping the routes
> that just an extension from the unused side). In a simple case evaluation
> would be simple - just total values of the best subset of cities and
> towns, but various bonuses make things more complicated. I'm using a bonus
> table containing various bonuses and their requirements. Bonuses can be:
> add extra value to the vertex, multiply value of the vertex, add value to
> the route (for example if 2 specific locations are visited) etc... Bonuses
> can be defined as sets if it's necessary to allow only one bonus from the
> set to be applied. Because of that, the route evaluation algorithm has to
> return updated "bonus usage context". There may be a need to iterate over
> bonus choices (such as not apply some bonus when possible), but I am not
> sure what game has such set of possible bonuses to require it. I haven't
> done such iteration because it would be bad for AI case (because of
> performance), for non-AI case, it's probably not a big issue.
>
> Some parts of the route evaluation code might need to be updated for
> specific games, but such updates should not affect the logic for anything
> else. Two types of trains I am aware of that might require more thought
> are hex trains and "N out of M" trains. Essentially, my current assumption
> is that for any route candidate the optimal route use (meaning use of
> trains and bonuses) can always be determined if both head and tail
> vertices are used.
>
> Alex
>
> On Sat, 20 Mar 2010 18:17:41 -0600, John A. Tamplin <ja...@ja...> wrote:
> > Yes, though see the archives for details about why it may be harder than
> > you
> > think.
> >
> > John A. Tamplin (Android)
> >
> > On Mar 20, 2010 8:12 PM, "Alex Tikhonov" <al...@sh...> wrote:
> >
> > Hi all,
> >
> > Per Brett Lentz suggestion I am moving this discussion here and reporting
> > my message from 18x yahoo group.
> >
> > This is my first post here, but I have been lurking for a while. I wonder
> > if there is an interest in adding automatic route calculation to Rails. I
> > am trying to create AI for some of the games (and no, it's not going
> > well), but as a side effect I have code that computes the routes. It
> > supports some of more widely used rules (various town treatment, city and
> > route bonuses, multipliers etc). It runs on an abstract connectivity
> > graph, so it should not be too hard to integrate.
> >
> > 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