code:
#include "common.h"

#include "General.h"
#include "Building.h"
#include "Treadable.h"
#include "Train.h"
#include "Pools.h"
#include "Timer.h"
#include "Camera.h"
#include "World.h"
#include "FileMgr.h"
#include "ZoneCull.h"
#include "Zones.h"

#include "Debug.h"
#include "Renderer.h"

int32     CCullZones::NumCullZones;
CCullZone CCullZones::aZones[NUMCULLZONES];
int32     CCullZones::NumAttributeZones;
CAttributeZone CCullZones::aAttributeZones[NUMATTRIBZONES];
uint16    CCullZones::aIndices[NUMZONEINDICES];
int16     CCullZones::aPointersToBigBuildingsForBuildings[NUMBUILDINGS];
int16     CCullZones::aPointersToBigBuildingsForTreadables[NUMTREADABLES];

int32 CCullZones::CurrentWantedLevelDrop_Player;
int32 CCullZones::CurrentFlags_Camera;
int32 CCullZones::CurrentFlags_Player;
int32 CCullZones::OldCullZone;
int32 CCullZones::EntityIndicesUsed;
bool CCullZones::bCurrentSubwayIsInvisible;
bool CCullZones::bCullZonesDisabled;

#define NUMUNCOMPRESSED (6000)
#define NUMTEMPINDICES (140000)

void
CCullZones::Init(void)
{
	int i;

	NumAttributeZones = 0;
	CurrentWantedLevelDrop_Player = 0;
	CurrentFlags_Camera = 0;
	CurrentFlags_Player = 0;
	bCurrentSubwayIsInvisible = false;
	NumCullZones = 0;
	OldCullZone = -1;
	EntityIndicesUsed = 0;

	for(i = 0; i < NUMBUILDINGS; i++)
		aPointersToBigBuildingsForBuildings[i] = -1;
	for(i = 0; i < NUMTREADABLES; i++)
		aPointersToBigBuildingsForTreadables[i] = -1;
}

uint16* pTempArrayIndices;
int TempEntityIndicesUsed;

void
CCullZones::ResolveVisibilities(void)
{
	int fd;

	CFileMgr::SetDir("");
	fd = CFileMgr::OpenFile("DATA\\cullzone.dat", "rb");
	if(fd > 0){
		CFileMgr::Read(fd, (char*)&NumCullZones, sizeof(NumCullZones));
		CFileMgr::Read(fd, (char*)aZones, sizeof(aZones));
		CFileMgr::Read(fd, (char*)&NumAttributeZones, sizeof(NumAttributeZones));
		CFileMgr::Read(fd, (char*)aAttributeZones, sizeof(aAttributeZones));
		CFileMgr::Read(fd, (char*)aIndices, sizeof(aIndices));
		CFileMgr::Read(fd, (char*)aPointersToBigBuildingsForBuildings, sizeof(aPointersToBigBuildingsForBuildings));
		CFileMgr::Read(fd, (char*)aPointersToBigBuildingsForTreadables, sizeof(aPointersToBigBuildingsForTreadables));
		CFileMgr::CloseFile(fd);
	}else{
#ifndef MASTER
		EntityIndicesUsed = 0;
		BuildListForBigBuildings();
		pTempArrayIndices = new uint16[NUMTEMPINDICES];
		TempEntityIndicesUsed = 0;

//		if(!LoadTempFile())	// not in final game
		{
			for (int i = 0; i < NumCullZones; i++) {
//printf("testing zone %d (%d indices)\n", i, TempEntityIndicesUsed);
				DoVisibilityTestCullZone(i, true);
			}

//			SaveTempFile();	// not in final game
		}

		CompressIndicesArray();
		delete[] pTempArrayIndices;
		pTempArrayIndices = nil;

		fd = CFileMgr::OpenFileForWriting("data\\cullzone.dat");
		if (fd != 0) {
			CFileMgr::Write(fd, (char*)&NumCullZones, sizeof(NumCullZones));
			CFileMgr::Write(fd, (char*)aZones, sizeof(aZones));
			CFileMgr::Write(fd, (char*)&NumAttributeZones, sizeof(NumAttributeZones));
			CFileMgr::Write(fd, (char*)&aAttributeZones, sizeof(aAttributeZones));
			CFileMgr::Write(fd, (char*)&aIndices, sizeof(aIndices));
			CFileMgr::Write(fd, (char*)&aPointersToBigBuildingsForBuildings, sizeof(aPointersToBigBuildingsForBuildings));
			CFileMgr::Write(fd, (char*)&aPointersToBigBuildingsForTreadables, sizeof(aPointersToBigBuildingsForTreadables));
			CFileMgr::CloseFile(fd);
		}
#endif
	}
}

bool
CCullZones::LoadTempFile(void)
{
	int fd = CFileMgr::OpenFile("cullzone.tmp");
	if (fd != 0) {
		CFileMgr::Read(fd, (char*)&NumCullZones, sizeof(NumCullZones));
		CFileMgr::Read(fd, (char*)aZones, sizeof(aZones));
		CFileMgr::Read(fd, (char*)&NumAttributeZones, sizeof(NumAttributeZones));
		CFileMgr::Read(fd, (char*)&aAttributeZones, sizeof(aAttributeZones));
		CFileMgr::Read(fd, (char*)pTempArrayIndices, NUMTEMPINDICES*sizeof(uint16));
		CFileMgr::Read(fd, (char*)&TempEntityIndicesUsed, sizeof(TempEntityIndicesUsed));
		CFileMgr::Read(fd, (char*)&aPointersToBigBuildingsForBuildings, sizeof(aPointersToBigBuildingsForBuildings));
		CFileMgr::Read(fd, (char*)&aPointersToBigBuildingsForTreadables, sizeof(aPointersToBigBuildingsForTreadables));
		CFileMgr::CloseFile(fd);
		return true;
	}
	return false;
}

void
CCullZones::SaveTempFile(void)
{
	int fd = CFileMgr::OpenFileForWriting("cullzone.tmp");
	if (fd != 0) {
		CFileMgr::Write(fd, (char*)&NumCullZones, sizeof(NumCullZones));
		CFileMgr::Write(fd, (char*)aZones, sizeof(aZones));
		CFileMgr::Write(fd, (char*)&NumAttributeZones, sizeof(NumAttributeZones));
		CFileMgr::Write(fd, (char*)&aAttributeZones, sizeof(aAttributeZones));
		CFileMgr::Write(fd, (char*)pTempArrayIndices, NUMTEMPINDICES*sizeof(uint16));
		CFileMgr::Write(fd, (char*)&TempEntityIndicesUsed, sizeof(TempEntityIndicesUsed));
		CFileMgr::Write(fd, (char*)&aPointersToBigBuildingsForBuildings, sizeof(aPointersToBigBuildingsForBuildings));
		CFileMgr::Write(fd, (char*)&aPointersToBigBuildingsForTreadables, sizeof(aPointersToBigBuildingsForTreadables));
		CFileMgr::CloseFile(fd);
	}
}

void
CCullZones::BuildListForBigBuildings()
{
	for (int i = CPools::GetBuildingPool()->GetSize()-1; i >= 0; i--) {
		CBuilding *building = CPools::GetBuildingPool()->GetSlot(i);
		if (building == nil || !building->bIsBIGBuilding) continue;
		CSimpleModelInfo *nonlod = ((CSimpleModelInfo *)CModelInfo::GetModelInfo(building->GetModelIndex()))->GetRelatedModel();
		if (nonlod == nil) continue;

		for (int j = CPools::GetBuildingPool()->GetSize()-1; j >= 0; j--) {
			CBuilding *building2 = CPools::GetBuildingPool()->GetSlot(j);
			if (building2 == nil || building2->bIsBIGBuilding) continue;
			if (CModelInfo::GetModelInfo(building2->GetModelIndex()) == nonlod) {
				if ((building2->GetPosition() - building->GetPosition()).Magnitude() < 5.0f) {
					aPointersToBigBuildingsForBuildings[j] = i;
				}
			}
		}

		for (int j = CPools::GetTreadablePool()->GetSize()-1; j >= 0; j--) {
			CTreadable *treadable = CPools::GetTreadablePool()->GetSlot(j);
			if (treadable == nil || treadable->bIsBIGBuilding) continue;
			if (CModelInfo::GetModelInfo(treadable->GetModelIndex()) == nonlod) {
				if ((treadable->GetPosition() - building->GetPosition()).Magnitude() < 5.0f) {
					aPointersToBigBuildingsForTreadables[j] = i;
				}
			}
		}
	}
}

void
CCullZones::DoVisibilityTestCullZone(int zoneId, bool findIndices)
{
	aZones[zoneId].m_groupIndexCount[0] = 0;
	aZones[zoneId].m_groupIndexCount[1] = 0;
	aZones[zoneId].m_groupIndexCount[2] = 0;
	aZones[zoneId].m_indexStart = TempEntityIndicesUsed;
	aZones[zoneId].FindTestPoints();

	if (!findIndices) return;

	for (int i = CPools::GetBuildingPool()->GetSize() - 1; i >= 0; i--) {
		CBuilding *building = CPools::GetBuildingPool()->GetSlot(i);
		if (building != nil && !building->bIsBIGBuilding && aZones[zoneId].IsEntityCloseEnoughToZone(building, aPointersToBigBuildingsForBuildings[i] != -1)) {
			CBuilding *LODbuilding = nil;
			if (aPointersToBigBuildingsForBuildings[i] != -1)
				LODbuilding = CPools::GetBuildingPool()->GetSlot(aPointersToBigBuildingsForBuildings[i]);

			if (!aZones[zoneId].TestEntityVisibilityFromCullZone(building, 0.0f, LODbuilding)) {
				assert(TempEntityIndicesUsed < NUMTEMPINDICES);
				pTempArrayIndices[TempEntityIndicesUsed++] = i;
				aZones[zoneId].m_groupIndexCount[0]++;
			}
		}
	}

	for (int i = CPools::GetTreadablePool()->GetSize() - 1; i >= 0; i--) {
		CBuilding* building = CPools::GetTreadablePool()->GetSlot(i);
		if (building != nil && aZones[zoneId].IsEntityCloseEnoughToZone(building, aPointersToBigBuildingsForTreadables[i] != -1)) {
			CBuilding *LODbuilding = nil;
			if (aPointersToBigBuildingsForTreadables[i] != -1)
				LODbuilding = CPools::GetBuildingPool()->GetSlot(aPointersToBigBuildingsForTreadables[i]);

			if (!aZones[zoneId].TestEntityVisibilityFromCullZone(building, 10.0f, LODbuilding)) {
				assert(TempEntityIndicesUsed < NUMTEMPINDICES);
				pTempArrayIndices[TempEntityIndicesUsed++] = i;
				aZones[zoneId].m_groupIndexCount[1]++;
			}
		}
	}

	for (int i = CPools::GetTreadablePool()->GetSize() - 1; i >= 0; i--) {
		CBuilding *building = CPools::GetTreadablePool()->GetSlot(i);
		if (building != nil && aZones[zoneId].CalcDistToCullZoneSquared(building->GetPosition().x, building->GetPosition().y) < SQR(200.0f)) {
			int start = aZones[zoneId].m_groupIndexCount[0] + aZones[zoneId].m_indexStart;
			int end = aZones[zoneId].m_groupIndexCount[1] + start;

			bool alreadyAdded = false;

			for (int k = start; k < end; k++) {
#ifdef FIX_BUGS
				if (pTempArrayIndices[k] == i)
#else
				if (aIndices[k] == i)
#endif
					alreadyAdded = true;
			}

			if (!alreadyAdded) {
				CBuilding *LODbuilding = nil;
				if (aPointersToBigBuildingsForTreadables[i] != -1)
					LODbuilding = CPools::GetBuildingPool()->GetSlot(aPointersToBigBuildingsForTreadables[i]);
				if (!aZones[zoneId].TestEntityVisibilityFromCullZone(building, 0.0f, LODbuilding)) {
					assert(TempEntityIndicesUsed < NUMTEMPINDICES);
					pTempArrayIndices[TempEntityIndicesUsed++] = i;
					aZones[zoneId].m_groupIndexCount[2]++;
				}
			}
		}
	}
}

void
CCullZones::Update(void)
{
	bool invisible;

	if(bCullZonesDisabled)
		return;

	switch(CTimer::GetFrameCounter() & 7){
	case 0:
	case 4:
		/* Update Cull zone */
		ForceCullZoneCoors(TheCamera.GetGameCamPosition());
		break;

	case 2:
		/* Update camera attributes */
		CurrentFlags_Camera = FindAttributesForCoors(TheCamera.GetGameCamPosition(), nil);
		invisible = (CurrentFlags_Camera & ATTRZONE_SUBWAYVISIBLE) == 0;
		if(invisible != bCurrentSubwayIsInvisible){
			MarkSubwayAsInvisible(!invisible);
			bCurrentSubwayIsInvisible = invisible;
		}
		break;

	case 6:
		/* Update player attributes */
		CurrentFlags_Player = FindAttributesForCoors(FindPlayerCoors(),
			&CurrentWantedLevelDrop_Player);
		break;
	}
}

void
CCullZones::ForceCullZoneCoors(CVector coors)
{
	int32 z;
	z = FindCullZoneForCoors(coors);
	if(z != OldCullZone){
		if(OldCullZone >= 0)
			aZones[OldCullZone].DoStuffLeavingZone();
		if(z >= 0)
			aZones[z].DoStuffEnteringZone();
		OldCullZone = z;
	}
}

int32
CCullZones::FindCullZoneForCoors(CVector coors)
{
	int i;

	for(i = 0; i < NumCullZones; i++)
		if(coors.x >= aZones[i].minx && coors.x <= aZones[i].maxx &&
		   coors.y >= aZones[i].miny && coors.y <= aZones[i].maxy &&
		   coors.z >= aZones[i].minz && coors.z <= aZones[i].maxz)
			return i;
	return -1;
}

int32
CCullZones::FindAttributesForCoors(CVector coors, int32 *wantedLevel)
{
	int i;
	int32 attribs;

	if (wantedLevel)
		*wantedLevel = 0;
	attribs = 0;
	for(i = 0; i < NumAttributeZones; i++)
		if(coors.x >= aAttributeZones[i].minx && coors.x <= aAttributeZones[i].maxx &&
		   coors.y >= aAttributeZones[i].miny && coors.y <= aAttributeZones[i].maxy &&
		   coors.z >= aAttributeZones[i].minz && coors.z <= aAttributeZones[i].maxz){
			attribs |= aAttributeZones[i].attributes;
			if(wantedLevel)
				*wantedLevel = Max(*wantedLevel, aAttributeZones[i].wantedLevel);
		}
	return attribs;
}

CAttributeZone*
CCullZones::FindZoneWithStairsAttributeForPlayer(void)
{
	int i;
	CVector coors;

	coors = FindPlayerCoors();
	for(i = 0; i < NumAttributeZones; i++)
		if(aAttributeZones[i].attributes & ATTRZONE_STAIRS &&
		   coors.x >= aAttributeZones[i].minx && coors.x <= aAttributeZones[i].maxx &&
		   coors.y >= aAttributeZones[i].miny && coors.y <= aAttributeZones[i].maxy &&
		   coors.z >= aAttributeZones[i].minz && coors.z <= aAttributeZones[i].maxz)
			return &aAttributeZones[i];
	return nil;
}

