[Freeciv-Dev] Re: [RFC] Path finding interface

[Jason Short <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

Raimar Falke wrote:
> On Mon, Apr 08, 2002 at 10:09:03AM +0200, Raimar Falke wrote:
>
> > On Mon, Apr 08, 2002 at 09:08:43AM +0200, Raimar Falke wrote:
> >
> > > Attached is my proposal to a unified path finding core. Although the
> > > parameter list contains 14 elements I would call this interface
> > > minimal and clean. It may be extended for performance reasons and if I
> > > forgot something which can't be expressed with the callbacks.
> > >
> > > Also possible is the replacement of the static allocation of the
> > > positions with a dynamic approach.
> > It turns out that the interface wasn't minimal. Diff and version 2
> > attached.
>
> To allow city warmaps the interface was changed to allow the full
> specification of all movement parameters. Diff and version 3 attached.
My understanding is that this path finding interface is to replace the 
existing warmap code, correct?  "Path finding" isn't a very good name, 
but as you point out "warmap" isn't either.
As long as we're developing a new interface, we should consider the 
underlying system itself.  The warmap system was a simple 
implementation, but the authors learned something from it.  From 
server/gotohand.c (above really_generate_warmap):
/***************************************************************
  [....]
This function is used by the AI in various cases when it is searching 
for something to do with a unit. Maybe we could make a version that 
processed the tiles in order after how many moves it took the unit to 
get to them, and then gave them to the unit. This would achive 2 things:
-The unit could stop the function the instant it found what it was 
looking for, or when it had already found something reasonably close and 
the distance to the tiles later being searched was reasoable big. In 
both cases avoiding to build the full warmap.
-The warmap would avoid examining a tile multiple times due to a series 
of path with succesively smaller cost, since we would always have the 
smallest possible cost the first time.
This would be done by inserting the tiles in a list after their 
move_cost as they were found.
****************************************************************/

A system like this makes fundamental sense to me, for several reasons:

- Under Dijikstra's algorithm, it should not increase the overhead of 
the search at all.  For a generic example, what matter if we do:
  generate_warmap(...);
  some_map_iterate(x, y) {
    check_position_xy_for_something(x, y);
  } some_map_iterate_end;

versus

  init_warqueue(...);
  do {
    pos = warqueue_pop();
    check_position_xy_for_something(pos->x, pos->y);
  while (position_is_relevant(pos));

?

- An optimized AI may be able to short-circuit the logic, like the 
comment says.  A good example is in find_nearest_friendly_port() in 
aiunit.c, where the code can simply stop once it has found the nearest 
friendly port [1].

The only drawback I can see to such a system is that it makes automatic 
caching of the warmap at the backend more difficult.  That, and it will 
require substantial changes to the AI code, but you're going to get that 
already.
With some thought, it might be possible to provide an interface that 
allows both a warmap and a warqueue to be generated, and caches them 
simultaneously.
[1] What's up with that code?  It divides the move cost by 3 for ports 
with port (buildings) in them?  Seems to me like the cur /= 3 should be 
more like cur -= 2 * punit->type->move_rate.  But I guess it doesn't 
much matter, since retreating to port doesn't work correctly anyway.
jason