pathestimator.cpp

来自「这是整套横扫千军3D版游戏的源码」· C++ 代码 · 共 895 行 · 第 1/2 页

#include "StdAfx.h"
#include "PathEstimator.h"
#include "LogOutput.h"
#include "Rendering/GL/myGL.h"
#include "FileSystem/FileHandler.h"
#include <fstream>
#include <memory>
#ifndef _WIN32
#include <stdlib.h>
#include <sys/stat.h>
#endif
#include "Map/Ground.h"
#include "Game/SelectedUnits.h"
#include "Sim/Units/Unit.h"
#include "Sim/Units/UnitDef.h"
#include "Rendering/glFont.h"
#include "Game/Camera.h"
#include "TimeProfiler.h"
#include "Platform/FileSystem.h"

#include "lib/minizip/zip.h"
#include "FileSystem/ArchiveZip.h"

#include "mmgr.h"

#define PATHDEBUG false


const unsigned int PATHDIR_LEFT = 0;		//+x
const unsigned int PATHDIR_LEFT_UP = 1;		//+x+z
const unsigned int PATHDIR_UP = 2;			//+z
const unsigned int PATHDIR_RIGHT_UP = 3;	//-x+z
const unsigned int PATHDIR_RIGHT = 4;		//-x
const unsigned int PATHDIR_RIGHT_DOWN = 5;	//-x-z
const unsigned int PATHDIR_DOWN = 6;		//-z
const unsigned int PATHDIR_LEFT_DOWN = 7;	//+x-z

const unsigned int PATHOPT_OPEN = 8;
const unsigned int PATHOPT_CLOSED = 16;
const unsigned int PATHOPT_FORBIDDEN = 32;
const unsigned int PATHOPT_BLOCKED = 64;
const unsigned int PATHOPT_SEARCHRELATED = (PATHOPT_OPEN | PATHOPT_CLOSED | PATHOPT_FORBIDDEN | PATHOPT_BLOCKED);
const unsigned int PATHOPT_OBSOLETE = 128;

const unsigned int PATHESTIMATOR_VERSION = 34;

const float PATHCOST_INFINITY = 10000000;

const int SQUARES_TO_UPDATE = 600;


extern string stupidGlobalMapname;


