Re: [Rails-devel] Automatic route calculation

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

On Sun, Mar 21, 2010 at 2:30 PM, alexti <al...@sh...> wrote:

> I am still unconvinced that this would be that relevant - in most games
> there's less than 200 tiles and there's probably 3-4 links per tile on
> average. That means less than 1000 edges even in the endgame, so it
> doesn't seem that we need to look at the asymptotic properties here. But I
> am familiar only with a limited subset of 18xx titles, are there any that
> exceed this number by much?


It really doesn't take a big number for n! to become intractable.

As a real-world example, we found that IE6 used an n^3 algorithm for CSS
evaluation in a certain scenario.  Back when IE6 was written, there wasn't a
lot of complicated AJAX apps that built complicated DOMs with lots of CSS
rules, but we found with Google AdWords a particular CSS rule caused IE6 to
compute for over 3 minutes to respond to a mouse move event!  Needless to
say, interactive performance was suboptimal :).

This was with a few thousand DOM nodes and a few hundred CSS rules.  If it
were an n! algorithm, it would have become unusable with a few dozens of
each.

Yes, I use brute-force approach of going through all possible routes that
> include a token. Why interaction with another train will be more
> complicated in this case? It still can't re-use the same track. Or are
> there games where it can?


Yes, but that actually makes it easier -- you just calculate the routes of
the trains that can reuse track independently of the others (such as TGV in
1826, 4D in 18Neb, etc).

The problem is when they can't reuse track, you have to choose the optimal
run for all trains together, not independently.  It is often the case that
the optimal run for running multiple trains is not an optimal run for any
one of the trains by itself.  Therefore, you must evaluate all the trains at
the same time, which in a brute force algorithm gets you back to n!^m.


> That's ok. I'm assuming that the bonus table is specific to the current
> phase (it also gets updated as privates change hands etc). Doubling a
> single city is also fine as it doesn't matter what train (if only one
> allowed) will benefit from it.


Normally in those cases only the train making the E-W/N-S/whatever run gets
to double that stop, and it may or may not include any other bonuses that
could be applied to that city.


> Perhaps it can be tested? There is no need to have complete support of
> such games in Rails to make experiment. We could create a graph
> representing "difficult case" and run algorithm on it.
>

Yes, though it could take time to manually build the graph the way your
algorithm wants it.


> > Some I would look at would be 18US, 18C2C (for sheer size and the ability
> > for a company to run lots of large trains), 1844 (which adds tunnels and
> > mountains that affect the route score), and 1860.
> Unfortunately, I don't own any of them :(
>

The complete rules are available for at least 18US and 1844, and ps18xx
includes the map/tiles for all of them.

-- 
John A. Tamplin