//----------------------------------------------------------------------------- // V12 Engine // // Copyright (c) 2001 GarageGames.Com // Portions Copyright (c) 2001 by Sierra Online, Inc. //----------------------------------------------------------------------------- #include "ai/graph.h" #include "console/console.h" #include "console/consoleTypes.h" #include "terrain/terrRender.h" //------------------------------------------------------------------------------------- #ifdef DEBUG #define DebugCheckHanging 1 #else #define DebugCheckHanging 0 #endif //------------------------------------------------------------------------------------- static bool cullOneEdgeDup(GraphEdgeList& edges, BitVector& mark) { GraphEdgeList::iterator it, cull = NULL; for (it = edges.begin(); it != edges.end(); it++) if (mark.test(it->mDest)) { cull = it; break; } else mark.set(it->mDest); for (it = edges.begin(); it != edges.end(); it++) mark.clear(it->mDest); if (cull) edges.erase_fast(cull); return (cull != NULL); } //------------------------------------------------------------------------------------- // This is where distances are calculated. Also used to verify that all edges have a // counterpart coming back. Other final stuff has found its way here as well... S32 NavigationGraph::doFinalFixups() { S32 numberHanging = 0, i; GraphEdge edgeBuffOuter[MaxOnDemandEdges]; GraphEdgeArray edgeListOuter; sTotalEdgeCount = 0; for (i = 0; i < mNodeList.size(); i++) { if (GraphNode * node = mNodeList[i]) { edgeListOuter = node->getEdges(edgeBuffOuter); sTotalEdgeCount += edgeListOuter.numEdges(); while (GraphEdge * edgePtrOuter = edgeListOuter++) { GraphNode * neighbor = mNodeList[edgePtrOuter->mDest]; AssertFatal(neighbor, "graph has bad neighbor indices"); // Main edge setup method- mJetManager.initEdge(*edgePtrOuter, node, neighbor); #if DebugCheckHanging if (edgePtrOuter->mDest == i) Con::errorf("Node (%d) has edge pointing to self!", i); // This debugging check only needed when we're modifying generation tools. // Otherwise it's slow, and the generation is pretty solid anyway. static GraphEdge sEdgeBuffInner[MaxOnDemandEdges]; bool found = false; GraphEdgeArray edgeListInner = neighbor->getEdges(sEdgeBuffInner); while (GraphEdge * edgePtrInner = edgeListInner++) if (edgePtrInner->mDest == i){ found = true; break; } if (!found) { numberHanging++; Point3F P = node->location(); Point3F N = neighbor->location(); S32 D = edgePtrOuter->mDest; Con::errorf("Hanging edge from %d (%f, %f, %f) to %d (%f, %f, %f)", i, P.x, P.y, P.z, D, N.x, N.y, N.z); } #endif } } } // Keep separate list of the non-transients. mTransientStart = mNodeList.size(); mNonTransient.reserve(mNodeList.size() + mMaxTransients); mNonTransient = mNodeList; for (i = 0; i < mMaxTransients; i++ ) mNodeList.push_back(NULL); // Trim duplicate edges. This is rare (interior generator can get a strange // boundary with parallel edges), and causes problems. Not the best fix for // this problem (see graphTransient.cc attempt), but reasonable. BitVector marker(mNodeList.size()); S32 numDups = 0; marker.clear(); for (i = 0; i < mNodeList.size(); i++) if (GraphNode * node = mNodeList[i]) while (cullOneEdgeDup(node->mEdges, marker)) numDups++; if (numDups) Con::printf("%d duplicate edges found on nodes.", numDups); // Good idea to mark islands AFTER checking for hanging. markIslands(); // See navGraph.cc- newIncarnation(); mValidLOSTable = (mLOSTable && mLOSTable->valid(numNodes())); mValidPathTable = false; // this has been dropped... return numberHanging; } //------------------------------------------------------------------------------------- // // Assemble the graph from data that has been stored on it, computed, etc. // bool NavigationGraph::makeGraph(bool needEdgePool) { mPushedBridges = 0; makeRunTimeNodes(needEdgePool); // (graphOutdoors.cc) Con::printf("MakeGraph: %d indoor, %d outdoor", mNumIndoor, mNumOutdoor); mIndoorPtrs.clear(); // convenience list mIndoorTree.clear(); // BSP for it if (mNumIndoor) { mIndoorPtrs.reserve(mNumIndoor); for (S32 i = 0; i < mNumIndoor; i++) mIndoorPtrs.push_back(mNodeList[i + mNumOutdoor]); // Set up tree for quickly finding indoor nodes- mIndoorTree.makeTree(mIndoorPtrs); } return true; } //------------------------------------------------------------------------------------- // For now this just makes the roaming distance table. // We compute these data separately since they take a while. S32 NavigationGraph::makeTables() { // Get a table of ordered offsets. mTerrainInfo.computeRoamRadii(); return 0; } //------------------------------------------------------------------------------------- // Initialize the terrain info data from the ground plan. bool NavigationGraph::setGround(GroundPlan * gp) { mTerrainInfo.haveGraph = true; if (gp->setTerrainGraphInfo(&mTerrainInfo)) { mTerrainInfo.doFinalDataSetup(); mTerrainInfo.consolidateData(mConjoin); } else { mTerrainInfo.haveGraph = false; } return mTerrainInfo.haveGraph; } //------------------------------------------------------------------------------------- #define LOOK_AT_SPECIFIC_NODE 0 #if LOOK_AT_SPECIFIC_NODE Point3F gSpecificNodeLoc(-149, -131.828, 163); F32 gSpecificNodeRad = 9.0; S32 findSpecificNode(const NodeInfoList& nodes) { S32 found = -1; for (S32 i = 0; i < nodes.size(); i++) { Point3F point = nodes[i].pos; if ((point - gSpecificNodeLoc).len() < gSpecificNodeRad) Con::printf("Node %d is where it's at", found = i); } return found; } #endif //------------------------------------------------------------------------------------- // Get / Set interior node data. This doesn't affect the graph (building // the graph from indoor and outdoor databases is a step that must be // called explicitly). S32 NavigationGraph::getNodesAndEdges(EdgeInfoList& edges, NodeInfoList& nodes) { edges = mEdgeInfoList; nodes = mNodeInfoList; return nodes.size(); } // Set the system up with the given list of edges and nodes. Resets / hooks up // nodes indoors. S32 NavigationGraph::setNodesAndEdges(const EdgeInfoList& edges, const NodeInfoList& nodes) { mEdgeInfoList = edges; mNodeInfoList = nodes; return nodes.size(); } //------------------------------------------------------------------------------------- S32 NavigationGraph::setEdgesAndNodes(const EdgeInfoList& edges, const NodeInfoList& nodes) { return setAlgorithmic(edges, nodes); } //------------------------------------------------------------------------------------- // Interior node generator calls this to add data to graph, plus these lists // then become hand-editable. We always clean out existing algorithmic first. S32 NavigationGraph::setAlgorithmic(const EdgeInfoList& edges, const NodeInfoList& nodes) { #if LOOK_AT_SPECIFIC_NODE findSpecificNode(nodes); #endif clearAlgorithmic(); // Add the edges with remapped dest index, and marked as algorithmic. S32 indexAdd = mNodeInfoList.size(); for (EdgeInfoList::const_iterator e = edges.begin(); e != edges.end(); e++) { GraphEdgeInfo edge = * e; edge.setAlgorithmic(); edge.to[0].dest += indexAdd; edge.to[1].dest += indexAdd; mEdgeInfoList.push_back(edge); } for (NodeInfoList::const_iterator n = nodes.begin(); n != nodes.end(); n++) { IndoorNodeInfo node = * n; node.setAlgorithmic(); mNodeInfoList.push_back(node); } return 0; } // Clear algorithmic nodes out of main list, plus edges that connect to any. S32 NavigationGraph::clearAlgorithmic() { Vector mapIndices; NodeInfoList keepNodes; EdgeInfoList keepEdges; setSizeAndClear(mapIndices, mNodeInfoList.size(), 0xff); // get which nodes we're keeping and set up remap for (S32 i = 0; i < mNodeInfoList.size(); i++) if (mNodeInfoList[i].isAlgorithmic() == false) { mapIndices[i] = keepNodes.size(); keepNodes.push_back(mNodeInfoList[i]); } // get the edges we're keeping and remap their destination indices EdgeInfoList::iterator edge; for (edge = mEdgeInfoList.begin(); edge != mEdgeInfoList.end(); edge++) if (edge->isAlgorithmic() == false) if (mNodeInfoList[edge->to[0].dest].isAlgorithmic() == false) if (mNodeInfoList[edge->to[1].dest].isAlgorithmic() == false) { for (S32 j = 0; j < 2; j++) edge->to[j].dest = mapIndices[edge->to[j].dest]; keepEdges.push_back(*edge); } // copy back the culled lists mNodeInfoList = keepNodes; mEdgeInfoList = keepEdges; return mNodeInfoList.size(); } //------------------------------------------------------------------------------------- S32 NavigationGraph::setNodeVolumes(const GraphVolumeList& volumes) { mNodeVolumes = volumes; mNodeVolumes.nudgeVolumesOut(); return mNodeVolumes.size(); } //------------------------------------------------------------------------------------- S32 NavigationGraph::setChuteHints(const Vector& hints) { S32 numHints = hints.size(); mChutes.init(hints); return numHints; } //------------------------------------------------------------------------------------- static const U32 sMask = InteriorObjectType|StaticShapeObjectType|TerrainObjectType; // The path logic as it pertains to jetting connections (often) needs to know for sure // that the player can jump (makes a big difference in achievable height). This method // must figure this out. It's Ok if we miss a few where it's possible to jump, but we // don't want to err the other way (SOMETIMES can't jump, but think we can). S32 NavigationGraph::findJumpableNodes() { S32 total = 0; if (!mIsSpawnGraph) { F32 check45 = mSqrt(0.5); RayInfo coll; S32 i, j; Point3F down(0, 0, -6); // ==> As an optimization, we should only do this with nodes that you jet out of. // Um, because of where this is called, we can't use numNodes()- S32 numNodes = (mNumIndoor + mNumOutdoor); for (i = 0; i < numNodes; i++) { if (GraphNode * node = lookupNode(i)) { if (node->getNormal().z > check45) { // Cast several rays down and check their normals. Point3F loc = node->location(); loc += Point3F(-0.8, -0.9, 2.0); for (j = 0; j < 4; j++) { Point3F corner((j & 1 != 0) * 1.6, (j & 2 != 0) * 1.7, 0.0); corner += loc; if (gServerContainer.castRay(corner, corner + down, sMask, &coll)) if (coll.normal.z < check45) break; } if (j == 4) { node->set(GraphNode::Flat); total++; } } } } } return total; }