Menu
▾
▴
[Planeshift-cvs] CVS: planeshift/src/npcclient pathfind.cpp,1.2,1.3 pathfind.h,1.1,1.2
|
From: Ondrej H. <tan...@us...> - 2005-03-16 21:39:56
|
Update of /cvsroot/planeshift/planeshift/src/npcclient In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv31945/src/npcclient Modified Files: pathfind.cpp pathfind.h Log Message: - Work on generator of walkable polygons maps, and generator of A* maps. Index: pathfind.cpp =================================================================== RCS file: /cvsroot/planeshift/planeshift/src/npcclient/pathfind.cpp,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** pathfind.cpp 5 Mar 2005 18:22:02 -0000 1.2 --- pathfind.cpp 16 Mar 2005 21:39:36 -0000 1.3 *************** *** 19,26 **** --- 19,31 ---- #include <math.h> #include <psconfig.h> + #include <csutil/hash.h> + #include <csutil/hashhandlers.h> + #include <engine/celbase.h> + #include "pathfind.h" #include "walkpoly.h" #include "util/log.h" #include "util/psxmlparser.h" + #include "util/consoleout.h" *************** *** 82,90 **** * Or we could adjust the coefficient dynamically according to CPU load. - - - spatindex - body na hranici patri do obou ! - lehce se zacykli - realbox muze byt vetsi nez bbox node */ --- 87,90 ---- *************** *** 106,112 **** void Dump(const char * name, const csBox3 & b) { ! printf("bbox '%s':\n", name); Dump3("b1", b.Min()); Dump3("b2", b.Max()); } --- 106,114 ---- void Dump(const char * name, const csBox3 & b) { ! CPrintf(CON_NONE, "bbox '%s':\n", name); ! CShift(); Dump3("b1", b.Min()); Dump3("b2", b.Max()); + CUnshift(); } *************** *** 122,127 **** - // normalized - /*********************************************************************************** * --- 124,127 ---- *************** *** 130,193 **** ************************************************************************************/ ! /* ! void ConnectToAllPolyVertices(psANode * node, psWalkPoly * toPoly, hash) { ! for (int vertNum=0; vertNum < poly->verts.Length(); vertNum++) { ! psWalkPoly * poly = &poly->verts[vertNum]; ! if (poly != toPoly) { ! csVector3 * vert1 = &poly->verts[vert1Num], ! * vert2 = &poly->verts[vert2Num]; ! psANode * node1 = map.Get(vert1), ! * node2 = map.Get(vert2); ! float dist = CalcDistance(node1, node2); ! node1->AddNeighbour(node2, dist); ! node2->AddNeighbour(node1, dist); } } } ! void BuildBasicAMap(const psWalkPolyMap & polyMap, psAMap & AMap) { ! csHash<psANode*,psWalkPoly*> map; ! csHash<psANode*,bool> processedConts; ! for (int polyNum=0; polyNum < polyMap.polys.Length(); polyNum++) { ! psWalkPoly * poly = polyMap.polys[polyNum]; ! for (int vertNum=0; vertNum < poly>verts.Length(); vertNum++) { ! csVector3 * vert = &poly->verts[vertNum]; ! psANode * node = new psANode(vert); AMap.AddNode(node); - map.Add(vert, node); } } ! for (int polyNum=0; polyNum < polyMap.polys.Length(); polyNum++) { ! psWalkPoly * poly = polyMap.polys[polyNum]; ! for (int vertNum=0; vertNum < poly>verts.Length(); vertNum++) ! { ! ConnectToAllPolyVertices(poly->verts[vertNum], poly->poly); ! } ! ! //pro kazdeho z vedlejsich polygonu .... ! //vazba se prirozene navaze 2x, neni potreba nic kontrolovat ! for (int edgeNum; edgeNum < poly->edges.Length(); edgeNum++) { ! psWalkPolyEdge & edge = poly->edges[edgeNum]; ! for (int contNum=0; contNum < edge.conts.Length(); contNum++) { ! if (!processedConts.Find()) { ! csVector3 middle = (begin - end) / 2; ! psANode * node = new psANode(middle); ! AMap.AddNode(node); ! ConnectToAllPolyVertices(node, poly); ! ConnectToAllPolyVertices(node, cont.poly); ! processedConts.Add(???, true); } } --- 130,321 ---- ************************************************************************************/ + void pathFindTest_AMapConstruction(CelBase * cel) + { + psAMap Amap; + psWalkPolyMap map(cel->GetObjectReg()); + map.LoadFromFile("/this/pf40.xml"); + map.CalcConts(); + map.BuildBasicAMap(Amap); + Amap.DumpJS(); + } ! psAMap::psAMap() { ! objReg = NULL; ! } ! ! psAMap::psAMap(iObjectRegistry * objReg) ! { ! this->objReg = objReg; ! } ! ! /*bool psAMap::LoadFromString(const csString & str) ! { ! csRef<iDocument> doc = ParseString(str); ! if (doc == NULL) ! return false; ! ! csRef<iDocumentNode> mapNode = doc->GetRoot()->GetNode("map"); ! if (mapNode == NULL) ! return false; ! ! csRef<iDocumentNodeIterator> it = mapNode->GetNodes(); ! while (it->HasNext()) { ! csRef<iDocumentNode> nodeNode = it->Next(); ! psANode * node = new psANode; ! ????? ! node->LoadFromXML(nodeNode); ! AddNode(node); ! } ! } ! ! bool psAMap::LoadFromFile(const csString & path) ! { ! csRef<iDataBuffer> buff = vfs->ReadFile(path); ! if (buff == NULL) ! { ! Error2("Could not find file: %s", path.GetData()); ! return NULL; ! } ! return LoadFromString(buff); ! } ! ! void psAMap::SaveToString(csString & str) ! { ! csList<psANode*>::Iterator it(nodes); ! ! str += "<map>\n"; ! while (it.HasNext()) ! { ! psANode * node = it.Next(); ! node->SaveToString(str); ! } ! str += "</map>\n"; ! } ! ! bool psAMap::SaveToFile(const csString & path) ! { ! csString str; ! SaveToString(str); ! return vfs->WriteFile(path, str.GetData(), str.Length()); ! }*/ ! ! ! void psANode::DumpJS() ! { ! if (edges.Length() == 0) ! return; ! csArray<psAEdge> & e = edges[0]; ! for (int neighNum=0; neighNum < e.Length(); neighNum++) ! { ! psANode * neigh = e[neighNum].neighbour; ! CPrintf(CON_NONE, "drawLine({begin: {x: %f, z: %f}, end: {x: %f, z: %f}}, 'black', '', '')\n", point.x, point.z, neigh->point.x, neigh->point.z); ! } ! } ! ! void psAMap::DumpJS() ! { ! csList <psANode*>::Iterator it(nodes); ! while (it.HasNext()) ! { ! psANode * node = it.Next(); ! node->DumpJS(); ! } ! } ! ! ! ! ! ! void psAMap::AddNode(psANode * node) ! { ! nodes.PushFront(node); ! } ! ! void psWalkPolyMap::BuildBasicAMap(psAMap & AMap) ! { ! int vertNum; ! csHash<bool, psWalkPoly*> doneConts; ! ! /* For each walkable polygon, create A* nodes in middles of contacts with neighbour polygons ! (if they were not created already) and connect them to all A* nodes ! from the current poly, and all the A* nodes from the poly that it contacts with. */ ! csList<psWalkPoly*>::Iterator it(polys); ! while (it.HasNext()) ! { ! psWalkPoly * poly = it.Next(); ! for (vertNum = 0; vertNum < poly->verts.Length(); vertNum++) { ! psWalkPolyVert & vert = poly->verts[vertNum]; ! csArray<psWalkPolyCont> & conts = vert.conts; ! ! for (int contNum = 0; contNum < conts.Length(); contNum++) ! { ! psWalkPolyCont & cont = conts[contNum]; ! if (!doneConts.Get(cont.poly, false)) ! { ! psANode * mean = new psANode((cont.begin+cont.end)/2); ! poly->AddNode(mean); ! cont.poly->AddNode(mean); ! poly->ConnectNodeToPoly(mean, true); ! cont.poly->ConnectNodeToPoly(mean, true); ! AMap.AddNode(mean); ! ! doneConts.Put(poly, true); ! } ! } } } } ! /*void psWalkPolyMap::BuildBasicAMap(psAMap & AMap) { ! int vertNum; ! csHash<bool, psWalkPoly*> doneConts; ! // For each walkable polygon, ! // create a psANode for each of its vertices, ! // then fully interconnect them ! csList<psWalkPoly*>::Iterator it(polys); ! while (it.HasNext()) { ! psWalkPoly * poly = it.Next(); ! for (vertNum = 0; vertNum < poly->verts.Length(); vertNum++) { ! psANode * node = new psANode(poly->verts[vertNum].pos); ! poly->AddNode(node); ! poly->ConnectNodeToPoly(node, false); AMap.AddNode(node); } } ! // For each walkable polygon, ! // create A* nodes in middle of contacts, and interconnect them ! // with all vertices of both polygons ! it = polys; ! while (it.HasNext()) { ! psWalkPoly * poly = it.Next(); ! for (vertNum = 0; vertNum < poly->verts.Length(); vertNum++) { ! psWalkPolyVert & vert = poly->verts[vertNum]; ! int nextVertNum = poly->GetNeighbourIndex(vertNum, +1); ! psWalkPolyVert & nextVert = poly->verts[nextVertNum]; ! csArray<psWalkPolyCont> & conts = vert.conts; ! ! for (int contNum = 0; contNum < conts.Length(); contNum++) { ! psWalkPolyCont & cont = conts[contNum]; ! if (!doneConts.Get(cont.poly, false)) { ! psANode * mean = new psANode((cont.begin+cont.end)/2); ! poly->AddNode(mean); ! cont.poly->AddNode(mean); ! poly->ConnectNodeToPoly(mean, true); ! cont.poly->ConnectNodeToPoly(mean, true); ! AMap.AddNode(mean); ! ! doneConts.Put(poly, true); } } *************** *** 197,200 **** --- 325,340 ---- + /* + + prunning + + mozna je nutne nejdriv zjistit koho chci vyhodit a udelat to az na konci, + nez vyhazovat rovnou ? ? ? + nebo spis mozna udelat tolik kol vyhazovani, dokud se neco vyhazuje + protoze node mohla prezit jen diky svemu napojeni na jinou node, ktera ale byla + pozdeji vyhozena + */ + + /*********************************************************************************** * *************** *** 263,266 **** --- 403,411 ---- } + psANode::psANode(const csVector3 & point) + { + this->point = point; + } + psANode::psANode(const csVector3 & point, const csString & name) { *************** *** 274,278 **** edges.SetLength(level+1, csArray<psAEdge>()); ! edges[level].Push(psAEdge(neighbour, cost)); if (bidirectional) neighbour->AddEdge(this, cost, level, false); --- 419,433 ---- edges.SetLength(level+1, csArray<psAEdge>()); ! int neighNum; ! csArray<psAEdge> & levEdges = edges[level]; ! for (neighNum=0; neighNum < levEdges.Length(); neighNum++) ! if (levEdges[neighNum].neighbour == neighbour) ! break; ! ! if (neighNum == levEdges.Length()) ! { ! levEdges.Push(psAEdge(neighbour, cost)); ! } ! if (bidirectional) neighbour->AddEdge(this, cost, level, false); *************** *** 433,448 **** ! ! ! ! ! ! ! ! ! //bool najdiCestu mezi vector3 ! ! ! void pathFindTest_A() { psAPath path; --- 588,592 ---- ! void pathFindTest_AStarWithArtificialMap() { psAPath path; *************** *** 473,476 **** --- 617,635 ---- } + void pathFindTest_AStarWithRealMap(CelBase * cel) + { + psAPath path; + psAMap AMap; + psWalkPolyMap PMap(cel->GetObjectReg()); + + PMap.LoadFromFile("/this/pf5.xml"); + PMap.CalcConts(); + PMap.BuildBasicAMap(AMap); + + //RunA(n0, ng, 0, 1, path); + Dump(path); + } + + void pathFindTest_CheckDirect(CelBase * cel); void pathFindTest_Inter(); void pathFindTest_PolyInter(); *************** *** 479,491 **** void pathFindTest_Stretch(CelBase * cel); void pathFindTest_Convex(); void pathFindTest(CelBase * cel) { ! // pathFindTest_CheckDirect(); //pathFindTest_NormEq(); //pathFindTest_Walkability(cel); //pathFindTest_PolyInter(); ! pathFindTest_Stretch(cel); //pathFindTest_Convex(); } --- 638,654 ---- void pathFindTest_Stretch(CelBase * cel); void pathFindTest_Convex(); + void pathFindTest_Save(CelBase * cel); void pathFindTest(CelBase * cel) { ! //pathFindTest_CheckDirect(cel); //pathFindTest_NormEq(); //pathFindTest_Walkability(cel); //pathFindTest_PolyInter(); ! //pathFindTest_Stretch(cel); //pathFindTest_Convex(); + //pathFindTest_Save(cel); + pathFindTest_AMapConstruction(cel); + //pathFindTest_AStarWithRealMap(cel); } Index: pathfind.h =================================================================== RCS file: /cvsroot/planeshift/planeshift/src/npcclient/pathfind.h,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** pathfind.h 19 Feb 2005 18:18:11 -0000 1.1 --- pathfind.h 16 Mar 2005 21:39:45 -0000 1.2 *************** *** 30,33 **** --- 30,34 ---- class CelBase; class psANode; + class psWalkPoly; /******************************************************************************* *************** *** 74,77 **** --- 75,79 ---- enum psAState {AState_open, AState_closed, AState_unknown}; + /**************************************************************************** * Describes one A* node and keeps temporary state for the current run *************** *** 81,84 **** --- 83,87 ---- * if its state is valid for the current A* run - if not, THEN we clear it. ****************************************************************************/ + class psANode : public psAHierarchyNode { *************** *** 95,98 **** --- 98,105 ---- void AddEdge(psANode * neighbour, float cost, int level, bool bidirectional=true); + void ConnectToPoly(psWalkPoly * poly, bool bidirectional); + + void DumpJS(); + csVector3 point; csArray<csArray<psAEdge> > edges; *************** *** 117,121 **** { public: ! /** Builds hierachy of A* nodes - it clusters the nodes, then clusters their clusters... etc. */ --- 124,132 ---- { public: ! psAMap(iObjectRegistry * objReg); ! psAMap(); ! ! void AddNode(psANode * node); ! /** Builds hierachy of A* nodes - it clusters the nodes, then clusters their clusters... etc. */ *************** *** 126,133 **** --- 137,152 ---- Returns true when path was found */ bool RunA(psANode * start, psANode * goal, int level, psAPath & path); + + void DumpJS(); + + bool LoadFromString(const csString & str); + bool LoadFromFile(const csString & path); + void SaveToString(csString & str); + bool SaveToFile(const csString & path); protected: csList <psANode*> nodes; csList <psACluster*> clusters; + iObjectRegistry * objReg; }; |