# different regions, different lists

This topic is 4164 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi I have a rts-map with round about 640 000 tiles (800x800) divided into naibourhoods. A hood can be for example x=400; y=322; w=200; h=250; defining one courner and the width and height (in tiles). All tiles in the world belongs to a certain hood (and only one hood), and as a unit stands on a tile, he must know what hood that tile belongs to. What is the fastest way to do this? Of course i could (each time a unit moves) go through a list of all hoods and find the corresponding one, but this seemes pretty brutish to me (i will have lots and lots of units wandering about). I could do this check more seldom but that would some ticks go before realizing he has entered a new hood. Thanks! Erik

##### Share on other sites
how bout making each hood have a list of neighboring hoods, and then the process of cycling through hoods would be much shorter

##### Share on other sites
Well if your hoods are not regularly spaced then it is a bit difficult, but can definitely be improved from standard brute force methods.

You could add a cache to each of your units (if you can afford the extra memory) as follows.

The basic algorithm is this:
1.) Test whether the unit is still in the last known region. If yes, early exit.
2.) Test whether the unit is in a neighbour of the last known region. If yes, update the cache and early exit.
3.) Brute force test against all regions, update the cache and exit.

CRegion *FindRegion(CUnit *pUnit){  int i;  // unit is still in the same region  if (pUnit->pCacheRegion->ContainsTile(pUnit->TileX, pUnit->TileY))  {    return pUnit->pCacheRegion;  }  // otherwise check the regions neighbours only  for (i = 0; i < pUnit->pCacheRegion->NumNeighbours; i++)  {    if (pUnit->pCacheRegion->apNeighbour->ContainsTile(pUnit->TileX, pUnit->TileY))    {      // update the cache for next time      pUnit->pCacheRegion = pUnit->pCacheRegion->apNeighbour;      return pUnit->pCacheRegion;    }  }  // otherwise as a last resort brute force it. (Should only happen if units     // can skip from one region to another without having to pass through     // neighbouring regions (eg. a teleporting unit)  for (i = 0; i < NumWorldRegions; i++)  {    if (WorldRegionList->ContainsTile(pUnit->TileX, pUnit->TileY))    {      // update the cache for next time      pUnit->pCacheRegion = WorldRegionList;      return pUnit->pCacheRegion;    }  }  return NULL;}

An important thing to note is that you probably want to NULL the pCacheRegion member on each unit upon initialization/creation of the unit - or have it copied from the pCacheRegion of the building that created the unit

Hope this helps...

##### Share on other sites
thanks. seems useful
Erik