/*
Constructor.
Loading precalculated data.
*/
CPathEstimator::CPathEstimator(CPathFinder* pf, unsigned int BSIZE, unsigned int mmOpt, string name) :
pathFinder(pf),
BLOCK_SIZE(BSIZE),
BLOCK_PIXEL_SIZE(BSIZE * SQUARE_SIZE),
BLOCKS_TO_UPDATE(SQUARES_TO_UPDATE / (BLOCK_SIZE * BLOCK_SIZE) + 1),
moveMathOptions(mmOpt)
{
	//Gives the changes in (x,z) when moved one step in given direction.
	//(Need to be placed befor pre-calculations)
	directionVector[PATHDIR_LEFT].x = 1;
	directionVector[PATHDIR_LEFT].y = 0;
	directionVector[PATHDIR_LEFT_UP].x = 1;
	directionVector[PATHDIR_LEFT_UP].y = 1;
	directionVector[PATHDIR_UP].x = 0;
	directionVector[PATHDIR_UP].y = 1;
	directionVector[PATHDIR_RIGHT_UP].x = -1;
	directionVector[PATHDIR_RIGHT_UP].y = 1;
	directionVector[PATHDIR_RIGHT].x = -1;
	directionVector[PATHDIR_RIGHT].y = 0;
	directionVector[PATHDIR_RIGHT_DOWN].x = -1;
	directionVector[PATHDIR_RIGHT_DOWN].y = -1;
	directionVector[PATHDIR_DOWN].x = 0;
	directionVector[PATHDIR_DOWN].y = -1;
	directionVector[PATHDIR_LEFT_DOWN].x = 1;
	directionVector[PATHDIR_LEFT_DOWN].y = -1;

	goalSqrOffset.x=BLOCK_SIZE/2;
	goalSqrOffset.y=BLOCK_SIZE/2;

	//Creates the block-map and the vertices-map.
	nbrOfBlocksX = gs->mapx / BLOCK_SIZE;
	nbrOfBlocksZ = gs->mapy / BLOCK_SIZE;
	nbrOfBlocks = nbrOfBlocksX * nbrOfBlocksZ;

	blockState = SAFE_NEW BlockInfo[nbrOfBlocks];
	nbrOfVertices = moveinfo->moveData.size() * nbrOfBlocks * PATH_DIRECTION_VERTICES;
	vertex = SAFE_NEW float[nbrOfVertices];
	openBlockBufferPointer=openBlockBuffer;

	int i;
	for(i = 0; i < nbrOfVertices; i++)
		vertex[i] = PATHCOST_INFINITY;

	//Initialize blocks.
	int x, z;
	for(z = 0; z < nbrOfBlocksZ; z++){
		for(x = 0; x < nbrOfBlocksX; x++) {
			int blocknr = z * nbrOfBlocksX + x;
			blockState[blocknr].cost = PATHCOST_INFINITY;
			blockState[blocknr].options = 0;
			blockState[blocknr].parentBlock.x = -1;
			blockState[blocknr].parentBlock.y = -1;
			blockState[blocknr].sqrCenter = SAFE_NEW int2[moveinfo->moveData.size()];
		}
	}

	//Pre-read/calculate data.
	PrintLoadMsg("Reading estimate path costs");
	if(!ReadFile(name)) {
		//Generate text-message.
		char calcMsg[1000], buffer[10];
		strcpy(calcMsg, "Analyzing map accessability \"");
		SNPRINTF(buffer,10,"%d",BLOCK_SIZE);
		strcat(calcMsg, buffer);
		strcat(calcMsg, "\"");
		PrintLoadMsg(calcMsg);
		//Calculating block-center-offsets.
		for(z = 0; z < nbrOfBlocksZ; z++) {
			for(x = 0; x < nbrOfBlocksX; x++) {
				vector<MoveData*>::iterator mi;
				for(mi = moveinfo->moveData.begin(); mi < moveinfo->moveData.end(); mi++) {
					FindOffset(**mi, x, z);
				}
			}
		}

		//Calculating vectors.
		vector<MoveData*>::iterator mi;
		for(mi = moveinfo->moveData.begin(); mi < moveinfo->moveData.end(); mi++) {
			//Generate text-message.
			char calcMsg[10000];
			sprintf(calcMsg,"Calculating estimate path costs \"%i\" %i/%i",BLOCK_SIZE,(*mi)->pathType,moveinfo->moveData.size());
			PrintLoadMsg(calcMsg);
			//Calculate
			for(z = 0; z < nbrOfBlocksZ; z++) {
				for(x = 0; x < nbrOfBlocksX; x++) {
					CalculateVertices(**mi, x, z);
				}
			}
		}
		WriteFile(name);
	}

	//As all vertexes are bidirectional and having equal values
	//in both directions, only one value are needed to be stored.
	//This vector helps getting the right vertex.
	//(Need to be placed after pre-calculations)
	directionVertex[PATHDIR_LEFT] = PATHDIR_LEFT;
	directionVertex[PATHDIR_LEFT_UP] = PATHDIR_LEFT_UP;
	directionVertex[PATHDIR_UP] = PATHDIR_UP;
	directionVertex[PATHDIR_RIGHT_UP] = PATHDIR_RIGHT_UP;
	directionVertex[PATHDIR_RIGHT] = int(PATHDIR_LEFT) - PATH_DIRECTION_VERTICES;
	directionVertex[PATHDIR_RIGHT_DOWN] = int(PATHDIR_LEFT_UP) - (nbrOfBlocksX * PATH_DIRECTION_VERTICES) - PATH_DIRECTION_VERTICES;
	directionVertex[PATHDIR_DOWN] = int(PATHDIR_UP) - (nbrOfBlocksX * PATH_DIRECTION_VERTICES);
	directionVertex[PATHDIR_LEFT_DOWN] = int(PATHDIR_RIGHT_UP) - (nbrOfBlocksX * PATH_DIRECTION_VERTICES) + PATH_DIRECTION_VERTICES;

	pathCache=SAFE_NEW CPathCache(nbrOfBlocksX,nbrOfBlocksZ);
}


