[freeciv-ai] Re: autoexplorers

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Tue, Jul 02, 2002 at 08:56:20PM +0200, Per I Mathisen wrote:
> On Tue, 2 Jul 2002, Gregory Berkolaiko wrote:
> > > discover huts (since there are distributes equally you have to
> > > maximize your uncovered tiles/turn) and to explore the surroundings to
> > > find good city spots. The current eXplorer mode doesn't meet the last
> > > task.
> >
> > Well, there are some tasks that you cannot trust to anyone, let alone
> > computer.  I won't waste my time trying to come up with an explorer mode
> > which is perfect for all tastes, just because it will involve so many
> > parameters that noone will ever use it.
> 
> Ah, but Raimar has got a point.
> 
> The current explorer mode is very bad at uncovering tiles for city
> settling. It is, however, rather good at finding enemies. Those, I think,
> are the two only modes of exploration that are needed.
> 
> Of course, then there is scooping up huts and empty cities, but that is
> something common to both modes.
> 
> We will want client-side autoexplorers, which means moving it into
> client/ai/common/.  This shouldn't present a big problem once the new
> pathfinding interface is in. User clients should use the old mode always,
> as this works fine as is.
> 
> On Tue, 2 Jul 2002, Raimar Falke wrote:
> > It really is quite easy. You just have to circle one point (the
> > capital for example or the center of known tiles at this island).
> 
> Hah. It is not easy.
> 
> Yes, in order to use the "explore greatest possible compact area" mode
> (for settling) you need a reference point. As opposed to the "explore the
> greatest possible amount of space" mode (for finding your enemy).
> 
> But, you will need to look at the terrain to avoid walking needlessly over
> mountains when you could save a lot of time going around. That's one
> warmap (or whatever you guys call it now). It is also needed for hut and
> empty city finding.
> 
> Then you need to keep in mind that what we are really concerned with here,
> isn't the number of tiles from your reference point and to the fogged
> tile, but the move cost for your settler to go somewhere. So it makes a
> lot less sense to explore a huge mountain range than to explore flat land
> or follow rivers. So you need another warmap from the reference point and
> outwards.
> 
> The best tile to explore is then something like (cost of warmap1)+(cost of
> warmap2).
> 
> Now, the case is quite different when it comes to sea exploration. Since
> the ocean is topographically flat, we don't need a warmap there, for
> either mode. In the first mode, we should circle the continent. In the
> second, we should just do as we do now. So we may want to separate the
> land and ocean autoexploration functions, since they have very different
> needs.
> 
> I did start rewriting the existing autoexplore in this direction, but
> didn't get too far, partly because you can't overlap two warmaps in the
> existing implementation.

The auto explorer mode can be coded easy:
 m=create_map
 while pos=get_next_pos(m):
   if pos.turn>THRESHOLD:
     return path to pos

So you create the shortest path of a minimum length (to get a larger
horizon and avoid getting stuck in some area). Now the complicated
part is the cost function. It should:
 - give uncovered tiles a bonus (larger if the tile has lower distance
 to the center) (you can do this linear or quadratic or whatever)
 - give huts a bonus (fixed one)
 - give undefended cities a bonus if the user wants this

All these bonuses are returned as extra cost (EC) but this isn't a
problem. So in terms of the path_finding interface you would end up
with: COP = EC

So you see with the new path_finding in the tree it is little work to
code a new Exploring Agent.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  The trick is to keep breathing.