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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Mon, Apr 15, 2002 at 04:44:25PM +0100, Gregory Berkolaiko wrote:
> 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.

Can we return both the total_moves_expended values and the turns?

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

Fixed in version 6 (which you will answer in 15 minutes) ;).

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

Fixed in version 6 using the moves_left in addition to x and y.

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

Can you explain it to me if it is 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.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  "With a PC, I always felt limited by the software available.
   On Unix, I am limited by my knowledge."
    -- Peter J. Schoenster <pschon@xxxxxxxxxxxxxxxxx>