Tribes2/engine
1
0
Fork 0
mirror of https://github.com/tribes2/engine.git synced 2026-01-19 19:24:45 +00:00
Code Issues Actions Packages Projects Releases Wiki Activity
engine/ai/graphBridge.cc

975 lines
34 KiB
C++
Raw Permalink Normal View History

t2 engine svn checkout
2024-01-07 04:36:33 +00:00
//-----------------------------------------------------------------------------
// V12 Engine
//
// Copyright (c) 2001 GarageGames.Com
// Portions Copyright (c) 2001 by Sierra Online, Inc.
//-----------------------------------------------------------------------------
#include "ai/graph.h"
#include "ai/graphLOS.h"
#include "ai/graphBridge.h"
//-------------------------------------------------------------------------------------
// Controls generation-
static bool sSpawnGraph = false;
// Numbers that are different between the two types of graphs. Most jet connections
// on NAV generation use the smaller lateral value, but we special case for large
// terrain-to-terrain hops that are passed through. cf. FireStorm.
#define NAVLateralMax 60.0
#define IslandHopLateralMax 120.0
#define SPNLateralMax 100.0
static const Point3F sBoxOffNAV(IslandHopLateralMax, IslandHopLateralMax, 10000.0);
static const Point3F sBoxOffSPN(SPNLateralMax, SPNLateralMax, 10000.0);
//-------------------------------------------------------------------------------------
static const U32 sLOSMask = InteriorObjectType
| StaticShapeObjectType
| StaticObjectType
| WaterObjectType
| TerrainObjectType;
static Point3F * sBreakPt1 = 0, * sBreakPt2 = 0;
static SphereF * sMagSphere;
static F32 sBreakRangeXY = 0.5, sBreakRangeZ = 2.0;
static const S32 sGraphFanCount = 10; // ==> 1-11-1, reduced, should be fine.
static const F32 sGraphFanWidth = 1.0;
static const F32 sWideFanRaise = 1.3;
// Clear distance assures they can get over a ledge, land Dist assures there's purchase.
// Second clear dist is for case when one node is a portal (i.e. chutes)
static const F32 sClearDists[2] = {1.3, 1.0};
static const F32 sLandDists[2] = {0.4, 0.2};
static const F32 sJumpAngDot = 0.707;
// NOT SURE ABOUT THIS # Sometimes we want more - maybe allow other checks to insure
// that things work when it's small (clear dist, etc.) There are some small ledge
// hops which are needed - but hop over code will probably assure...
static const F32 sMinXY = 2.0;
static const F32 sMinXYSqrd = (sMinXY * sMinXY);
static const Point3F sMinAboveVec(0,0,2.0);
#define SlightlyOffFloor 0.157
#define MaxHopOverXY 37.0
// lhpatch- Make this # go on graph (was barely too small in one map at 17)
#define MaxWalkableXY 20.0
#define MinLateralThresh 12.0
//-------------------------------------------------------------------------------------
#define SquareOf(x) ((x)*(x))
static bool bridgeable(const Point3F& from, const Point3F& to, bool bothOutdoor)
{
F32 lateralThresh;
if (sSpawnGraph)
{
lateralThresh = SPNLateralMax;
}
else
{
if (bothOutdoor)
lateralThresh = IslandHopLateralMax;
else
lateralThresh = NAVLateralMax;
// Pull down the lateral thresh for tall hops. Basically subtract off of it for
// every meter of Z, but keep a minimum amount, which is necessary to assure
// floating bases do get bridged (if only the downward hop is doable).
if ( (lateralThresh -= mFabs(from.z - to.z)) < MinLateralThresh )
lateralThresh = MinLateralThresh;
}
Point2F lateral(from.x - to.x, from.y - to.y);
return (lateral.lenSquared() < SquareOf(lateralThresh));
}
//-------------------------------------------------------------------------------------
// Get the fan vector in passed ref, and return number of increments. horzVec
// is a horizontal vector guaranteed to have length.
static S32 calcFanVector(const VectorF& horzVec, VectorF& fanIncOut)
{
fanIncOut.set(-horzVec.y, horzVec.x, 0);
fanIncOut.normalize(sGraphFanWidth / F32(sGraphFanCount));
return sGraphFanCount;
}
//-------------------------------------------------------------------------------------
// Some code for isolating cases in the debugger. Mainly for focusing on a couple of
// nodes to see why they're not getting bridged. See navGraph.genDebug() in graph.cc
static bool doBreak() {return true;}
static bool checkEnds(const Point3F& n1, const Point3F& n2)
{
if (mFabs(n1.x - sBreakPt1->x) < sBreakRangeXY)
if (mFabs(n2.x - sBreakPt2->x) < sBreakRangeXY)
if (mFabs(n2.y - sBreakPt2->y) < sBreakRangeXY)
if (mFabs(n1.y - sBreakPt1->y) < sBreakRangeXY)
if (mFabs(n1.z - sBreakPt1->z) < sBreakRangeZ)
if (mFabs(n2.z - sBreakPt2->z) < sBreakRangeZ)
return doBreak();
return false;
}
//-------------------------------------------------------------------------------------
GraphBridge::GraphBridge(const GraphNodeList& mainList, S32 islands,
BridgeDataList& listOut)
: mMainList(mainList),
mIslands(islands),
mBridgesOut(listOut)
{
heedSeeds(false);
}
//-------------------------------------------------------------------------------------
// This is a bit indirect... but here's where we control which brdiges to attempt on
// the two passes. On the first, all seeds are ignored. On the second we only bridge
// where at least one useful seed is present, and NO useless seed is involved.
bool GraphBridge::heedThese(const GraphNode* from, const GraphNode* to)
{
if (mHeedSeeds)
if (from->usefulSeed() || to->usefulSeed())
return !(from->uselessSeed() || to->uselessSeed());
else
return false;
else
return !(from->potentialSeed() || to->potentialSeed());
}
void GraphBridge::heedSeeds(bool b)
{
mHeedSeeds = b;
}
//-------------------------------------------------------------------------------------
// Try straight distance for the ratios. After we added good scale values on the
// edges, our bridger makes too many edges since the ratios are off. Until this is
// addressed (if indeed it really needs it), let's use straight distance on edges.
F32 GraphBridge::getEdgeTime(const GraphEdge * edge)
{
return edge->mDist;
}
//-------------------------------------------------------------------------------------
// Here's where we do all the work - try to see if a bridge exists.
//
bool GraphBridge::tryToBridge(const GraphNode* from, const GraphNode* to, F32 heuristic)
{
// This is actually where the separate passes (normal, then seeding) is controlled-
if (!heedThese(from, to))
return false;
// Check for in, or near, liquids.
if (from->liquidZone() || to->liquidZone())
return false;
S32 fromIndex = from->getIndex();
S32 toIndex = to->getIndex();
Point3F fromLoc = from->location();
Point3F toLoc = to->location();
bool oneIsPortal = (from->belowPortal() ^ to->belowPortal());
// Debug stopping points.
if (sBreakPt1 && sBreakPt2)
{
if (checkEnds(fromLoc, toLoc) || checkEnds(toLoc, fromLoc))
if (oneIsPortal)
doBreak();
}
// NOTE: we can make the OffFloor amount smaller if outdoor node locations are
// raised up to always be above terrain. (U16 rounding I think)
fromLoc.z += SlightlyOffFloor;
toLoc.z += SlightlyOffFloor;
bool bothOutside = (from->outdoor() && to->outdoor());
if (from->neighbors(to))
return false;
else
{
// Prefer to bridge going UP to insure that the ratio check gets handled (larger
// travel times going up).
if (fromLoc.z > toLoc.z)
return false;
else if (fromLoc.z == toLoc.z && fromIndex > toIndex)
return false;
}
// Create low, high, mid (point above low, but on level with high).
Point3F mid, low, high;
low = fromLoc;
high = toLoc;
(mid = low).z = high.z;
F32 zDist = (high.z - low.z);
// Get 2D dist
Point2F xyVec(toLoc.x - fromLoc.x, toLoc.y - fromLoc.y);
F32 xyDistSq = xyVec.lenSquared();
// Handles all the LOS work
Loser los(sLOSMask, true);
if ((xyDistSq > 0.0001) && bridgeable(fromLoc, toLoc, bothOutside))
{
Point3F aboveM, aboveH, clearPt, landRoom, across;
bool isChute = false, chuteTop = false;
bool walkable = false, gapWalk = false;
bool canCheckJet = true, direct = false;
bool makeBridge = false;
F32 wall;
// See if we shouldn't look for jetting.
F32 xyDist = mSqrt(xyDistSq);
if (from->inventory() || to->inventory() || xyDistSq < sMinXYSqrd)
canCheckJet = false;
else
{
if (from->getNormal().z < sJumpAngDot || to->getNormal().z < sJumpAngDot)
canCheckJet = false;
}
bool checkLandRoom = (zDist > 1.0 && to->indoor());
Point3F aboveVec = sMinAboveVec;
aboveM = mid + aboveVec;
aboveH = high + aboveVec;
across = (high - mid);
across.normalize();
clearPt = mid + (sClearDists[oneIsPortal] * across);
landRoom = high - (sLandDists[oneIsPortal] * across);
// Move back on the up checks so the guy has room behind him. We have to
// raise up the low a little bit to account for slope, but of course
// we can't raise more than height.
if (canCheckJet)
{
// There are two types of chute situations here, one for if we have this
// connection goes to the top of the chute, the other for middle ones.
// For the top we do a slope check off the collision up there and are lax
// about other LOS checks. For the middle we require a couple more.
if (ChuteHints::Info info = gNavGraph->getChutes().info(low, mid))
{
isChute = true;
if (info == ChuteHints::ChuteTop)
chuteTop = true;
}
// Might still want to do a little of this on chutes... ?
if (!isChute)
{
VectorF backUpVec = (across * 0.8);
low -= backUpVec;
low.z += getMin(2.0f, zDist);
mid -= backUpVec;
aboveM -= backUpVec;
}
}
bool walkOff = los.haveLOS(mid, high);
bool hopOver = false;
if (!walkOff && xyDist < MaxHopOverXY)
{
hopOver = los.findHopLine(mid, high, 2, wall);
if (hopOver)
{
mid.z += wall;
high.z += wall;
aboveM.z += wall;
aboveH.z += wall;
}
}
if (walkOff || hopOver)
if (los.haveLOS(high, aboveH))
if (chuteTop || los.haveLOS(low, aboveM))
if (chuteTop || los.haveLOS(aboveM, aboveH))
{
// Don't do walk checks between two outdoor nodes-
if (!isChute && (!from->outdoor() || !to->outdoor()))
{
// do gap walk for special case of small zdiff or direct LOS
direct = los.haveLOS(low, high);
if (direct)
gapWalk = los.walkOverGaps(low, high, 0.8);
else if (zDist < gNavGlobs.mStepHeight)
gapWalk = los.walkOverGaps(mid, high, 0.8);
// If there's a wall to hop over, don't do the walk code. Also, if both
// nodes are in the same island, we only consider walking if the
// heuristic (ratio of best-path-so-far to straight line dist) is high.
if (walkOff)
if ((from->island() != to->island()) || (heuristic > 3.7))
walkable = los.walkOverBumps(aboveM, aboveH);
}
if (walkable || canCheckJet)
{
// Do the fanned LOS - just replicate the above slew of checks.
VectorF fanInc;
S32 numFan = calcFanVector(across, fanInc);
// Added extra checks 1-11-1: Must do a wider fanned check on
// low -> aboveM. Connections without room are slipping through
// the tests because they are diagonal. Also must from a point
// below the clear point, else they effectively can't clear on
// tall hops.
bool ignoreWide = (chuteTop || (zDist < sWideFanRaise + 0.1));
Point3F aboveL, belowC;
if (!ignoreWide)
{
aboveL.set(low.x, low.y, low.z + sWideFanRaise);
belowC.set(clearPt.x, clearPt.y, low.z + sWideFanRaise);
}
if (los.fannedLOS1(high, aboveH, fanInc, numFan))
if (los.fannedLOS1(high, mid, fanInc, numFan))
if (chuteTop || los.fannedLOS1(low, aboveM, fanInc, numFan))
if (chuteTop || los.fannedLOS2(aboveM, aboveH, fanInc, numFan))
if (ignoreWide || los.fannedLOS2(aboveL, aboveM, fanInc, numFan))
{
if (!isChute)
{
if (gapWalk)
if (direct) // in the direct case we need one more fanned LOS
gapWalk = los.fannedLOS1(low, high, fanInc, numFan);
if (gapWalk)
walkable = true;
else if (walkable) // (i.e. walkable so far in our checks)
walkable = los.fannedBumpWalk(aboveM, aboveH, fanInc, numFan);
}
if (walkable)
{
// Well, it's too bad we had to do all this work on to find long
// connections that we throw out, but we have to figure out if it
// needs jet.
makeBridge = (xyDist < MaxWalkableXY);
}
else
{
if (canCheckJet && (xyDist > GraphJetBridgeXY))
{
// The clear check is only needed for jetting connections,
// same with landing room check - which we should only use when
// going up to indoor nodes (and one LOS failure is adequate)
if (!checkLandRoom || !los.haveLOS(low, landRoom))
if (isChute || los.haveLOS(low, clearPt))
if (isChute || los.fannedLOS1(low, clearPt, fanInc, numFan))
if (ignoreWide || los.fannedLOS2(belowC, clearPt, fanInc, numFan))
{
// Check for bonk due to jumps, which add a couple meters.
// We want this to pass chutes and other indoor situations Ok,
// so do LOS up at each end and use that as endpoints.
F32 jumpAdd = (oneIsPortal && xyDist < LiberalBonkXY ? 0.6 : gNavGlobs.mJumpAdd);
aboveM.z += (los.heightUp(aboveM, jumpAdd) - 0.1);
aboveH.z += (los.heightUp(aboveH, jumpAdd) - 0.1);
if (isChute || los.fannedLOS2(aboveM, aboveH, fanInc, numFan))
makeBridge = true;
}
// LOS keeps track of this at lowest level- don't allow
// jetting connections through force fields.
if (los.mHitForceField)
makeBridge = false;
}
}
}
}
}
if (makeBridge)
{
GraphBridgeData bridge1(fromIndex, toIndex);
if (walkable)
bridge1.setWalkable();
if (hopOver)
bridge1.setHop(wall);
mBridgesOut.push_back(bridge1);
return true;
}
}
return false;
}
// We use a searcher to find those same-island nodes which we should try to bridge
// to - namely those who are far on the path relative to straight line distance.
// This will hopefully find for us all indoor jetting connections which are 'useful',
// as well as finding which terrain nodes should be bridged (like over water).
void GraphBridge::onQExtraction()
{
GraphNode * mExtractNode = extractedNode();
if (mExtractNode != mCurrent)
{
if (mSameIslandMark.test(mHead.mIndex))
{
AssertFatal(mSameIslandCount > 0, "GraphBridge::onQExtraction()");
// done when we've visited all the possibilities in the same island
if (--mSameIslandCount == 0)
setEarlyOut(true);
Point3F nodeLoc = mExtractNode->location();
F32 straightLineDist = (mStartLoc - nodeLoc).len();
if (straightLineDist > 0.01)
{
bool bothOutdoor = (mFromOutdoor && mExtractNode->outdoor());
F32 ratio = distSoFar() / straightLineDist;
F32 thresh = mRatios[bothOutdoor];
if (ratio > thresh)
{
// Same-island bridges with good ratios are considered first...
Candidate candidate(mExtractNode, -ratio);
mCandidates.push_back(candidate);
}
}
mSameIslandMark.clear(mHead.mIndex);
}
}
}
// Do all the bridging. Has two modes- spawn and regular nav. Each iteration performs
// one loop of bridging- from one source node to all nodes that need to be bridged.
S32 GraphBridge::findAllBridges()
{
S32 nodeCount = mMainList.size();
Vector<S32> islandCross(mIslands);
GraphNodeList considerList;
mSameIslandMark.setSize(nodeCount);
mSameIslandMark.clear();
mRatios[1] = 1.6; // Outdoor-to-outdoor- try a little smaller ratio than-
mRatios[0] = 2.2; // Other combinations of connections
setSizeAndClear(islandCross, mIslands);
for (S32 i = 0; i < nodeCount; i++)
{
if ((mCurrent = mMainList[i]) != NULL)
{
// Get list of all possibilities (bound box query)
mStartLoc = mCurrent->location();
if (sMagSphere)
{
Point3F pt = sMagSphere->center;
if ((pt -= mStartLoc).lenSquared() > SquareOf(sMagSphere->radius))
continue;
}
Point3F boxOff = (sSpawnGraph ? sBoxOffSPN : sBoxOffNAV);
Box3F area(mStartLoc - boxOff, mStartLoc + boxOff);
S32 curIsland = mCurrent->island();
gNavGraph->getNodesInBox(area, considerList);
// Divy out those in separate island, and mark those in the same island for
// consideration by the special seacher.
mCandidates.clear();
mSameIslandCount = 0;
for (S32 j = 0; j < considerList.size(); j++) {
GraphNode * consider = considerList[j];
if (consider != mCurrent) {
if (consider->island() == curIsland) {
if (!sSpawnGraph) {
mSameIslandMark.set(consider->getIndex());
mSameIslandCount++;
}
}
else {
// Bridges to different islands sorted by distance
F32 dist = (mStartLoc - consider->location()).lenSquared();
Candidate candidate(consider, dist);
mCandidates.push_back(candidate);
}
}
}
// Special search to find which same-island nodes need consideration. We want
// to bridge same-island nodes if their ground travel distance is far relative
// to their straight-line distance.
if (!sSpawnGraph)
{
setEarlyOut(false);
mFromOutdoor = mCurrent->outdoor();
performSearch(mCurrent, NULL);
}
// Candidates considered in order of best-ness heuristic
mCandidates.sort();
// Try to bridge to all candidates which remain.
setSizeAndClear(islandCross, mIslands);
for (CandidateList::iterator c = mCandidates.begin(); c != mCandidates.end(); c++)
{
if (sSpawnGraph)
{
// For spawn we only need to cross to an island once.
if (!islandCross[c->node->island()])
if (tryToBridge(mCurrent, c->node))
islandCross[c->node->island()] = true;
}
else
{
// For regular graph, allow a certain number of bridges to each island.
// Need to sort list, and vary base on island size. We pass in the
// heuristic # for avoiding too many walking connections.
if (islandCross[c->node->island()] < 3)
if (tryToBridge(mCurrent, c->node, -(c->heuristic)))
islandCross[c->node->island()]++;
}
}
}
}
return mBridgesOut.size();
}
S32 gCountReplacementEdges, gCountUnreachable;
// This checks to see if outdoor neighbor edges need to be modified or removed due
// to steepness. If so, a special 'replacement' bridge is created, which either
// removes the default one at startup, or converts it to a jetting connection. Note
// that this also needs to remove steep edges underwater as well.
void GraphBridge::checkOutdoor(const GraphNode* from, const GraphNode* to)
{
static const F32 stepD = 0.3;
Point3F fromLoc = from->location();
Point3F toLoc = to->location();
// Vector for stepping sideways, and across. We're given that these are
// non-zero vectors since from and to are separate neighbors.
Point3F across = (toLoc - fromLoc);
Point3F sideVec(across.y, -across.x, 0);
sideVec.normalize(0.8);
// Figure out step across vector, and number of iterations.
across.z = 0;
F32 dist2D = across.len();
S32 numSteps = S32(dist2D / stepD + 1.0);
across /= F32(numSteps);
// Get top and bottom points. Add amount should be enough given that the
// consolidator generally won't pass really large peaks between nodes.
F32 maxZ = getMax(fromLoc.z, toLoc.z);
Point3F stepVec(fromLoc.x, fromLoc.y, maxZ);
// Step three separate lines across to account for player width.
VectorF normal;
F32 height, previousZ, highestZ = -1e12;
bool removeEdge = false;
bool walkable = true;
stepVec -= sideVec;
for (F32 sideWise = 0.0; sideWise < 2.1 && !removeEdge; sideWise += 1.0)
{
Point3F point = (stepVec + sideVec * sideWise);
if (gNavGraph->terrainHeight(point, &height))
highestZ = getMax(previousZ = height, highestZ);
else
removeEdge = true;
// Do loop plus one extra for last point. Look for too steep a slope if our Z
// is increasing. This means we can't walk. Also check to see if it's possible
// to jet - namely if the highest point isn't too far above higher node.
for (S32 N = 0; N <= numSteps && !removeEdge; N++, point += across)
{
if (gNavGraph->terrainHeight(point, &height, &normal))
{
// Going up and too steep?
if (normal.z < gNavGlobs.mWalkableDot && height > previousZ)
walkable = false;
highestZ = getMax(previousZ = height, highestZ);
}
else
removeEdge = true;
}
}
// Most of the time, this should happen-
if (walkable && !removeEdge)
return;
GraphBridgeData bridge(from->getIndex(), to->getIndex());
bridge.setReplacement();
// See if we can at least jet.
if (!removeEdge &&
(from->getNormal().z >= sJumpAngDot && to->getNormal().z >= sJumpAngDot) &&
(!from->liquidZone() && !to->liquidZone()) &&
(highestZ - maxZ < 5.0)
)
{
gCountReplacementEdges++;
bridge.setHop(highestZ - maxZ + 1.0);
}
else
{
gCountUnreachable++;
bridge.setUnreachable();
}
mBridgesOut.push_back(bridge);
}
// Special pass to find those outdoor neighbors that are too steep to walk up. The
// collision checking in checkOutdoor() only masks with terrain since it is already
// established that there are no other obstructions along the ground.
void GraphBridge::trimOutdoorSteep()
{
gCountReplacementEdges = 0;
gCountUnreachable = 0;
S32 nodeCount = mMainList.size();
for (S32 i = 0; i < nodeCount; i++)
if (GraphNode * from = mMainList[i])
if (from->outdoor()) {
GraphEdgeArray edges = from->getEdges(NULL);
while (GraphEdge * e = edges++)
if (!e->isJetting())
if (GraphNode * to = gNavGraph->lookupNode(e->mDest))
if (to->outdoor())
checkOutdoor(from, to);
}
}
//-------------------------------------------------------------------------------------
S32 QSORT_CALLBACK GraphBridge::CandidateList::cmpCandidates(const void * a,const void * b)
{
F32 A = ((Candidate*)a)->heuristic;
F32 B = ((Candidate*)b)->heuristic;
return (A < B ? -1 : (A > B ? 1 : 0));
}
void GraphBridge::CandidateList::sort()
{
dQsort((void* )(this->address()), this->size(), sizeof(Candidate), cmpCandidates);
}
//-------------------------------------------------------------------------------------
// Something to make it easy to quickly check out the graph generation in a particular
// area by only doing bridge building in that vicinity.
void NavigationGraph::setGenMagnify(const SphereF * sphere,
const Point3F * end1, const Point3F * end2,
F32 xyCheck, F32 zCheck)
{
static SphereF sSphere;
static Point3F sPoint1, sPoint2;
sMagSphere = NULL;
sBreakPt2 = sBreakPt1 = NULL;
if (sphere)
*(sMagSphere = &sSphere) = *sphere;
if (end1)
*(sBreakPt1 = &sPoint1) = *end1;
if (end2)
*(sBreakPt2 = &sPoint2) = *end2;
sBreakRangeXY = xyCheck;
sBreakRangeZ = zCheck;
}
//-------------------------------------------------------------------------------------
const char * NavigationGraph::findBridges()
{
const char * errorText = NULL;
if (!mIslandPtrs.size())
errorText = "Error: islands haven't been marked in graph";
else
{
BridgeDataList bridges;
GraphBridge builder(mNodeList, numIslands(), bridges);
sSpawnGraph = mIsSpawnGraph;
Loser::mCasts = 0;
builder.findAllBridges();
builder.trimOutdoorSteep();
// set the graph variable:
mBridgeList = bridges;
}
return errorText;
}
const char * NavigationGraph::pushBridges()
{
if (mPushedBridges)
return "Bridges already pushed - do MakeGraph() to remove them";
if (mBridgeList.size() == 0)
return "No bridges exist";
for (S32 i = 0; i < mBridgeList.size(); i++)
{
GraphBridgeData & B = mBridgeList[i];
if (!B.isReplacement())
{
for (S32 k = 0; k < 2; k++)
{
RegularNode * src = dynamic_cast<RegularNode*>(mNodeList[B.nodes[k^0]]);
RegularNode * dst = dynamic_cast<RegularNode*>(mNodeList[B.nodes[k^1]]);
GraphEdge& edge = src->pushEdge(dst);
if (B.mustJet()) {
edge.setJetting();
if (B.jetClear)
edge.setHop(B.jetClear);
}
mJetManager.initEdge(edge, src, dst);
}
}
else
{
mJetManager.replaceEdge(B);
}
}
Con::printf("Connected %d bridges", mBridgeList.size());
mPushedBridges = true;
markIslands();
return NULL;
}
//-------------------------------------------------------------------------------------
GraphSeeds::GraphSeeds(NavigationGraph& graph)
: mGraph(graph),
mLoser(InteriorObjectType)
{
// Save node count for later mapping into antecedent index table.
mOriginalCount = graph.numNodes();
}
// Add the seed. We have to remember our parent (antecedent) that spawned us thinking
// that we might be potentially useful.
void GraphSeeds::pushSeed(GraphNode* antecedent, const Point3F& pos, GraphSeed::Type type)
{
S32 index = antecedent->getIndex();
GraphSeed seed(index, pos, type);
mAntecedents.push_back(index);
push_back(seed);
}
Point3F sgCheckSeedUpper(-149.0, -136.5, 166.42);
// Look at drop off from each edge of node. If it lands inside of an interior volume
// with a modicum of containment, then we want to add a seed node there.
void GraphSeeds::seedDropOffs(GraphNode * antecedent)
{
// Just for quick testing - look at our shape and see if we can get the behavior we
// want locally here-
// if (!within(antecedent->location(), sgCheckSeedUpper, 0.6))
// return;
mVolume = mGraph.fetchVolume(antecedent, false);
Vector<Point3F> &corners = mVolume.mCorners;
if (S32 N = corners.size())
{
// Simplify the loop-
corners.push_back(corners[0]);
// Do drop offs on each edge.
for (S32 i = 0; i < N; i++)
{
Point3F p0 = corners[i + 0];
Point3F p1 = corners[i + 1];
Point3F drop = scaleBetween(p0, p1, 0.5);
VectorF normal(p0.y - p1.y, p1.x - p0.x, 0);
F32 len = normal.len();
if (len > 0.01)
{
// Go out at least by clear distance. Insure we're above our plane.
normal *= ((sClearDists[0] * 1.2) / len);
drop += normal;
F32 floorZ = solveForZ(mVolume.mFloor, drop);
drop.z = (floorZ + 0.5);
if (mLoser.hitBelow(drop, 50.0f))
{
// Now see if we landed inside of a (different) node that's large,
// as defined by having good containment on this point.
drop.z += 0.2;
F32 containment;
// if (within(drop, sgCheckSeedLower, 3.0))
if (GraphNode * closest = mGraph.closestNode(drop, &containment))
{
if (closest == antecedent)
{
AssertFatal(containment > 0, "GraphSeeds::seedDropOffs()");
}
else
{
if (containment < -1.3)
{
GraphSeed::Type seedType = GraphSeed::DropOff;
// For those close to chute nodes, we make these regular nodes
// that go through full bridging process.
if (mGraph.getChutes().findNear(drop, 2.2, 1.0, mNearChutes))
seedType = GraphSeed::Regular;
}
}
}
}
}
}
}
}
// Procedure is then to cast across any of the walls we are outside of and see if
// the point that is cast across has decent containment within this selfsame node.
// Probably the containment we are looking for is a little less than the cast
// across distance. If Ok, then we create the node with our given antecedent.
// See crossNearbyVolumes() in graphFind.cc where most of this work happens.
void GraphSeeds::seedInventory(GraphNode * antecedent)
{
Vector<Point3F> crossings;
const Point3F& nodeLoc = antecedent->location();
if (S32 N = mGraph.crossNearbyVolumes(antecedent->location(), crossings))
for (S32 i = 0; i < N; i++)
if (mLoser.haveLOS(nodeLoc, crossings[i]))
pushSeed(antecedent, crossings[i], GraphSeed::Inventory);
}
S32 GraphSeeds::scatter()
{
for (S32 i = 0; i < mGraph.numNodes(); i++)
if (GraphNode * node = mGraph.lookupNode(i))
if (node->indoor())
if (node->inventory())
seedInventory(node);
else if (NavigationGraph::sSeedDropOffs)
seedDropOffs(node);
return size();
}
// Find those seeds which have antecedents that aren't part of the largest island
// in the graph. These are the seeds we will want to use. For the drop off seeds
// we only attempt to bridge to their antecedent.
void GraphSeeds::markUsefulSeeds()
{
// Make sure offsets are managed Ok - all seeds should now be nodes.
AssertFatal(mOriginalCount + size() == mGraph.numNodes(), "markUsefulSeeds()");
for (iterator it = begin(); it != end(); it++)
{
GraphNode * antecedent = mGraph.lookupNode(it->antecedent());
if (antecedent->island() != mGraph.largestIsland())
{
S32 mapIndex = mOriginalCount + (it - begin());
GraphNode * seed = mGraph.lookupNode(mapIndex);
// Bridge builder uses this bit-
seed->setUsefulSeed();
}
}
}
//-------------------------------------------------------------------------------------
#define SeedBoxW 0.3
#define SeedBoxH 2.0
// Here's where we're adding the seed into the (persisted) data lists. They will
// take effect as run time nodes on the next call to makeGraph().
void NavigationGraph::installSeed(const Point3F& pos)
{
IndoorNodeInfo nodeInfo;
nodeInfo.pos = pos;
nodeInfo.setSeed(true);
mNodeInfoList.push_back(nodeInfo);
mNodeVolumes.addVolume(pos, SeedBoxW, SeedBoxH);
}
//
// What was previously several calls from script (makeGraph, findBridges, pushBridges)
// has now been rolled altogether for the purposes of trying to fill the last holes
// that we are seeing in the graph. This assumes that script has already uploaded
// the groundPlan and floorPlan information.
//
bool NavigationGraph::assemble()
{
sSpawnGraph = mIsSpawnGraph;
Loser::mCasts = 0;
// First we need a made graph for the seeder to work.
makeGraph();
// Look for problem areas and scatter seeds.
GraphSeeds seeds(*this);
seeds.scatter();
for (S32 i = 0; i < seeds.size(); i++)
installSeed(seeds[i].location());
// Remake to create the run time seed nodes.
makeGraph();
// Now build bridges WITHOUT using the seed nodes-
BridgeDataList bridges;
GraphBridge bridgeBuilder(mNodeList, numIslands(), bridges);
bridgeBuilder.heedSeeds(false);
bridgeBuilder.findAllBridges();
// Set the bridges and connect. This finds largest island, which puts us -
mBridgeList = bridges;
pushBridges();
// - in a position to know which seeds might matter (those with stranded parents)
seeds.markUsefulSeeds();
// Now bridge seed nodes-
bridges.clear();
bridgeBuilder.heedSeeds(true);
bridgeBuilder.findAllBridges();
// Still need to trim outdoor steep connections (this adds to bridges)
bridgeBuilder.trimOutdoorSteep();
// Add the new bridges to the list and rebuild everything-
mBridgeList.merge(bridges);
makeGraph();
pushBridges();
// Done
return 0;
}
Reference in a new issue Copy permalink