[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Wed, Jun 26, 2002 at 06:14:52PM +0100, Gregory Berkolaiko wrote:
> On Wed, 26 Jun 2002, Raimar Falke wrote:
> 
> > On Wed, Jun 26, 2002 at 04:27:33PM +0100, Gregory Berkolaiko wrote:
> > > 
> > > I'll send you the whole profile, but here is the most important bit with 
> > > my comments:
> > > 
> > > -----------------------------------------------
> > >                 4.91    8.77 3212784/3212784     time_path_finding [1]
> > > [3]     58.5    4.91    8.77 3212784         pf_iterate_map [3]
> > >                 4.21    0.00 3212784/3212784     pf_get_from_queue [4]
> > >                 1.42    0.00 7798194/7798194     adjust_cost [8]
> > >                 1.02    0.00 12257730/12257730     normal_move_unit [10]
> > >                 0.62    0.00 25702272/25726248     get_xy_from_x_and_y 
> > > [13]
> > >                 0.51    0.00 12257730/12257730     server_get_known [14]
> > >                 0.51    0.00 3188808/3188808     pf_add_to_queue [15]
> > >                 0.34    0.00 3188808/3188808     get_x_from_xy [16]
> > >                 0.14    0.00 3188808/3188808     get_y_from_xy [19]
> > > 
> > > get_from_queue is quite a surprise to me.
> > > I'll look into it.
> > 
> > > adjust_cost is also quite surprising -- it changes the cost
> > > according to the Turn Mode.  It should be inlined.
> > 
> > Is it called with TM_NONE or with another value?
> 
> TM_MAXIMUM it was

How much will it go down if you use TM_NONE?

> > > normal_move_unit is the move_cost callback
> > > server_get_known is is_known callback
> > 
> > > get_*_from_* are (x,y) <-> xy converters.  They can be optimized by 
> > > setting MAX_[XY]SIZE to a power of 2.
> > 
> > Just treat the x and y values as two 16 bit values and pack them into
> > a 32 bit value.
> 
> It is used as an offset into the lattice.

Ahh.

> So to minimize memory usage it would be better to use map.xsize and 
> map.ysize, but for speed it's better to use some predefined powers of 2 I 
> think.

So you just have to choose two constants and ensure that
PRIVATE_[XY]SIZE >= MAX_[XY]SIZE.

> > > What do you mean by 3 existing implementations?
> > > Clinet-side, warmap and find_the_shortest_path?
> > 
> > Server, client and (not included yet) agents.
> > 
> > > I am not so eager to replace warmap completely.  It can still be trusted 
> > > with some dumb cases where any reasonable approximation will do.
> > 
> > But I need an implementation for the agents.
> 
> So the new implementation is going to serve agents, client-side and arcane 
> AI cases, while the majority of AI cases will be handled by 
> generate_warmap until they could be also optimized away.

This is the plan.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  "Windows is the one true OS. MS invented the GUI. MS invented 
   the 32 bit OS. MS is open and standard. MS loves you. We have 
   always been at war with Oceana."