void
CCullZones::MarkSubwayAsInvisible(bool visible)
{
	int i, n;
	CEntity *e;
	CVehicle *v;

	n = CPools::GetBuildingPool()->GetSize()-1;
	for(i = n; i >= 0; i--){
		e = CPools::GetBuildingPool()->GetSlot(i);
		if(e && e->bIsSubway)
			e->bIsVisible = visible;
	}

	n = CPools::GetTreadablePool()->GetSize()-1;
	for(i = n; i >= 0; i--){
		e = CPools::GetTreadablePool()->GetSlot(i);
		if(e && e->bIsSubway)
			e->bIsVisible = visible;
	}

	n = CPools::GetVehiclePool()->GetSize()-1;
	for(i = n; i >= 0; i--){
		v = CPools::GetVehiclePool()->GetSlot(i);
		if(v && v->IsTrain() && ((CTrain*)v)->m_nTrackId != TRACK_ELTRAIN)
			v->bIsVisible = visible;
	}
}

void
CCullZones::AddCullZone(CVector const &position,
                        float minx, float maxx,
                        float miny, float maxy,
                        float minz, float maxz,
                        uint16 flag, int16 wantedLevel)
{
	CCullZone *cull;
	CAttributeZone *attrib;

	CVector v;
	if((flag & ATTRZONE_NOTCULLZONE) == 0){
		cull = &aZones[NumCullZones++];
		v = position;
		// reposition start point to the start/end of the
		// alley next to the big building in the industrial district.
		// probably isn't analyzed correctly otherwise?s
		if((v-CVector(1032.14f, -624.255f, 24.93f)).Magnitude() < 1.0f)
			v = CVector(1061.7f, -613.0f, 19.0f);
		if((v-CVector(1029.48f, -495.757f, 21.98f)).Magnitude() < 1.0f)
			v = CVector(1061.4f, -506.0f, 18.5f);
		cull->position.x = Clamp(v.x, minx, maxx);
		cull->position.y = Clamp(v.y, miny, maxy);
		cull->position.z = Clamp(v.z, minz, maxz);
		cull->minx = minx;
		cull->maxx = maxx;
		cull->miny = miny;
		cull->maxy = maxy;
		cull->minz = minz;
		cull->maxz = maxz;
		cull->m_groupIndexCount[0] = 0;
		cull->m_groupIndexCount[1] = 0;
		cull->m_groupIndexCount[2] = 0;
		cull->m_indexStart = 0;
	}
	if(flag & ~ATTRZONE_NOTCULLZONE){
		attrib = &aAttributeZones[NumAttributeZones++];
		attrib->minx = minx;
		attrib->maxx = maxx;
		attrib->miny = miny;
		attrib->maxy = maxy;
		attrib->minz = minz;
		attrib->maxz = maxz;
		attrib->attributes = flag;
		attrib->wantedLevel = wantedLevel;
	}
}

uint16 *pExtraArrayIndices;

void
CCullZones::CompressIndicesArray()
{
	uint16 set[3];

	// These are used to hold the compressed groups in sets of 3
	int numExtraIndices = 0;
	pExtraArrayIndices = new uint16[NUMTEMPINDICES];

	for(int numOccurrences = 6; numOccurrences > 1; numOccurrences--){
		if(NumCullZones == 0)
			break;

//printf("checking occurrences %d\n", numOccurrences);
		int attempt = 0;
		while(attempt < 10000){
			for(;;){
				attempt++;

				int zone = CGeneral::GetRandomNumber() % NumCullZones;
				int group = CGeneral::GetRandomNumber() % 3;
				if(!PickRandomSetForGroup(zone, group, set))
					break;
				if(!DoWeHaveMoreThanXOccurencesOfSet(numOccurrences, set))
					break;

				// add this set
				attempt = 1;
				int setId = numExtraIndices + NUMUNCOMPRESSED;
				pExtraArrayIndices[numExtraIndices++] = set[0];
				pExtraArrayIndices[numExtraIndices++] = set[1];
				pExtraArrayIndices[numExtraIndices++] = set[2];
				ReplaceSetForAllGroups(set, setId);
			}
		}
	}

	TidyUpAndMergeLists(pExtraArrayIndices, numExtraIndices);

	delete[] pExtraArrayIndices;
}

// Get three random indices for this group of a zone
bool
CCullZones::PickRandomSetForGroup(int32 zone, int32 group, uint16 *set)
{
	int32 start;
	int32 size;

	aZones[zone].GetGroupStartAndSize(group, start, size);
	if(size <= 0)
		return false;

	int numIndices = 0;
	for(int i = 0; i < size; i++)
		if(pTempArrayIndices[start + i] != 0xFFFF)
			numIndices++;
	if(numIndices < 3)
		return false;

	int first = CGeneral::GetRandomNumber() % (numIndices-2);

	numIndices = 0;
	int n = 0;
	for(int i = 0; i < size; i++)
		if(pTempArrayIndices[start + i] != 0xFFFF){
			if(n++ < first) continue;

			set[numIndices++] = pTempArrayIndices[start + i];
			if(numIndices == 3)
				break;
		}
	return true;
}

bool
CCullZones::DoWeHaveMoreThanXOccurencesOfSet(int32 count, uint16 *set)
{
	int32 curCount;
	int32 start;
	int32 size;

	curCount = 0;
	for (int i = 0; i < NumCullZones; i++) {
		for (int group = 0; group < 3; group++) {
			aZones[i].GetGroupStartAndSize(group, start, size);
			if(size <= 0) continue;

			// check if the set is a subset of the group
			int n = 0;
			for (int j = 0; j < size; j++) {
				for (int k = 0; k < 3; k++) {
					if (pTempArrayIndices[start+j] == set[k])
						n++;
				}
			}
			// yes it is
			if(n == 3){
				curCount++;
				// check if we have seen this set often enough
				if(curCount >= count)
					return true;
			}
		}
	}
	return false;
}

void
CCullZones::ReplaceSetForAllGroups(uint16 *set, uint16 setid)
{
	int32 start;
	int32 size;

	for(int i = 0; i < NumCullZones; i++)
		for(int group = 0; group < 3; group++){
			aZones[i].GetGroupStartAndSize(group, start, size);
			if(size <= 0) continue;

			// check if the set is a subset of the group
			int n = 0;
			for(int j = 0; j < size; j++){
				for(int k = 0; k < 3; k++){
					if(pTempArrayIndices[start+j] == set[k])
						n++;
				}
			}

			// yes it is, so replace it
			if(n == 3){
				bool insertedSet = false;
				for(int j = 0; j < size; j++){
					for(int k = 0; k < 3; k++){
						// replace first element by set, invalidate others
						if(pTempArrayIndices[start+j] == set[k]){
							if(!insertedSet)
								pTempArrayIndices[start+j] = setid;
							else
								pTempArrayIndices[start+j] = 0xFFFF;
							insertedSet = true;
						}
					}
				}
			}
		}
}

void
CCullZones::TidyUpAndMergeLists(uint16 *extraIndices, int32 numExtraIndices)
{
	int numTempIndices = 0;
	for(int i = 0; i < TempEntityIndicesUsed; i++)
		if(pTempArrayIndices[i] != 0xFFFF)
			numTempIndices++;

	// Fix up zone ranges such that there are no holes
	for(int i = 0; i < NumCullZones; i++){
		int j;
		int start = 0;
		for(j = 0; j < aZones[i].m_indexStart; j++)
			if(pTempArrayIndices[j] != 0xFFFF)
				start++;

		aZones[i].m_indexStart = start;
		aZones[i].m_numBuildings = 0;
		aZones[i].m_numTreadablesPlus10m = 0;
		aZones[i].m_numTreadables = 0;

		for(int k = 0; k < aZones[i].m_groupIndexCount[0]; k++)
			if(pTempArrayIndices[j++] != 0xFFFF)
				aZones[i].m_numBuildings++;
		for(int k = 0; k < aZones[i].m_groupIndexCount[1]; k++)
			if(pTempArrayIndices[j++] != 0xFFFF)
				aZones[i].m_numTreadablesPlus10m++;
		for(int k = 0; k < aZones[i].m_groupIndexCount[2]; k++)
			if(pTempArrayIndices[j++] != 0xFFFF)
				aZones[i].m_numTreadables++;
	}

	// Now copy the actually used indices
	EntityIndicesUsed = 0;
	for(int i = 0; i < TempEntityIndicesUsed; i++)
		if(pTempArrayIndices[i] != 0xFFFF){
			assert(EntityIndicesUsed < NUMZONEINDICES);
			if(pTempArrayIndices[i] < NUMUNCOMPRESSED)
				aIndices[EntityIndicesUsed++] = pTempArrayIndices[i];
			else
				aIndices[EntityIndicesUsed++] = pTempArrayIndices[i] + numTempIndices;
		}
	for(int i = 0; i < numExtraIndices; i++)
		if(extraIndices[i] != 0xFFFF){
			assert(EntityIndicesUsed < NUMZONEINDICES);
			if(extraIndices[i] < NUMUNCOMPRESSED)
				aIndices[EntityIndicesUsed++] = extraIndices[i];
			else
				aIndices[EntityIndicesUsed++] = extraIndices[i] + numTempIndices;
		}
}

void
CCullZone::DoStuffLeavingZone(void)
{
	int i;

	for(i = 0; i < m_numBuildings; i++)
		DoStuffLeavingZone_OneBuilding(CCullZones::aIndices[m_indexStart + i]);
	for(; i < m_numBuildings + m_numTreadablesPlus10m + m_numTreadables ; i++)
		DoStuffLeavingZone_OneTreadableBoth(CCullZones::aIndices[m_indexStart + i]);
}

void
CCullZone::DoStuffLeavingZone_OneBuilding(uint16 i)
{
	int16 bb;
	int j;

	if(i < NUMUNCOMPRESSED){
		CPools::GetBuildingPool()->GetSlot(i)->bZoneCulled = false;
		bb = CCullZones::aPointersToBigBuildingsForBuildings[i];
		if(bb != -1)
			CPools::GetBuildingPool()->GetSlot(bb)->bZoneCulled = false;
	}else{
		i -= NUMUNCOMPRESSED;
		for(j = 0; j < 3; j++)
			DoStuffLeavingZone_OneBuilding(CCullZones::aIndices[i+j]);
	}
}

void
CCullZone::DoStuffLeavingZone_OneTreadableBoth(uint16 i)
{
	int16 bb;
	int j;

	if(i < NUMUNCOMPRESSED){
		CPools::GetTreadablePool()->GetSlot(i)->bZoneCulled = false;
		CPools::GetTreadablePool()->GetSlot(i)->bZoneCulled2 = false;
		bb = CCullZones::aPointersToBigBuildingsForTreadables[i];
		if(bb != -1)
			CPools::GetBuildingPool()->GetSlot(bb)->bZoneCulled = false;
	}else{
		i -= NUMUNCOMPRESSED;
		for(j = 0; j < 3; j++)
			DoStuffLeavingZone_OneTreadableBoth(CCullZones::aIndices[i+j]);
	}
}

void
CCullZone::DoStuffEnteringZone(void)
{
	int i;

	for(i = 0; i < m_numBuildings; i++)
		DoStuffEnteringZone_OneBuilding(CCullZones::aIndices[m_indexStart + i]);
	for(; i < m_numBuildings + m_numTreadablesPlus10m; i++)
		DoStuffEnteringZone_OneTreadablePlus10m(CCullZones::aIndices[m_indexStart + i]);
	for(; i < m_numBuildings + m_numTreadablesPlus10m + m_numTreadables; i++)
		DoStuffEnteringZone_OneTreadable(CCullZones::aIndices[m_indexStart + i]);
}

void
CCullZone::DoStuffEnteringZone_OneBuilding(uint16 i)
{
	int16 bb;
	int j;

	if(i < NUMUNCOMPRESSED){
		CPools::GetBuildingPool()->GetSlot(i)->bZoneCulled = true;
		bb = CCullZones::aPointersToBigBuildingsForBuildings[i];
		if(bb != -1)
			CPools::GetBuildingPool()->GetSlot(bb)->bZoneCulled = true;
	}else{
		i -= NUMUNCOMPRESSED;
		for(j = 0; j < 3; j++)
			DoStuffEnteringZone_OneBuilding(CCullZones::aIndices[i+j]);
	}
}

void
CCullZone::DoStuffEnteringZone_OneTreadablePlus10m(uint16 i)
{
	int16 bb;
	int j;

	if(i < NUMUNCOMPRESSED){
		CPools::GetTreadablePool()->GetSlot(i)->bZoneCulled = true;
		CPools::GetTreadablePool()->GetSlot(i)->bZoneCulled2 = true;
		bb = CCullZones::aPointersToBigBuildingsForTreadables[i];
		if(bb != -1)
			CPools::GetBuildingPool()->GetSlot(bb)->bZoneCulled = true;
	}else{
		i -= NUMUNCOMPRESSED;
		for(j = 0; j < 3; j++)
			DoStuffEnteringZone_OneTreadablePlus10m(CCullZones::aIndices[i+j]);
	}
}

void
CCullZone::DoStuffEnteringZone_OneTreadable(uint16 i)
{
	int16 bb;
	int j;

	if(i < NUMUNCOMPRESSED){
		CPools::GetTreadablePool()->GetSlot(i)->bZoneCulled = true;
		bb = CCullZones::aPointersToBigBuildingsForTreadables[i];
		if(bb != -1)
			CPools::GetBuildingPool()->GetSlot(bb)->bZoneCulled = true;
	}else{
		i -= NUMUNCOMPRESSED;
		for(j = 0; j < 3; j++)
			DoStuffEnteringZone_OneTreadable(CCullZones::aIndices[i+j]);
	}
}

float
CCullZone::CalcDistToCullZoneSquared(float x, float y)
{
	float rx, ry;

	if (x < minx) rx = sq(x - minx);
	else if (x > maxx) rx = sq(x - maxx);
	else rx = 0.0f;

	if (y < miny) ry = sq(y - miny);
	else if (y > maxy) ry = sq(y - maxy);
	else ry = 0.0f;

	return rx + ry;
}

bool
CCullZone::TestLine(CVector vec1, CVector vec2)
{
	CColPoint colPoint;
	CEntity *entity;

	if (CWorld::ProcessLineOfSight(vec1, vec2, colPoint, entity, true, false, false, false, false, true, false))
		return true;
	if (CWorld::ProcessLineOfSight(CVector(vec1.x + 0.05f, vec1.y, vec1.z), CVector(vec2.x + 0.05f, vec2.y, vec2.z), colPoint, entity, true, false, false, false, false, true, false))
		return true;
	if (CWorld::ProcessLineOfSight(CVector(vec1.x - 0.05f, vec1.y, vec1.z), CVector(vec2.x - 0.05f, vec2.y, vec2.z), colPoint, entity, true, false, false, false, false, true, false))
		return true;
	if (CWorld::ProcessLineOfSight(CVector(vec1.x, vec1.y + 0.05f, vec1.z), CVector(vec2.x, vec2.y + 0.05f, vec2.z), colPoint, entity, true, false, false, false, false, true, false))
		return true;
	if (CWorld::ProcessLineOfSight(CVector(vec1.x, vec1.y - 0.05f, vec1.z), CVector(vec2.x, vec2.y - 0.05f, vec2.z), colPoint, entity, true, false, false, false, false, true, false))
		return true;
	if (CWorld::ProcessLineOfSight(CVector(vec1.x, vec1.y, vec1.z + 0.05f), CVector(vec2.x, vec2.y, vec2.z + 0.05f), colPoint, entity, true, false, false, false, false, true, false))
		return true;
	return CWorld::ProcessLineOfSight(CVector(vec1.x, vec1.y, vec1.z - 0.05f), CVector(vec2.x, vec2.y, vec2.z - 0.05f), colPoint, entity, true, false, false, false, false, true, false);
}