/*
Destructor
Free all used memory.
*/
CPathEstimator::~CPathEstimator() {
	int i;
	for(i = 0; i < nbrOfBlocks; i++) {
		delete[] blockState[i].sqrCenter;
	}
	delete[] blockState;
	delete[] vertex;
	delete pathCache;
}

/*
Finds a square accessable by the given movedata within the given block.
*/
void CPathEstimator::FindOffset(const MoveData& moveData, int blockX, int blockZ) {
	//Block lower corner position.
	int lowerX = blockX * BLOCK_SIZE;
	int lowerZ = blockZ * BLOCK_SIZE;

	//Search for an accessable position.
	float best=100000000;
	int bestX=BLOCK_SIZE/2;
	int bestZ=BLOCK_SIZE/2;

	int x, z;
	for(z = 1; z < BLOCK_SIZE; z += 2){
		for(x = 1; x < BLOCK_SIZE; x += 2) {
			int dx=x-BLOCK_SIZE/2;
			int dz=z-BLOCK_SIZE/2;
			float cost=dx*dx+dz*dz+(BLOCK_SIZE*BLOCK_SIZE/8)/(0.001f+moveData.moveMath->SpeedMod(moveData, lowerX+x, lowerZ+z));
			if(moveData.moveMath->IsBlocked2(moveData, lowerX+x, lowerZ+z) & (CMoveMath::BLOCK_STRUCTURE | CMoveMath::BLOCK_TERRAIN))
				cost+=1000000;
			if(cost<best){
				best=cost;
				bestX=x;
				bestZ=z;
			}
		}
	}

	//Store the offset found.
	blockState[blockZ * nbrOfBlocksX + blockX].sqrCenter[moveData.pathType].x = blockX * BLOCK_SIZE + bestX;
	blockState[blockZ * nbrOfBlocksX + blockX].sqrCenter[moveData.pathType].y = blockZ * BLOCK_SIZE + bestZ;
}


/*
Calculate all vertices connected from given block.
(Which is 4 out of 8 vertices connected to the block.)
*/
void CPathEstimator::CalculateVertices(const MoveData& moveData, int blockX, int blockZ) {
	unsigned int dir;
	for(dir = 0; dir < PATH_DIRECTION_VERTICES; dir++)
		CalculateVertex(moveData, blockX, blockZ, dir);
}


/*
Calculate requested vertex.
*/
void CPathEstimator::CalculateVertex(const MoveData& moveData, int parentBlockX, int parentBlockZ, unsigned int direction) {
	//Initial calculations.
	int parentBlocknr = parentBlockZ * nbrOfBlocksX + parentBlockX;
	int childBlockX = parentBlockX + directionVector[direction].x;
	int childBlockZ = parentBlockZ + directionVector[direction].y;
	int vertexNbr = moveData.pathType * nbrOfBlocks * PATH_DIRECTION_VERTICES + parentBlocknr * PATH_DIRECTION_VERTICES + direction;

	//Outside map?
	if(childBlockX < 0 || childBlockZ < 0
	|| childBlockX >= nbrOfBlocksX || childBlockZ >= nbrOfBlocksZ) {
		vertex[vertexNbr] = PATHCOST_INFINITY;
		return;
	}

	//Starting position.
	int parentXSquare = blockState[parentBlocknr].sqrCenter[moveData.pathType].x;
	int parentZSquare = blockState[parentBlocknr].sqrCenter[moveData.pathType].y;
	float3 startPos = SquareToFloat3(parentXSquare, parentZSquare);

	//Goal position.
	int childBlocknr = childBlockZ * nbrOfBlocksX + childBlockX;
	int childXSquare = blockState[childBlocknr].sqrCenter[moveData.pathType].x;
	int childZSquare = blockState[childBlocknr].sqrCenter[moveData.pathType].y;
	float3 goalPos = SquareToFloat3(childXSquare, childZSquare);

	//PathFinder definiton.
	CRangedGoalWithCircularConstraint pfDef(startPos, goalPos, 0, 1.1f,2);

	//Path
	Path path;

	//Performs the search.
	SearchResult result = pathFinder->GetPath(moveData, startPos, pfDef, path, false, true,10000,false);

	//Store the result.
	if(result == Ok) {
		vertex[vertexNbr] = path.pathCost;
	} else {
		vertex[vertexNbr] = PATHCOST_INFINITY;
	}
}


