[Freeciv-Dev] Re: freeciv2 kernel,modules and rulesets

[Andrew Sutton <ansutton@xxxxxxx>]

On Monday 03 December 2001 08:05 am, Julian Rüth wrote:
> Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> writes:
> >  1) current situation: deref a pointer of the tile and go trough the
> >  short (<7) list; costs 4 bytes per tile
> >  2) proposed solution: go through all units (this can be hundreds) and
> >  select the units you want; costs 0 bytes per tile

dear god no! give me some credit ;)

> >
> > We can afford these 4 bytes per tile. Max size is 200x100 ==
> > 200*100*4=80k.
> >     Raimar
>
> I don't think this is a real problem. Just put all the units in some kind
> of tree (ordered by x and y positions) so it costs only something like
> O(lgn). Jule

closer... i was thinking of a map that stored some informatic structure about 
the tile. it could be keyed on the x,y coordinate of the tile. if nothing's 
on the tile, there's no associated key in the map. it's a constant time 
lookup and hashtables _are_ built for sparsely populated arrays :)

andy