自学教程：C++ FindPath函数代码示例

CString XMLSerialized::LoadInfo(const CString& sName,TagType tagType,const CString parent=L""){	CMarkup xml = OpenFile();		if(tagType== TagType::Element){		if(FindPath(sName,&xml))			return xml.GetData();	}	if(tagType== TagType::Attribute){		if(FindPath(parent,&xml))			return xml.GetAttrib(sName);	}	return L"";}

int _tmain(int argc, _TCHAR* argv[]){	unsigned char pMap[] = { 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1 };	int pOutBuffer[12];	const int result1 = FindPath(0, 0, 1, 2, pMap, 4, 3, pOutBuffer, 12);	Output(pOutBuffer, result1);	unsigned char pMap2[] = { 0, 0, 1, 0, 1, 1, 1, 0, 1 };	int pOutBuffer2[7];	const int result2 = FindPath(2, 0, 0, 2, pMap2, 3, 3, pOutBuffer2, 7);	Output(pOutBuffer, result2);	system("PAUSE");	return 0;}

bool NavGrid::FindPath(const CU::Vector3f& aStartPoint, const CU::Vector3f& aEndPoint, CU::GrowingArray<CU::Vector2f>& aOutPath){	CU::Vector2i startPos(static_cast<int>(aStartPoint.x), static_cast<int>(aStartPoint.z));	CU::Vector2i endPos(static_cast<int>(aEndPoint.x), static_cast<int>(aEndPoint.z));	return FindPath(startPos, endPos, aOutPath);}