bool
CCullZone::DoThoroughLineTest(CVector start, CVector end, CEntity *testEntity)
{
	CColPoint colPoint;
	CEntity *entity;

	if(CWorld::ProcessLineOfSight(start, end, colPoint, entity, true, false, false, false, false, true, false) &&
	   testEntity != entity)
		return false;

	CVector side;
#ifdef FIX_BUGS
	if(start.x != end.x || start.y != end.y)
#else
	if(start.x != end.x && start.y != end.y)
#endif
		side = CVector(0.0f, 0.0f, 1.0f);
	else
		side = CVector(1.0f, 0.0f, 0.0f);
	CVector up = CrossProduct(side, end - start);
	side = CrossProduct(up, end - start);
	side.Normalise();
	up.Normalise();
	side *= 0.1f;
	up *= 0.1f;

	if(CWorld::ProcessLineOfSight(start+side, end+side, colPoint, entity, true, false, false, false, false, true, false) &&
	   testEntity != entity)
		return false;
	if(CWorld::ProcessLineOfSight(start-side, end-side, colPoint, entity, true, false, false, false, false, true, false) &&
	   testEntity != entity)
		return false;
	if(CWorld::ProcessLineOfSight(start+up, end+up, colPoint, entity, true, false, false, false, false, true, false) &&
	   testEntity != entity)
		return false;
	if(CWorld::ProcessLineOfSight(start-up, end-up, colPoint, entity, true, false, false, false, false, true, false) &&
	   testEntity != entity)
		return false;
	return true;
}

bool
CCullZone::IsEntityCloseEnoughToZone(CEntity *entity, bool checkLevel)
{
	const CVector &pos = entity->GetPosition();

	CSimpleModelInfo *minfo = (CSimpleModelInfo*)CModelInfo::GetModelInfo(entity->GetModelIndex());
	float distToZone = CalcDistToCullZone(pos.x, pos.y);
	float lodDist;
	if (minfo->m_noFade)
		lodDist = minfo->GetLargestLodDistance() + STREAM_DISTANCE;
	else
		lodDist = minfo->GetLargestLodDistance() + STREAM_DISTANCE + FADE_DISTANCE;

	if (lodDist > distToZone) return true;
	if (!checkLevel) return false;
	CVector tempPos(minx, miny, minz);
	return CTheZones::GetLevelFromPosition(&pos) == CTheZones::GetLevelFromPosition(&tempPos);
}

bool
CCullZone::PointFallsWithinZone(CVector pos, float radius)
{
	if(minx - radius > pos.x ||
	   maxx + radius < pos.x ||
	   miny - radius > pos.y ||
	   maxy + radius < pos.y ||
	   minz - radius > pos.z ||
	   maxz + radius < pos.z)
		return false;
	return true;
}

CVector ExtraFudgePointsCoors[] = {
	CVector(978.0f, -394.0f, 18.0f),
	CVector(1189.7f, -414.6f, 27.0f),
	CVector(978.8f, -391.0f, 19.0f),
	CVector(1199.0f, -502.3f, 28.0f),
	CVector(1037.0f, -391.9f, 18.4f),
	CVector(1140.0f, -608.7f, 16.0f),
	CVector(1051.0f, -26.0f, 11.0f),
	CVector(951.5f, -345.1f, 12.0f),
	CVector(958.2f, -394.6f, 16.0f),
	CVector(1036.5f, -390.0f, 15.2f),
	CVector(960.6f, -390.5f, 20.9f),
	CVector(1061.0f, -640.6f, 16.3f),
	CVector(1034.5f, -388.96f, 14.78f),
	CVector(1038.4f, -13.98f, 12.2f),
	CVector(1047.2f, -16.7f, 10.6f),
	CVector(1257.9f, -333.3f, 40.0f),
	CVector(885.6f, -424.9f, 17.0f),
	CVector(1127.5f, -795.8f, 17.7f),
	CVector(1133.0f, -716.0f, 19.0f),
	CVector(1125.0f, -694.0f, 18.5f),
	CVector(1125.0f, -670.0f, 16.3f),
	CVector(1051.6f, 36.3f, 17.9f),
	CVector(1054.6f, -11.4f, 15.0f),
	CVector(1058.9f, -278.0f, 15.0f),
	CVector(1059.4f, -261.0f, 10.9f),
	CVector(1051.5f, -638.5f, 16.5f),
	CVector(1058.2f, -643.4f, 15.5f),
	CVector(1058.2f, -643.4f, 18.0f),
	CVector(826.0f, -260.0f, 7.0f),
	CVector(826.0f, -260.0f, 11.0f),
	CVector(833.0f, -603.6f, 16.4f),
	CVector(833.0f, -603.6f, 20.0f),
	CVector(1002.0f, -318.5f, 10.5f),
	CVector(998.0f, -318.0f, 9.8f),
	CVector(1127.0f, -183.0f, 18.1f),
	CVector(1123.0f, -331.5f, 23.8f),
	CVector(1123.8f, -429.0f, 24.0f),
	CVector(1197.0f, -30.0f, 13.7f),
	CVector(1117.5f, -230.0f, 17.3f),
	CVector(1117.5f, -230.0f, 20.0f),
	CVector(1120.0f, -281.6f, 21.5f),
	CVector(1120.0f, -281.6f, 24.0f),
	CVector(1084.5f, -1022.7f, 17.0f),
	CVector(1071.5f, 5.4f, 4.6f),
	CVector(1177.2f, -215.7f, 27.6f),
	CVector(841.6f, -460.0f, 19.7f),
	CVector(874.8f, -456.6f, 16.6f),
	CVector(918.3f, -451.8f, 17.8f),
	CVector(844.0f, -495.7f, 16.7f),
	CVector(842.0f, -493.4f, 21.0f),
	CVector(1433.5f, -774.4f, 16.9f),
	CVector(1051.0f, -205.0f, 7.5f),
	CVector(885.5f, -425.6f, 15.6f),
	CVector(182.6f, -470.4f, 27.8f),
	CVector(132.5f, -930.2f, 29.0f),
	CVector(124.7f, -904.0f, 28.0f),
	CVector(-50.0f, -686.0f, 22.0f),
	CVector(-49.1f, -694.5f, 22.5f),
	CVector(1063.8f, -404.45f, 16.2f),
	CVector(1062.2f, -405.5f, 17.0f)
};
int32 NumTestPoints;
int32 aTestPointsX[100];
int32 aTestPointsY[100];
int32 aTestPointsZ[100];
CVector aTestPoints[100];
int32 ElementsX, ElementsY, ElementsZ;
float StepX, StepY, StepZ;
int32 Memsize;
uint8 *pMem;
#define MEM(x, y, z) pMem[((x)*ElementsY + (y))*ElementsZ + (z)]
#define FLAG_FREE 1
#define FLAG_PROCESSED 2

int32 MinValX, MaxValX;
int32 MinValY, MaxValY;
int32 MinValZ, MaxValZ;
int32 Point1, Point2;
int32 NewPointX, NewPointY, NewPointZ;