/*
Mark affected blocks as obsolete.
*/
void CPathEstimator::MapChanged(unsigned int x1, unsigned int z1, unsigned int x2, unsigned z2) {
	//Finding the upper and lower corner of the rectangular area.
	int lowerX, upperX, lowerZ, upperZ;
	if(x1 < x2) {
		lowerX = x1 / BLOCK_SIZE-1;
		upperX = x2 / BLOCK_SIZE;
	} else {
		lowerX = x2 / BLOCK_SIZE-1;
		upperX = x1 / BLOCK_SIZE;
	}
	if(z1 < z2) {
		lowerZ = z1 / BLOCK_SIZE-1;
		upperZ = z2 / BLOCK_SIZE;
	} else {
		lowerZ = z2 / BLOCK_SIZE-1;
		upperZ = z1 / BLOCK_SIZE;
	}

	//Error-check.
	upperX = min(upperX, nbrOfBlocksX - 1);
	upperZ = min(upperZ, nbrOfBlocksZ - 1);
	if(lowerX<0) lowerX=0;
	if(lowerZ<0) lowerZ=0;

	//Marking the blocks inside the rectangle.
	//Enqueing them from upper to lower becourse of
	//the placement of the bi-directional vertices.
	for(int z = upperZ; z >= lowerZ; z--){
		for(int x = upperX; x >= lowerX; x--) {
			if(!(blockState[z * nbrOfBlocksX + x].options & PATHOPT_OBSOLETE)){
				vector<MoveData*>::iterator mi;
				for(mi = moveinfo->moveData.begin(); mi < moveinfo->moveData.end(); mi++) {
					SingleBlock sb;
					sb.block.x = x;
					sb.block.y = z;
					sb.moveData = *mi;
					needUpdate.push_back(sb);
					blockState[z * nbrOfBlocksX + x].options |= PATHOPT_OBSOLETE;
				}
			}
		}
	}
}


/*
Updating some obsolete blocks.
Using FIFO-principle.
*/
void CPathEstimator::Update() {
	pathCache->Update();
	int counter = 0;
	while(!needUpdate.empty() && counter < BLOCKS_TO_UPDATE) {
		//Next block in line.
		SingleBlock sb = needUpdate.front();
		needUpdate.pop_front();
		int blocknr = sb.block.y * nbrOfBlocksX + sb.block.x;

		//Check if already updated.
		if(!(blockState[blocknr].options & PATHOPT_OBSOLETE))
			continue;

		//Update the block.
		FindOffset(*sb.moveData, sb.block.x, sb.block.y);
		CalculateVertices(*sb.moveData, sb.block.x, sb.block.y);

		//Mark as updated.
		if(sb.moveData==moveinfo->moveData.back()){
			blockState[blocknr].options &= ~PATHOPT_OBSOLETE;
		}

		//One block updated.
		counter++;
	}
}


