[Freeciv-Dev] Re: (PR#4004) A canvas_iterate macro for mapview

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

Gregory Berkolaiko wrote:
> On Tue, 15 Apr 2003, Jason Short wrote:

>>2.  We need to catch all tiles that overlap the area.  Even in non-iso 
>>view you need to consider the case where (x0,y0) does not mark a tile 
>>origin.  In iso-view it becomes quite a bit more complicated since the 
>>tiles are aligned isometrically, and you need to account for the extra 
>>UNIT_TILE_HEIGHT area (which is one reason why having a draw_type 
>>parameter would be helpful - to allow the users to filter out unwanted 
>>tiles).
> 
> 
> I drew a couple of iso example on a piece of paper and I think that
> "catching all tiles that overlap" can produce rather strange shapes.  I
> think "all tiles whose centers are in the rectangle" is both nicer 
> visually and easier to implement.

Yes, it certainly does give some strange shapes.  Unfortunately just 
catching those with centers in the rectangle is not too helpful in most 
cases, although a wrapper could be used to get all cases.

The core problem is that in iso view, the origin of the canvas rectangle 
may fall within any of 4 different cases:

         XX
       XX  XX
     XX 1  2 XX
   XX          XX
     XX 3  4 XX
       XX  XX
         XX

this figure shows the tile that covers the rectangle origin.

If the origin is at point 1 then the top-left corner of the rectangle 
looks like:

      X X
     * X     where * is the origin tile.
    X X X
     X X

in case 2 it becomes:

    X X
   * X X
    X X
   X X X

in case 3 it is

    * X
   X X X
    X X
   X X X

and in case 4

   * X X
    X X
   X X X
    X X

similarly there are 4 different cases for each of the 4 corners, for a 
total of 16 possible cases.

For the loop to know all this is no good.  Even in the above cases, case 
2 and 3 differs from cases 3 and 4 because the origin of the iteration 
is on a half-tile, not a tile.  This means the compression code used to 
get native GUI coordinates would have to be different for an exact loop.

In my ugly-but-efficient implementation, I simply expand the rectangle 
of iteration sufficiently so that a simple loop can be used - basically 
taking a bounding box of all the above cases.  Then I filter out the few 
border cases that we actually don't want to find.  This filtering isn't 
full since it only checks the bounding box of the tile to see if it 
overlaps (so case 1 will have an extra tile in the loop).

Looking further, it's actually difficult to tell what parts of the tile 
we're concerned about overlapping.  An isometric tile looks something like:

   XXXXXXXXXXXXXX
   X            X
   X     4      X
   XXXXXXXXXXXXXX
   X 3 XX  XX 3 X
   X XX      XX X
   XX     1    XX
   X XX      XX X
   X 2 XX  XX 2 X
   XXXXXXXXXXXXXX

where area 1 is the base tile, area 2 may be used for units (and maybe 
other graphics?), area 3 is used for "3d terrain" and units (and maybe 
others), and area 4 is used only for units (but will eventually be used 
for 3d terrain).  Any particular canvas_iterate loop will want to find 
all tiles whose "active areas" overlap the canvas rectangle.

- For show_city_descriptions, the active area is 1+2+3.
- For update_map_canvas_visible, the active area would be 1+2+3+4.
- For a drag-to-select-units feature, the active area would be 1+2+3+4.
- For a drag-to-select-tiles feature, the active area would be 1.

My only real conclusion is that this problem is hard.  But I _really_ 
don't want these iteration loops to be duplicated throughout the code - 
a poor/ugly implementation of canvas_iterate would be better than that 
(at least it hides the ugliness).

jason