void
CCullZone::FindTestPoints()
{
	static int CZNumber;

	NumTestPoints = 0;
	ElementsX = (maxx-minx) < 1.0f ? 2 : (maxx-minx)+1.0f;
	ElementsY = (maxy-miny) < 1.0f ? 2 : (maxy-miny)+1.0f;
	ElementsZ = (maxz-minz) < 1.0f ? 2 : (maxz-minz)+1.0f;
	if(ElementsX > 32) ElementsX = 32;
	if(ElementsY > 32) ElementsY = 32;
	if(ElementsZ > 32) ElementsZ = 32;
	Memsize = ElementsX * ElementsY * ElementsZ;
	StepX = (maxx-minx)/(ElementsX-1);
	StepY = (maxy-miny)/(ElementsY-1);
	StepZ = (maxz-minz)/(ElementsZ-1);

	pMem = new uint8[Memsize];
	memset(pMem, 0, Memsize);

	// indices of center
	int x = ElementsX * (position.x-minx)/(maxx-minx);
	x = Clamp(x, 0, ElementsX-1);
	int y = ElementsY * (position.y-miny)/(maxy-miny);
	y = Clamp(y, 0, ElementsY-1);
	int z = ElementsZ * (position.z-minz)/(maxz-minz);
	z = Clamp(z, 0, ElementsZ-1);

	// Mark which test points inside the zone are not occupied by buildings.
	// To do this, mark the start point as free and do a food fill.

	// NB: we just assume the start position is free here!
	MEM(x, y, z) |= FLAG_FREE;
	aTestPointsX[NumTestPoints] = x;
	aTestPointsY[NumTestPoints] = y;
	aTestPointsZ[NumTestPoints] = z;
	NumTestPoints++;

	bool notDoneYet;
	do{
		notDoneYet = false;
		for(x = 0; x < ElementsX; x++){
			for(y = 0; y < ElementsY; y++){
				for(z = 0; z < ElementsZ; z++){
					if(!(MEM(x, y, z) & FLAG_FREE) || MEM(x, y, z) & FLAG_PROCESSED)
						continue;

					float pX = x*StepX + minx;
					float pY = y*StepY + miny;
					float pZ = z*StepZ + minz;

					if(x > 0 && !(MEM(x-1, y, z) & (FLAG_FREE | FLAG_PROCESSED)) &&
					   !TestLine(CVector(pX, pY, pZ), CVector(pX-StepX, pY, pZ)))
						MEM(x-1, y, z) |= FLAG_FREE;
					if(x < ElementsX-1 && !(MEM(x+1, y, z) & (FLAG_FREE | FLAG_PROCESSED)) &&
					   !TestLine(CVector(pX, pY, pZ), CVector(pX+StepX, pY, pZ)))
						MEM(x+1, y, z) |= FLAG_FREE;

					if(y > 0 && !(MEM(x, y-1, z) & (FLAG_FREE | FLAG_PROCESSED)) &&
					   !TestLine(CVector(pX, pY, pZ), CVector(pX, pY-StepY, pZ)))
						MEM(x, y-1, z) |= FLAG_FREE;
					if(y < ElementsY-1 && !(MEM(x, y+1, z) & (FLAG_FREE | FLAG_PROCESSED)) &&
					   !TestLine(CVector(pX, pY, pZ), CVector(pX, pY+StepY, pZ)))
						MEM(x, y+1, z) |= FLAG_FREE;

					if(z > 0 && !(MEM(x, y, z-1) & (FLAG_FREE | FLAG_PROCESSED)) &&
					   !TestLine(CVector(pX, pY, pZ), CVector(pX, pY, pZ-StepZ)))
						MEM(x, y, z-1) |= FLAG_FREE;
					if(z < ElementsZ-1 && !(MEM(x, y, z+1) & (FLAG_FREE | FLAG_PROCESSED)) &&
					   !TestLine(CVector(pX, pY, pZ), CVector(pX, pY, pZ+StepZ)))
						MEM(x, y, z+1) |= FLAG_FREE;

					notDoneYet = true;
					MEM(x, y, z) |= FLAG_PROCESSED;
				}
			}
		}
	}while(notDoneYet);

	bool done;

	// Find bound planes of free space

	// increase x, bounds in y and z
	x = 0;
	do{
		done = false;
		int minA = 10000;
		int minB = 10000;
		int maxA = -10000;
		int maxB = -10000;
		for(y = 0; y < ElementsY; y++)
			for(z = 0; z < ElementsZ; z++)
				if(MEM(x, y, z) & FLAG_FREE){
					if(y + z < minA){
						minA = y + z;
						aTestPointsX[NumTestPoints] = x;
						aTestPointsY[NumTestPoints] = y;
						aTestPointsZ[NumTestPoints] = z;
					}
					if(y + z > maxA){
						maxA = y + z;
						aTestPointsX[NumTestPoints+1] = x;
						aTestPointsY[NumTestPoints+1] = y;
						aTestPointsZ[NumTestPoints+1] = z;
					}
					if(y - z < minB){
						minB = y - z;
						aTestPointsX[NumTestPoints+2] = x;
						aTestPointsY[NumTestPoints+2] = y;
						aTestPointsZ[NumTestPoints+2] = z;
					}
					if(y - z > maxB){
						maxB = y - z;
						aTestPointsX[NumTestPoints+3] = x;
						aTestPointsY[NumTestPoints+3] = y;
						aTestPointsZ[NumTestPoints+3] = z;
					}
					done = true;
				}
		x++;
	}while(!done);
	NumTestPoints += 4;

	// decrease x, bounds in y and z
	x = ElementsX-1;
	do{
		done = false;
		int minA = 10000;
		int minB = 10000;
		int maxA = -10000;
		int maxB = -10000;
		for(y = 0; y < ElementsY; y++)
			for(z = 0; z < ElementsZ; z++)
				if(MEM(x, y, z) & FLAG_FREE){
					if(y + z < minA){
						minA = y + z;
						aTestPointsX[NumTestPoints] = x;
						aTestPointsY[NumTestPoints] = y;
						aTestPointsZ[NumTestPoints] = z;
					}
					if(y + z > maxA){
						maxA = y + z;
						aTestPointsX[NumTestPoints+1] = x;
						aTestPointsY[NumTestPoints+1] = y;
						aTestPointsZ[NumTestPoints+1] = z;
					}
					if(y - z < minB){
						minB = y - z;
						aTestPointsX[NumTestPoints+2] = x;
						aTestPointsY[NumTestPoints+2] = y;
						aTestPointsZ[NumTestPoints+2] = z;
					}
					if(y - z > maxB){
						maxB = y - z;
						aTestPointsX[NumTestPoints+3] = x;
						aTestPointsY[NumTestPoints+3] = y;
						aTestPointsZ[NumTestPoints+3] = z;
					}
					done = true;
				}
		x--;
	}while(!done);
	NumTestPoints += 4;

	// increase y, bounds in x and z
	y = 0;
	do{
		done = false;
		int minA = 10000;
		int minB = 10000;
		int maxA = -10000;
		int maxB = -10000;
		for(x = 0; x < ElementsX; x++)
			for(z = 0; z < ElementsZ; z++)
				if(MEM(x, y, z) & FLAG_FREE){
					if(x + z < minA){
						minA = x + z;
						aTestPointsX[NumTestPoints] = x;
						aTestPointsY[NumTestPoints] = y;
						aTestPointsZ[NumTestPoints] = z;
					}
					if(x + z > maxA){
						maxA = x + z;
						aTestPointsX[NumTestPoints+1] = x;
						aTestPointsY[NumTestPoints+1] = y;
						aTestPointsZ[NumTestPoints+1] = z;
					}
					if(x - z < minB){
						minB = x - z;
						aTestPointsX[NumTestPoints+2] = x;
						aTestPointsY[NumTestPoints+2] = y;
						aTestPointsZ[NumTestPoints+2] = z;
					}
					if(x - z > maxB){
						maxB = x - z;
						aTestPointsX[NumTestPoints+3] = x;
						aTestPointsY[NumTestPoints+3] = y;
						aTestPointsZ[NumTestPoints+3] = z;
					}
					done = true;
				}
		y++;
	}while(!done);
	NumTestPoints += 4;

	// decrease y, bounds in x and z
	y = ElementsY-1;
	do{
		done = false;
		int minA = 10000;
		int minB = 10000;
		int maxA = -10000;
		int maxB = -10000;
		for(x = 0; x < ElementsX; x++)
			for(z = 0; z < ElementsZ; z++)
				if(MEM(x, y, z) & FLAG_FREE){
					if(x + z < minA){
						minA = x + z;
						aTestPointsX[NumTestPoints] = x;
						aTestPointsY[NumTestPoints] = y;
						aTestPointsZ[NumTestPoints] = z;
					}
					if(x + z > maxA){
						maxA = x + z;
						aTestPointsX[NumTestPoints+1] = x;
						aTestPointsY[NumTestPoints+1] = y;
						aTestPointsZ[NumTestPoints+1] = z;
					}
					if(x - z < minB){
						minB = x - z;
						aTestPointsX[NumTestPoints+2] = x;
						aTestPointsY[NumTestPoints+2] = y;
						aTestPointsZ[NumTestPoints+2] = z;
					}
					if(x - z > maxB){
						maxB = x - z;
						aTestPointsX[NumTestPoints+3] = x;
						aTestPointsY[NumTestPoints+3] = y;
						aTestPointsZ[NumTestPoints+3] = z;
					}
					done = true;
				}
		y--;
	}while(!done);
	NumTestPoints += 4;

	// increase z, bounds in x and y
	z = 0;
	do{
		done = false;
		int minA = 10000;
		int minB = 10000;
		int maxA = -10000;
		int maxB = -10000;
		for(x = 0; x < ElementsX; x++)
			for(y = 0; y < ElementsY; y++)
				if(MEM(x, y, z) & FLAG_FREE){
					if(x + y < minA){
						minA = x + y;
						aTestPointsX[NumTestPoints] = x;
						aTestPointsY[NumTestPoints] = y;
						aTestPointsZ[NumTestPoints] = z;
					}
					if(x + y > maxA){
						maxA = x + y;
						aTestPointsX[NumTestPoints+1] = x;
						aTestPointsY[NumTestPoints+1] = y;
						aTestPointsZ[NumTestPoints+1] = z;
					}
					if(x - y < minB){
						minB = x - y;
						aTestPointsX[NumTestPoints+2] = x;
						aTestPointsY[NumTestPoints+2] = y;
						aTestPointsZ[NumTestPoints+2] = z;
					}
					if(x - y > maxB){
						maxB = x - y;
						aTestPointsX[NumTestPoints+3] = x;
						aTestPointsY[NumTestPoints+3] = y;
						aTestPointsZ[NumTestPoints+3] = z;
					}
					done = true;
				}
		z++;
	}while(!done);
	NumTestPoints += 4;

	// decrease z, bounds in x and y
	z = ElementsZ-1;
	do{
		done = false;
		int minA = 10000;
		int minB = 10000;
		int maxA = -10000;
		int maxB = -10000;
		for(x = 0; x < ElementsX; x++)
			for(y = 0; y < ElementsY; y++)
				if(MEM(x, y, z) & FLAG_FREE){
					if(x + y < minA){
						minA = x + y;
						aTestPointsX[NumTestPoints] = x;
						aTestPointsY[NumTestPoints] = y;
						aTestPointsZ[NumTestPoints] = z;
					}
					if(x + y > maxA){
						maxA = x + y;
						aTestPointsX[NumTestPoints+1] = x;
						aTestPointsY[NumTestPoints+1] = y;
						aTestPointsZ[NumTestPoints+1] = z;
					}
					if(x - y < minB){
						minB = x - y;
						aTestPointsX[NumTestPoints+2] = x;
						aTestPointsY[NumTestPoints+2] = y;
						aTestPointsZ[NumTestPoints+2] = z;
					}
					if(x - y > maxB){
						maxB = x - y;
						aTestPointsX[NumTestPoints+3] = x;
						aTestPointsY[NumTestPoints+3] = y;
						aTestPointsZ[NumTestPoints+3] = z;
					}
					done = true;
				}
		z--;
	}while(!done);
	NumTestPoints += 4;

	// divide the axis aligned bounding planes into 4 and place some test points

	// x = 0 plane
	MinValY = 999999;
	MinValZ = 999999;
	MaxValY = 0;
	MaxValZ = 0;
	for(y = 0; y < ElementsY; y++)
		for(z = 0; z < ElementsZ; z++)
			if(MEM(0, y, z) & FLAG_FREE){
				if(y < MinValY) MinValY = y;
				if(z < MinValZ) MinValZ = z;
				if(y > MaxValY) MaxValY = y;
				if(z > MaxValZ) MaxValZ = z;
			}
	// pick 4 points in the found bounds and add new test points
	if(MaxValY != 0 && MaxValZ != 0)
		for(Point1 = 0; Point1 < 2; Point1++)
			for(Point2 = 0; Point2 < 2; Point2++){
				NewPointY = (Point1 + 0.5f)*(MaxValY - MinValY)*0.5f + MinValY;
				NewPointZ = (Point2 + 0.5f)*(MaxValZ - MinValZ)*0.5f + MinValZ;
				if(MEM(0, NewPointY, NewPointZ) & FLAG_FREE){
					aTestPointsX[NumTestPoints] = 0;
					aTestPointsY[NumTestPoints] = NewPointY;
					aTestPointsZ[NumTestPoints] = NewPointZ;
					NumTestPoints++;
				}
			}

	// x = ElementsX-1 plane
	MinValY = 999999;
	MinValZ = 999999;
	MaxValY = 0;
	MaxValZ = 0;
	for(y = 0; y < ElementsY; y++)
		for(z = 0; z < ElementsZ; z++)
			if(MEM(ElementsX-1, y, z) & FLAG_FREE){
				if(y < MinValY) MinValY = y;
				if(z < MinValZ) MinValZ = z;
				if(y > MaxValY) MaxValY = y;
				if(z > MaxValZ) MaxValZ = z;
			}
	// pick 4 points in the found bounds and add new test points
	if(MaxValY != 0 && MaxValZ != 0)
		for(Point1 = 0; Point1 < 2; Point1++)
			for(Point2 = 0; Point2 < 2; Point2++){
				NewPointY = (Point1 + 0.5f)*(MaxValY - MinValY)*0.5f + MinValY;
				NewPointZ = (Point2 + 0.5f)*(MaxValZ - MinValZ)*0.5f + MinValZ;
				if(MEM(ElementsX-1, NewPointY, NewPointZ) & FLAG_FREE){
					aTestPointsX[NumTestPoints] = ElementsX-1;
					aTestPointsY[NumTestPoints] = NewPointY;
					aTestPointsZ[NumTestPoints] = NewPointZ;
					NumTestPoints++;
				}
			}

	// y = 0 plane
	MinValX = 999999;
	MinValZ = 999999;
	MaxValX = 0;
	MaxValZ = 0;
	for(x = 0; x < ElementsX; x++)
		for(z = 0; z < ElementsZ; z++)
			if(MEM(x, 0, z) & FLAG_FREE){
				if(x < MinValX) MinValX = x;
				if(z < MinValZ) MinValZ = z;
				if(x > MaxValX) MaxValX = x;
				if(z > MaxValZ) MaxValZ = z;
			}
	// pick 4 points in the found bounds and add new test points
	if(MaxValX != 0 && MaxValZ != 0)
		for(Point1 = 0; Point1 < 2; Point1++)
			for(Point2 = 0; Point2 < 2; Point2++){
				NewPointX = (Point1 + 0.5f)*(MaxValX - MinValX)*0.5f + MinValX;
				NewPointZ = (Point2 + 0.5f)*(MaxValZ - MinValZ)*0.5f + MinValZ;
				if(MEM(NewPointX, 0, NewPointZ) & FLAG_FREE){
					aTestPointsX[NumTestPoints] = NewPointX;
					aTestPointsY[NumTestPoints] = 0;
					aTestPointsZ[NumTestPoints] = NewPointZ;
					NumTestPoints++;
				}
			}

	// y = ElementsY-1 plane
	MinValX = 999999;
	MinValZ = 999999;
	MaxValX = 0;
	MaxValZ = 0;
	for(x = 0; x < ElementsX; x++)
		for(z = 0; z < ElementsZ; z++)
			if(MEM(x, ElementsY-1, z) & FLAG_FREE){
				if(x < MinValX) MinValX = x;
				if(z < MinValZ) MinValZ = z;
				if(x > MaxValX) MaxValX = x;
				if(z > MaxValZ) MaxValZ = z;
			}
	// pick 4 points in the found bounds and add new test points
	if(MaxValX != 0 && MaxValZ != 0)
		for(Point1 = 0; Point1 < 2; Point1++)
			for(Point2 = 0; Point2 < 2; Point2++){
				NewPointX = (Point1 + 0.5f)*(MaxValX - MinValX)*0.5f + MinValX;
				NewPointZ = (Point2 + 0.5f)*(MaxValZ - MinValZ)*0.5f + MinValZ;
				if(MEM(NewPointX, ElementsY-1, NewPointZ) & FLAG_FREE){
					aTestPointsX[NumTestPoints] = NewPointX;
					aTestPointsY[NumTestPoints] = ElementsY-1;
					aTestPointsZ[NumTestPoints] = NewPointZ;
					NumTestPoints++;
				}
			}

	// z = 0 plane
	MinValX = 999999;
	MinValY = 999999;
	MaxValX = 0;
	MaxValY = 0;
	for(x = 0; x < ElementsX; x++)
		for(y = 0; y < ElementsY; y++)
			if(MEM(x, y, 0) & FLAG_FREE){
				if(x < MinValX) MinValX = x;
				if(y < MinValY) MinValY = y;
				if(x > MaxValX) MaxValX = x;
				if(y > MaxValY) MaxValY = y;
			}
	// pick 4 points in the found bounds and add new test points
	if(MaxValX != 0 && MaxValY != 0)
		for(Point1 = 0; Point1 < 2; Point1++)
			for(Point2 = 0; Point2 < 2; Point2++){
				NewPointX = (Point1 + 0.5f)*(MaxValX - MinValX)*0.5f + MinValX;
				NewPointY = (Point2 + 0.5f)*(MaxValY - MinValY)*0.5f + MinValY;
				if(MEM(NewPointX, NewPointY, 0) & FLAG_FREE){
					aTestPointsX[NumTestPoints] = NewPointX;
					aTestPointsY[NumTestPoints] = NewPointY;
					aTestPointsZ[NumTestPoints] = 0;
					NumTestPoints++;
				}
			}

	// z = ElementsZ-1 plane
	MinValX = 999999;
	MinValY = 999999;
	MaxValX = 0;
	MaxValY = 0;
	for(x = 0; x < ElementsX; x++)
		for(y = 0; y < ElementsY; y++)
			if(MEM(x, y, ElementsZ-1) & FLAG_FREE){
				if(x < MinValX) MinValX = x;
				if(y < MinValY) MinValY = y;
				if(x > MaxValX) MaxValX = x;
				if(y > MaxValY) MaxValY = y;
			}
	// pick 4 points in the found bounds and add new test points
	if(MaxValX != 0 && MaxValY != 0)
		for(Point1 = 0; Point1 < 2; Point1++)
			for(Point2 = 0; Point2 < 2; Point2++){
				NewPointX = (Point1 + 0.5f)*(MaxValX - MinValX)*0.5f + MinValX;
				NewPointY = (Point2 + 0.5f)*(MaxValY - MinValY)*0.5f + MinValY;
				if(MEM(NewPointX, NewPointY, ElementsZ-1) & FLAG_FREE){
					aTestPointsX[NumTestPoints] = NewPointX;
					aTestPointsY[NumTestPoints] = NewPointY;
					aTestPointsZ[NumTestPoints] = ElementsZ-1;
					NumTestPoints++;
				}
			}

	// add some hardcoded test points
	for(int i = 0; i < ARRAY_SIZE(ExtraFudgePointsCoors); i++)
		if(PointFallsWithinZone(ExtraFudgePointsCoors[i], 0.0f)){
			x = ElementsX * (ExtraFudgePointsCoors[i].x-minx)/(maxx-minx);
			y = ElementsY * (ExtraFudgePointsCoors[i].y-miny)/(maxy-miny);
			z = ElementsZ * (ExtraFudgePointsCoors[i].z-minz)/(maxz-minz);
			if(MEM(x, y, z) & FLAG_FREE){
				aTestPointsX[NumTestPoints] = x;
				aTestPointsY[NumTestPoints] = y;
				aTestPointsZ[NumTestPoints] = z;
				NumTestPoints++;
			}
		}

	// remove duplicate points
	for(int i = 0; i < NumTestPoints; i++)
		for(int j = i+1; j < NumTestPoints; j++)
			if(aTestPointsX[j] == aTestPointsX[i] &&
			   aTestPointsY[j] == aTestPointsY[i] &&
			   aTestPointsZ[j] == aTestPointsZ[i]){
				// get rid of [j]
				for(int k = j; k < NumTestPoints-1; k++){
					aTestPointsX[k] = aTestPointsX[k+1];
					aTestPointsY[k] = aTestPointsY[k+1];
					aTestPointsZ[k] = aTestPointsZ[k+1];
				}
				NumTestPoints--;
			}

	// convert points to floating point
	for(int i = 0; i < NumTestPoints; i++){
		aTestPoints[i].x = aTestPointsX[i]*StepX + minx;
		aTestPoints[i].y = aTestPointsY[i]*StepY + miny;
		aTestPoints[i].z = aTestPointsZ[i]*StepZ + minz;
	}

	CZNumber++;

	delete[] pMem;
	pMem = nil;
}

bool
CCullZone::TestEntityVisibilityFromCullZone(CEntity *entity, float extraDist, CEntity *LODentity)
{
	CColModel *colmodel = entity->GetColModel();
	float boundMaxX = colmodel->boundingBox.max.x;
	float boundMaxY = colmodel->boundingBox.max.y;
	float boundMaxZ = colmodel->boundingBox.max.z;
	float boundMinX = colmodel->boundingBox.min.x;
	float boundMinY = colmodel->boundingBox.min.y;
	float boundMinZ = colmodel->boundingBox.min.z;
	if(LODentity){
		colmodel = LODentity->GetColModel();
		boundMaxX = Max(boundMaxX, colmodel->boundingBox.max.x);
		boundMaxY = Max(boundMaxY, colmodel->boundingBox.max.y);
		boundMaxZ = Max(boundMaxZ, colmodel->boundingBox.max.z);
		boundMinX = Min(boundMinX, colmodel->boundingBox.min.x);
		boundMinY = Min(boundMinY, colmodel->boundingBox.min.y);
		boundMinZ = Min(boundMinZ, colmodel->boundingBox.min.z);
	}

	if(boundMaxZ-boundMinZ + extraDist < 0.5f)
		boundMaxZ = boundMinZ + 0.5f;
	else
		boundMaxZ += extraDist;

	CVector vecMin = entity->GetMatrix() * CVector(boundMinX, boundMinY, boundMinZ);
	CVector vecMaxX = entity->GetMatrix() * CVector(boundMaxX, boundMinY, boundMinZ);
	CVector vecMaxY = entity->GetMatrix() * CVector(boundMinX, boundMaxY, boundMinZ);
	CVector vecMaxZ = entity->GetMatrix() * CVector(boundMinX, boundMinY, boundMaxZ);
	CVector dirx = vecMaxX - vecMin;
	CVector diry = vecMaxY - vecMin;
	CVector dirz = vecMaxZ - vecMin;

	// If building intersects zone at all, it's visible
	int x, y, z;
	for(x = 0; x < 9; x++){
		CVector posX = vecMin + x/8.0f*dirx;
		for(y = 0; y < 9; y++){
			CVector posY = posX + y/8.0f*diry;
			for(z = 0; z < 9; z++){
 				CVector posZ = posY + z/8.0f*dirz;
				if(PointFallsWithinZone(posZ, 2.0f))
					return true;
			}
		}
	}

	float distToZone = CalcDistToCullZone(entity->GetPosition().x, entity->GetPosition().y)/15.0f;
	distToZone = Max(distToZone, 7.0f);
	int numX = (boundMaxX - boundMinX)/distToZone + 2.0f;
	int numY = (boundMaxY - boundMinY)/distToZone + 2.0f;
	int numZ = (boundMaxZ - boundMinZ)/distToZone + 2.0f;

	float stepX = 1.0f/(numX-1);
	float stepY = 1.0f/(numY-1);
	float stepZ = 1.0f/(numZ-1);
	float midX = (boundMaxX + boundMinX)/2.0f;
	float midY = (boundMaxY + boundMinY)/2.0f;
	float midZ = (boundMaxZ + boundMinZ)/2.0f;

	// check both xy planes
	for(int i = 0; i < NumTestPoints; i++){
		CVector testPoint = aTestPoints[i];
		CVector mid = entity->GetMatrix() * CVector(midX, midY, midZ);
		mid.z += 0.1f;
		if(DoThoroughLineTest(testPoint, mid, entity))
			return true;

		CVector ray = entity->GetPosition() - testPoint;

		float dotX = DotProduct(ray, dirx);
		float dotY = DotProduct(ray, diry);
		float dotZ = DotProduct(ray, dirz);

		for(x = 0; x < numX; x++){
			CVector pMinZ = vecMin + x*stepX*dirx;
			CVector pMaxZ = vecMin + x*stepX*dirx + dirz;
			for(y = 0; y < numY; y++)
				if(dotZ > 0.0f){
					if(DoThoroughLineTest(testPoint, pMinZ + y*stepY*diry, entity))
						return true;
				}else{
					if(DoThoroughLineTest(testPoint, pMaxZ + y*stepY*diry, entity))
						return true;
				}
		}

		for(x = 0; x < numX; x++){
			CVector pMinY = vecMin + x*stepX*dirx;
			CVector pMaxY = vecMin + x*stepX*dirx + diry;
			for(z = 1; z < numZ-1; z++)	// edge cases already handled
				if(dotY > 0.0f){
					if(DoThoroughLineTest(testPoint, pMinY + z*stepZ*dirz, entity))
						return true;
				}else{
					if(DoThoroughLineTest(testPoint, pMaxY + z*stepZ*dirz, entity))
						return true;
				}
		}

		for(y = 1; y < numY-1; y++){	// edge cases already handled
			CVector pMinX = vecMin + y*stepY*diry;
			CVector pMaxX = vecMin + y*stepY*diry + dirx;
			for(z = 1; z < numZ-1; z++)	// edge cases already handled
				if(dotX > 0.0f){
					if(DoThoroughLineTest(testPoint, pMinX + z*stepZ*dirz, entity))
						return true;
				}else{
					if(DoThoroughLineTest(testPoint, pMaxX + z*stepZ*dirz, entity))
						return true;
				}
		}
	}

	return false;
}


