开发工具:
文件大小: 19kb
下载次数: 0
上传时间: 2009-10-28
详细说明： 讲解 Dijkstra 算法的基本思想，另外还有算法实现. 当然了，这个算法当路径点上万的时候效率上会降低。 我有另外的改进实现， 上万个点也是在200毫秒内完成。但是不知道怎么添加， 我只能在这里贴关键代码了 ： static std::list vecNodes; static std::list vecEdges; bool CDijkstras::DijkstrasFindPath(Node* psrcNode, Node* pdstNode, std ::list& vec, double& fromSrcDist) { if (psrcNode == 0 || pdstNode == 0) return false; if (psrcNode == pdstNode) { vec.push_back(pdstNode); return false; } std::list::const_iterator it; for (it=vecNodes.begin(); it!=vecNodes.end(); it++) { (*it)->bAdded = false; (*it)->previous = 0; (*it)->distanceFromStart = MAXDOUBLE; (*it)->smallest = 0; } bool bFindDst = DijkstrasRouteInitialize(psrcNode, pdstNode); fromSrcDist = pdstNode->distanceFromStart; Node* previous = pdstNode; while (previous) { vec.push_back(previous); previous = previous->previous; } m_pDstNode = pdstNode; return bFindDst; } bool CDijkstras::DijkstrasRouteInitialize(Node* psrcNode, Node* pdstNode) { bool bFindDst = false; psrcNode->distanceFromStart = 0; Node* smallest = psrcNode; smallest->bAdded = true; std::list::const_iterator it, ait; std::list AdjAdjNodes ; for (it=psrcNode->connectNodes.begin(); it!=psrcNode->connectNodes.end(); it++) { if ((*it)->bAdded) continue; (*it)->smallest = psrcNode; (*it)->bAdded = true; AdjAdjNodes.push_back(*it); } while (1) { std::list tempAdjAdjNodes; for (it=AdjAdjNodes.begin(); it!=AdjAdjNodes.end(); it++) { Node* curNode = *it; for (ait=curNode->connectNodes.begin(); ait!=curNode->connectNodes.end(); ait++) { Node* pns = *ait; double distance = Distance(pns, curNode) + pns->distanceFromStart; if (distance < curNode->distanceFromStart) { curNode->distanceFromStart = distance; curNode->previous = pns; } if (pns->bAdded == false) { tempAdjAdjNodes.push_back(pns); pns->bAdded = true; } } if (curNode == pdstNode) { bFindDst = true; } } if (bFindDst) break; if (tempAdjAdjNodes.size() == 0) break; AdjAdjNodes.clear(); AdjAdjNodes = tempAdjAdjNodes; } return bFindDst; } // Return distance between two connected nodes float CDijkstras::Distance(Node* node1, Node* node2) { std::list::const_iterator it; for (it=node1->connectEdges.begin(); it!=node1->connectEdges.end(); it++) { if ( (*it)->node1 == node2 || (*it)->node2 == node2 ) return (*it)->distance; } #ifdef _DEBUG __asm {int 3}; #endif return (float)ULONG_MAX; } /****************************************************************************/ /****************************************************************************/ /****************************************************************************/ //得到区域的Key// __int64 CDijkstras::GetRegionKey( float x, float z ) { long xRegion = (long)(x / m_regionWidth); long zRegion = (long)(z / m_regionHeight); __int64 key = xRegion; key <<= 32; key |= ( zRegion & 0x00000000FFFFFFFF ); return key; } //得到区域的Key// __int64 CDijkstras::GetRegionKey( long tx, long tz ) { long xRegion = tx ; long zRegion = tz ; __int64 key = xRegion; key <<= 32; key |= ( zRegion & 0x00000000FFFFFFFF ); return key; } //取得一个区域内的所有的路径点, 返回添加的路径点的个数// unsigned long CDijkstras::GetRegionWaypoint (__int64 rkey, std::vector& vec) { unsigned long i = 0; SAME_RANGE_NODE rangeNode = mmapWaypoint.equal_range(rkey); for (CRWPIT it=rangeNode.first; it!=rangeNode.second; it++) { i++; Node* pn = it->second; vec.push_back(pn); } return i; } inline bool cmdDistanceNode (Node* pNode1, Node* pNode2) { return pNode1->cmpFromStart < pNode2->cmpFromStart; }; //添加一个路径点// Node* CDijkstras::AddNode (unsigned long id, float x, float y, float z) { Node* pNode = new Node(id, x, y, z); __int64 rkey = GetRegionKey(x, z); mmapWaypoint.insert(make_pair(rkey, pNode)); mapID2Node[id] = pNode; return pNode; } //添加一条边// Edge* CDijkstras::AddEdge (Node* node1, Node* node2, float fCost) { Edge* e = new Edge (node1, node2, fCost); return e; } //通过路径点ID得到路径点的指针// Node* CDijkstras::GetNodeByID (unsigned long nid) { std::map::const_iterator it; it = mapID2Node.find(nid); if (it!=mapID2Node.end()) return it->second; return NULL; } ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