void TestSparsePerformance(bool outputMap){	int cellSize = 16;	int w = 40;	int h = 100;	double map = CreateSparseMap(w*cellSize,h*cellSize,cellSize);	//map = CreateMap(w*cellSize,h*cellSize,cellSize);	SetCellMap(map, 4*cellSize, 4*cellSize, 1);	SetCellMap(map, 5*cellSize, 4*cellSize, 1);	SetCellMap(map, 5*cellSize, 5*cellSize, 1);	SetCellMap(map, 5*cellSize, 6*cellSize, 1);	SetCellMap(map, 5*cellSize, 7*cellSize, 1);	SetCellMap(map, 4*cellSize, 7*cellSize, 1);	SetCellMapRegion(map, (w/2)*cellSize, 0*cellSize, 2*cellSize, (h*0.75)*cellSize, 1);	//SetCellMapRegion(map, (w/2)*cellSize, (h/2+1)*cellSize, 2*cellSize, (h/2-2)*cellSize, 1);#ifndef _DEBUG	double pathFinder = CreatePathFinder(map);#else	double mapDebug = CreateMap(w*cellSize,h*cellSize,cellSize);	double pathFinder = CreatePathFinderDebug(map, mapDebug);#endif		double path = FindPath(pathFinder, 2.0*cellSize, 8.0*cellSize, (w-2)*cellSize, 2.0*cellSize);	if (outputMap)	{		OutputPath(map, path);	}	DestroyMap(map);	DestroyPathFinder(pathFinder);	DestroyPath(path);#ifdef _DEBUG	DestroyMap(mapDebug);#endif}

void CRole::SetDst(Pos pos){	m_bBeginFindPath = false;	m_fdst = m_dst = pos;	ComputeDir();	int x = (int)(m_fdst.x/m_pMap->m_tileWidth);	int y = (int)(m_fdst.y/m_pMap->m_tileHeight);	if(!m_pMap->Passable(x, y))//如果目标不可到达	{		int bestx;int besty;		m_bestPosFinder->FindBestPos(x, y, &bestx, &besty, m_pMap->m_map);//寻找最近可走点		m_fdst.x = (float)bestx*m_pMap->m_tileWidth;		m_fdst.y = (float)besty*m_pMap->m_tileHeight;		//printf("%d %d/n", bestx, besty);	}	ClearPath();	//int t=timeGetTime(); //计算寻路时间	FindPath(&m_pos, &m_fdst);	//printf("寻路消耗时间: %d/n",timeGetTime()-t); //	if(GetNextPos(&m_dst, 			(float)m_pMap->m_tileWidth/2, (float)m_pMap->m_tileHeight/2))	ComputeDir();	else		SetStop();}

void Operator::CalcPEC_Curves(){	//special treatment for primitives of type curve (treated as wires)	double p1[3];	double p2[3];	struct Grid_Path path;	vector<CSProperties*> vec_prop = CSX->GetPropertyByType(CSProperties::METAL);	for (size_t p=0; p<vec_prop.size(); ++p)	{		CSProperties* prop = vec_prop.at(p);		for (size_t n=0; n<prop->GetQtyPrimitives(); ++n)		{			CSPrimitives* prim = prop->GetPrimitive(n);			CSPrimCurve* curv = prim->ToCurve();			if (curv)			{				for (size_t i=1; i<curv->GetNumberOfPoints(); ++i)				{					curv->GetPoint(i-1,p1);					curv->GetPoint(i,p2);					path = FindPath(p1,p2);					if (path.dir.size()>0)						prim->SetPrimitiveUsed(true);					for (size_t t=0; t<path.dir.size(); ++t)					{						SetVV(path.dir.at(t),path.posPath[0].at(t),path.posPath[1].at(t),path.posPath[2].at(t), 0 );						SetVI(path.dir.at(t),path.posPath[0].at(t),path.posPath[1].at(t),path.posPath[2].at(t), 0 );						++m_Nr_PEC[path.dir.at(t)];					}				}			}		}	}}

//移动地图到目的坐标，同可移动对象的移动类似void CGameMap::MoveTo(Point goal){    m_Paths.clear();    std::vector<Point>* Paths = &m_Paths;    Point start((int)m_CurrentXY.x, (int)m_CurrentXY.y);    FindPath(start, goal, Paths, m_pMapAstar);    //寻路失败,寻不到路或者寻路地址即为源地址    if(m_Paths.empty())    {        m_bArrived = true;    }    //寻路成功    else    {        //平滑路径        CActiveObject::SmoothPath(m_Paths, 50);        //当前Paths最后一个元素为当前位置        m_Paths.pop_back();        __Move1Step();        m_bArrived = false;    }}

	virtual void KillLoop(VertexId start, VertexId finish, const set<VertexId> &component) {		vector<EdgeId> path = FindPath(start, finish, component);		set<EdgeId> edges(path.begin(), path.end());		if(path.size() > 0 || start == finish) {//			if(start != finish || component.size() > 2)			if(/*!CheckStrong(component) || */!CheckNotMuchRemoved(edges, component)) {				return;			}/*			cout << this->g().int_id(start) << " " << this->g().int_id(finish) << endl;			cout << this->g().VertexNucls(start) << endl;			for(auto it = component.begin(); it != component.end(); ++it) {				vector<EdgeId> outgoing = this->g().OutgoingEdges(*it);				for(auto eit = outgoing.begin(); eit != outgoing.end(); ++eit) {					if(component.count(this->g().EdgeEnd(*eit)) == 1) {						cout << this->g().int_id(*it) << " -> " << this->g().int_id(this->g().EdgeEnd(*eit)) << " : " << this->g().length(*eit) << " : " << edges.count(*eit) << " : " << this->g().int_id(*eit) << endl;					}				}			}*/			RemoveExtraEdges(edges, component);			RemoveIsolatedVertices(component);		}	}

voidProfileListWidget::SelectPath(const TCHAR *path){  auto i = FindPath(path);  if (i >= 0)    GetList().SetCursorIndex(i);}

void main(void){    welcome();    InputMaze();    if (FindPath()) OutputPath();    else cout << "No path" << endl;}

void BinTree::FindPath(int expectedSum) {    if (pHead == NULL)        return ;    std::vector<int> path;    int currentSum = 0;    FindPath (pHead,expectedSum,path,currentSum);}

void path_check2(){    printf("Testing FindPath(...) on World2/n");    int i, j;    Grid *g;    g = ReadWorld("world2.txt");        Search *s;    s = FindPath(g);    assert_i(s->Length, -1, "Shortest path length - World2");    assert_i(stack_size(s->s), s->Length+1, "Stack size - World2");    int actual[14][17] = {{5000, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT},                          {5000,      10,       9,      10,      11,      12,      13,      14,      15,      16,      17,      18, MAX_INT, MAX_INT, MAX_INT},                          {5000,       9,       8,       9,      10,      11,      12,      13,      14,      15,      16,      17, MAX_INT, MAX_INT, MAX_INT},                          {5000,       8,       7,       8,       9,      10,      11,      12,      13,      14,      15,      16,      17,      18, MAX_INT},                          {5000,       7,       6,       7,       8,       9,      10,      11,      12,      13,      14,      15,      16,      17, MAX_INT},                          {5000,       6,       5,       6,       7,       8,       9,      10,      11,      12,      13,      14,      15,      16, MAX_INT},                          {5000,       5,       4, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT,      16,      17, MAX_INT},                          {5000,       4,       3,       2,       1,       2,       3,       4,       5,       6,       7, MAX_INT,      17,      18, MAX_INT},                          {5000,       3,       2,       1,       0,       1,       2,       3,       4,       5,       6, MAX_INT,      18,      19, MAX_INT},                          {5000,       4,       3,       2,       1,       2,       3,       4,       5,       6,       7, MAX_INT,      19,      20, MAX_INT},                          {5000, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT, MAX_INT}};    int correct_dist = 1;    // Compare Calculated Distances to Model Solution.    for(i = 0; i < g->rows; i++){        for(j = 0; j < g->cols; j++){            if(actual[i][j] != s->Distance[i][j]){                correct_dist = 0;            }         }    }    assert_i(correct_dist, 1, "Distance Array - World2");}

void updateMap() {    for(int i = 0; i < mapWidth; ++i) {    for(int j = 0; j < mapHeight; ++j) {      QGraphicsRectItem* rect = rects[RectsKey(j, i)];      if(pMap[i*mapWidth+j] == 0)        rect->setBrush(QBrush(Qt::blue));      if(pMap[i*mapWidth+j] == 1)        rect->setBrush(QBrush(Qt::red));    }  }  int pOutBuffer[128];  int nNumSteps = FindPath(startX, startY, endX, endY, pMap, mapWidth, mapHeight, pOutBuffer, 128);  for(int i = 0; i < nNumSteps; i++) {    int y = pOutBuffer[i]/mapWidth;    int x = pOutBuffer[i] - y*mapWidth;    QGraphicsRectItem* rect = rects[RectsKey(x, y)];    rect->setBrush(QBrush(Qt::green));  }  if(startX != -1 && startY != -1)  {    QGraphicsRectItem* rect = rects[RectsKey(startX, startY)];    rect->setBrush(QBrush(Qt::green));  }  if(endX != -1 && endY != -1)  {    QGraphicsRectItem* rect = rects[RectsKey(endX, endY)];    rect->setBrush(QBrush(Qt::gray));  }}

void Enemy::GenerateRandomPath(){	pathStatus = PathFinder::NONEXISTENT;	for( int i = 0 ; i < numberOfRandomPathPoints ; i++ )	{		do{		target.x = rand()%( 2 * MovementVector.x ) + ( startPosition.x - MovementVector.x );		target.y = rand()%( 2 * MovementVector.y ) + ( startPosition.y - MovementVector.y );	//	std::cout<<target.x<<" "<<target.y<<"/n";		pathSearched = false;		if( (target.x/32 != myPosition.x/32) &&		    (target.y/32 != myPosition.y/32) )		{			if( FindPath( target ) == PathFinder::FOUND )			{				pathStatus = PathFinder::NONEXISTENT;				randomPatrolPath[i] = pathfinderPath;				break;			}		}		}while( pathStatus != PathFinder::FOUND );	}				}

void bm_Periodical_1s(){	for (u32 i=0;i<del_blocks.size();i++)		delete del_blocks[i];	del_blocks.clear();	if (rebuild_counter>0) rebuild_counter--;#if HOST_OS==OS_WINDOWS && 0	std::sort(all_blocks.begin(),all_blocks.end(),UDgreaterX);	map<u32,u32> vmap;	map<u32,u32> calls;	u32 total_runs=0;	for(int i=0;i<all_blocks.size();i++)	{		RuntimeBlockInfo* rbi=all_blocks[i];		total_runs+=rbi->runs;		if (rbi->BranchBlock!=-1 && rbi->BranchBlock < rbi->addr)		{			if (rbi->BlockType==BET_Cond_0 || rbi->BlockType==BET_Cond_1 || rbi->BlockType==BET_StaticJump)			{				RuntimeBlockInfo* bbi=bm_GetBlock(all_blocks[i]->BranchBlock);				if (bbi && bbi->runs)				{					vmap[all_blocks[i]->BranchBlock]=bbi->runs;				}			}			if (rbi->BlockType==BET_StaticCall)			{				RuntimeBlockInfo* bbi=bm_GetBlock(all_blocks[i]->BranchBlock);				if (bbi && bbi->runs)				{					calls[all_blocks[i]->BranchBlock]+=rbi->runs;				}			}		}		verify(rbi->NextBlock>rbi->addr);	}	map<u32,u32>::iterator iter=vmap.begin();	total_saved=0;	u32 total_l_runs=0;	while(iter!=vmap.end())	{		FindPath(iter->first);		total_l_runs+=iter->second;		iter++;	}	for(int i=0;i<all_blocks.size();i++)		all_blocks[i]->runs=0;	printf("Total Saved: %.2f || Total Loop Runs: %.2f  || Total Runs: %.2f/n",total_saved/1000.f,total_l_runs/1000.f,total_runs/1000.f);#endif}

PathPlan* PathingGraph::FindPath(const Vec3& startPoint, const Vec3& endPoint){	// Find the closest nodes to the start and end points.  There really should be some ray-casting 	// to ensure that we can actually make it to the closest node, but this is good enough for now.	PathingNode* pStart = FindClosestNode(startPoint);	PathingNode* pGoal = FindClosestNode(endPoint);	return FindPath(pStart,pGoal);}

void main(void){   Position s,f, *p;   int l;   InputGrid(s,f);   if (FindPath(s,f,l,p)) OutputPath(l,p);   else cout << "No path" << endl;}

void MapOverview::OnButtonExecuteClick(wxCommandEvent& event){   signed int res=FindPath(GetWorldHandler(),OURROBOT,100); //TimeMS->GetValue()*10  //floor_plan->FindPathTo(endx,endy,);  if ( res <1 ) { fprintf(stderr,"Could not establish a route./n"); /*TTS((char *)"Could not establish a route.");*/  } else                { fprintf(stderr,"New route established."); }  Refresh();}

void Player::GeneratePath(){	path.clear();	next = NULL;	x = nodeMap->GetStart()->x;	y = nodeMap->GetStart()->y;	path = *FindPath();}

void FindPath(BinaryTreeNode* pRoot, int expectedSum){	if(pRoot == NULL)		return;	std::vector<int> path;	int currentSum = 0;	FindPath(pRoot, expectedSum, path, currentSum);}

// ====================测试代码====================void Test(char* testName, BinaryTreeNode* pRoot, int expectedSum){    if(testName != NULL)        printf("%s begins:/n", testName);    FindPath(pRoot, expectedSum);    printf("/n");}

//===============================================================================//Play Functions:int PlayMove(HWND hwnd, int dx, int dy) {		ptagLevel cur_level;	int curx,cury;	int iRow, iCol;		int *iGoRecord;	int a;	BOOL bRet;	int curbefore,curafter;	int nextbefore,nextafter;	ptagStep pAStep;	cur_level = theMap->currentLevel;	iCol = cur_level->col;	a = cur_level->data[dy * iCol + dx];	if ((a != B_GOAL) && (a != B_NOTHING))		return 0;		iRow = cur_level->row;	curx = cur_level->manx;	cury = cur_level->many;	iGoRecord = (int *) calloc (iRow * iCol, sizeof(int));	memcpy(iGoRecord, cur_level->data, iRow * iCol * sizeof(int));	bRet = FindPath(iGoRecord, curx, cury, dx, dy, iRow, iCol);	free(iGoRecord);	if (!bRet) 		return 0;		curbefore = cur_level->data[cury  * iCol + curx];	curafter  = manLeave[curbefore];	nextbefore = cur_level->data[dy * iCol + dx];	nextafter  = manGoInto[nextbefore];	assert(curafter != B_FORBID);	assert(nextafter != B_FORBID);	//for UNDO	pAStep = (ptagStep) calloc (1, sizeof(Step));	pAStep->iType  = STEP_TYPE_MOVE;	pAStep->pt1[0] = curx;	pAStep->pt1[1] = cury;	pAStep->pt1[2] = curbefore;	pAStep->pt2[0] = dx;	pAStep->pt2[1] = dy;	pAStep->pt2[2] = nextbefore;	PushStep(pAStep);	//act	cur_level->data[cury  * iCol + curx]  = curafter;	cur_level->data[dy * iCol + dx] = nextafter;	DrawALittleBlock(hwnd, curx, cury, curafter);		DrawALittleBlock(hwnd, dx, dy, nextafter);		cur_level->manx = dx;	cur_level->many = dy;		return STEP_TYPE_MOVE;}

int OgreRecast::FindPath(Ogre::Vector3 startPos, Ogre::Vector3 endPos, int nPathSlot, int nTarget){    float start[3];    float end[3];    OgreVect3ToFloatA(startPos, start);    OgreVect3ToFloatA(endPos, end);    return FindPath(start,end,nPathSlot,nTarget);}

u32 FindPath(RuntimeBlockInfo* rbi, u32 sa,s32 mc,u32& plc){	if (mc < 0 || rbi==0)		return 0;	plc++;	if (rbi->BlockType==BET_Cond_0 || rbi->BlockType==BET_Cond_1)	{		u32 plc1=plc,plc2=plc,v1=0,v2=0;		if (rbi->BranchBlock>sa)		{			v1=FindPath(bm_GetBlock(rbi->BranchBlock),rbi->addr,mc-rbi->guest_cycles,plc1);		}		v2=FindPath(bm_GetBlock(rbi->NextBlock),rbi->addr,mc-rbi->guest_cycles,plc2);		if (plc1>plc2)		{			plc=plc1;			return rbi->guest_cycles+v1;		}		else		{			plc=plc2;			return rbi->guest_cycles+v2;		}			}	else if (rbi->BlockType==BET_StaticJump)	{		if (rbi->BranchBlock>sa)			return rbi->guest_cycles+FindPath(bm_GetBlock(rbi->BranchBlock),rbi->addr,mc-rbi->guest_cycles,plc);		else		{			return rbi->guest_cycles;		}	}	else	{		if (plc!=1)			printf("Chain lost due to %d/n",rbi->BlockType);		else			printf("Chain fail due to %d/n",rbi->BlockType);		return rbi->guest_cycles;	}}

bool CWallDirListItem::RemoveAllPath(CString &sPath){	bool bRes = false;	if (m_mux.Lock()) {		int iIndex = FindPath(sPath);		if (iIndex >= 0) {			bRes = true;		} else {			bRes = false;		}		while (iIndex >= 0) {			m_saPicPath.RemoveAt(iIndex);			iIndex = FindPath(sPath);		}		m_mux.Unlock();	}	return bRes;}

vector<vector<int>> FindPath(BinaryTreeNode *root, int expectedSum){    vector<vector<int>> res;    vector<int> path;        FindPath(root, expectedSum, path, res);        return res;}

void FindPathTest(double map, double pathFinder, int w, int h, int cellSize, bool outputMap){	double path = FindPath(pathFinder, 2.0*cellSize, 8.0*cellSize, (w-2)*cellSize, 2.0*cellSize);    //double path = FindPath(pathFinder, (w-2)*cellSize, 2.0*cellSize, 2.0*cellSize, 8.0*cellSize);	if (outputMap)	{		OutputPath(map, path);	}	DestroyPath(path);}

// Check if we have a matching triggerint GotoFileList::FindMatchesAndSelection(const std::map<wxString,wxString>& triggers) {	if (!m_items.size()) return wxNOT_FOUND;	int selection = wxNOT_FOUND;	std::map<wxString,wxString>::const_iterator p = triggers.find(m_searchText);	if (p != triggers.end())		selection = FindPath(p->second);	if (selection != wxNOT_FOUND)		return selection;	// Check if we have a partial match, using saved triggers	for (p = triggers.begin(); p != triggers.end(); ++p) {		if (!p->first.StartsWith(m_searchText)) continue;		selection = FindPath(p->second);		if (selection != wxNOT_FOUND) continue;		// Since we have a trigger but it is not in list yet		// Let's check if it exists and add it temporarily		if (wxFileExists(p->second)) {			m_tempEntry->SetPath(p->second);			// Add entry with highlighted search chars			AddFileIfMatching(m_searchText, m_tempEntry);			// Find position it will end up after sort			std::vector<aItem>::iterator insPos = lower_bound(m_items.begin(), m_items.end()-1, m_items.back());			selection = distance(m_items.begin(), insPos);			// Move item to correct position			if (m_items.size() > 1)				inplace_merge(m_items.begin(), m_items.end()-1, m_items.end());			return selection;		}	}	return selection;}

int main(){	// Case #0	int case_zero_result = FindPath(0, 0, 3, 2, gCaseZeroMap, 4, 3, gCaseZeroBuffer, gCaseZeroBufferSize);	LogResult(4 * 0 + 0, case_zero_result, gCaseZeroBuffer);	// Case #1	int case_one_result = FindPath(2, 0, 0, 2, gCaseOneMap, 3, 3, gCaseOneBuffer, gCaseOneBufferSize);	LogResult(3 * 0 + 2, case_one_result, gCaseOneBuffer);	// Case #2 - test with a larger map	int result = FindPath(0, 0, 4, 5, gLargerMap, 5, 6, gLargerBuffer, gLargerBufferSize);	LogResult(0, result, gLargerBuffer);	// Case #3 - map with only one available path, but we can't move diagonally so it is invalid	int one_available_result = FindPath(0, 0, 1, 1, gOneAvailableMap, 2, 2, gOneAvialableBuffer, gOneAvailableBufferSize);	LogResult(0, one_available_result, gOneAvialableBuffer);	// Case #4 - output buffer is too small to hold the output buffer	int small_buffer_result = FindPath(0, 0, 3, 3, gSmallBufferMap, 4, 4, gSmallBufferBuffer, gSmallBufferBufferSize);	LogResult(0, small_buffer_result, gSmallBufferBuffer);	// Case #5 - huge map	int huge_map_result = FindPath(0, 0, 0, 19, gHugeMap, 20, 20, gHugeBuffer, gHugeBufferSize);	LogResult(0, huge_map_result, gHugeBuffer);		return 0;}