code:
class CEntity;

class CCullZone
{
public:
	CVector position;
	float minx;
	float maxx;
	float miny;
	float maxy;
	float minz;
	float maxz;

	int32 m_indexStart;
	int16 m_groupIndexCount[3];	// only useful during resolution stage
	int16 m_numBuildings;
	int16 m_numTreadablesPlus10m;
	int16 m_numTreadables;

	void DoStuffLeavingZone(void);
	static void DoStuffLeavingZone_OneBuilding(uint16 i);
	static void DoStuffLeavingZone_OneTreadableBoth(uint16 i);
	void DoStuffEnteringZone(void);
	static void DoStuffEnteringZone_OneBuilding(uint16 i);
	static void DoStuffEnteringZone_OneTreadablePlus10m(uint16 i);
	static void DoStuffEnteringZone_OneTreadable(uint16 i);

	static bool TestLine(CVector vec1, CVector vec2);
	static bool DoThoroughLineTest(CVector vec1, CVector vec2, CEntity *testEntity);
	float CalcDistToCullZoneSquared(float x, float y);
	float CalcDistToCullZone(float x, float y) { return Sqrt(CalcDistToCullZoneSquared(x, y)); };
	bool IsEntityCloseEnoughToZone(CEntity* entity, bool checkLevel);
	bool PointFallsWithinZone(CVector pos, float radius);
	bool TestEntityVisibilityFromCullZone(CEntity *entity, float extraDist, CEntity *LODentity);
	void FindTestPoints();

	void GetGroupStartAndSize(int32 groupid, int32 &start, int32 &size) {
		switch (groupid) {
		case 0:
		default:
			// buildings
			start = m_indexStart;
			size = m_groupIndexCount[0];
			break;
		case 1:
			// treadables + 10m
			start = m_groupIndexCount[0] + m_indexStart;
			size = m_groupIndexCount[1];
			break;
		case 2:
			// treadables
			start = m_groupIndexCount[0] + m_groupIndexCount[1] + m_indexStart;
			size = m_groupIndexCount[2];
			break;
		}
	}
};

enum eZoneAttribs
{
	ATTRZONE_CAMCLOSEIN		= 1,
	ATTRZONE_STAIRS			= 2,
	ATTRZONE_1STPERSON		= 4,
	ATTRZONE_NORAIN			= 8,
	ATTRZONE_NOPOLICE		= 0x10,
	ATTRZONE_NOTCULLZONE		= 0x20,
	ATTRZONE_DOINEEDCOLLISION	= 0x40,
	ATTRZONE_SUBWAYVISIBLE		= 0x80,
};

struct CAttributeZone
{
	float minx;
	float maxx;
	float miny;
	float maxy;
	float minz;
	float maxz;
	int16 attributes;
	int16 wantedLevel;
};

class CCullZones
{
public:
	static int32     NumCullZones;
	static CCullZone aZones[NUMCULLZONES];
	static int32     NumAttributeZones;
	static CAttributeZone aAttributeZones[NUMATTRIBZONES];
	static uint16        aIndices[NUMZONEINDICES];
	static int16         aPointersToBigBuildingsForBuildings[NUMBUILDINGS];
	static int16         aPointersToBigBuildingsForTreadables[NUMTREADABLES];

	static int32 CurrentWantedLevelDrop_Player;
	static int32 CurrentFlags_Camera;
	static int32 CurrentFlags_Player;
	static int32 OldCullZone;
	static int32 EntityIndicesUsed;
	static bool bCurrentSubwayIsInvisible;
	static bool bCullZonesDisabled;

	static void Init(void);
	static void ResolveVisibilities(void);
	static void Update(void);
	static void ForceCullZoneCoors(CVector coors);
	static int32 FindCullZoneForCoors(CVector coors);
	static int32 FindAttributesForCoors(CVector coors, int32 *wantedLevel);
	static CAttributeZone *FindZoneWithStairsAttributeForPlayer(void);
	static void MarkSubwayAsInvisible(bool visible);
	static void AddCullZone(CVector const &position,
		float minx, float maxx,
		float miny, float maxy,
		float minz, float maxz,
		uint16 flag, int16 wantedLevel);
	static bool CamCloseInForPlayer(void) { return (CurrentFlags_Player & ATTRZONE_CAMCLOSEIN) != 0; }
	static bool CamStairsForPlayer(void) { return (CurrentFlags_Player & ATTRZONE_STAIRS) != 0; }
	static bool Cam1stPersonForPlayer(void) { return (CurrentFlags_Player & ATTRZONE_1STPERSON) != 0; }
	static bool NoPolice(void) { return (CurrentFlags_Player & ATTRZONE_NOPOLICE) != 0; }
	static bool DoINeedToLoadCollision(void) { return (CurrentFlags_Player & ATTRZONE_DOINEEDCOLLISION) != 0; }
	static bool PlayerNoRain(void) { return (CurrentFlags_Player & ATTRZONE_NORAIN) != 0; }
	static bool CamNoRain(void) { return (CurrentFlags_Camera & ATTRZONE_NORAIN) != 0; }
	static int32 GetWantedLevelDrop(void) { return CurrentWantedLevelDrop_Player; }

	static void BuildListForBigBuildings();
	static void DoVisibilityTestCullZone(int zoneId, bool doIt);
	static bool DoWeHaveMoreThanXOccurencesOfSet(int32 count, uint16 *set);

	static void CompressIndicesArray();
	static bool PickRandomSetForGroup(int32 zone, int32 group, uint16 *set);
	static void ReplaceSetForAllGroups(uint16 *set, uint16 setid);
	static void TidyUpAndMergeLists(uint16 *extraIndices, int32 numExtraIndices);

	// debug
	static bool LoadTempFile(void);
	static void SaveTempFile(void);
};

license: mit


code:
#include "common.h"

#include <ctype.h>

#include "Zones.h"

#include "Clock.h"
#include "Text.h"
#include "World.h"
#include "Timer.h"
#include "SaveBuf.h"

#ifdef COMPATIBLE_SAVES
#define ZONEARRAY_SAVE_SIZE 0xAF0
#define MAPZONEARRAY_SAVE_SIZE 0x578
#else
#define ZONEARRAY_SAVE_SIZE sizeof(ZoneArray)
#define MAPZONEARRAY_SAVE_SIZE sizeof(MapZoneArray)
#endif

eLevelName CTheZones::m_CurrLevel;
CZone *CTheZones::m_pPlayersZone;
int16 CTheZones::FindIndex;

uint16 CTheZones::NumberOfAudioZones;
int16 CTheZones::AudioZoneArray[NUMAUDIOZONES];
uint16 CTheZones::TotalNumberOfMapZones;
uint16 CTheZones::TotalNumberOfZones;
CZone CTheZones::ZoneArray[NUMZONES];
CZone CTheZones::MapZoneArray[NUMMAPZONES];
uint16 CTheZones::TotalNumberOfZoneInfos;
CZoneInfo CTheZones::ZoneInfoArray[2*NUMZONES];

#define SWAPF(a, b) { float t; t = a; a = b; b = t; }

inline bool IsNormalZone(int type) { return type == ZONE_DEFAULT || type == ZONE_NAVIG || type == ZONE_INFO; }

static void
CheckZoneInfo(CZoneInfo *info)
{
	assert(info->carThreshold[0] >= 0);
	assert(info->carThreshold[0] <= info->carThreshold[1]);
	assert(info->carThreshold[1] <= info->carThreshold[2]);
	assert(info->carThreshold[2] <= info->carThreshold[3]);
	assert(info->carThreshold[3] <= info->carThreshold[4]);
	assert(info->carThreshold[4] <= info->carThreshold[5]);
	assert(info->carThreshold[5] <= info->copThreshold);
	assert(info->copThreshold <= info->gangThreshold[0]);
	assert(info->gangThreshold[0] <= info->gangThreshold[1]);
	assert(info->gangThreshold[1] <= info->gangThreshold[2]);
	assert(info->gangThreshold[2] <= info->gangThreshold[3]);
	assert(info->gangThreshold[3] <= info->gangThreshold[4]);
	assert(info->gangThreshold[4] <= info->gangThreshold[5]);
	assert(info->gangThreshold[5] <= info->gangThreshold[6]);
	assert(info->gangThreshold[6] <= info->gangThreshold[7]);
	assert(info->gangThreshold[7] <= info->gangThreshold[8]);
}

wchar*
CZone::GetTranslatedName(void)
{
	return TheText.Get(name);
}

void
CTheZones::Init(void)
{
	int i;
	for(i = 0; i < NUMAUDIOZONES; i++)
		AudioZoneArray[i] = -1;
	NumberOfAudioZones = 0;

	for(i = 0; i < NUMZONES; i++)
		memset(&ZoneArray[i], 0, sizeof(CZone));

	CZoneInfo *zonei;
	int x = 1000/6;
	for(i = 0; i < 2*NUMZONES; i++){
		zonei = &ZoneInfoArray[i];
		zonei->carDensity = 10;
		zonei->carThreshold[0] = x;
		zonei->carThreshold[1] = zonei->carThreshold[0] + x;
		zonei->carThreshold[2] = zonei->carThreshold[1] + x;
		zonei->carThreshold[3] = zonei->carThreshold[2] + x;
		zonei->carThreshold[4] = zonei->carThreshold[3];
		zonei->carThreshold[5] = zonei->carThreshold[4];
		zonei->copThreshold = zonei->carThreshold[5] + x;
		zonei->gangThreshold[0] = zonei->copThreshold;
		zonei->gangThreshold[1] = zonei->gangThreshold[0];
		zonei->gangThreshold[2] = zonei->gangThreshold[1];
		zonei->gangThreshold[3] = zonei->gangThreshold[2];
		zonei->gangThreshold[4] = zonei->gangThreshold[3];
		zonei->gangThreshold[5] = zonei->gangThreshold[4];
		zonei->gangThreshold[6] = zonei->gangThreshold[5];
		zonei->gangThreshold[7] = zonei->gangThreshold[6];
		zonei->gangThreshold[8] = zonei->gangThreshold[7];
		CheckZoneInfo(zonei);
	}

	TotalNumberOfZoneInfos = 1;	// why 1?
	TotalNumberOfZones = 1;

	m_CurrLevel = LEVEL_GENERIC;
	m_pPlayersZone = &ZoneArray[0];

	strcpy(ZoneArray[0].name, "CITYZON");
	ZoneArray[0].minx = -4000.0f;
	ZoneArray[0].miny = -4000.0f;
	ZoneArray[0].minz = -500.0f;
	ZoneArray[0].maxx =  4000.0f;
	ZoneArray[0].maxy =  4000.0f;
	ZoneArray[0].maxz =  500.0f;
	ZoneArray[0].level = LEVEL_GENERIC;

	for(i = 0; i < NUMMAPZONES; i++){
		memset(&MapZoneArray[i], 0, sizeof(CZone));
		MapZoneArray[i].type = ZONE_MAPZONE;
	}

	TotalNumberOfMapZones = 1;

	strcpy(MapZoneArray[0].name, "THEMAP");
	MapZoneArray[0].minx = -4000.0f;
	MapZoneArray[0].miny = -4000.0f;
	MapZoneArray[0].minz = -500.0f;
	MapZoneArray[0].maxx =  4000.0f;
	MapZoneArray[0].maxy =  4000.0f;
	MapZoneArray[0].maxz =  500.0f;
	MapZoneArray[0].level = LEVEL_GENERIC;
}

void
CTheZones::Update(void)
{
#ifdef SQUEEZE_PERFORMANCE
	if (CTimer::GetFrameCounter() % 5 != 0)
		return;
#endif
	CVector pos;
	pos = FindPlayerCoors();
	m_pPlayersZone = FindSmallestZonePosition(&pos);
	m_CurrLevel = GetLevelFromPosition(&pos);
}

void
CTheZones::CreateZone(char *name, eZoneType type,
	              float minx, float miny, float minz,
	              float maxx, float maxy, float maxz,
	              eLevelName level)
{
	char *p;
	char tmpname[8];

	if(minx > maxx) SWAPF(minx, maxx);
	if(miny > maxy) SWAPF(miny, maxy);
	if(minz > maxz) SWAPF(minz, maxz);

	// make upper case
	for(p = name; *p; p++) if(islower(*p)) *p = toupper(*p);

	// add zone
	strncpy(tmpname, name, 7);
	tmpname[7] = '\0';
	strcpy(ZoneArray[TotalNumberOfZones].name, tmpname);
	ZoneArray[TotalNumberOfZones].type = type;
	ZoneArray[TotalNumberOfZones].minx = minx;
	ZoneArray[TotalNumberOfZones].miny = miny;
	ZoneArray[TotalNumberOfZones].minz = minz;
	ZoneArray[TotalNumberOfZones].maxx = maxx;
	ZoneArray[TotalNumberOfZones].maxy = maxy;
	ZoneArray[TotalNumberOfZones].maxz = maxz;
	ZoneArray[TotalNumberOfZones].level = level;
	if(IsNormalZone(type)){
		ZoneArray[TotalNumberOfZones].zoneinfoDay = TotalNumberOfZoneInfos++;
		ZoneArray[TotalNumberOfZones].zoneinfoNight = TotalNumberOfZoneInfos++;
	}
	TotalNumberOfZones++;
}

