[Freeciv-Dev] Re: [PATCH] aiunit.c ai_manage_explorer cleanup (PR#1210)

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

At 04:24 AM 02/01/08 -0800, Raahul Kumar wrote:
>
>--- Petr Baudis <pasky@xxxxxxxxxxx> wrote: > 

>> -  /* BEGIN PART TWO: Move into unexplored territory */
>> -  /* move the unit as long as moving will unveil unknown territory */
>> +  /* 
>> +   * PART 2: Move into unexplored territory
>> +   * Move the unit as long as moving will unveil unknown territory
>> +   */
>> +  
>>    while (punit->moves_left) {
>> +    /* Best (highest) number of unknown tiles adjectent (in vision
range) */
>>      int most_unknown = 0;
>> -    int unknown;
>> +    /* Desired destination */
>> +    int best_x = -1, best_y = -1;
>>  
>> -    /* evaluate all adjacent tiles */
>> +    /* Evaluate all adjacent tiles. */
>> +    
>
>Someone posted an algorithm to the mailing list, showing that moving in a zig
>zag pattern was the best way to explore mostly uncovered territory.

Actually, that is not quite right although it is the way it was explained.

If you move forward in a cartesian direction you see 3 new tiles per move.
If you move diagonally you see 5, except when you do a right angle turn
you only see 4.

So the optimum move pattern between any two points is the diagonal move 
with the fewest turns, which often looks like a zigzag.

But for pure exploring, i.e. unconstrained by endpoint, straightline 
diagonals are clearly best.

It is usually worth asking why, i.e. doing a simple analysis, on some of
these urban myths before committing them to code :-).

>__________________________________________________
>Do You Yahoo!?
>Send FREE video emails in Yahoo! Mail!
>http://promo.yahoo.com/videomail/

Cheers,
RossW
=====