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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Wed, Jun 05, 2002 at 06:36:01PM +0100, Gregory Berkolaiko wrote:
> On Wed, 5 Jun 2002, Raimar Falke wrote:
> 
> > On Wed, Jun 05, 2002 at 06:04:29PM +0100, Gregory Berkolaiko wrote:
> > > On Wed, 5 Jun 2002, Raimar Falke wrote:
> > > 
> > > > On Wed, Jun 05, 2002 at 04:36:09PM +0100, Gregory Berkolaiko wrote:
> > > > > BMCs are provided as call-backs.  Once we've identified all necessary 
> > > > > BMCs 
> > > > > and done some performance tests, they can be hard-wired inside the 
> > > > > main 
> > > > > loop.
> > > > > 
> > > > > pf_parameter is not used.  And I don't really see a point in using 
> > > > > it: 
> > > > > user'd have to allocate it, fill it in, give it to map initialization 
> > > > > routine for processing, which seems a waste of time.  Just give the 
> > > > > map 
> > > > > initializator the unit or, if you are doing something exotic, full 
> > > > > details.  An intermediate case (unit_type + initial_position) can 
> > > > > also be 
> > > > > done.
> > > > 
> > > > The path_finding must be able to cope with virtual units. This is one
> > > > of the reason for pf_parameter. From the move_type you can also deduce
> > > > the BMC type.
> > > 
> > > Of course.  But to use pf_parameter, the user has to set 5 (!) parameters
> > > relating to the type of the unit.  To cope with virtual units it is easier
> > > to have a wrapper which you supply with the unit_type and the initial
> > > positions, which I already mentioned above.
> > 
> > The base version should use pf_parameter. There may be a wrapper which
> > get punit and uses the base version.
> 
> Why so categorically, "should use"?  Why not pass all the parameters as 
> the arguments?  Where is the advantage in having a spoof data structure 
> which is never used?
> 
> You are probably right, but please give reasons.

The struct is faster because you can reuse the struct and only have to
change certain fields. Well this isn't such a big argument.

enum unit_move_result test_unit_move_to_tile(Unit_Type_id type,
                                             struct player *unit_owner,
                                             enum unit_activity activity,
                                             bool connecting, int src_x,
                                             int src_y, int dest_x,
                                             int dest_y, bool igzoc);

has 9 arguments. Version 10's pf_parameter contains 17 fields. Can you
expect how messy this will be? However we are far from the limits:

C99:

       5.2.4.1  Translation limits

       [#1] The implementation  shall  be  able  to  translate  and
       execute  at  least  one  program  that contains at least one
       instance of every one of the following limits:13
...
          - 127 parameters in one function definition

          - 127 arguments in one function call

          - 127 parameters in one macro definition

          - 127 arguments in one macro invocation

The struct can also be better commented.

> > > > > Lifting the paths from a ready map is not implemented.  That 
> > > > > shouldn't be 
> > > > > a problem though.
> > > > > 
> > > > > The definition of the best path is simplified.  We can include more 
> > > > > information, but I don't yet see any examples which are both doable 
> > > > > and 
> > > > > useful.
> > > > > 
> > > > > As a working example I include a patch to ai_manage_explorer.  It 
> > > > > becomes 
> > > > > trireme-safe, but the drawback is that triremes lack imagination 
> > > > > (_always_ 
> > > > > keep to the shore). 
> > > > > 
> > > > > Files:
> > > > > path_finding10.[ch]  --- to go into server/ although they should 
> > > > > really 
> > > > >                        migrate to client
> > > > > dynamic_pf.diff --- patch to manage_explorer against today's CVS, 
> > > > > assumes 
> > > > >                        path_finding10.[ch] are in server/
> > > > 
> > > > Extra cost doesn't have to fit into a char. You have no ZOC handling.
> > > 
> > > You can increase the extra cost limit.  But that will increase the size 
> > > of 
> > > the bucket list...
> > > 
> > > I will write an alternative implementation with a priority queue instead 
> > > of the bucket list --- there you can have any extra cost.
> > 
> > > ZOC, yes, I forgot about it.  It can be done via (maybe even 
> > > user-supplied) function is_enemy_zoc(int x, int y, struct player).
> > 
> > I though we have agreed that user supplied zoc checking is useless?!
> 
> Let me think again (I actually don't remember ever thinking about it, I 
> think it was you arguing with yourself and then reaching an agreement with 
> yourself.  I was too afraid to interfere ;)...

;)

You didn't object so I took this as an agreement ;)

> Some goto-related code uses a rather esoteric function goto_zoc_ok...
> 
> There is no need to have an end-user-specified function, but maybe some
> service code could specify it.  It really depends if we want to convert
> find_the_shortest_path to use PF module.  That'd be a messy job though.

You will see that the zoc function can be splitted and cached
nicely. So the zoc function is rather ditributed in the code (at least
in my code).

I won't force people to change code in ai/ to use the new interface.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Make it idiot-proof and someone will make a better idiot."