void
CTheZones::CreateMapZone(char *name, eZoneType type,
	                 float minx, float miny, float minz,
	                 float maxx, float maxy, float maxz,
	                 eLevelName level)
{
	CZone *zone;
	char *p;

	if(minx > maxx) SWAPF(minx, maxx);
	if(miny > maxy) SWAPF(miny, maxy);
	if(minz > maxz) SWAPF(minz, maxz);

	// make upper case
	for(p = name; *p; p++) if(islower(*p)) *p = toupper(*p);

	// add zone
	zone = &MapZoneArray[TotalNumberOfMapZones++];
	strncpy(zone->name, name, 7);
	zone->name[7] = '\0';
	zone->type = type;
	zone->minx = minx;
	zone->miny = miny;
	zone->minz = minz;
	zone->maxx = maxx;
	zone->maxy = maxy;
	zone->maxz = maxz;
	zone->level = level;
}

void
CTheZones::PostZoneCreation(void)
{
	int i;
	for(i = 1; i < TotalNumberOfZones; i++)
		InsertZoneIntoZoneHierarchy(&ZoneArray[i]);
	InitialiseAudioZoneArray();
}

void
CTheZones::InsertZoneIntoZoneHierarchy(CZone *zone)
{
	zone->child = nil;
	zone->parent = nil;
	zone->next = nil;
	InsertZoneIntoZoneHierRecursive(zone, &ZoneArray[0]);
}

bool
CTheZones::InsertZoneIntoZoneHierRecursive(CZone *inner, CZone *outer)
{
	int n;
	CZone *child, *next, *insert;

	// return false if inner was not inserted into outer
	if(outer == nil ||
	   !ZoneIsEntirelyContainedWithinOtherZone(inner, outer))
		return false;

	// try to insert inner into children of outer
	for(child = outer->child; child; child = child->next)
		if(InsertZoneIntoZoneHierRecursive(inner, child))
			return true;

	// insert inner as child of outer
	// count number of outer's children contained within inner
	n = 0;
	for(child = outer->child; child; child = child->next)
		if(ZoneIsEntirelyContainedWithinOtherZone(child, inner))
			n++;
	inner->next = outer->child;
	inner->parent = outer;
	outer->child = inner;
	// move children from outer to inner
	if(n){
		insert = inner;
		for(child = inner->next; child; child = next){
			next = child->next;
			if(ZoneIsEntirelyContainedWithinOtherZone(child,inner)){
				insert->next = child->next;
				child->parent = inner;
				child->next = inner->child;
				inner->child = child;
			}else
				insert = child;
		}
	}

	return true;
}

bool
CTheZones::ZoneIsEntirelyContainedWithinOtherZone(CZone *inner, CZone *outer)
{
	char tmp[100];

	if(inner->minx < outer->minx ||
	   inner->maxx > outer->maxx ||
	   inner->miny < outer->miny ||
	   inner->maxy > outer->maxy ||
	   inner->minz < outer->minz ||
	   inner->maxz > outer->maxz){
		CVector vmin(inner->minx, inner->miny, inner->minz);
		if(PointLiesWithinZone(&vmin, outer))
			sprintf(tmp, "Overlapping zones %s and %s\n",
			      inner->name, outer->name);
		CVector vmax(inner->maxx, inner->maxy, inner->maxz);
		if(PointLiesWithinZone(&vmax, outer))
			sprintf(tmp, "Overlapping zones %s and %s\n",
			      inner->name, outer->name);
		return false;
	}
	return true;
}

bool
CTheZones::PointLiesWithinZone(const CVector *v, CZone *zone)
{
	return zone->minx <= v->x && v->x <= zone->maxx &&
	       zone->miny <= v->y && v->y <= zone->maxy &&
	       zone->minz <= v->z && v->z <= zone->maxz;
}

eLevelName
CTheZones::GetLevelFromPosition(CVector const *v)
{
	int i;
//	char tmp[116];
//	if(!PointLiesWithinZone(v, &MapZoneArray[0]))
//		sprintf(tmp, "x = %.3f y= %.3f z = %.3f\n", v.x, v.y, v.z);
	for(i = 1; i < TotalNumberOfMapZones; i++)
		if(PointLiesWithinZone(v, &MapZoneArray[i]))
			return MapZoneArray[i].level;
	return MapZoneArray[0].level;
}

CZone*
CTheZones::FindSmallestZonePosition(const CVector *v)
{
	CZone *best = &ZoneArray[0];
	// zone to test next
	CZone *zone = ZoneArray[0].child;
	while(zone)
		// if in zone, descent into children
		if(PointLiesWithinZone(v, zone)){
			best = zone;
			zone = zone->child;
		// otherwise try next zone
		}else
			zone = zone->next;
	return best;
}

CZone*
CTheZones::FindSmallestZonePositionType(const CVector *v, eZoneType type)
{
	CZone *best = nil;
	if(ZoneArray[0].type == type)
		best = &ZoneArray[0];
	// zone to test next
	CZone *zone = ZoneArray[0].child;
	while(zone)
		// if in zone, descent into children
		if(PointLiesWithinZone(v, zone)){
			if(zone->type == type)
				best = zone;
			zone = zone->child;
		// otherwise try next zone
		}else
			zone = zone->next;
	return best;
}

CZone*
CTheZones::FindSmallestZonePositionILN(const CVector *v)
{
	CZone *best = nil;
	if(IsNormalZone(ZoneArray[0].type))
		best = &ZoneArray[0];
	// zone to test next
	CZone *zone = ZoneArray[0].child;
	while(zone)
		// if in zone, descent into children
		if(PointLiesWithinZone(v, zone)){
			if(IsNormalZone(zone->type))
				best = zone;
			zone = zone->child;
		// otherwise try next zone
		}else
			zone = zone->next;
	return best;
}

int16
CTheZones::FindZoneByLabelAndReturnIndex(Const char *name)
{
	char str[8];
	memset(str, 0, 8);
	strncpy(str, name, 8);
	for(FindIndex = 0; FindIndex < TotalNumberOfZones; FindIndex++)
		if(strcmp(GetZone(FindIndex)->name, name) == 0)
			return FindIndex;
	return -1;
}

CZoneInfo*
CTheZones::GetZoneInfo(const CVector *v, uint8 day)
{
	CZone *zone;
	zone = FindSmallestZonePositionILN(v);
	if(zone == nil)
		return &ZoneInfoArray[0];
	return &ZoneInfoArray[day ? zone->zoneinfoDay : zone->zoneinfoNight];
}

void
CTheZones::GetZoneInfoForTimeOfDay(const CVector *pos, CZoneInfo *info)
{
	CZoneInfo *day, *night;
	float d, n;

	day = GetZoneInfo(pos, 1);
	night = GetZoneInfo(pos, 0);

	if(CClock::GetIsTimeInRange(8, 19))
		*info = *day;
	else if(CClock::GetIsTimeInRange(22, 5))
		*info = *night;
	else{
		if(CClock::GetIsTimeInRange(19, 22)){
			n = (CClock::GetHours() - 19) / 3.0f;
			assert(n >= 0.0f && n <= 1.0f);
			d = 1.0f - n;
		}else{
			d = (CClock::GetHours() - 5) / 3.0f;
			assert(d >= 0.0f && d <= 1.0f);
			n = 1.0f - d;
		}
		info->carDensity = day->carDensity * d + night->carDensity * n;
		info->carThreshold[0] = day->carThreshold[0] * d + night->carThreshold[0] * n;
		info->carThreshold[1] = day->carThreshold[1] * d + night->carThreshold[1] * n;
		info->carThreshold[2] = day->carThreshold[2] * d + night->carThreshold[2] * n;
		info->carThreshold[3] = day->carThreshold[3] * d + night->carThreshold[3] * n;
		info->carThreshold[4] = day->carThreshold[4] * d + night->carThreshold[4] * n;
		info->carThreshold[5] = day->carThreshold[5] * d + night->carThreshold[5] * n;
		info->copThreshold = day->copThreshold * d + night->copThreshold * n;
		info->gangThreshold[0] = day->gangThreshold[0] * d + night->gangThreshold[0] * n;
		info->gangThreshold[1] = day->gangThreshold[1] * d + night->gangThreshold[1] * n;
		info->gangThreshold[2] = day->gangThreshold[2] * d + night->gangThreshold[2] * n;
		info->gangThreshold[3] = day->gangThreshold[3] * d + night->gangThreshold[3] * n;
		info->gangThreshold[4] = day->gangThreshold[4] * d + night->gangThreshold[4] * n;
		info->gangThreshold[5] = day->gangThreshold[5] * d + night->gangThreshold[5] * n;
		info->gangThreshold[6] = day->gangThreshold[6] * d + night->gangThreshold[6] * n;
		info->gangThreshold[7] = day->gangThreshold[7] * d + night->gangThreshold[7] * n;
		info->gangThreshold[8] = day->gangThreshold[8] * d + night->gangThreshold[8] * n;

		info->pedDensity = day->pedDensity * d + night->pedDensity * n;
		info->copDensity = day->copDensity * d + night->copDensity * n;
		info->gangDensity[0] = day->gangDensity[0] * d + night->gangDensity[0] * n;
		info->gangDensity[1] = day->gangDensity[1] * d + night->gangDensity[1] * n;
		info->gangDensity[2] = day->gangDensity[2] * d + night->gangDensity[2] * n;
		info->gangDensity[3] = day->gangDensity[3] * d + night->gangDensity[3] * n;
		info->gangDensity[4] = day->gangDensity[4] * d + night->gangDensity[4] * n;
		info->gangDensity[5] = day->gangDensity[5] * d + night->gangDensity[5] * n;
		info->gangDensity[6] = day->gangDensity[6] * d + night->gangDensity[6] * n;
		info->gangDensity[7] = day->gangDensity[7] * d + night->gangDensity[7] * n;
		info->gangDensity[8] = day->gangDensity[8] * d + night->gangDensity[8] * n;
	}
	if(CClock::GetIsTimeInRange(5, 19))
		info->pedGroup = day->pedGroup;
	else
		info->pedGroup = night->pedGroup;

	CheckZoneInfo(info);
}

void
CTheZones::SetZoneCarInfo(uint16 zoneid, uint8 day, int16 carDensity,
	int16 gang0Num, int16 gang1Num, int16 gang2Num,
	int16 gang3Num, int16 gang4Num, int16 gang5Num,
	int16 gang6Num, int16 gang7Num, int16 gang8Num,
	int16 copNum,
	int16 car0Num, int16 car1Num, int16 car2Num,
	int16 car3Num, int16 car4Num, int16 car5Num)
{
	CZone *zone;
	CZoneInfo *info;
	zone = GetZone(zoneid);
	info = &ZoneInfoArray[day ? zone->zoneinfoDay : zone->zoneinfoNight];

	CheckZoneInfo(info);

	if(carDensity != -1) info->carDensity = carDensity;
	int16 oldCar1Num = info->carThreshold[1] - info->carThreshold[0];
	int16 oldCar2Num = info->carThreshold[2] - info->carThreshold[1];
	int16 oldCar3Num = info->carThreshold[3] - info->carThreshold[2];
	int16 oldCar4Num = info->carThreshold[4] - info->carThreshold[3];
	int16 oldCar5Num = info->carThreshold[5] - info->carThreshold[4];
	int16 oldCopNum = info->copThreshold - info->carThreshold[5];
	int16 oldGang0Num = info->gangThreshold[0] - info->copThreshold;
	int16 oldGang1Num = info->gangThreshold[1] - info->gangThreshold[0];
	int16 oldGang2Num = info->gangThreshold[2] - info->gangThreshold[1];
	int16 oldGang3Num = info->gangThreshold[3] - info->gangThreshold[2];
	int16 oldGang4Num = info->gangThreshold[4] - info->gangThreshold[3];
	int16 oldGang5Num = info->gangThreshold[5] - info->gangThreshold[4];
	int16 oldGang6Num = info->gangThreshold[6] - info->gangThreshold[5];
	int16 oldGang7Num = info->gangThreshold[7] - info->gangThreshold[6];
	int16 oldGang8Num = info->gangThreshold[8] - info->gangThreshold[7];

	if(car0Num != -1) info->carThreshold[0] = car0Num;
	if(car1Num != -1) info->carThreshold[1] = info->carThreshold[0] + car1Num;
	else              info->carThreshold[1] = info->carThreshold[0] + oldCar1Num;
	if(car2Num != -1) info->carThreshold[2] = info->carThreshold[1] + car2Num;
	else              info->carThreshold[2] = info->carThreshold[1] + oldCar2Num;
	if(car3Num != -1) info->carThreshold[3] = info->carThreshold[2] + car3Num;
	else              info->carThreshold[3] = info->carThreshold[2] + oldCar3Num;
	if(car4Num != -1) info->carThreshold[4] = info->carThreshold[3] + car4Num;
	else              info->carThreshold[4] = info->carThreshold[3] + oldCar4Num;
	if(car5Num != -1) info->carThreshold[5] = info->carThreshold[4] + car5Num;
	else              info->carThreshold[5] = info->carThreshold[4] + oldCar5Num;
	if(copNum != -1) info->copThreshold = info->carThreshold[5] + copNum;
	else             info->copThreshold = info->carThreshold[5] + oldCopNum;
	if(gang0Num != -1) info->gangThreshold[0] = info->copThreshold + gang0Num;
	else               info->gangThreshold[0] = info->copThreshold + oldGang0Num;
	if(gang1Num != -1) info->gangThreshold[1] = info->gangThreshold[0] + gang1Num;
	else               info->gangThreshold[1] = info->gangThreshold[0] + oldGang1Num;
	if(gang2Num != -1) info->gangThreshold[2] = info->gangThreshold[1] + gang2Num;
	else               info->gangThreshold[2] = info->gangThreshold[1] + oldGang2Num;
	if(gang3Num != -1) info->gangThreshold[3] = info->gangThreshold[2] + gang3Num;
	else               info->gangThreshold[3] = info->gangThreshold[2] + oldGang3Num;
	if(gang4Num != -1) info->gangThreshold[4] = info->gangThreshold[3] + gang4Num;
	else               info->gangThreshold[4] = info->gangThreshold[3] + oldGang4Num;
	if(gang5Num != -1) info->gangThreshold[5] = info->gangThreshold[4] + gang5Num;
	else               info->gangThreshold[5] = info->gangThreshold[4] + oldGang5Num;
	if(gang6Num != -1) info->gangThreshold[6] = info->gangThreshold[5] + gang6Num;
	else               info->gangThreshold[6] = info->gangThreshold[5] + oldGang6Num;
	if(gang7Num != -1) info->gangThreshold[7] = info->gangThreshold[6] + gang7Num;
	else               info->gangThreshold[7] = info->gangThreshold[6] + oldGang7Num;
	if(gang8Num != -1) info->gangThreshold[8] = info->gangThreshold[7] + gang8Num;
	else               info->gangThreshold[8] = info->gangThreshold[7] + oldGang8Num;

	CheckZoneInfo(info);
}

