[Freeciv-Dev] Re: [RFC] Move cost map interface

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sat, 13 Apr 2002, Raimar Falke wrote:

> On Fri, Apr 12, 2002 at 02:13:02PM +0100, Gregory Berkolaiko wrote:
> > On Thu, 11 Apr 2002, Raimar Falke wrote:
> > 
> > > On Thu, Apr 11, 2002 at 05:14:23PM +0100, Gregory Berkolaiko wrote:
> > > > I think there are only 4 issues remaining:
> > > > 1. Calculating # of turns.
> > > > 2. Returning path with every new location (aka performance killa)
> > > > 3. Taking into account possibility of waiting.
> > > > 4. Special type of map "city map".
> > 
> > > I'm also for (a) with the extention to have a "int turns[3];" in the
> > > result. Which is calculated is controlled by ORing NTM_s together.
> > 
> > yes (with a correction: turns are computable from total_moves_expended, 
> > therefore int total_moves_expended[NTM_LAST])
> 
> Why should the user do the final division? Does a user want the
> total_moves_expended values?

/me is putting on his AI-developer hat
Yes.  Why should I bother with initial_moves_left, turns and moves left, 
when I just want to exstimate the distance.  Besides you put the division 
into a function, not leave it upto user.

> > > > And I object vehemently to the attitude "let's ignore performance 
> > > > issues 
> > > > now and later we'll see".
> > > 
> > > We already have the method to calculate the path: pf_get_path_from_map.
> > 
> > I want a non-destructive one too
> 
> So we may add as a comment:
> 
>  A computed position is a position which is returned by
>  pf_get_next_path_from_map.
> 
> And change
>  * The next best path is written in the given struct pf_path. Caller
>  * should test path->found_a_valid. Behavior is undefined after
>  * pf_get_path_from_map was called.
> to
>  * The next best path is written in the given struct pf_path. Caller
>  * should test path->found_a_valid. Behavior is undefined after
>  * pf_get_path_from_map was called with a non-computed position.

this sort of thing.
but I would still prefer two functions (as done in my .h file)

> > > Problem: (x,y) does _NOT_ exactly describe a path. Because there is
> > > "(4,5) with 1 moves left" and (4,5) and waited a turn and now 3 moves
> > > left". But I agree that from a performance point of view the path is
> > > unneeded. Solution? Adding an result moves_left to pf_get_next_path
> > > and also moves_left as a parameter to pf_get_path_from_map?
> > 
> > if you waited a turn it's going to count on your total_moves_expended, 
> > which is returned together with your next destination (or accessible using 
> > your next destination)
> > if you want to be at your final destination with full points, come there 
> > using the shortest path and wait a turn.  It should be user responsibility 
> > to ensure that the destination is safe (if it's an attack goto, first find 
> > a safe place for the seige camp next to the city).
> 
> You misunderstood. We want to change
>  void pf_get_next_path_from_map(pf_map_t map, struct pf_path *path);
> into
>  void pf_get_next_path_from_map(pf_map_t map, int *dest_x, int *dest_y);
> 
> for performance reasons. However we also want to get the patch which
> would let us travel to (dest_x, dest_y). We can get this path from
> pf_get_path_from_map. pf_get_path_from_map takes (dest_x, dest_y) and
> returns the path. 
> 
> Problem is that (dest_x, dest_y) doesn't identify the path
> exactly. Example:
>  unit is at A with moves_left=2. A is a safe position. B is adjacent
>  to A and it costs 1 move point. So both "unit at A with moves_left=2
>  at turn N" and "unit at A with moves_left=move_rate at turn N+1" are
>  "pushed". If you now call pf_get_next_path_from_map multiple times it
>  will return two time the position of B. But the first time the
>  position is rather a "unit at B with moves_left=1 at turn N" and the
>  second time it is "unit at B with moves_left=move_rate-1 at turn
>  N+1". However pf_get_path_from_map can't distinguish them only based
>  on the position.

I think the second path won't be returned at all, but let me think some 
more about it...

> > > > 4. Special "city map" type is the cheapest way to have a map 
> > > > incorporating 
> > > > information usable by all types of units.  If we choose to do away with 
> > > > it, 
> > > > we'd face the necessity of calculating 4 maps per city: for units with 
> > > > speed 1, 2, 3 and IGTER units.  What happens if someone starts hacking 
> > > > rulesets is sad to visualize.  I think that "city map" is an acceptable 
> > > > estimation for AI use.  In really serious cases (in such case the unit 
> > > > type will be known) AI can make another map for this particular unit.  
> > > > "Non-exact" is not synonymous with "useless".
> > > 
> > > Can you please explain to me the properties of a city_map? What costs
> > > does it calculate?
> > 
> > average distance to/from the city.
> 
> > for more concrete numbers have a look at the really_generate_warmap
> 
> I wanted to avoid this ;) Ok lets see:
>  - there is no pcity depending code in really_generate_warmap
>  - in generate_warmap warcity is set but no code depends on it
>  - so it looks like if punit==NULL these lines get executed in
>  generate_warmap
>     really_generate_warmap(pcity, NULL, LAND_MOVING);
>     really_generate_warmap(pcity, NULL, SEA_MOVING);

you missed some code:
341         else { /* we have a city */
342           int tmp = map_get_tile(x1, y1)->move_cost[DIR_REVERSE(dir)];
343           move_cost = (ptile->move_cost[dir] + tmp +
344                        (ptile->move_cost[dir] > tmp ? 1 : 0))/2;
345         }

I am not sure what the ternary operator in line 344 is doing, but the rest 
is kind of obvious.


> 
> So you generate two maps (.cost and .seacost) in one warmap. This is
> just from the interface very ugly. It can be easily simulate this with
> two seperate maps. With no extra costs. Only drawback I can see is
> that the two iterators for the maps aren't synchron:
>  the land map may yield the costs 1,2,5,9,20
>  the sea map may yield the costs 1,2,3,4,5,6,7
> So if you want increasing costs the user have to do some extra logic
> to choose the iterator. I don't know in which way the current AI uses
> the two maps.
> 
> Summary: there will be no city map.

We can still split city-map into three (to-city-land, from-city-land, 
city-sea) or even more (depending on the move_rates), but it will be quite 
a work.

G.