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