[Freeciv-Dev] Re: (PR#7169) Path finding modification

["Raimar Falke" <i-freeciv-lists@xxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7169 >

On Sun, Jan 11, 2004 at 12:57:48PM -0800, Gregory Berkolaiko wrote:
> 
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=7169 >
> 
> > [i-freeciv-lists@xxxxxxxxxxxxx - Sat Jan 10 12:54:32 2004]:
> > 
> > On Sun, Dec 28, 2003 at 01:47:15PM -0800, Arnstein Lindgard wrote:
> > > 
> > > <URL: http://rt.freeciv.org/Ticket/Display.html?id=7169 >
> > > 
> > > I want to propose a modification to the path finding module:
> > > 
> > > I think I want to change the boolean "is_dangerous" into a bitvector
> > > that indicates which turns the tile is dangerous on. The "turn" is
> > > like the relative turn in "pf_position->turn". When all bits are set,
> > > the tile is always dangerous, as with triremes and non-coastal tiles.
> > > 
> > > I could use this to good effect for the Battlegroups patch, where
> > > many gotos are planned at the same time, for a group of units.
> > > 
> > > Already, the path finding's concept of dangerous tiles, in
> > > combination with the ability to "wait" (opting to not expend all
> > > movement points, while retaining the goto state) is very useful for
> > > anti-stacking group movement. In fact, it makes army groups of
> > > Musketeers work like it was intended to in the war client.
> > > 
> > > However, I currently mark all tiles that any unit intends to end it's
> > > turn on, as "dangerous", regardless of _which_ turn. This causes the
> > > group to become paranoid, believing that most of the tiles are
> > > dangerous all the time. Members will make artful manouvers, detours
> > > to avoid wrongly percieved dangerous tiles.
> > > 
> > > When horsing around with large battlegroups, I get this error a lot:
> > > 
> > > civclient: path_finding.c:740: create_danger_segment: Assertion
> > > `!pf_map->d_lattice[index].is_dangerous' failed.
> > > 
> > > and it looks like the reason is that too many tiles are dangerous.
> > > (It is the nature of battlegroups to concentrate in a small area.)
> > > This could also be a stand alone bug.
> > > 
> > > The path finding is quite complex, but I think I could make the
> > > modification without actually groking the Dijkstra system.
> > > 
> > > Maybe an alternative solution is to pass the is_pos_dangerous()
> > > callback information about the current node, by expanding the
> > > pf_parameter. Maybe it's also neccessary to turn off the caching? I'm
> > > also not sure if this would be a violation of the author's (Gregory?
> > > I guess he's away now) idea of a clean module - not allowing the user
> > > to read internal variables.
> > > 
> > > Any ideas?
> > 
> > A change from 
> >   bool (*is_pos_dangerous) (int x, int y, enum known_type,
> >                             struct pf_parameter * param);
> > to
> >   bool (*is_pos_dangerous) (int x, int y, enum known_type,
> >                             struct pf_parameter * param,
> >                         int turn);
> > and adding a
> >   bool is_pos_dangerous_return_values_depend_on_turn;
> > to struct pf_parameter is ok for me.
> > 
> > How this is internally handled is another question. And if this turn
> > depended values are cached and it what form is another question.
> > 
> > Also possible are two callbacks (the current is untouched and one with
> > "turn" is added). This will remove the need for the extra bool option.
> 
> I agree with Raimar.  The first way is preferable I think.
> The second doesn't need an extra bool at a higher cost to code readability.
> 
> However, I must warn Arnstein from trying to achive perfection.  I think
> you are heading in the direction of code so complicated that it won't
> ever be debugged.  I could be wrong though.

So who will code it?

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Microsoft DNS service terminates abnormally when it recieves a response
  to a DNS query that was never made.
  Fix Information: Run your DNS service on a different platform."
    -- MS service information on bugtraq