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

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxx>]

<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.

G.