[FreecivDev] Re: Warmap
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
On Thu, Aug 15, 2002 at 10:17:41AM +0100, Gregory Berkolaiko wrote:
> 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.
From http://citeseer.nj.nec.com/meyer01singlesource.html:
Nearly all of these algorithms are based on Dijkstra's algorithm and
improve the priority queue data structure. Thorup has given the
first ... His approac applies labelsetting but significantly
deviates from Dijkstra's algorithm in that it does not visit the
nodes in order of increasing distance from ....
Raimar

email: rf13@xxxxxxxxxxxxxxxxx
"Any sufficiently advanced technology is indistinguishable from magic."
 Arthur C. Clarke