/*
Storing data and doing some top-administration.
*/
IPath::SearchResult CPathEstimator::GetPath(const MoveData& moveData, float3 start, const CPathFinderDef& peDef, Path& path, unsigned int maxSearchedBlocks) {
	start.CheckInBounds();
	//Clear path.
	path.path.clear();
	path.pathCost = PATHCOST_INFINITY;

	//Initial calculations.
	maxBlocksToBeSearched = std::min(maxSearchedBlocks, (unsigned int) MAX_SEARCHED_BLOCKS);
	startBlock.x = (int)(start.x / BLOCK_PIXEL_SIZE);
	startBlock.y = (int)(start.z / BLOCK_PIXEL_SIZE);
	startBlocknr = startBlock.y * nbrOfBlocksX + startBlock.x;
	int2 goalBlock;
	goalBlock.x=peDef.goalSquareX/BLOCK_SIZE;
	goalBlock.y=peDef.goalSquareZ/BLOCK_SIZE;

	CPathCache::CacheItem* ci=pathCache->GetCachedPath(startBlock,goalBlock,peDef.sqGoalRadius,moveData.pathType);
	if(ci){
//		logOutput.Print("Using cached path %i",BLOCK_SIZE);
		path=ci->path;
/*		if(BLOCK_SIZE==8){
		}else{
		}*/
		return ci->result;
	}
//	logOutput.Print("----Creating new path %i",BLOCK_SIZE);

	//Search
	SearchResult result = InitSearch(moveData, peDef);

	//If successful, generate path.
	if(result == Ok || result == GoalOutOfRange) {
		FinishSearch(moveData, path);
		pathCache->AddPath(&path,result,startBlock,goalBlock,peDef.sqGoalRadius,moveData.pathType);		//only add succesfull paths to the cache
		if(PATHDEBUG) {
			logOutput << "PE: Search completed.\n";
			logOutput << "Tested blocks: " << testedBlocks << "\n";
			logOutput << "Open blocks: " << (float)(openBlockBufferPointer - openBlockBuffer) << "\n";
			logOutput << "Path length: " << (int)(path.path.size()) << "\n";
			logOutput << "Path cost: " << path.pathCost << "\n";
		}
	} else {
		if(PATHDEBUG) {
			logOutput << "PE: Search failed!\n";
			logOutput << "Tested blocks: " << testedBlocks << "\n";
			logOutput << "Open blocks: " << (float)(openBlockBufferPointer - openBlockBuffer) << "\n";
		}
	}
/*	if(BLOCK_SIZE==8){
	}else{
	}*/
	return result;
}


/*
Making some initial calculations and preparations.
*/
IPath::SearchResult CPathEstimator::InitSearch(const MoveData& moveData, const CPathFinderDef& peDef) {
	//Starting square is inside goal area?
	int xSquare = blockState[startBlocknr].sqrCenter[moveData.pathType].x;
	int zSquare = blockState[startBlocknr].sqrCenter[moveData.pathType].y;
	if(peDef.IsGoal(xSquare, zSquare))
		return CantGetCloser;

	//Cleaning the system from last search.
	ResetSearch();

	//Marks and store the start-block.
	blockState[startBlocknr].options |= PATHOPT_OPEN;
	blockState[startBlocknr].cost = 0;
	dirtyBlocks.push_back(startBlocknr);

	//Adding the starting block to the open-blocks-queue.
	OpenBlock* ob = openBlockBufferPointer = openBlockBuffer;
	ob->cost = 0;
	ob->currentCost = 0;
	ob->block = startBlock;
	ob->blocknr = startBlocknr;
	openBlocks.push(ob);

	//Mark starting point as best found position.
	goalBlock = startBlock;
	goalHeuristic = peDef.Heuristic(xSquare, zSquare);

	//Gets goal square offset.
	goalSqrOffset = peDef.GoalSquareOffset(BLOCK_SIZE);

	//Performs the search.
	SearchResult result = DoSearch(moveData, peDef);

	//If no improvements are found, then return CantGetCloser instead.