Re: [Rails-devel] Automatic route calculation

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

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


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