Complete.Org: Mailing Lists: Archives: freeciv-ai: August 2004:
[freeciv-ai] Re: Settler code plans

[freeciv-ai] Re: Settler code plans

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: Per Inge Mathisen <per@xxxxxxxxxxx>
Cc: Freeciv AI development <freeciv-ai@xxxxxxxxxxx>
Subject: [freeciv-ai] Re: Settler code plans
From: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxxx>
Date: Mon, 2 Aug 2004 12:03:25 -0500 (CDT)

On Sun, 1 Aug 2004, Per Inge Mathisen wrote:

> You may have noticed (or probably not) that progress on the new settlers
> code has been very slow. The reason for this is mostly that I am having
> gnawing doubts about its design. While the patch as it is performs
> considerably better than the current code, is much more readable, and is
> somewhat more generalized, it is slower and is certainly not generalized
> enough.
> Most fatally, it has an implicit assumption in favour of smallpox. This is
> vital for speed, and improves results - for the current rules.
> But I do not have time to write a replacement at this time. So I can
> commit the code as it stands, or let it wait. It is not code that will not
> suffer much from bitrot.
> In any case, here is my plan for another design of the AI settlers code:
> On game start, analyze the map. Create a genlist of struct
> wanted_city_spots { x, y, want }. When we consider building a settler or
> consider where to send one, we find the closest spot on the same continent
> and the closest spot anywhere, find the wants to settle those two, and use
> the higher one to compare to other build targets.

I don't like this idea much.  It's inflexible and too dependent on
omniscience.  I had a different concept for the future AI settling.

But first about whether to commit your current patch.

I think pretty much any design will include the following layers:
1. Estimating how good a tile is
2. Estimating how good a spot is (taking into account surrounding tiles)
3. Estimating the want for settlers
4. Finding spots for settlers to settle

Various proposals will differ only in how they recombine (and cache)
components 1 and 2 to produce results for 3 and 4.

So I think your patch should be committed just because it makes 1 and 2
transparent and reusable.

Now about speedup.  I think (I am guessing) the main CPU burn happens when
each city tries to answer question 3.  I suspect existing settlers don't
take nearly as much time (in particular because you make them remember
where they are going and not recompute it every turn).  So to speed things
up we need a better scheme for part 3.

I propose to run a single PF iteration with multiple start points to
select top N city spots (N is not large, around 3).  We can cache the
locations of these spots for several turns.  Then, starting from each spot
we backtrack PF search to find the most qualified city to build the

I would rather first commit your code and then experiment with this idea.


[Prev in Thread] Current Thread [Next in Thread]