ClosestBuildSite problem

[Tournesol]

I notised this problem with ClosestBuildSite:
Its searchRadius parameter appears to only give a search radius of sqrt(searchRadius / 64) * 16.

Code: Select all

float3 CAICallback::ClosestBuildSite(const UnitDef* unitdef,float3 pos,float searchRadius,int minDist)
{
	CFeature* feature;
	int allyteam=gs->AllyTeam(team);

	int endr = (int)(searchRadius / (SQUARE_SIZE*2));
	const vector<SearchOffset>& ofs = GetSearchOffsetTable (endr);

	for(int so=0;so<endr;so++) {
		float x = pos.x+ofs[so].dx*SQUARE_SIZE*2;
		float z = pos.z+ofs[so].dy*SQUARE_SIZE*2;
		float3 p(x,0,z);
		p = helper->Pos2BuildPos (p, unitdef);
		if(uh->TestUnitBuildSquare(p,unitdef,feature) && (!feature || feature->allyteam!=allyteam))
		{
			int xs=(int)(x/SQUARE_SIZE);
			int zs=(int)(z/SQUARE_SIZE);
			bool good=true;
			for(int z2=max(0,zs-unitdef->ysize/2-minDist);z2<min(gs->mapy,zs+unitdef->ysize+minDist);++z2){
				for(int x2=max(0,xs-unitdef->xsize/2-minDist);x2<min(gs->mapx,xs+unitdef->xsize+minDist);++x2){
					CSolidObject* so=readmap->groundBlockingObjectMap[z2*gs->mapx+x2];
					if(so && so->immobile && !dynamic_cast<CFeature*>(so)){
						good=false;
						break;
					}
				}
			}
			if(good) 
				return p;
		}
	}

	return float3(-1.0f,0.0f,0.0f);	
}

Showing what happens with searchRadius = 10000:

int endr = (int)(searchRadius / (SQUARE_SIZE*2)); // endr = 625 (SQUARE_SIZE is 8 )

const vector<SearchOffset>& ofs = GetSearchOffsetTable (endr); // Make a vector with sorted offsets (625*625*4 = 1.562.500, its cached for later use)

for(int so=0;so<endr;so++) { // Iterate over the first 625 offsets, and not the last 1.5 million

Testing only the first 625 offsets will have almost the same effect as what a searchRadius of 200 was intended to have.
The runtime is very bad too, a correct version will get something like O(searchRadius^2 * (buildingSizeX + minDist) * (buildingSizeY + minDist)). Its posible to change this to O(searchRadius^2 + (buildingSizeX + minDist) * (buildingSizeY + minDist)) with some smart programing.

Fixing this might have some sideeffects with the current use of searchRadius in CBS however

[AF]

If you do modify it try allowing us to shove in a functor for custom blocking maps, so say we want it work as it currently does, but to avoid these points too that represent say mex spots, the inside of a factory, and untis (for untis buildign units).