[FreecivDev] Re: Warmap
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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 singlesource 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 nonplanar
> > > graph with nonnegative (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 speedup: 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 unfinishednodes
> 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^81 in server/gotohand.c, planned to be
> 2^321 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 2heap: 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 nonDijkstra 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.

