[freeciv-ai] Re: [Freeciv-Dev] (PR#6293) pf iterator design woes

["Raimar Falke" <i-freeciv-lists@xxxxxxxxxxxxx>]

On Fri, Sep 26, 2003 at 01:12:19AM -0700, Per I. Mathisen wrote:
> 
> My surprise was great when I discovered that pf does not, in fact, have a
> reusable iterator. In order to start over again with a pf iterator, you
> need to throw away the previous pf map and make a new one. What a waste!
> 
> I spoke about this with Raimar and Greg on irc, and the solution they
> suggested was a cache wrapper around the iterator written outside of pf.
> They didn't want it in the pf code because pf was already getting too
> complex...
> 
> As I started looking at how to fix this, the first thing I realized was
> that implementing it outside pf is impossible. We need to wrap every call
> to pf_next() to feed the cache, and since pf_get_position() calls
> pf_next(), we need to put at least part of the code for such a cache
> inside pf_next(). The good news is that the code for this cache can be
> written in about 20 lines and when used (it is optional) it consumes max
> 10kb memory for large maps.

> However, eventually another problem dawned on me. Every call that we make
> to pf_get_position() inside an iterator that looks further ahead than the
> iterator, is going to make the iterator skip ahead to this position!

> Yes, this misfeature is documented

Hehe ;)

> , but I only now realized what this really meant: We cannot look
> further ahead than the current iterator position without generating
> a second pf map. This means that great care must be taken while
> programming such iterators to avoid bugs, and also that there are a
> number of things they simply cannot do, which is not obvious at
> first. I am worried that this behaviour is going to lead to some
> very hard to find bugs.

The reason for this is that the PF was design for two different usage
cases: 
 - you know the goal and want to get a path and
 - you don't know the goal and you iterate till you find the goal

Mixing these two for one map is possible but not encouraged. I would
even go this far to disable it i.e. after your first call to
pf_get_position you can't use pf_next and the other way around.

> Say you pf_next() for a short-term attack target, and then find something
> that looks promising, but before you make this decision, you just want to
> know how far you are from your long-term target. Calling pf_get_position()
> on this long-term target will likely screw up the iterator. So you must
> create a second pf map to find this information. This is bug prone and
> slow.

If this is _really needed_ (please think hard about it) we have to
redesign the PF code. However for this you first have to describe the
semantics you want.

> So I think this design needs to be revised. pf_next() needs to be split
> into a public interface which is not affected by pf_get_position() and
> which can be reset, and a pf_next() that is used internally for building
> out the pf map.

You want that pf_next and pf_get_position are independent?!

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I heard if you play the NT-4.0-CD backwards, you get a satanic message."
 "That's nothing, if you play it forward, it installs NT-4.0"