void
CTheZones::SetZonePedInfo(uint16 zoneid, uint8 day, int16 pedDensity,
	int16 gang0Density, int16 gang1Density, int16 gang2Density, int16 gang3Density,
	int16 gang4Density, int16 gang5Density, int16 gang6Density, int16 gang7Density,
	int16 gang8Density, int16 copDensity)
{
	CZone *zone;
	CZoneInfo *info;
	zone = GetZone(zoneid);
	info = &ZoneInfoArray[day ? zone->zoneinfoDay : zone->zoneinfoNight];
	if(pedDensity != -1) info->pedDensity = pedDensity;
	if(copDensity != -1) info->copDensity = copDensity;
	if(gang0Density != -1) info->gangDensity[0] = gang0Density;
	if(gang1Density != -1) info->gangDensity[1] = gang1Density;
	if(gang2Density != -1) info->gangDensity[2] = gang2Density;
	if(gang3Density != -1) info->gangDensity[3] = gang3Density;
	if(gang4Density != -1) info->gangDensity[4] = gang4Density;
	if(gang5Density != -1) info->gangDensity[5] = gang5Density;
	if(gang6Density != -1) info->gangDensity[6] = gang6Density;
	if(gang7Density != -1) info->gangDensity[7] = gang7Density;
	if(gang8Density != -1) info->gangDensity[8] = gang8Density;
}

void
CTheZones::SetCarDensity(uint16 zoneid, uint8 day, uint16 cardensity)
{
	CZone *zone;
	zone = GetZone(zoneid);
	if(IsNormalZone(zone->type))
		ZoneInfoArray[day ? zone->zoneinfoDay : zone->zoneinfoNight].carDensity = cardensity;
}

void
CTheZones::SetPedDensity(uint16 zoneid, uint8 day, uint16 peddensity)
{
	CZone *zone;
	zone = GetZone(zoneid);
	if(IsNormalZone(zone->type))
		ZoneInfoArray[day ? zone->zoneinfoDay : zone->zoneinfoNight].pedDensity = peddensity;
}

void
CTheZones::SetPedGroup(uint16 zoneid, uint8 day, uint16 pedgroup)
{
	CZone *zone;
	zone = GetZone(zoneid);
	if(IsNormalZone(zone->type))
		ZoneInfoArray[day ? zone->zoneinfoDay : zone->zoneinfoNight].pedGroup = pedgroup;
}

int16
CTheZones::FindAudioZone(CVector *pos)
{
	int i;

	for(i = 0; i < NumberOfAudioZones; i++)
		if(PointLiesWithinZone(pos, GetAudioZone(i)))
			return i;
	return -1;
}

eLevelName
CTheZones::FindZoneForPoint(const CVector &pos)
{
	if(PointLiesWithinZone(&pos, GetZone(FindZoneByLabelAndReturnIndex("IND_ZON"))))
		return LEVEL_INDUSTRIAL;
	if(PointLiesWithinZone(&pos, GetZone(FindZoneByLabelAndReturnIndex("COM_ZON"))))
		return LEVEL_COMMERCIAL;
	if(PointLiesWithinZone(&pos, GetZone(FindZoneByLabelAndReturnIndex("SUB_ZON"))))
		return LEVEL_SUBURBAN;
	return LEVEL_GENERIC;
}

void
CTheZones::AddZoneToAudioZoneArray(CZone *zone)
{
	int i, z;

	if(zone->type != ZONE_DEFAULT)
		return;

	/* This is a bit stupid */
	z = -1;
	for(i = 0; i < NUMZONES; i++)
		if(&ZoneArray[i] == zone)
			z = i;
	AudioZoneArray[NumberOfAudioZones++] = z;
}

void
CTheZones::InitialiseAudioZoneArray(void)
{
	bool gonext;
	CZone *zone;

	gonext = false;
	zone = &ZoneArray[0];
	// Go deep first,
	// set gonext when backing up a level to visit the next child
	while(zone)
		if(gonext){
			AddZoneToAudioZoneArray(zone);
			if(zone->next){
				gonext = false;
				zone = zone->next;
			}else
				zone = zone->parent;
		}else if(zone->child)
			zone = zone->child;
		else{
			AddZoneToAudioZoneArray(zone);
			if(zone->next)
				zone = zone->next;
			else{
				gonext = true;
				zone = zone->parent;
			}
		}
}

#ifdef COMPATIBLE_SAVES
static inline void
SaveOneZone(CZone &zone, uint8 *&buffer)
{
	memcpy(buffer, zone.name, sizeof(zone.name));
	SkipSaveBuf(buffer, sizeof(zone.name));
	WriteSaveBuf(buffer, zone.minx);
	WriteSaveBuf(buffer, zone.miny);
	WriteSaveBuf(buffer, zone.minz);
	WriteSaveBuf(buffer, zone.maxx);
	WriteSaveBuf(buffer, zone.maxy);
	WriteSaveBuf(buffer, zone.maxz);
	WriteSaveBuf(buffer, zone.type);
	WriteSaveBuf(buffer, zone.level);
	WriteSaveBuf(buffer, zone.zoneinfoDay);
	WriteSaveBuf(buffer, zone.zoneinfoNight);
	WriteSaveBuf(buffer, (int32)CTheZones::GetIndexForZonePointer(zone.child));
	WriteSaveBuf(buffer, (int32)CTheZones::GetIndexForZonePointer(zone.parent));
	WriteSaveBuf(buffer, (int32)CTheZones::GetIndexForZonePointer(zone.next));
}
#endif

void
CTheZones::SaveAllZones(uint8 *buffer, uint32 *size)
{
	INITSAVEBUF
	int i;

	*size = SAVE_HEADER_SIZE
		+ sizeof(int32) // GetIndexForZonePointer
		+ sizeof(m_CurrLevel) + sizeof(FindIndex)
		+ sizeof(int16) // padding
		+ ZONEARRAY_SAVE_SIZE + sizeof(ZoneInfoArray)
		+ sizeof(TotalNumberOfZones) + sizeof(TotalNumberOfZoneInfos)
		+ MAPZONEARRAY_SAVE_SIZE + sizeof(AudioZoneArray)
		+ sizeof(TotalNumberOfMapZones) + sizeof(NumberOfAudioZones);

	WriteSaveHeader(buffer, 'Z', 'N', 'S', '\0', *size - SAVE_HEADER_SIZE);

	WriteSaveBuf(buffer, (int32)GetIndexForZonePointer(m_pPlayersZone));
	WriteSaveBuf(buffer, m_CurrLevel);
	WriteSaveBuf(buffer, FindIndex);
	WriteSaveBuf(buffer, (int16)0); // padding

	for(i = 0; i < ARRAY_SIZE(ZoneArray); i++){
#ifdef COMPATIBLE_SAVES
		SaveOneZone(ZoneArray[i], buffer);
#else
		CZone *zone = WriteSaveBuf(buffer, ZoneArray[i]);
		zone->child = (CZone*)GetIndexForZonePointer(ZoneArray[i].child);
		zone->parent = (CZone*)GetIndexForZonePointer(ZoneArray[i].parent);
		zone->next = (CZone*)GetIndexForZonePointer(ZoneArray[i].next);
#endif
	}

	for(i = 0; i < ARRAY_SIZE(ZoneInfoArray); i++)
		WriteSaveBuf(buffer, ZoneInfoArray[i]);

	WriteSaveBuf(buffer, TotalNumberOfZones);
	WriteSaveBuf(buffer, TotalNumberOfZoneInfos);

	for(i = 0; i < ARRAY_SIZE(MapZoneArray); i++) {
#ifndef COMPATIBLE_SAVES
		CZone* zone = WriteSaveBuf(buffer, MapZoneArray[i]);
#endif

		/*
		The call of GetIndexForZonePointer is wrong, as it is
		meant for a different array, but the game doesn't brake
		if those fields are nil. Let's make sure they are.
		*/
		assert(MapZoneArray[i].child == nil);
		assert(MapZoneArray[i].parent == nil);
		assert(MapZoneArray[i].next == nil);
#ifndef COMPATIBLE_SAVES
		zone->child = (CZone*)GetIndexForZonePointer(MapZoneArray[i].child);
		zone->parent = (CZone*)GetIndexForZonePointer(MapZoneArray[i].parent);
		zone->next = (CZone*)GetIndexForZonePointer(MapZoneArray[i].next);
#else
		SaveOneZone(MapZoneArray[i], buffer);
#endif
	}

	for(i = 0; i < ARRAY_SIZE(AudioZoneArray); i++)
		WriteSaveBuf(buffer, AudioZoneArray[i]);

	WriteSaveBuf(buffer, TotalNumberOfMapZones);
	WriteSaveBuf(buffer, NumberOfAudioZones);

	VALIDATESAVEBUF(*size)
}

#ifdef COMPATIBLE_SAVES
static inline void
LoadOneZone(CZone &zone, uint8 *&buffer)
{
	memcpy(zone.name, buffer, sizeof(zone.name));
	SkipSaveBuf(buffer, sizeof(zone.name));
	ReadSaveBuf(&zone.minx, buffer);
	ReadSaveBuf(&zone.miny, buffer);
	ReadSaveBuf(&zone.minz, buffer);
	ReadSaveBuf(&zone.maxx, buffer);
	ReadSaveBuf(&zone.maxy, buffer);
	ReadSaveBuf(&zone.maxz, buffer);
	ReadSaveBuf(&zone.type, buffer);
	ReadSaveBuf(&zone.level, buffer);
	ReadSaveBuf(&zone.zoneinfoDay, buffer);
	ReadSaveBuf(&zone.zoneinfoNight, buffer);
	int32 tmp;
	ReadSaveBuf(&tmp, buffer);
	zone.child = CTheZones::GetPointerForZoneIndex(tmp);
	ReadSaveBuf(&tmp, buffer);
	zone.parent = CTheZones::GetPointerForZoneIndex(tmp);
	ReadSaveBuf(&tmp, buffer);
	zone.next = CTheZones::GetPointerForZoneIndex(tmp);
}
#endif

void
CTheZones::LoadAllZones(uint8 *buffer, uint32 size)
{
	INITSAVEBUF
	int32 i;

	CheckSaveHeader(buffer, 'Z', 'N', 'S', '\0', size - SAVE_HEADER_SIZE);

	ReadSaveBuf(&i, buffer);
	m_pPlayersZone = GetPointerForZoneIndex(i);
	ReadSaveBuf(&m_CurrLevel, buffer);
	ReadSaveBuf(&FindIndex, buffer);
	SkipSaveBuf(buffer, 2);

	for(i = 0; i < ARRAY_SIZE(ZoneArray); i++){
#ifdef COMPATIBLE_SAVES
		LoadOneZone(ZoneArray[i], buffer);
#else
		ReadSaveBuf(&ZoneArray[i], buffer);

		ZoneArray[i].child = GetPointerForZoneIndex((uintptr)ZoneArray[i].child);
		ZoneArray[i].parent = GetPointerForZoneIndex((uintptr)ZoneArray[i].parent);
		ZoneArray[i].next = GetPointerForZoneIndex((uintptr)ZoneArray[i].next);
#endif
	}

	for(i = 0; i < ARRAY_SIZE(ZoneInfoArray); i++)
		ReadSaveBuf(&ZoneInfoArray[i], buffer);

	ReadSaveBuf(&TotalNumberOfZones, buffer);
	ReadSaveBuf(&TotalNumberOfZoneInfos, buffer);

	for(i = 0; i < ARRAY_SIZE(MapZoneArray); i++){
#ifdef COMPATIBLE_SAVES
		LoadOneZone(MapZoneArray[i], buffer);
#else
		ReadSaveBuf(&MapZoneArray[i], buffer);

		/*
		The call of GetPointerForZoneIndex is wrong, as it is
		meant for a different array, but the game doesn't brake
		if save data stored is -1.
		*/
		MapZoneArray[i].child = GetPointerForZoneIndex((uintptr)MapZoneArray[i].child);
		MapZoneArray[i].parent = GetPointerForZoneIndex((uintptr)MapZoneArray[i].parent);
		MapZoneArray[i].next = GetPointerForZoneIndex((uintptr)MapZoneArray[i].next);
#endif
		assert(MapZoneArray[i].child == nil);
		assert(MapZoneArray[i].parent == nil);
		assert(MapZoneArray[i].next == nil);
	}

	for(i = 0; i < ARRAY_SIZE(AudioZoneArray); i++)
		ReadSaveBuf(&AudioZoneArray[i], buffer);

	ReadSaveBuf(&TotalNumberOfMapZones, buffer);
	ReadSaveBuf(&NumberOfAudioZones, buffer);

	VALIDATESAVEBUF(size)
}


code:
#pragma once

#include "Game.h"
#include "Gangs.h"

enum eZoneType
{
	ZONE_DEFAULT,
	ZONE_NAVIG,
	ZONE_INFO,
	ZONE_MAPZONE,
};

class CZone
{
public:
	char       name[8];
	float      minx;
	float      miny;
	float      minz;
	float      maxx;
	float      maxy;
	float      maxz;
	eZoneType  type;
	eLevelName level;
	int16      zoneinfoDay;
	int16      zoneinfoNight;
	CZone     *child;
	CZone     *parent;
	CZone     *next;

	wchar *GetTranslatedName(void);
};

class CZoneInfo
{
public:
	// Car data
	int16 carDensity;
	int16 carThreshold[6];
	int16 copThreshold;
	int16 gangThreshold[NUM_GANGS];

	// Ped data
	uint16 pedDensity;
	uint16 copDensity;
	uint16 gangDensity[NUM_GANGS];
	uint16 pedGroup;
};

class CTheZones
{
	static CZone *m_pPlayersZone;
	static int16 FindIndex;

	static uint16 NumberOfAudioZones;
	static int16 AudioZoneArray[NUMAUDIOZONES];
	static uint16 TotalNumberOfMapZones;
	static uint16 TotalNumberOfZones;
	static CZone ZoneArray[NUMZONES];
	static CZone MapZoneArray[NUMMAPZONES];
	static uint16 TotalNumberOfZoneInfos;
	static CZoneInfo ZoneInfoArray[2*NUMZONES];
public:
	static eLevelName m_CurrLevel;

	static void Init(void);
	static void Update(void);
	static void CreateZone(char *name, eZoneType type,
	                       float minx, float miny, float minz,
	                       float maxx, float maxy, float maxz,
	                       eLevelName level);
	static void CreateMapZone(char *name, eZoneType type,
	                          float minx, float miny, float minz,
	                          float maxx, float maxy, float maxz,
	                          eLevelName level);
	static CZone *GetZone(uint16 i) { return &ZoneArray[i]; }
	static CZone *GetAudioZone(uint16 i) { return &ZoneArray[AudioZoneArray[i]]; }
	static void PostZoneCreation(void);
	static void InsertZoneIntoZoneHierarchy(CZone *zone);
	static bool InsertZoneIntoZoneHierRecursive(CZone *z1, CZone *z2);
	static bool ZoneIsEntirelyContainedWithinOtherZone(CZone *z1, CZone *z2);
	static bool PointLiesWithinZone(const CVector *v, CZone *zone);
	static eLevelName GetLevelFromPosition(const CVector *v);
	static CZone *FindSmallestZonePosition(const CVector *v);
	static CZone *FindSmallestZonePositionType(const CVector *v, eZoneType type);
	static CZone *FindSmallestZonePositionILN(const CVector *v);
	static int16 FindZoneByLabelAndReturnIndex(Const char *name);
	static CZoneInfo *GetZoneInfo(const CVector *v, uint8 day);
	static void GetZoneInfoForTimeOfDay(const CVector *pos, CZoneInfo *info);
	static void SetZoneCarInfo(uint16 zoneid, uint8 day, int16 carDensity,
		int16 gang0Num, int16 gang1Num, int16 gang2Num,
		int16 gang3Num, int16 gang4Num, int16 gang5Num,
		int16 gang6Num, int16 gang7Num, int16 gang8Num,
		int16 copNum,
		int16 car0Num, int16 car1Num, int16 car2Num,
		int16 car3Num, int16 car4Num, int16 car5Num);
	static void SetZonePedInfo(uint16 zoneid, uint8 day, int16 pedDensity,
		int16 gang0Density, int16 gang1Density, int16 gang2Density, int16 gang3Density,
		int16 gang4Density, int16 gang5Density, int16 gang6Density, int16 gang7Density,
		int16 gang8Density, int16 copDensity);
	static void SetCarDensity(uint16 zoneid, uint8 day, uint16 cardensity);
	static void SetPedDensity(uint16 zoneid, uint8 day, uint16 peddensity);
	static void SetPedGroup(uint16 zoneid, uint8 day, uint16 pedgroup);
	static int16 FindAudioZone(CVector *pos);
	static eLevelName FindZoneForPoint(const CVector &pos);
	static CZone *GetPointerForZoneIndex(ssize_t i) { return i == -1 ? nil : &ZoneArray[i]; }
	static ssize_t GetIndexForZonePointer(CZone *zone) { return zone == nil ? -1 : zone - ZoneArray; }
	static void AddZoneToAudioZoneArray(CZone *zone);
	static void InitialiseAudioZoneArray(void);
	static void SaveAllZones(uint8 *buffer, uint32 *length);
	static void LoadAllZones(uint8 *buffer, uint32 length);
};


