[Freeciv-Dev] Re: Warmap

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Life is too short for reboots."