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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 10 Apr 2002, Jason Short wrote:

> Raimar Falke wrote:
> 
> 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 below comment belongs to the pre-priorityqueue implementation of the 
warmap and should be discarded.

And implementing the above is the reason I am interested in all this 
business.  I submitted a patch implementing this a while ago, but it was 
built on top of gotohand.c and was therefore rather messy.  Now we are 
trying to do it from scratch.

> -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));
> 
> ?

I suspect the second would have higher function call overhead but if 
position_is_relevant is well implemented, it will still save a lot of 
time.

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

yes.  But I once turned the caching off and didn't get any performance 
change: most of the caching is built in the usage of warmap.

also the map generated by things like friendly port is unlikely to be 
recycled.


Raimar: I am not so sure that you get_path and get_next_path functions 
have the same function as my iterators.  I think they are principally 
different.

G.