[FreecivDev] Re: Warmap
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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.
Raimar

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

