mirror of
https://github.com/tribes2/engine.git
synced 2026-01-19 19:24:45 +00:00
268 lines
8.3 KiB
C++
268 lines
8.3 KiB
C++
//-----------------------------------------------------------------------------
|
|
// V12 Engine
|
|
//
|
|
// Copyright (c) 2001 GarageGames.Com
|
|
// Portions Copyright (c) 2001 by Sierra Online, Inc.
|
|
//-----------------------------------------------------------------------------
|
|
|
|
#include "ai/graph.h"
|
|
|
|
//-------------------------------------------------------------------------------------
|
|
// Interior Node Methods
|
|
|
|
|
|
NodeProximity InteriorNode::containment(const Point3F& loc) const
|
|
{
|
|
if (gNavGraph->haveVolumes())
|
|
return gNavGraph->getContainment(mIndex, loc);
|
|
else
|
|
return Parent::containment(loc);
|
|
}
|
|
|
|
void InteriorNode::init(const IndoorNodeInfo & g, S32 index, const Point3F& normal)
|
|
{
|
|
mIndex = index;
|
|
mLoc = g.pos;
|
|
mNormal = normal;
|
|
mFlags.set(Inventory, g.isInventory());
|
|
mFlags.set(Algorithmic, g.isAlgorithmic());
|
|
mFlags.set(BelowPortal, g.isBelowPortal());
|
|
mFlags.set(PotentialSeed, g.isSeed());
|
|
}
|
|
|
|
GraphEdge& InteriorNode::pushOneWay(const GraphEdgeInfo::OneWay & edgeIn)
|
|
{
|
|
GraphEdge edgeOn;
|
|
edgeOn.mDest = edgeIn.dest;
|
|
if(edgeIn.isJetting())
|
|
edgeOn.setJetting();
|
|
mEdges.push_back(edgeOn);
|
|
return mEdges.last();
|
|
}
|
|
|
|
InteriorNode::InteriorNode()
|
|
{
|
|
mFlags.set(Indoor);
|
|
mMinDim = 0.5;
|
|
mArea = (mMinDim * mMinDim);
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------------
|
|
|
|
// Must destruct the nodes.
|
|
void IndoorNodeList::clear()
|
|
{
|
|
for (iterator it = begin(); it != end(); it++)
|
|
it->~InteriorNode();
|
|
Parent::clear();
|
|
}
|
|
|
|
void IndoorNodeList::init(S32 size)
|
|
{
|
|
clear();
|
|
setSizeAndConstruct(*this, size);
|
|
}
|
|
|
|
// Must destruct elements.
|
|
IndoorNodeList::~IndoorNodeList()
|
|
{
|
|
clear();
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------------
|
|
|
|
GraphBoundary::GraphBoundary(const GraphEdgeInfo& edgeInfo)
|
|
{
|
|
seg[0] = edgeInfo.segPoints[0];
|
|
seg[1] = edgeInfo.segPoints[1];
|
|
|
|
normal.x = seg[0].y - seg[1].y;
|
|
normal.y = seg[1].x - seg[0].x;
|
|
normal.z = 0;
|
|
F32 len = normal.len();
|
|
AssertFatal(len > 0.001, "GraphBoundry has small border");
|
|
normal *= (1.0f / len);
|
|
}
|
|
|
|
//==> Note - we may want to just have one boundary segment per edge - if so
|
|
// we can still compute both and then merge them. I think we may need both though
|
|
// since we will want to define a complete segment that they can cross over
|
|
// at some point.
|
|
|
|
// Some computations needed to set it up to know how to navigate through there.
|
|
void GraphBoundary::setItUp(S32 nodeIndex, const NodeInfoList& nodes,
|
|
const GraphVolumeList& volumes)
|
|
{
|
|
Point3F midpoint = scaleBetween(seg[0], seg[1], 0.5f);
|
|
|
|
// Set normal to point in the direction (outbound) we need-
|
|
Point3F nodeCenter = nodes[nodeIndex].pos;
|
|
Point3F outbound = (midpoint - nodeCenter);
|
|
if (mDot(outbound, normal) < 0)
|
|
normal *= -1.0;
|
|
|
|
// Find minimum of the midpoint from all planes, skipping current one.
|
|
//==> SKIP??
|
|
//==> This all needs to be better smoothed.
|
|
F32 D, minDist = 1e9;
|
|
S32 numWalls = volumes.planeCount(nodeIndex) - 2;
|
|
const PlaneF* planes = volumes.planeArray(nodeIndex);
|
|
AssertFatal(numWalls > 2, "Graph node has no meaningful volume");
|
|
while (numWalls--)
|
|
if ((D = -planes[numWalls].distToPlane(midpoint)) > 0.01)
|
|
if (D < minDist)
|
|
minDist = D;
|
|
|
|
distIn = getMin(minDist, 1.2f);
|
|
|
|
// Now set up the point we need to go through.
|
|
seekPt = midpoint - (distIn * normal);
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------------
|
|
|
|
bool NavigationGraph::initInteriorNodes(const EdgeInfoList & edges,
|
|
const NodeInfoList & nodes, S32 startIndex)
|
|
{
|
|
// This allocation must happen before (in caller) for edge pool purposes-
|
|
mBoundaries.clear();
|
|
|
|
mHaveVolumes = (mNodeVolumes.size() == nodes.size());
|
|
|
|
// Build node list
|
|
Vector<Point3F> utilityBuffer;
|
|
for (S32 i = 0; i < nodes.size(); i++) {
|
|
Point3F normal(0,0,1);
|
|
F32 minDim = 1.0;
|
|
F32 area = 1.0;
|
|
if (mHaveVolumes) {
|
|
Point3F floorVec = mNodeVolumes.floorPlane(i);
|
|
if (floorVec.z != 0)
|
|
normal = -floorVec;
|
|
else
|
|
warning("Graph needs regeneration (missing floor plane)");
|
|
|
|
minDim = mNodeVolumes.getMinExt(i, utilityBuffer);
|
|
}
|
|
mIndoorNodes[i].init(nodes[i], startIndex + i, normal);
|
|
mIndoorNodes[i].setDims(minDim, area);
|
|
}
|
|
|
|
for (S32 j = 0; j < edges.size(); j++)
|
|
{
|
|
const GraphEdgeInfo& E = edges[j];
|
|
|
|
for (U32 k = 0; k < 2; k++)
|
|
{
|
|
GraphEdgeInfo::OneWay edgeOneWay = E.to[k^1];
|
|
S32 dstIndex = edgeOneWay.dest;
|
|
S32 srcIndex = E.to[k].dest;
|
|
edgeOneWay.dest += startIndex;
|
|
GraphEdge& edge = mIndoorNodes[srcIndex].pushOneWay(edgeOneWay);
|
|
|
|
// set up the boundary information
|
|
if (mHaveVolumes)
|
|
{
|
|
edge.mBorder = mBoundaries.size();
|
|
GraphBoundary boundary(E);
|
|
boundary.setItUp(srcIndex, nodes, mNodeVolumes);
|
|
mBoundaries.push_back(boundary);
|
|
AssertFatal(mBoundaries.size() < (1 << 15), "Maximum Boundaries = 32K");
|
|
}
|
|
}
|
|
}
|
|
|
|
return nodes.size();
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------------
|
|
|
|
// Given a list of interior node indices to get rid of, compact those nodes (and any
|
|
// edges left hanging) out of the lists (mEdgeInfoList & mNodeInfoList). Also
|
|
// compacts out of the volume list if such is present.
|
|
S32 NavigationGraph::compactIndoorData(const Vector<S32>& cullList, S32 numOutdoor)
|
|
{
|
|
// On balance, it's more convenient to map into the indoor node list 'space' here...
|
|
S32 i;
|
|
Vector<S32> axeList(cullList.size());
|
|
for (i = 0; i < cullList.size(); i++)
|
|
axeList.push_back(cullList[i] - numOutdoor);
|
|
|
|
// Minimize fragmentation by pre-reserving.
|
|
NodeInfoList culledNodes(mNodeInfoList.size());
|
|
EdgeInfoList culledEdges(mEdgeInfoList.size());
|
|
BridgeDataList culledBridges;
|
|
GraphVolumeList culledVolumes;
|
|
culledVolumes.reserve(mNodeVolumes.size());
|
|
culledBridges.reserve(mBridgeList.size());
|
|
|
|
// ==> This looks wasteful, these need to be culled
|
|
if (mHaveVolumes)
|
|
culledVolumes.mPlanes = mNodeVolumes.mPlanes;
|
|
|
|
// Mark nodes-to-axe with -1, the rest at zero.
|
|
Vector<S32> remap;
|
|
for (i = 0, setSizeAndClear(remap,mNodeInfoList.size()); i < axeList.size(); i++)
|
|
{
|
|
S32 removedNode = axeList[i];
|
|
AssertFatal(removedNode >= 0, "NavigationGraph::compactIndoorData()");
|
|
remap[removedNode] = -1;
|
|
}
|
|
|
|
// Fetch nodes to keep into new list and build remap indices for remaining
|
|
for (i = 0; i < mNodeInfoList.size(); i++) if (remap[i] == 0)
|
|
{
|
|
remap[i] = culledNodes.size();
|
|
culledNodes.push_back(mNodeInfoList[i]);
|
|
if (mHaveVolumes)
|
|
culledVolumes.push_back(mNodeVolumes[i]);
|
|
}
|
|
|
|
// Copy down culled edge list and remap the "to" pointers.
|
|
for (i = 0; i < mEdgeInfoList.size(); i++)
|
|
{
|
|
GraphEdgeInfo edge = mEdgeInfoList[i];
|
|
if ((edge.to[0].dest = remap[edge.to[0].dest]) >= 0)
|
|
{
|
|
edge.to[1].dest = remap[edge.to[1].dest];
|
|
culledEdges.push_back(edge);
|
|
}
|
|
}
|
|
|
|
// Remap bridge indices, and remove any invalid. Note that outdoor nodes don't get
|
|
// culled, even if they have a stranded pocket.
|
|
for (i = 0; i < mBridgeList.size(); i++)
|
|
{
|
|
GraphBridgeData bridge = mBridgeList[i];
|
|
bool stillGood = true;
|
|
|
|
for (S32 j = 0; stillGood && (j < 2); j++)
|
|
{
|
|
// Remap indoor nodes, or see if it's been culled-
|
|
S32 nodeInd = bridge.nodes[j];
|
|
if (nodeInd >= numOutdoor)
|
|
{
|
|
S32 mappedNode = remap[nodeInd - numOutdoor];
|
|
if (mappedNode >= 0)
|
|
bridge.nodes[j] = (mappedNode + numOutdoor);
|
|
else
|
|
stillGood = false;
|
|
}
|
|
}
|
|
|
|
if (stillGood)
|
|
culledBridges.push_back(bridge);
|
|
}
|
|
|
|
// install the new lists:
|
|
mEdgeInfoList = culledEdges;
|
|
mNodeInfoList = culledNodes;
|
|
mNodeVolumes = culledVolumes;
|
|
mNodeVolumes.cullUnusedPlanes();
|
|
mBridgeList = culledBridges;
|
|
|
|
// whatever-
|
|
return culledNodes.size();
|
|
}
|
|
|