[Freeciv-Dev] Re: PATCH: rand_pos function and usage (PR#1017)

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 11:12 AM 01/10/24 +0200, Raimar Falke wrote:
>On Tue, Oct 23, 2001 at 03:10:53PM -0400, Jason Dorje Short wrote:
>> Raimar Falke wrote:
>> > If I see this example I vote for an action part in the
>> > RAND_POS_CHECKED macro. It is silly to accumulate positions and than
>> > do a for loop over them. So it should possible to pass a
>> > "make_forest(x, y, hmap(x, y), 25)" to the RAND_POS_CHECKED
>> > macro. This would also save us the malloc/free.
>> 
>> Yes, it would.  It would also allow other random position generation (like
>> making huts) to use this macro.

Again, most of the time the constraints on positions to randomize mean
that this approach is useless or unwieldy. You need a constraint function
to check, and a process function if the check succeeds.

It is usually simpler to just leave the logic in the code flow the way
it is, and not try to invert it in wierd ways to get the rand() function
extracted.

>> At this point, though, we see a descrepancy between the "random" method and
>> the "structured" method of choosing positions, since the random method may
>> happily choose the same position twice. 

The problem is not just choosing it twice. If you have two rows of the map
you are selecting to add a "polar" feature, then in a normal 80x50 map your
general rand function is going to be successful 4% of the time, or you need
to make 25 calls on average to find a value. The filtered approach will find
any number of values in 160 calls, or it wins if for more than 7 elements.

If you are adding deserts into 6 rows of the map, where land is typically
1/3 and grassland 1/3 of this, then your rand function will be successful
2/3% of the time or on average once in evey 133 calls. Note that you are
calling rand() and check_constraints() each time before getting to the 
process_action() functions in each cycle using your interface.

 ... while preselecting "efficiently" loops in that it only does the 
T_GRASSLAND check, and does not do a function call to any rand() routine
unless it hits an actual value. So it will likely only do 480/9 or 54 rand()
calls plus some significantly faster iteration overhead to find these 54
cases and produce a randomly ordered list for the process_function.

And again, you find any number of values for the filtered approach in the
same constant time.

Now ask youself what your RAND_POS method is costing to find 5% desert and
25% forest in 30% land of a 80x50. This is 60 desert or 300 forest at the
probabilities above for finding a single tile.

Also ask yourself what happens when you run out of deserts in the above
example. Can you say spin, spin, spin ... ?

Are you both sufficiently embarassed in adding yet another O(n) algorithm
to Freeciv to drop this misguided over-generalization nonsense yet, and get
back to practical reality :-?

>> If we have an action element to the
>> loop as well, it will have to be done within both the random and structured
>> algorithms; it will no longer be possible to discard all the
randomly-chosen
>> points if we move to a structured algorithm.  
>
>> So, it would make more sense IMO to separate these algorithms.
>
>Ok as long as the interface it the same or similar.
>
>       Raimar
>-- 
> email: rf13@xxxxxxxxxxxxxxxxx
>  reality.sys corrupt. Reboot Universe? (y,n,q)

Cheers,
RossW
=====