Sign in to follow this  
suliman

different regions, different lists

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 this post


Link to post
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 this post


Link to post
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[i]->ContainsTile(pUnit->TileX, pUnit->TileY))
{
// update the cache for next time
pUnit->pCacheRegion = pUnit->pCacheRegion->apNeighbour[i];
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[i]->ContainsTile(pUnit->TileX, pUnit->TileY))
{
// update the cache for next time
pUnit->pCacheRegion = WorldRegionList[i];
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this