Re: [Rails-devel] 18xx Rails: Feature Request 1517702 - automatic route calculation

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

On Tue, Dec 22, 2009 at 5:18 AM, Frederick Weld <
fre...@go...> wrote:

> (2) What SimTex's 1830 (most probably) does: A separate model (multi-edge
> graph) for route calculation is updated whenever someone lays a tile. By
> doing this, you get a very low constant factor of the time the algorithm
> needs, meaning you'll still have exponential time but you won't perceive
> this until the size of the graph becomes very large.
>

Also note that PC 1830 frequently computed incorrect routes.

Building the connectivity graph isn't actually the time-consuming part (and
as you say, is trivial to build incrementally).  Also, building a route
calculation engine that didn't have to work for multiple games would
probably work ok, but when you start adding things like bonuses that depend
on which stops you make, trains that can skip cities, etc, all the heuristic
graph algorithms go out the window.

-- 
John A. Tamplin