[Freeciv-Dev] Re: Warmap

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 14 Aug 2002, Raimar Falke wrote:

> On Tue, Aug 13, 2002 at 10:16:28PM +0100, Vasco Alexandre Da Silva Costa 
> wrote:
> > On Tue, 13 Aug 2002, Gregory Berkolaiko wrote:
> > 
> > > On Mon, 12 Aug 2002, Vasco Alexandre Da Silva Costa wrote:
> > >
> > > > Regarding warmap speedups:
> > > >
> > > > If anyone feels up to implementing them, there are some algorithms which
> > > > promise to solve the single-source problem:
> > > > <http://www.boost.org/libs/graph/doc/graph_theory_review.html>
> > > >
> > > > in linear time for undirected planar graphs:
> > > > <http://mathworld.wolfram.com/PlanarGraph.html>.
> > > >
> > > > IIRC Dijkstra takes quadratic time in our implementation.
> > >
> > > Yes I did some research on it previously, in particular read the papers by
> > > Thorup and Goldberg that you are referring to below.  Some of the
> > > algorithms you mention are not applicable to our case which is non-planar
> > > graph with non-negative (rather than strictly positive) weights.
> > 
> > Argh... silly me, only now that you mentioned it i noticed the graph has
> > edges that cross. I had noticed that Thorup's paper was only for positive
> > weights, i put it mostly as reference, hence why i placed the link to the
> > planar graph algorithm first (which seemingly doesn't apply here either,
> > doh!).
> > 
> > > Besides AFAIU the current implementation _is_ linear, at least in the
> > > sense that Thorup's algorithm is linear (his discovery was that you can
> > > pile nodes into a bucket list even though your weights are not integers --
> > > this is already done in the current warmap).  My own empirical discovery
> > > was that if in our case you go for priority queue (log(n) time) rather
> > > than for bucket list (constant time) you get a speed-up: the bucket list
> > > is too expensive to set up for the small $n$ we usually get.
> > 
> > Hmmm... Ok. So on your optimization you use a heap instead? (log(n) time
> > suggests some tree structure).
> > 
> > Did you benchmark it after several runs? Glancing at it it seems to me
> > that it only does those nasty mallocs() once, afterwards memory is fetched
> > from a pool.
> 
> Since Dresden got flooded yesterday and I lost the internet I have
> also done some research. Results are: most of the algorithms derive
> from Dijkstra's algorithm and differ in the way the unfinished-nodes
> are managed. You can use:
> 
> n - number of nodes = number of tiles
> m - number of edges (roughly 4*n)
> c - largest cost of edge (2^8-1 in server/gotohand.c, planned to be
>     2^32-1 in the new path finding)
> 
>  - a list which you search for the minimum: gives O(n^2) = 4000k
>  - a bucket list (current server/gotohand.c) also known as Dial's
>  algorithm: O(m+n*c) = 518k
>  - a 2-heap: as in path_finding13.diff: gives O(m*ldn+2*n*ldn) = 132k
>  - a radix heap: O(m+n*ld(n*c)) = 46k
>  - a fibonacci heap: O(m+n*logn) = 23k
> 
> All of these should be taken with a grain of salt since out n is at
> most 2000 and so the (unknown) constant factors may be more important.
> 
> Profiling the server/gotohand.c shows that <10% of the time is spend
> in add_to_mapqueue and get_from_mapqueue. It is even less for
> path_finding13.diff. Most of the time is used not for the path finding
> per se but the information gathering: can a unit move to this tile
> (zoc, attack enemy, ground_unit_transporter_capacity), how much would
> this move cost (map_get_terrain,...) and misc (like can I see the
> target tile). So more can be achieved by caching these values like
> ptile->move_cost does.
> 
> I haven't looked at non-Dijkstra algorithms like Thorup's. But even if
> this algorithm can be applied on our problem the big question is the
> constant factor.

But Thorup is Dijkstra!  His algorithm is essentially on how to split 
costs into bucket AFAIR.