code:
#pragma once

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma warning(disable: 4244)	// int to float
#pragma warning(disable: 4800)	// int to bool
#pragma warning(disable: 4838)  // narrowing conversion
#pragma warning(disable: 4996)  // POSIX names

#ifdef __MWERKS__
#define __STDC_LIMIT_MACROS // so we get UINT32_MAX etc
#endif

#ifdef __SWITCH__
#include <switch.h>
#endif

#include <stdint.h>
#include <string.h>
#include <math.h>

#ifdef __MWERKS__
#define AUDIO_MSS
#define RWLIBS // codewarrior doesn't support project level defines - so not even this is enough, but still catches most ifdefs
#endif

#if !defined RW_D3D9 && defined LIBRW
#undef WITHD3D
#undef WITHDINPUT
#endif

#if (defined WITHD3D && !defined LIBRW)
#define WITHWINDOWS
#endif

#if defined _WIN32 && defined WITHWINDOWS && !defined _INC_WINDOWS
#include <windows.h>
#endif

#ifdef WITHD3D
	#ifdef LIBRW
		#define WITH_D3D // librw includes d3d9 itself via this right now
	#else
		#ifndef USE_D3D9
		#include <d3d8.h>
		#else
		#include <d3d9.h>
		#endif
	#endif
#endif

#ifdef WITHDINPUT
#define DIRECTINPUT_VERSION 0x0800
#include <dinput.h>
#endif

#include <rwcore.h>
#include <rpworld.h>

// gotta put this somewhere
#ifdef LIBRW
#define STREAMPOS(str) ((str)->tell())
#define STREAMFILE(str) (((rw::StreamFile*)(str))->file)
#define HIERNODEINFO(hier) ((hier)->nodeInfo)
#define HIERNODEID(hier, i) ((hier)->nodeInfo[i].id)
#define HANIMFRAME(anim, i) ((RwUInt8*)(anim)->keyframes + (i)*(anim)->interpInfo->animKeyFrameSize)
#else
#define RWHALFPIXEL	// always d3d
#define STREAMPOS(str) ((str)->Type.memory.position)
#define STREAMFILE(str) ((str)->Type.file.fpFile)
#define HIERNODEINFO(hier) ((hier)->pNodeInfo)
#define HIERNODEID(hier, i) ((hier)->pNodeInfo[i].nodeID)
#define HANIMFRAME(anim, i) ((RwUInt8*)(anim)->pFrames + (i)*(anim)->interpInfo->keyFrameSize)
#define RpHAnimStdInterpFrame RpHAnimStdKeyFrame
#endif

#ifdef RWHALFPIXEL
#define HALFPX (0.5f)
#else
#define HALFPX (0.0f)
#endif

#define rwVENDORID_ROCKSTAR 0x0253F2

#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))

// Use this to add const that wasn't there in the original code
#define Const const

typedef uint8_t uint8;
typedef int8_t int8;
typedef uint16_t uint16;
typedef int16_t int16;
#ifndef __MWERKS__
typedef uint32_t uint32;
typedef int32_t int32;
#else
typedef unsigned int uint32;
typedef int int32;
#endif
typedef uintptr_t uintptr;
typedef intptr_t intptr;
typedef uint64_t uint64;
typedef int64_t int64;
// hardcode ucs-2
typedef uint16_t wchar;

typedef uint8 bool8;
typedef uint16 bool16;
typedef uint32 bool32;

#if defined(_MSC_VER) || defined (__MWERKS__)
typedef ptrdiff_t ssize_t;
#endif

#ifndef nil
#define nil NULL
#endif

#include "config.h"

#ifdef PED_SKIN
#include <rphanim.h>
#include <rpskin.h>
#endif

#ifdef __GNUC__
#define TYPEALIGN(n) __attribute__ ((aligned (n)))
#else
#ifdef _MSC_VER
#define TYPEALIGN(n) __declspec(align(n))
#else
#define TYPEALIGN(n)	// unknown compiler...ignore
#endif
#endif

#define ALIGNPTR(p) (void*)((((uintptr)(void*)p) + sizeof(void*)-1) & ~(sizeof(void*)-1))

// PDP-10 like byte functions
#define MASK(p, s) (((1<<(s))-1) << (p))
inline uint32 dpb(uint32 b, uint32 p, uint32 s, uint32 w)
{
	uint32 m = MASK(p,s);
	return (w & ~m) | ((b<<p) & m);
}
inline uint32 ldb(uint32 p, uint32 s, uint32 w)
{
	return w>>p & (1<<s)-1;
}

#include "skeleton.h"
#include "Draw.h"

#if defined(PROPER_SCALING) || defined(PS2_HUD)
	#ifdef FORCE_PC_SCALING
		#define DEFAULT_SCREEN_WIDTH  (640)
		#define DEFAULT_SCREEN_HEIGHT (448)
	#else
		#define DEFAULT_SCREEN_WIDTH  (640)
		#define DEFAULT_SCREEN_HEIGHT (480)
	#endif
#elif defined(GTA_PS2)
		#define DEFAULT_SCREEN_WIDTH  (640)
		#define DEFAULT_SCREEN_HEIGHT (480)
#else //elif defined(GTA_PC)
		#define DEFAULT_SCREEN_WIDTH  (640)
		#define DEFAULT_SCREEN_HEIGHT (448)
#endif

#define DEFAULT_ASPECT_RATIO (4.0f/3.0f)
#define DEFAULT_VIEWWINDOW (0.7f)

// game uses maximumWidth/Height, but this probably won't work
// with RW windowed mode
#ifdef GTA_PS2
	#ifdef GTA_PAL
		#define SCREEN_WIDTH  ((float)640)
		#define SCREEN_HEIGHT ((float)512)
	#else
		#define SCREEN_WIDTH  ((float)640)
		#define SCREEN_HEIGHT ((float)448)
	#endif
#else
#define SCREEN_WIDTH  ((float)RsGlobal.width)
#define SCREEN_HEIGHT ((float)RsGlobal.height)
#endif

#define SCREEN_HEIGHT_PAL ((float)512)
#define SCREEN_HEIGHT_NTSC ((float)448)

#define SCREEN_ASPECT_RATIO (CDraw::GetAspectRatio())
#define SCREEN_VIEWWINDOW (Tan(DEGTORAD(CDraw::GetScaledFOV() * 0.5f)))

// This scales from PS2 pixel coordinates to the real resolution
#define SCREEN_STRETCH_X(a)   ((a) * (float) SCREEN_WIDTH / DEFAULT_SCREEN_WIDTH)
#define SCREEN_STRETCH_Y(a)   ((a) * (float) SCREEN_HEIGHT / DEFAULT_SCREEN_HEIGHT)
#define SCREEN_STRETCH_FROM_RIGHT(a)  (SCREEN_WIDTH - SCREEN_STRETCH_X(a))
#define SCREEN_STRETCH_FROM_BOTTOM(a) (SCREEN_HEIGHT - SCREEN_STRETCH_Y(a))

// This scales from PS2 pixel coordinates while optionally maintaining the aspect ratio
#define SCREEN_SCALE_X(a) SCREEN_SCALE_AR(SCREEN_STRETCH_X(a))
#define SCREEN_SCALE_Y(a) SCREEN_STRETCH_Y(a)
#define SCREEN_SCALE_FROM_RIGHT(a) (SCREEN_WIDTH - SCREEN_SCALE_X(a))
#define SCREEN_SCALE_FROM_BOTTOM(a) (SCREEN_HEIGHT - SCREEN_SCALE_Y(a))

#ifdef ASPECT_RATIO_SCALE
#define SCREEN_SCALE_AR(a) ((a) * DEFAULT_ASPECT_RATIO / SCREEN_ASPECT_RATIO)
#define SCALE_AND_CENTER_X(x) ((SCREEN_WIDTH == DEFAULT_SCREEN_WIDTH) ? (x) : (SCREEN_WIDTH - SCREEN_SCALE_X(DEFAULT_SCREEN_WIDTH)) / 2 + SCREEN_SCALE_X((x)))
#ifdef PROPER_SCALING
	#ifndef FORCE_PC_SCALING
		#undef SCREEN_SCALE_Y
		#define SCREEN_SCALE_Y(a) CDraw::ScaleY(SCREEN_STRETCH_Y(a))
	#endif
#endif
#else
#define SCREEN_SCALE_AR(a) (a)
#define SCALE_AND_CENTER_X(x) SCREEN_STRETCH_X(x)
#endif

#include "maths.h"
#include "Vector.h"
#ifdef GTA_PS2
#include "VuVector.h"
#define CVUVECTOR CVuVector
#else
#define CVUVECTOR CVector
#endif
#include "Vector2D.h"
#include "Matrix.h"
#include "Rect.h"

class CRGBA
{
public:
	union
	{
	    uint32 color32;
		struct { uint8 r, g, b, a; };
		struct { uint8 red, green, blue, alpha; };
#ifdef RWCORE_H
		struct  { RwRGBA rwRGBA; };
#endif
	};

	CRGBA(void) { }
	CRGBA(uint8 r, uint8 g, uint8 b, uint8 a) : r(r), g(g), b(b), a(a) { }

	bool operator ==(const CRGBA &right)
	{
		return this->r == right.r && this->g == right.g && this->b == right.b && this->a == right.a;
	}

	bool operator !=(const CRGBA &right)
	{
		return !(*this == right);
	}

	CRGBA &operator =(const CRGBA &right)
	{
		this->r = right.r;
		this->g = right.g;
		this->b = right.b;
		this->a = right.a;
		return *this;
	}
#ifdef RWCORE_H
	operator RwRGBA &(void) {
		return rwRGBA;
	}

	operator RwRGBA *(void) {
		return &rwRGBA;
	}

	operator RwRGBA (void) const {
		return rwRGBA;
	}

	CRGBA &operator =(const RwRGBA &right)
	{
		this->r = right.red;
		this->g = right.green;
		this->b = right.blue;
		this->a = right.alpha;
		return *this;
	}
#endif
};

#if (defined(_MSC_VER))
extern int strcasecmp(const char *str1, const char *str2);
#endif

extern wchar *AllocUnicode(const char*src);

#define Clamp(v, low, high) ((v)<(low) ? (low) : (v)>(high) ? (high) : (v))

#define Clamp2(v, center, radius) ((v) > (center) ? Min(v, center + radius) : Max(v, center - radius))

inline float sq(float x) { return x*x; }
#define SQR(x) ((x) * (x))

#ifdef __MWERKS__
#define M_E        2.71828182845904523536   // e
#define M_LOG2E    1.44269504088896340736   // log2(e)
#define M_LOG10E   0.434294481903251827651  // log10(e)
#define M_LN2      0.693147180559945309417  // ln(2)
#define M_LN10     2.30258509299404568402   // ln(10)
#define M_PI       3.14159265358979323846   // pi
#define M_PI_2     1.57079632679489661923   // pi/2
#define M_PI_4     0.785398163397448309616  // pi/4
#define M_1_PI     0.318309886183790671538  // 1/pi
#define M_2_PI     0.636619772367581343076  // 2/pi
#define M_2_SQRTPI 1.12837916709551257390   // 2/sqrt(pi)
#define M_SQRT2    1.41421356237309504880   // sqrt(2)
#define M_SQRT1_2  0.707106781186547524401  // 1/sqrt(2)
#endif

#define PI (float)M_PI
#define TWOPI (PI*2)
#define HALFPI (PI/2)
#define DEGTORAD(x) ((x) * PI / 180.0f)
#define RADTODEG(x) ((x) * 180.0f / PI)

#ifdef USE_PS2_RAND
#define MYRAND_MAX		65535
#else
#define MYRAND_MAX		32767
#endif

int myrand(void);
void mysrand(unsigned int seed);

void re3_debug(const char *format, ...);
void re3_trace(const char *filename, unsigned int lineno, const char *func, const char *format, ...);
void re3_assert(const char *expr, const char *filename, unsigned int lineno, const char *func);
void re3_usererror(const char *format, ...);

#define DEBUGBREAK() __debugbreak();

// Switch to enable development messages.
#if 1
#define DEV(f, ...)
#else
#define DEV(f, ...)   re3_debug("[DEV]: " f, ## __VA_ARGS__)
#endif

#ifdef __MWERKS__
void debug(char *f, ...);
void Error(char *f, ...);
__inline__ void TRACE(char *f, ...) { } // this is re3 only, and so the function needs to be inline - this way no call actually gets placed
// USERERROR only gets used in oal builds ... once
#else
#define debug(f, ...) re3_debug("[DBG]: " f, ## __VA_ARGS__)
#define Error(f, ...) re3_debug("[ERROR]: " f, ## __VA_ARGS__)
#ifndef MASTER
#define TRACE(f, ...) re3_trace(__FILE__, __LINE__, __FUNCTION__, f, ## __VA_ARGS__)
#define USERERROR(f, ...) re3_usererror(f, ## __VA_ARGS__)
#else
#define TRACE(f, ...)
#define USERERROR(f, ...)
#endif
#endif

#ifndef MASTER
#define assert(_Expression) (void)( (!!(_Expression)) || (re3_assert(#_Expression, __FILE__, __LINE__, __FUNCTION__), 0) )
#else
#define assert(_Expression) (_Expression)
#endif
#define ASSERT assert

#ifdef __MWERKS__
#define static_assert(bool_constexpr, message)
#endif

#define _TODO(x)
#define _TODOCONST(x) (x)

#ifdef CHECK_STRUCT_SIZES
template<int s, int t> struct check_size {
	static_assert(s == t, "Invalid structure size");
};
#define VALIDATE_SIZE(struc, size) check_size<sizeof(struc), size> struc ## Check
#else
#define VALIDATE_SIZE(struc, size)
#endif
#define VALIDATE_OFFSET(struc, member, offset) static_assert(offsetof(struc, member) == offset, "The offset of " #member " in " #struc " is not " #offset "...")

#define PERCENT(x, p)                    ((float(x) * (float(p) / 100.0f)))
#define ARRAY_SIZE(array)                (sizeof(array) / sizeof(array[0]))
#define BIT(num)                         (1<<(num))

#define ABS(a)  (((a) < 0) ? (-(a)) : (a))
#define norm(value, min, max) (((value) < (min)) ? 0 : (((value) > (max)) ? 1 : (((value) - (min)) / ((max) - (min)))))
#define lerp(norm, min, max) ( (norm) * ((max) - (min)) + (min) )

#define STRINGIFY(x)                    #x
#define STR(x)                          STRINGIFY(x)
#define CONCAT_(x,y) x##y
#define CONCAT(x,y) CONCAT_(x,y)