This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Oct 12th, 2011  |  syntax: None  |  size: 60.13 KB  |  views: 27  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.  
  2. //========= Copyright © 1996-2005, Valve Corporation, All rights reserved. ============//
  3. //
  4. // Purpose:
  5. //
  6. // $NoKeywords: $
  7. //
  8. //=============================================================================//
  9. // nav_generate.cpp
  10. // Auto-generate a Navigation Mesh by sampling the current map
  11. // Author: Michael S. Booth (mike@turtlerockstudios.com), 2003
  12.  
  13. #include "cbase.h"
  14. #include "util_shared.h"
  15. #include "nav_mesh.h"
  16. #include "nav_node.h"
  17. #include "nav_pathfind.h"
  18. #include "viewport_panel_names.h"
  19.  
  20. enum { MAX_BLOCKED_AREAS = 256 };
  21. static unsigned int blockedID[ MAX_BLOCKED_AREAS ];
  22. static int blockedIDCount = 0;
  23. static float lastMsgTime = 0.0f;
  24.  
  25.  
  26. ConVar nav_slope_limit( "nav_slope_limit", "0.7", FCVAR_GAMEDLL, "The ground unit normal's Z component must be greater than this for nav areas to be generated." );
  27. ConVar nav_restart_after_analysis( "nav_restart_after_analysis", "1", FCVAR_GAMEDLL, "When nav nav_restart_after_analysis finishes, restart the server.  Turning this off can cause crashes, but is useful for incremental generation." );
  28.  
  29.  
  30. //--------------------------------------------------------------------------------------------------------------
  31. inline float round( float val, float unit )
  32. {
  33.         val = val + ((val < 0.0f) ? -unit*0.5f : unit*0.5f);
  34.         return (float)( ((int)val) / (int)unit );
  35. }
  36.  
  37.  
  38. //--------------------------------------------------------------------------------------------------------------
  39. /**
  40.  * Shortest path cost, paying attention to "blocked" areas
  41.  */
  42. class ApproachAreaCost
  43. {
  44. public:
  45.         float operator() ( CNavArea *area, CNavArea *fromArea, const CNavLadder *ladder )
  46.         {
  47.                 // check if this area is "blocked"
  48.                 for( int i=0; i<blockedIDCount; ++i )
  49.                 {
  50.                         if (area->GetID() == blockedID[i])
  51.                         {
  52.                                 return -1.0f;
  53.                         }
  54.                 }
  55.  
  56.                 if (fromArea == NULL)
  57.                 {
  58.                         // first area in path, no cost
  59.                         return 0.0f;
  60.                 }
  61.                 else
  62.                 {
  63.                         // compute distance traveled along path so far
  64.                         float dist;
  65.  
  66.                         if (ladder)
  67.                         {
  68.                                 dist = ladder->m_length;
  69.                         }
  70.                         else
  71.                         {
  72.                                 dist = (area->GetCenter() - fromArea->GetCenter()).Length();
  73.                         }
  74.  
  75.                         float cost = dist + fromArea->GetCostSoFar();
  76.  
  77.                         return cost;
  78.                 }
  79.         }
  80. };
  81.  
  82.  
  83. //--------------------------------------------------------------------------------------------------------------
  84. /**
  85.  * Determine the set of "approach areas".
  86.  * An approach area is an area representing a place where players
  87.  * move into/out of our local neighborhood of areas.
  88.  * @todo Optimize by search from eye outward and modifying pathfinder to treat all links as bi-directional
  89.  */
  90. void CNavArea::ComputeApproachAreas( void )
  91. {
  92.         m_approachCount = 0;
  93.  
  94.         if (nav_quicksave.GetBool())
  95.                 return;
  96.  
  97.         // use the center of the nav area as the "view" point
  98.         Vector eye = m_center;
  99.         if (TheNavMesh->GetGroundHeight( eye, &eye.z ) == false)
  100.                 return;
  101.  
  102.         // approximate eye position
  103.         if (GetAttributes() & NAV_MESH_CROUCH)
  104.                 eye.z += 0.9f * HalfHumanHeight;
  105.         else
  106.                 eye.z += 0.9f * HumanHeight;
  107.  
  108.         enum { MAX_PATH_LENGTH = 256 };
  109.         CNavArea *path[ MAX_PATH_LENGTH ];
  110.         ApproachAreaCost cost;
  111.  
  112.         enum SearchType
  113.         {
  114.                 FROM_EYE,               ///< start search from our eyepoint outward to farArea
  115.                 TO_EYE,                 ///< start search from farArea beack towards our eye
  116.                 SEARCH_FINISHED
  117.         };
  118.  
  119.         //
  120.         // In order to *completely* enumerate all of the approach areas, we
  121.         // need to search from our eyepoint outward, as well as from outwards
  122.         // towards our eyepoint
  123.         //
  124.         for( int searchType = FROM_EYE; searchType != SEARCH_FINISHED; ++searchType )
  125.         {
  126.                 //
  127.                 // In order to enumerate all of the approach areas, we need to
  128.                 // run the algorithm many times, once for each "far away" area
  129.                 // and keep the union of the approach area sets
  130.                 //
  131.                 int it;
  132.                 for( it = TheNavAreaList.Head(); it != TheNavAreaList.InvalidIndex(); it = TheNavAreaList.Next( it ) )
  133.                 {
  134.                         CNavArea *farArea = TheNavAreaList[ it ];
  135.  
  136.                         blockedIDCount = 0;
  137.  
  138.                         // skip the small areas
  139.                         const float minSize = 200.0f;           // 150
  140.                         const Extent &extent = farArea->GetExtent();
  141.                         if (extent.SizeX() < minSize || extent.SizeY() < minSize)
  142.                         {
  143.                                 continue;
  144.                         }
  145.  
  146.                         // if we can see 'farArea', try again - the whole point is to go "around the bend", so to speak
  147.                         if (farArea->IsVisible( eye ))
  148.                         {
  149.                                 continue;
  150.                         }
  151.  
  152.                         //
  153.                         // Keep building paths to farArea and blocking them off until we
  154.                         // cant path there any more.
  155.                         // As areas are blocked off, all exits will be enumerated.
  156.                         //
  157.                         while( m_approachCount < MAX_APPROACH_AREAS )
  158.                         {
  159.                                 CNavArea *from, *to;
  160.  
  161.                                 if (searchType == FROM_EYE)
  162.                                 {
  163.                                         // find another path *to* 'farArea'
  164.                                         // we must pathfind from us in order to pick up one-way paths OUT OF our area
  165.                                         from = this;
  166.                                         to = farArea;
  167.                                 }
  168.                                 else // TO_EYE
  169.                                 {
  170.                                         // find another path *from* 'farArea'
  171.                                         // we must pathfind to us in order to pick up one-way paths INTO our area
  172.                                         from = farArea;
  173.                                         to = this;
  174.                                 }
  175.  
  176.                                 // build the actual path
  177.                                 if (NavAreaBuildPath( from, to, NULL, cost ) == false)
  178.                                 {
  179.                                         break;
  180.                                 }
  181.  
  182.                                 // find number of areas on path
  183.                                 int count = 0;
  184.                                 CNavArea *area;
  185.                                 for( area = to; area; area = area->GetParent() )
  186.                                 {
  187.                                         ++count;
  188.                                 }
  189.  
  190.                                 if (count > MAX_PATH_LENGTH)
  191.                                 {
  192.                                         count = MAX_PATH_LENGTH;
  193.                                 }
  194.  
  195.                                 // if the path is only two areas long, there can be no approach points
  196.                                 if (count <= 2)
  197.                                 {
  198.                                         break;
  199.                                 }
  200.  
  201.                                 // build path starting from eye
  202.                                 int i = 0;
  203.  
  204.                                 if (searchType == FROM_EYE)
  205.                                 {
  206.                                         for( area = to; i < count && area; area = area->GetParent() )
  207.                                         {
  208.                                                 path[ count-i-1 ] = area;
  209.                                                 ++i;
  210.                                         }
  211.                                 }
  212.                                 else // TO_EYE
  213.                                 {
  214.                                         for( area = to; i < count && area; area = area->GetParent() )
  215.                                         {
  216.                                                 path[ i++ ] = area;
  217.                                         }
  218.                                 }
  219.  
  220.                                 // traverse path to find first area we cannot see (skip the first area)
  221.                                 for( i=1; i<count; ++i )
  222.                                 {
  223.                                         // if we see this area, continue on
  224.                                         if (path[i]->IsVisible( eye ))
  225.                                         {
  226.                                                 continue;
  227.                                         }
  228.  
  229.                                         // we can't see this area - mark this area as "blocked" and unusable by subsequent approach paths
  230.                                         if (blockedIDCount == MAX_BLOCKED_AREAS)
  231.                                         {
  232.                                                 Msg( "Overflow computing approach areas for area #%d.\n", m_id );
  233.                                                 return;
  234.                                         }
  235.  
  236.                                         // if the area to be blocked is actually farArea, block the one just prior
  237.                                         // (blocking farArea will cause all subsequent pathfinds to fail)
  238.                                         int block = (path[i] == farArea) ? i-1 : i;
  239.  
  240.                                         // dont block the start area, or all subsequence pathfinds will fail
  241.                                         if (block == 0)
  242.                                         {
  243.                                                 continue;
  244.                                         }
  245.  
  246.                                         blockedID[ blockedIDCount++ ] = path[ block ]->GetID();
  247.  
  248.                                         // store new approach area if not already in set
  249.                                         int a;
  250.                                         for( a=0; a<m_approachCount; ++a )
  251.                                         {
  252.                                                 if (m_approach[a].here.area == path[block-1])
  253.                                                 {
  254.                                                         break;
  255.                                                 }
  256.                                         }
  257.  
  258.                                         if (a == m_approachCount)
  259.                                         {
  260.                                                 m_approach[ m_approachCount ].prev.area = (block >= 2) ? path[block-2] : NULL;
  261.  
  262.                                                 m_approach[ m_approachCount ].here.area = path[block-1];
  263.                                                 m_approach[ m_approachCount ].prevToHereHow = path[block-1]->GetParentHow();
  264.  
  265.                                                 m_approach[ m_approachCount ].next.area = path[block];
  266.                                                 m_approach[ m_approachCount ].hereToNextHow = path[block]->GetParentHow();
  267.  
  268.                                                 ++m_approachCount;
  269.                                         }
  270.  
  271.                                         // we are done with this path
  272.                                         break;
  273.                                 }
  274.                         }
  275.                 }
  276.         }
  277. }
  278.  
  279.  
  280. //--------------------------------------------------------------------------------------------------------------
  281. /**
  282.  * Start at given position and find first area in given direction
  283.  */
  284. inline CNavArea *findFirstAreaInDirection( const Vector *start, NavDirType dir, float range, float beneathLimit, CBaseEntity *traceIgnore = NULL, Vector *closePos = NULL )
  285. {
  286.         CNavArea *area = NULL;
  287.  
  288.         Vector pos = *start;
  289.  
  290.         int end = (int)((range / GenerationStepSize) + 0.5f);
  291.  
  292.         for( int i=1; i<=end; i++ )
  293.         {
  294.                 AddDirectionVector( &pos, dir, GenerationStepSize );
  295.  
  296.                 // make sure we dont look thru the wall
  297.                 trace_t result;
  298.  
  299.                 UTIL_TraceLine( *start, pos, MASK_PLAYERSOLID_BRUSHONLY, traceIgnore, COLLISION_GROUP_NONE, &result );
  300.  
  301.                 if (result.fraction < 1.0f)
  302.                         break;
  303.  
  304.                 area = TheNavMesh->GetNavArea( pos, beneathLimit );
  305.                 if (area)
  306.                 {
  307.                         if (closePos)
  308.                         {
  309.                                 closePos->x = pos.x;
  310.                                 closePos->y = pos.y;
  311.                                 closePos->z = area->GetZ( pos.x, pos.y );
  312.                         }
  313.  
  314.                         break;
  315.                 }
  316.         }
  317.  
  318.         return area;
  319. }
  320.  
  321.  
  322. //--------------------------------------------------------------------------------------------------------------
  323. /**
  324.  * For each ladder in the map, create a navigation representation of it.
  325.  */
  326. void CNavMesh::BuildLadders( void )
  327. {
  328.         // remove any left-over ladders
  329.         DestroyLadders();
  330.  
  331.         trace_t result;
  332.  
  333.         CInfoLadder *entity = NULL;
  334.         while( (entity = dynamic_cast< CInfoLadder * >(gEntList.FindEntityByClassname( entity, "info_ladder" ))) != NULL )
  335.         {
  336.                 CreateLadder( entity->WorldAlignMins(), entity->WorldAlignMaxs(), NULL );
  337.         }
  338. }
  339.  
  340.  
  341. //--------------------------------------------------------------------------------------------------------------
  342. /**
  343.  * Create a navigation representation of a ladder.
  344.  */
  345. void CNavMesh::CreateLadder( const Vector& absMin, const Vector& absMax, const Vector2D *ladderDir )
  346. {
  347.         CNavLadder *ladder = new CNavLadder;
  348.  
  349.         // compute top & bottom of ladder
  350.         ladder->m_top.x = (absMin.x + absMax.x) / 2.0f;
  351.         ladder->m_top.y = (absMin.y + absMax.y) / 2.0f;
  352.         ladder->m_top.z = absMax.z;
  353.  
  354.         ladder->m_bottom.x = ladder->m_top.x;
  355.         ladder->m_bottom.y = ladder->m_top.y;
  356.         ladder->m_bottom.z = absMin.z;
  357.  
  358.         // determine facing - assumes "normal" runged ladder
  359.         float xSize = absMax.x - absMin.x;
  360.         float ySize = absMax.y - absMin.y;
  361.         trace_t result;
  362.         if (xSize > ySize)
  363.         {
  364.                 // ladder is facing north or south - determine which way
  365.                 // "pull in" traceline from bottom and top in case ladder abuts floor and/or ceiling
  366.                 Vector from = ladder->m_bottom + Vector( 0.0f, GenerationStepSize, GenerationStepSize/2 );
  367.                 Vector to = ladder->m_top + Vector( 0.0f, GenerationStepSize, -GenerationStepSize/2 );
  368.  
  369.                 UTIL_TraceLine( from, to, MASK_PLAYERSOLID_BRUSHONLY, NULL, COLLISION_GROUP_NONE, &result );
  370.  
  371.                 if (result.fraction != 1.0f || result.startsolid)
  372.                         ladder->SetDir( NORTH );
  373.                 else
  374.                         ladder->SetDir( SOUTH );
  375.  
  376.                 ladder->m_width = xSize;
  377.         }
  378.         else
  379.         {
  380.                 // ladder is facing east or west - determine which way
  381.                 Vector from = ladder->m_bottom + Vector( GenerationStepSize, 0.0f, GenerationStepSize/2 );
  382.                 Vector to = ladder->m_top + Vector( GenerationStepSize, 0.0f, -GenerationStepSize/2 );
  383.  
  384.                 UTIL_TraceLine( from, to, MASK_PLAYERSOLID_BRUSHONLY, NULL, COLLISION_GROUP_NONE, &result );
  385.  
  386.                 if (result.fraction != 1.0f || result.startsolid)
  387.                         ladder->SetDir( WEST );
  388.                 else
  389.                         ladder->SetDir( EAST );
  390.  
  391.                 ladder->m_width = ySize;
  392.         }
  393.  
  394.         // adjust top and bottom of ladder to make sure they are reachable
  395.         // (cs_office has a crate right in front of the base of a ladder)
  396.         Vector along = ladder->m_top - ladder->m_bottom;
  397.         float length = along.NormalizeInPlace();
  398.         Vector on, out;
  399.         const float minLadderClearance = 32.0f;
  400.  
  401.         // adjust bottom to bypass blockages
  402.         const float inc = 10.0f;
  403.         float t;               
  404.         for( t = 0.0f; t <= length; t += inc )
  405.         {
  406.                 on = ladder->m_bottom + t * along;
  407.  
  408.                 out = on + ladder->GetNormal() * minLadderClearance;
  409.  
  410.                 UTIL_TraceLine( on, out, MASK_PLAYERSOLID_BRUSHONLY, NULL, COLLISION_GROUP_NONE, &result );
  411.  
  412.                 if (result.fraction == 1.0f && !result.startsolid)
  413.                 {
  414.                         // found viable ladder bottom
  415.                         ladder->m_bottom = on;
  416.                         break;
  417.                 }
  418.         }
  419.  
  420.         // adjust top to bypass blockages
  421.         for( t = 0.0f; t <= length; t += inc )
  422.         {
  423.                 on = ladder->m_top - t * along;
  424.  
  425.                 out = on + ladder->GetNormal() * minLadderClearance;
  426.  
  427.                 UTIL_TraceLine( on, out, MASK_PLAYERSOLID_BRUSHONLY, NULL, COLLISION_GROUP_NONE, &result );
  428.  
  429.                 if (result.fraction == 1.0f && !result.startsolid)
  430.                 {
  431.                         // found viable ladder top
  432.                         ladder->m_top = on;
  433.                         break;
  434.                 }
  435.         }
  436.  
  437.         ladder->m_length = (ladder->m_top - ladder->m_bottom).Length();
  438.  
  439.         ladder->SetDir( ladder->GetDir() );     // now that we've adjusted the top and bottom, re-check the normal
  440.  
  441.         ladder->m_bottomArea = NULL;
  442.         ladder->m_topForwardArea = NULL;
  443.         ladder->m_topLeftArea = NULL;
  444.         ladder->m_topRightArea = NULL;
  445.         ladder->m_topBehindArea = NULL;
  446.         ladder->ConnectGeneratedLadder();
  447.  
  448.         // add ladder to global list
  449.         m_ladderList.AddToTail( ladder );              
  450. }
  451.  
  452.  
  453. //--------------------------------------------------------------------------------------------------------------
  454. void CNavLadder::ConnectGeneratedLadder( void )
  455. {
  456.         const float nearLadderRange = 75.0f;            // 50
  457.  
  458.         //
  459.         // Find naviagtion area at bottom of ladder
  460.         //
  461.  
  462.         // get approximate postion of player on ladder
  463.         Vector center = m_bottom + Vector( 0, 0, GenerationStepSize );
  464.         AddDirectionVector( &center, m_dir, HalfHumanWidth );
  465.  
  466.         m_bottomArea = TheNavMesh->GetNearestNavArea( center, true );
  467.         if (!m_bottomArea)
  468.         {
  469.                 DevMsg( "ERROR: Unconnected ladder bottom at ( %g, %g, %g )\n", m_bottom.x, m_bottom.y, m_bottom.z );
  470.         }
  471.         else
  472.         {
  473.                 // store reference to ladder in the area
  474.                 m_bottomArea->AddLadderUp( this );
  475.         }
  476.  
  477.         //
  478.         // Find adjacent navigation areas at the top of the ladder
  479.         //
  480.  
  481.         // get approximate postion of player on ladder
  482.         center = m_top + Vector( 0, 0, GenerationStepSize );
  483.         AddDirectionVector( &center, m_dir, HalfHumanWidth );
  484.  
  485.         float beneathLimit = min( 120.0f, m_top.z - m_bottom.z + HalfHumanWidth );
  486.  
  487.         // find "ahead" area
  488.         m_topForwardArea = findFirstAreaInDirection( &center, OppositeDirection( m_dir ), nearLadderRange, beneathLimit, NULL );
  489.         if (m_topForwardArea == m_bottomArea)
  490.                 m_topForwardArea = NULL;
  491.  
  492.         // find "left" area
  493.         m_topLeftArea = findFirstAreaInDirection( &center, DirectionLeft( m_dir ), nearLadderRange, beneathLimit, NULL );
  494.         if (m_topLeftArea == m_bottomArea)
  495.                 m_topLeftArea = NULL;
  496.  
  497.         // find "right" area
  498.         m_topRightArea = findFirstAreaInDirection( &center, DirectionRight( m_dir ), nearLadderRange, beneathLimit, NULL );
  499.         if (m_topRightArea == m_bottomArea)
  500.                 m_topRightArea = NULL;
  501.  
  502.         // find "behind" area - must look farther, since ladder is against the wall away from this area
  503.         m_topBehindArea = findFirstAreaInDirection( &center, m_dir, 2.0f*nearLadderRange, beneathLimit, NULL );
  504.         if (m_topBehindArea == m_bottomArea)
  505.                 m_topBehindArea = NULL;
  506.  
  507.         // can't include behind area, since it is not used when going up a ladder
  508.         if (!m_topForwardArea && !m_topLeftArea && !m_topRightArea)
  509.                 DevMsg( "ERROR: Unconnected ladder top at ( %g, %g, %g )\n", m_top.x, m_top.y, m_top.z );
  510.  
  511.         // store reference to ladder in the area(s)
  512.         if (m_topForwardArea)
  513.                 m_topForwardArea->AddLadderDown( this );
  514.  
  515.         if (m_topLeftArea)
  516.                 m_topLeftArea->AddLadderDown( this );
  517.  
  518.         if (m_topRightArea)
  519.                 m_topRightArea->AddLadderDown( this );
  520.  
  521.         if (m_topBehindArea)
  522.         {
  523.                 m_topBehindArea->AddLadderDown( this );
  524.                 Disconnect( m_topBehindArea );
  525.         }
  526.  
  527.         // adjust top of ladder to highest connected area
  528.         float topZ = m_bottom.z + 5.0f;
  529.         bool topAdjusted = false;
  530.         CNavArea *topAreaList[4];
  531.         topAreaList[0] = m_topForwardArea;
  532.         topAreaList[1] = m_topLeftArea;
  533.         topAreaList[2] = m_topRightArea;
  534.         topAreaList[3] = m_topBehindArea;
  535.  
  536.         for( int a=0; a<4; ++a )
  537.         {
  538.                 CNavArea *topArea = topAreaList[a];
  539.                 if (topArea == NULL)
  540.                         continue;
  541.  
  542.                 Vector close;
  543.                 topArea->GetClosestPointOnArea( m_top, &close );
  544.                 if (topZ < close.z)
  545.                 {
  546.                         topZ = close.z;
  547.                         topAdjusted = true;
  548.                 }
  549.         }
  550.  
  551.         if (topAdjusted)
  552.         {
  553.                 m_top.z = topZ;
  554.         }
  555.  
  556.         //
  557.         // Determine whether this ladder is "dangling" or not
  558.         // "Dangling" ladders are too high to go up
  559.         //
  560.         if (m_bottomArea)
  561.         {
  562.                 Vector bottomSpot;
  563.                 m_bottomArea->GetClosestPointOnArea( m_bottom, &bottomSpot );
  564.                 if (m_bottom.z - bottomSpot.z > HumanHeight)
  565.                 {
  566.                         m_bottomArea->Disconnect( this );
  567.                 }
  568.         }
  569. }
  570.  
  571.  
  572. //--------------------------------------------------------------------------------------------------------------
  573. /**
  574.  * Mark all areas that require a jump to get through them.
  575.  * This currently relies on jump areas having extreme slope.
  576.  */
  577. void CNavMesh::MarkJumpAreas( void )
  578. {
  579.         FOR_EACH_LL( TheNavAreaList, it )
  580.         {
  581.                 CNavArea *area = TheNavAreaList[ it ];
  582.                 if ( !area->HasNodes() )
  583.                         continue;
  584.  
  585.                 Vector normal, otherNormal;
  586.                 area->ComputeNormal( &normal );
  587.                 area->ComputeNormal( &otherNormal, true );
  588.  
  589.                 if (normal.z < nav_slope_limit.GetFloat() ||
  590.                         otherNormal.z < nav_slope_limit.GetFloat())
  591.                 {
  592.                         area->SetAttributes( area->GetAttributes() | NAV_MESH_JUMP );
  593.                 }
  594.         }
  595. }
  596.  
  597. //--------------------------------------------------------------------------------------------------------------
  598. /**
  599.  * Jump areas that are connected to only one non-jump area won't be used.  Delete them.
  600.  */
  601. void CNavMesh::RemoveUnusedJumpAreas( void )
  602. {
  603.         CUtlLinkedList< CNavArea *, int > unusedAreas;
  604.  
  605.         FOR_EACH_LL( TheNavAreaList, it )
  606.         {
  607.                 CNavArea *testArea = TheNavAreaList[ it ];
  608.                 if ( !(testArea->GetAttributes() & NAV_MESH_JUMP) )
  609.                 {
  610.                         continue;
  611.                 }
  612.  
  613.                 NavConnect connectedArea;
  614.                 NavLadderConnect connectedLadder;
  615.                 connectedArea.area = NULL;
  616.                 connectedLadder.ladder = NULL;
  617.  
  618.                 bool doubleConnected = false;
  619.  
  620.                 // Look at testArea->ladder connections
  621.                 int i;
  622.                 for ( i=0; i<CNavLadder::NUM_LADDER_DIRECTIONS; ++i )
  623.                 {
  624.                         const NavLadderConnectList *ladderList = testArea->GetLadderList( (CNavLadder::LadderDirectionType)i );
  625.                         if ( !ladderList )
  626.                         {
  627.                                 continue;
  628.                         }
  629.  
  630.                         if ( ladderList->Count() == 0 )
  631.                         {
  632.                                 continue;
  633.                         }
  634.  
  635.                         if ( ladderList->Count() > 1 )
  636.                         {
  637.                                 doubleConnected = true;
  638.                                 break;
  639.                         }
  640.  
  641.                         NavLadderConnect ladderConnect = (*ladderList)[ ladderList->Head() ];
  642.                         if ( connectedArea.area || (connectedLadder.ladder && connectedLadder.ladder != ladderConnect.ladder) )
  643.                         {
  644.                                 doubleConnected = true;
  645.                                 break;
  646.                         }
  647.  
  648.                         connectedLadder = ladderConnect;
  649.                 }
  650.  
  651.                 if ( doubleConnected )
  652.                 {
  653.                         continue;
  654.                 }
  655.  
  656.                 // Look at testArea->area connections
  657.                 for ( i=0; i<NUM_DIRECTIONS; ++i )
  658.                 {
  659.                         const NavConnectList *areaList = testArea->GetAdjacentList( (NavDirType)i );
  660.                         if ( !areaList )
  661.                         {
  662.                                 continue;
  663.                         }
  664.  
  665.                         if ( areaList->Count() == 0 )
  666.                         {
  667.                                 continue;
  668.                         }
  669.  
  670.                         FOR_EACH_LL ( (*areaList), ait )
  671.                         {
  672.                                 NavConnect areaConnect = (*areaList)[ ait ];
  673.                                 if ( areaConnect.area->GetAttributes() & NAV_MESH_JUMP )
  674.                                 {
  675.                                         continue;
  676.                                 }
  677.  
  678.                                 if ( connectedLadder.ladder || (connectedArea.area && connectedArea.area != areaConnect.area) )
  679.                                 {
  680.                                         doubleConnected = true;
  681.                                         break;
  682.                                 }
  683.  
  684.                                 connectedArea = areaConnect;
  685.                         }
  686.                 }
  687.  
  688.                 if ( doubleConnected )
  689.                 {
  690.                         continue;
  691.                 }
  692.  
  693.                 // Look at ladder->testArea connections
  694.                 FOR_EACH_LL( m_ladderList, lit )
  695.                 {
  696.                         CNavLadder *ladder = m_ladderList[lit];
  697.                         if ( !ladder )
  698.                         {
  699.                                 continue;
  700.                         }
  701.  
  702.                         if ( !ladder->IsConnected( testArea, CNavLadder::NUM_LADDER_DIRECTIONS ) )
  703.                         {
  704.                                 continue;
  705.                         }
  706.  
  707.                         if ( connectedArea.area )
  708.                         {
  709.                                 doubleConnected = true;
  710.                                 break;
  711.                         }
  712.  
  713.                         if ( ladder == connectedLadder.ladder )
  714.                         {
  715.                                 continue;
  716.                         }
  717.  
  718.                         if ( connectedLadder.ladder )
  719.                         {
  720.                                 doubleConnected = true;
  721.                                 break;
  722.                         }
  723.  
  724.                         connectedLadder.ladder = ladder;
  725.                 }
  726.  
  727.                 if ( doubleConnected )
  728.                 {
  729.                         continue;
  730.                 }
  731.  
  732.                 // Look at area->testArea connections
  733.                 FOR_EACH_LL( TheNavAreaList, ait )
  734.                 {
  735.                         CNavArea *area = TheNavAreaList[ait];
  736.                         if ( !area )
  737.                         {
  738.                                 continue;
  739.                         }
  740.  
  741.                         if ( area->GetAttributes() & NAV_MESH_JUMP )
  742.                         {
  743.                                 continue;
  744.                         }
  745.  
  746.                         if ( !area->IsConnected( testArea, NUM_DIRECTIONS ) )
  747.                         {
  748.                                 continue;
  749.                         }
  750.  
  751.                         if ( connectedLadder.ladder )
  752.                         {
  753.                                 doubleConnected = true;
  754.                                 break;
  755.                         }
  756.  
  757.                         if ( area == connectedArea.area )
  758.                         {
  759.                                 continue;
  760.                         }
  761.  
  762.                         if ( connectedArea.area )
  763.                         {
  764.                                 doubleConnected = true;
  765.                                 break;
  766.                         }
  767.  
  768.                         connectedArea.area = area;
  769.                 }
  770.  
  771.                 if ( doubleConnected )
  772.                 {
  773.                         continue;
  774.                 }
  775.  
  776.                 // Since we got here, at most one ladder or non-jump area is connected to us, so we can be deleted.
  777.                 unusedAreas.AddToTail( testArea );
  778.         }
  779.  
  780.         FOR_EACH_LL( unusedAreas, uit )
  781.         {
  782.                 CNavArea *areaToDelete = unusedAreas[ uit ];
  783.                 TheNavAreaList.FindAndRemove( areaToDelete );
  784.                 delete areaToDelete;
  785.         }
  786.  
  787.         StripNavigationAreas();
  788.  
  789.         SetMarkedArea( NULL );                  // unmark the mark area
  790.         m_markedCorner = NUM_CORNERS;   // clear the corner selection
  791. }
  792.  
  793.  
  794. //--------------------------------------------------------------------------------------------------------------
  795. void CNavMesh::CommandNavRemoveUnusedJumpAreas( void )
  796. {
  797.         RemoveUnusedJumpAreas();
  798. }
  799.  
  800.  
  801. //--------------------------------------------------------------------------------------------------------------
  802. /**
  803.  * Recursively chop area in half along X until child areas are roughly square
  804.  */
  805. static void splitX( CNavArea *area )
  806. {
  807.         if (area->IsRoughlySquare())
  808.                 return;
  809.  
  810.         float split = area->GetSizeX();
  811.         split /= 2.0f;
  812.         split += area->GetExtent().lo.x;
  813.  
  814.         split = TheNavMesh->SnapToGrid( split );
  815.  
  816.         const float epsilon = 0.1f;
  817.         if (fabs(split - area->GetExtent().lo.x) < epsilon ||
  818.                 fabs(split - area->GetExtent().hi.x) < epsilon)
  819.         {
  820.                 // too small to subdivide
  821.                 return;
  822.         }
  823.  
  824.         CNavArea *alpha, *beta;
  825.         if (area->SplitEdit( false, split, &alpha, &beta ))
  826.         {
  827.                 // split each new area until square
  828.                 splitX( alpha );
  829.                 splitX( beta );
  830.         }
  831. }
  832.  
  833. //--------------------------------------------------------------------------------------------------------------
  834. /**
  835.  * Recursively chop area in half along Y until child areas are roughly square
  836.  */
  837. static void splitY( CNavArea *area )
  838. {
  839.         if (area->IsRoughlySquare())
  840.                 return;
  841.  
  842.         float split = area->GetSizeY();
  843.         split /= 2.0f;
  844.         split += area->GetExtent().lo.y;
  845.  
  846.         split = TheNavMesh->SnapToGrid( split );
  847.  
  848.         const float epsilon = 0.1f;
  849.         if (fabs(split - area->GetExtent().lo.y) < epsilon ||
  850.                 fabs(split - area->GetExtent().hi.y) < epsilon)
  851.         {
  852.                 // too small to subdivide
  853.                 return;
  854.         }
  855.  
  856.         CNavArea *alpha, *beta;
  857.         if (area->SplitEdit( true, split, &alpha, &beta ))
  858.         {
  859.                 // split each new area until square
  860.                 splitY( alpha );
  861.                 splitY( beta );
  862.         }
  863. }
  864.  
  865. //--------------------------------------------------------------------------------------------------------------
  866. /**
  867.  * Split any long, thin, areas into roughly square chunks.
  868.  */
  869. void CNavMesh::SquareUpAreas( void )
  870. {
  871.         int it = TheNavAreaList.Head();
  872.  
  873.         while( it != TheNavAreaList.InvalidIndex() )
  874.         {
  875.                 CNavArea *area = TheNavAreaList[ it ];
  876.  
  877.                 // move the iterator in case the current area is split and deleted
  878.                 it = TheNavAreaList.Next( it );
  879.  
  880.                 if (area->HasNodes() && !area->IsRoughlySquare())
  881.                 {
  882.                         // chop this area into square pieces
  883.                         if (area->GetSizeX() > area->GetSizeY())
  884.                                 splitX( area );
  885.                         else
  886.                                 splitY( area );
  887.                 }
  888.         }
  889. }
  890.  
  891.  
  892. //--------------------------------------------------------------------------------------------------------------
  893. /**
  894.  * Determine if we can "jump down" from given point
  895.  */
  896. inline bool testJumpDown( const Vector *fromPos, const Vector *toPos )
  897. {
  898.         float dz = fromPos->z - toPos->z;
  899.  
  900.         // drop can't be too far, or too short (or nonexistant)
  901.         if (dz <= JumpCrouchHeight || dz >= DeathDrop)
  902.                 return false;
  903.  
  904.         //
  905.         // Check LOS out and down
  906.         //
  907.         // ------+
  908.         //       |
  909.         // F     |
  910.         //       |
  911.         //       T
  912.         //
  913.  
  914.         Vector from( fromPos->x, fromPos->y, fromPos->z + HumanHeight );
  915.         Vector to( toPos->x, toPos->y, from.z );
  916.  
  917.         trace_t result;
  918.         UTIL_TraceLine( from, to, MASK_PLAYERSOLID_BRUSHONLY, NULL, COLLISION_GROUP_NONE, &result );
  919.         if (result.fraction != 1.0f || result.startsolid)
  920.                 return false;
  921.  
  922.         from = to;
  923.         to.z = toPos->z + 2.0f;
  924.         UTIL_TraceLine( from, to, MASK_PLAYERSOLID_BRUSHONLY, NULL, COLLISION_GROUP_NONE, &result );
  925.         if (result.fraction != 1.0f || result.startsolid)
  926.                 return false;
  927.  
  928.         return true;
  929. }
  930.  
  931.  
  932. //--------------------------------------------------------------------------------------------------------------
  933. inline CNavArea *findJumpDownArea( const Vector *fromPos, NavDirType dir )
  934. {
  935.         Vector start( fromPos->x, fromPos->y, fromPos->z + HalfHumanHeight );
  936.         AddDirectionVector( &start, dir, GenerationStepSize/2.0f );
  937.  
  938.         Vector toPos;
  939.         CNavArea *downArea = findFirstAreaInDirection( &start, dir, 4.0f * GenerationStepSize, DeathDrop, NULL, &toPos );
  940.  
  941.         if (downArea && testJumpDown( fromPos, &toPos ))
  942.                 return downArea;
  943.  
  944.         return NULL;
  945. }
  946.  
  947.  
  948. //--------------------------------------------------------------------------------------------------------------
  949. /**
  950.  * Define connections between adjacent generated areas
  951.  */
  952. void CNavMesh::ConnectGeneratedAreas( void )
  953. {
  954.         Msg( "Connecting navigation areas...\n" );
  955.  
  956.         FOR_EACH_LL( TheNavAreaList, it )
  957.         {
  958.                 CNavArea *area = TheNavAreaList[ it ];
  959.  
  960.                 // scan along edge nodes, stepping one node over into the next area
  961.                 // for now, only use bi-directional connections
  962.  
  963.                 // north edge
  964.                 CNavNode *node;
  965.                 for( node = area->m_node[ NORTH_WEST ]; node != area->m_node[ NORTH_EAST ]; node = node->GetConnectedNode( EAST ) )
  966.                 {
  967.                         CNavNode *adj = node->GetConnectedNode( NORTH );
  968.  
  969.                         if (adj && adj->GetArea() && adj->GetConnectedNode( SOUTH ) == node)
  970.                         {
  971.                                 area->ConnectTo( adj->GetArea(), NORTH );
  972.                         }
  973.                         else
  974.                         {
  975.                                 CNavArea *downArea = findJumpDownArea( node->GetPosition(), NORTH );
  976.                                 if (downArea && downArea != area)
  977.                                         area->ConnectTo( downArea, NORTH );
  978.                         }
  979.                 }
  980.  
  981.                 // west edge
  982.                 for( node = area->m_node[ NORTH_WEST ]; node != area->m_node[ SOUTH_WEST ]; node = node->GetConnectedNode( SOUTH ) )
  983.                 {
  984.                         CNavNode *adj = node->GetConnectedNode( WEST );
  985.                        
  986.                         if (adj && adj->GetArea() && adj->GetConnectedNode( EAST ) == node)
  987.                         {
  988.                                 area->ConnectTo( adj->GetArea(), WEST );
  989.                         }
  990.                         else
  991.                         {
  992.                                 CNavArea *downArea = findJumpDownArea( node->GetPosition(), WEST );
  993.                                 if (downArea && downArea != area)
  994.                                         area->ConnectTo( downArea, WEST );
  995.                         }
  996.                 }
  997.  
  998.                 // south edge - this edge's nodes are actually part of adjacent areas
  999.                 // move one node north, and scan west to east
  1000.                 /// @todo This allows one-node-wide areas - do we want this?
  1001.                 node = area->m_node[ SOUTH_WEST ];
  1002.                 if ( node ) // pre-existing areas in incremental generates won't have nodes
  1003.                 {
  1004.                         node = node->GetConnectedNode( NORTH );
  1005.                 }
  1006.                 if (node)
  1007.                 {
  1008.                         CNavNode *end = area->m_node[ SOUTH_EAST ]->GetConnectedNode( NORTH );
  1009.                         /// @todo Figure out why cs_backalley gets a NULL node in here...
  1010.                         for( ; node && node != end; node = node->GetConnectedNode( EAST ) )
  1011.                         {
  1012.                                 CNavNode *adj = node->GetConnectedNode( SOUTH );
  1013.                                
  1014.                                 if (adj && adj->GetArea() && adj->GetConnectedNode( NORTH ) == node)
  1015.                                 {
  1016.                                         area->ConnectTo( adj->GetArea(), SOUTH );
  1017.                                 }
  1018.                                 else
  1019.                                 {
  1020.                                         CNavArea *downArea = findJumpDownArea( node->GetPosition(), SOUTH );
  1021.                                         if (downArea && downArea != area)
  1022.                                                 area->ConnectTo( downArea, SOUTH );
  1023.                                 }
  1024.                         }
  1025.                 }
  1026.  
  1027.                 // east edge - this edge's nodes are actually part of adjacent areas
  1028.                 node = area->m_node[ NORTH_EAST ];
  1029.                 if ( node ) // pre-existing areas in incremental generates won't have nodes
  1030.                 {
  1031.                         node = node->GetConnectedNode( WEST );
  1032.                 }
  1033.                 if (node)
  1034.                 {
  1035.                         CNavNode *end = area->m_node[ SOUTH_EAST ]->GetConnectedNode( WEST );
  1036.                         for( ; node && node != end; node = node->GetConnectedNode( SOUTH ) )
  1037.                         {
  1038.                                 CNavNode *adj = node->GetConnectedNode( EAST );
  1039.                                
  1040.                                 if (adj && adj->GetArea() && adj->GetConnectedNode( WEST ) == node)
  1041.                                 {
  1042.                                         area->ConnectTo( adj->GetArea(), EAST );
  1043.                                 }
  1044.                                 else
  1045.                                 {
  1046.                                         CNavArea *downArea = findJumpDownArea( node->GetPosition(), EAST );
  1047.                                         if (downArea && downArea != area)
  1048.                                                 area->ConnectTo( downArea, EAST );
  1049.                                 }
  1050.                         }
  1051.                 }
  1052.         }
  1053. }
  1054.  
  1055. //--------------------------------------------------------------------------------------------------------------
  1056. /**
  1057.  * Merge areas together to make larger ones (must remain rectangular - convex).
  1058.  * Areas can only be merged if their attributes match.
  1059.  */
  1060. void CNavMesh::MergeGeneratedAreas( void )
  1061. {
  1062.         Msg( "Merging navigation areas...\n" );
  1063.  
  1064.         bool merged;
  1065.  
  1066.         do
  1067.         {
  1068.                 merged = false;
  1069.  
  1070.                 FOR_EACH_LL( TheNavAreaList, it )
  1071.                 {
  1072.                         CNavArea *area = TheNavAreaList[ it ];
  1073.                         if ( !area->HasNodes() )
  1074.                                 continue;
  1075.  
  1076.                         // north edge
  1077.                         FOR_EACH_LL( area->m_connect[ NORTH ], nit )
  1078.                         {
  1079.                                 CNavArea *adjArea = area->m_connect[ NORTH ][ nit ].area;
  1080.                                 if ( !adjArea->HasNodes() ) // pre-existing areas in incremental generates won't have nodes
  1081.                                         continue;
  1082.  
  1083.                                 if (area->m_node[ NORTH_WEST ] == adjArea->m_node[ SOUTH_WEST ] &&
  1084.                                         area->m_node[ NORTH_EAST ] == adjArea->m_node[ SOUTH_EAST ] &&
  1085.                                         area->GetAttributes() == adjArea->GetAttributes() &&
  1086.                                         area->IsCoplanar( adjArea ))
  1087.                                 {
  1088.                                         // merge vertical
  1089.                                         area->m_node[ NORTH_WEST ] = adjArea->m_node[ NORTH_WEST ];
  1090.                                         area->m_node[ NORTH_EAST ] = adjArea->m_node[ NORTH_EAST ];
  1091.  
  1092.                                         merged = true;
  1093.                                         //CONSOLE_ECHO( "  Merged (north) areas #%d and #%d\n", area->m_id, adjArea->m_id );
  1094.  
  1095.                                         area->FinishMerge( adjArea );
  1096.  
  1097.                                         // restart scan - iterator is invalidated
  1098.                                         break;
  1099.                                 }
  1100.                         }
  1101.  
  1102.                         if (merged)
  1103.                                 break;
  1104.  
  1105.                         // south edge
  1106.                         FOR_EACH_LL( area->m_connect[ SOUTH ], sit )
  1107.                         {
  1108.                                 CNavArea *adjArea = area->m_connect[ SOUTH ][ sit ].area;
  1109.                                 if ( !adjArea->HasNodes() ) // pre-existing areas in incremental generates won't have nodes
  1110.                                         continue;
  1111.  
  1112.                                 if (adjArea->m_node[ NORTH_WEST ] == area->m_node[ SOUTH_WEST ] &&
  1113.                                         adjArea->m_node[ NORTH_EAST ] == area->m_node[ SOUTH_EAST ] &&
  1114.                                         area->GetAttributes() == adjArea->GetAttributes() &&
  1115.                                         area->IsCoplanar( adjArea ))
  1116.                                 {
  1117.                                         // merge vertical
  1118.                                         area->m_node[ SOUTH_WEST ] = adjArea->m_node[ SOUTH_WEST ];
  1119.                                         area->m_node[ SOUTH_EAST ] = adjArea->m_node[ SOUTH_EAST ];
  1120.  
  1121.                                         merged = true;
  1122.                                         //CONSOLE_ECHO( "  Merged (south) areas #%d and #%d\n", area->m_id, adjArea->m_id );
  1123.  
  1124.                                         area->FinishMerge( adjArea );
  1125.  
  1126.                                         // restart scan - iterator is invalidated
  1127.                                         break;
  1128.                                 }
  1129.  
  1130.                         }
  1131.  
  1132.                         if (merged)
  1133.                                 break;
  1134.  
  1135.  
  1136.                         // west edge
  1137.                         FOR_EACH_LL( area->m_connect[ WEST ], wit )
  1138.                         {
  1139.                                 CNavArea *adjArea = area->m_connect[ WEST ][ wit ].area;
  1140.                                 if ( !adjArea->HasNodes() ) // pre-existing areas in incremental generates won't have nodes
  1141.                                         continue;
  1142.  
  1143.                                 if (area->m_node[ NORTH_WEST ] == adjArea->m_node[ NORTH_EAST ] &&
  1144.                                                 area->m_node[ SOUTH_WEST ] == adjArea->m_node[ SOUTH_EAST ] &&
  1145.                                                 area->GetAttributes() == adjArea->GetAttributes() &&
  1146.                                                 area->IsCoplanar( adjArea ))
  1147.                                 {
  1148.                                         // merge horizontal
  1149.                                         area->m_node[ NORTH_WEST ] = adjArea->m_node[ NORTH_WEST ];
  1150.                                         area->m_node[ SOUTH_WEST ] = adjArea->m_node[ SOUTH_WEST ];
  1151.  
  1152.                                         merged = true;
  1153.                                         //CONSOLE_ECHO( "  Merged (west) areas #%d and #%d\n", area->m_id, adjArea->m_id );
  1154.  
  1155.                                         area->FinishMerge( adjArea );
  1156.  
  1157.                                         // restart scan - iterator is invalidated
  1158.                                         break;
  1159.                                 }
  1160.  
  1161.                         }
  1162.  
  1163.                         if (merged)
  1164.                                 break;
  1165.  
  1166.                         // east edge
  1167.                         FOR_EACH_LL( area->m_connect[ EAST ], eit )
  1168.                         {
  1169.                                 CNavArea *adjArea = area->m_connect[ EAST ][ eit ].area;
  1170.                                 if ( !adjArea->HasNodes() ) // pre-existing areas in incremental generates won't have nodes
  1171.                                         continue;
  1172.  
  1173.                                 if (adjArea->m_node[ NORTH_WEST ] == area->m_node[ NORTH_EAST ] &&
  1174.                                         adjArea->m_node[ SOUTH_WEST ] == area->m_node[ SOUTH_EAST ] &&
  1175.                                         area->GetAttributes() == adjArea->GetAttributes() &&
  1176.                                         area->IsCoplanar( adjArea ))
  1177.                                 {
  1178.                                         // merge horizontal
  1179.                                         area->m_node[ NORTH_EAST ] = adjArea->m_node[ NORTH_EAST ];
  1180.                                         area->m_node[ SOUTH_EAST ] = adjArea->m_node[ SOUTH_EAST ];
  1181.  
  1182.                                         merged = true;
  1183.                                         //CONSOLE_ECHO( "  Merged (east) areas #%d and #%d\n", area->m_id, adjArea->m_id );
  1184.  
  1185.                                         area->FinishMerge( adjArea );
  1186.  
  1187.                                         // restart scan - iterator is invalidated
  1188.                                         break;
  1189.                                 }
  1190.                         }
  1191.  
  1192.                         if (merged)
  1193.                                 break;
  1194.                 }
  1195.         }
  1196.         while( merged );
  1197. }
  1198.  
  1199.  
  1200. //--------------------------------------------------------------------------------------------------------------
  1201. /**
  1202.  * Check if an rectangular area of the given size can be
  1203.  * made starting from the given node as the NW corner.
  1204.  * Only consider fully connected nodes for this check.
  1205.  * All of the nodes within the test area must have the same attributes.
  1206.  * All of the nodes must be approximately co-planar w.r.t the NW node's normal, with the
  1207.  * exception of 1x1 areas which can be any angle.
  1208.  */
  1209. bool CNavMesh::TestArea( CNavNode *node, int width, int height )
  1210. {
  1211.         Vector normal = *node->GetNormal();
  1212.         float d = -DotProduct( normal, *node->GetPosition() );
  1213.  
  1214.         bool nodeCrouch = node->m_crouch[ SOUTH_EAST ];
  1215.         unsigned char nodeAttributes = node->GetAttributes() & ~NAV_MESH_CROUCH;
  1216.  
  1217.         const float offPlaneTolerance = 5.0f;
  1218.  
  1219.         CNavNode *vertNode, *horizNode;
  1220.  
  1221.         vertNode = node;
  1222.         for( int y=0; y<height; y++ )
  1223.         {
  1224.                 horizNode = vertNode;
  1225.  
  1226.                 for( int x=0; x<width; x++ )
  1227.                 {
  1228.                         //
  1229.                         // Compute the crouch attributes for the test node, taking into account only the side(s) of the node
  1230.                         // that are in the area
  1231.                         bool horizNodeCrouch = false;
  1232.                         bool westEdge = (x == 0);
  1233.                         bool eastEdge = (x == width - 1);
  1234.                         bool northEdge = (y == 0);
  1235.                         bool southEdge = (y == height - 1);
  1236.  
  1237.                         // Check corners first
  1238.                         if ( northEdge && westEdge )
  1239.                         {
  1240.                                 horizNodeCrouch = horizNode->m_crouch[ SOUTH_EAST ];
  1241.                         }
  1242.                         else if ( northEdge && eastEdge )
  1243.                         {
  1244.                                 horizNodeCrouch = horizNode->m_crouch[ SOUTH_EAST ] || horizNode->m_crouch[ SOUTH_WEST ];
  1245.                         }
  1246.                         else if ( southEdge && westEdge )
  1247.                         {
  1248.                                 horizNodeCrouch = horizNode->m_crouch[ SOUTH_EAST ] || horizNode->m_crouch[ NORTH_EAST ];
  1249.                         }
  1250.                         else if ( southEdge && eastEdge )
  1251.                         {
  1252.                                 horizNodeCrouch = (horizNode->GetAttributes() & NAV_MESH_CROUCH) != 0;
  1253.                         }
  1254.                         // check sides next
  1255.                         else if ( northEdge )
  1256.                         {
  1257.                                 horizNodeCrouch = horizNode->m_crouch[ SOUTH_EAST ] || horizNode->m_crouch[ SOUTH_WEST ];
  1258.                         }
  1259.                         else if ( southEdge )
  1260.                         {
  1261.                                 horizNodeCrouch = (horizNode->GetAttributes() & NAV_MESH_CROUCH) != 0;
  1262.                         }
  1263.                         else if ( eastEdge )
  1264.                         {
  1265.                                 horizNodeCrouch = (horizNode->GetAttributes() & NAV_MESH_CROUCH) != 0;
  1266.                         }
  1267.                         else if ( westEdge )
  1268.                         {
  1269.                                 horizNodeCrouch = horizNode->m_crouch[ SOUTH_EAST ] || horizNode->m_crouch[ NORTH_EAST ];
  1270.                         }
  1271.                         // finally, we have a center node
  1272.                         else
  1273.                         {
  1274.                                 horizNodeCrouch = (horizNode->GetAttributes() & NAV_MESH_CROUCH) != 0;
  1275.                         }
  1276.  
  1277.                         // all nodes must be crouch/non-crouch
  1278.                         if ( nodeCrouch != horizNodeCrouch )
  1279.                                 return false;
  1280.  
  1281.                         // all nodes must have the same non-crouch attributes
  1282.                         unsigned char horizNodeAttributes = horizNode->GetAttributes() & ~NAV_MESH_CROUCH;
  1283.                         if (horizNodeAttributes != nodeAttributes)
  1284.                                 return false;
  1285.  
  1286.                         if (horizNode->IsCovered())
  1287.                                 return false;
  1288.  
  1289.                         if (!horizNode->IsClosedCell())
  1290.                                 return false;
  1291.  
  1292.                         horizNode = horizNode->GetConnectedNode( EAST );
  1293.                         if (horizNode == NULL)
  1294.                                 return false;
  1295.  
  1296.                         // nodes must lie on/near the plane
  1297.                         if (width > 1 || height > 1)
  1298.                         {
  1299.                                 float dist = (float)fabs( DotProduct( *horizNode->GetPosition(), normal ) + d );
  1300.                                 if (dist > offPlaneTolerance)
  1301.                                         return false;
  1302.                         }                                      
  1303.                 }
  1304.  
  1305.                 vertNode = vertNode->GetConnectedNode( SOUTH );
  1306.                 if (vertNode == NULL)
  1307.                         return false;
  1308.  
  1309.                 // nodes must lie on/near the plane
  1310.                 if (width > 1 || height > 1)
  1311.                 {
  1312.                         float dist = (float)fabs( DotProduct( *vertNode->GetPosition(), normal ) + d );
  1313.                         if (dist > offPlaneTolerance)
  1314.                                 return false;
  1315.                 }                                      
  1316.         }
  1317.  
  1318.         // check planarity of southern edge
  1319.         if (width > 1 || height > 1)
  1320.         {
  1321.                 horizNode = vertNode;
  1322.  
  1323.                 for( int x=0; x<width; x++ )
  1324.                 {
  1325.                         horizNode = horizNode->GetConnectedNode( EAST );
  1326.                         if (horizNode == NULL)
  1327.                                 return false;
  1328.  
  1329.                         // nodes must lie on/near the plane
  1330.                         float dist = (float)fabs( DotProduct( *horizNode->GetPosition(), normal ) + d );
  1331.                         if (dist > offPlaneTolerance)
  1332.                                 return false;
  1333.                 }
  1334.         }
  1335.  
  1336.         return true;
  1337. }
  1338.  
  1339. //--------------------------------------------------------------------------------------------------------------
  1340. /**
  1341.  * Create a nav area, and mark all nodes it overlaps as "covered"
  1342.  * NOTE: Nodes on the east and south edges are not included.
  1343.  * Returns number of nodes covered by this area, or -1 for error;
  1344.  */
  1345. int CNavMesh::BuildArea( CNavNode *node, int width, int height )
  1346. {
  1347.         CNavNode *nwNode = node;
  1348.         CNavNode *neNode = NULL;
  1349.         CNavNode *swNode = NULL;
  1350.         CNavNode *seNode = NULL;
  1351.  
  1352.         CNavNode *vertNode = node;
  1353.         CNavNode *horizNode;
  1354.  
  1355.         int coveredNodes = 0;
  1356.  
  1357.         for( int y=0; y<height; y++ )
  1358.         {
  1359.                 horizNode = vertNode;
  1360.  
  1361.                 for( int x=0; x<width; x++ )
  1362.                 {
  1363.                         horizNode->Cover();
  1364.                         ++coveredNodes;
  1365.                        
  1366.                         horizNode = horizNode->GetConnectedNode( EAST );
  1367.                 }
  1368.  
  1369.                 if (y == 0)
  1370.                         neNode = horizNode;
  1371.  
  1372.                 vertNode = vertNode->GetConnectedNode( SOUTH );
  1373.         }
  1374.  
  1375.         swNode = vertNode;
  1376.  
  1377.         horizNode = vertNode;          
  1378.         for( int x=0; x<width; x++ )
  1379.         {
  1380.                 horizNode = horizNode->GetConnectedNode( EAST );
  1381.         }
  1382.         seNode = horizNode;
  1383.  
  1384.         if (!nwNode || !neNode || !seNode || !swNode)
  1385.         {
  1386.                 Error( "BuildArea - NULL node.\n" );
  1387.                 return -1;
  1388.         }
  1389.  
  1390.         CNavArea *area = new CNavArea( nwNode, neNode, seNode, swNode );
  1391.         TheNavAreaList.AddToTail( area );
  1392.  
  1393.         // since all internal nodes have the same attributes, set this area's attributes
  1394.         area->SetAttributes( node->GetAttributes() );
  1395.  
  1396.         // Check that the node was crouch in the right direction
  1397.         bool nodeCrouch = node->m_crouch[ SOUTH_EAST ];
  1398.         if ( (area->GetAttributes() & NAV_MESH_CROUCH) && !nodeCrouch )
  1399.         {
  1400.                 area->SetAttributes( area->GetAttributes() & ~NAV_MESH_CROUCH );
  1401.         }
  1402.  
  1403.         return coveredNodes;
  1404. }
  1405.  
  1406.  
  1407. //--------------------------------------------------------------------------------------------------------------
  1408. /**
  1409.  * This function uses the CNavNodes that have been sampled from the map to
  1410.  * generate CNavAreas - rectangular areas of "walkable" space. These areas
  1411.  * are connected to each other, proving information on know how to move from
  1412.  * area to area.
  1413.  *
  1414.  * This is a "greedy" algorithm that attempts to cover the walkable area
  1415.  * with the fewest, largest, rectangles.
  1416.  */
  1417. void CNavMesh::CreateNavAreasFromNodes( void )
  1418. {
  1419.         // haven't yet seen a map use larger than 30...
  1420.         int tryWidth = 50;
  1421.         int tryHeight = 50;
  1422.         int uncoveredNodes = CNavNode::GetListLength();
  1423.  
  1424.         while( uncoveredNodes > 0 )
  1425.         {
  1426.                 for( CNavNode *node = CNavNode::GetFirst(); node; node = node->GetNext() )
  1427.                 {
  1428.                         if (node->IsCovered())
  1429.                                 continue;
  1430.  
  1431.                         if (TestArea( node, tryWidth, tryHeight ))
  1432.                         {
  1433.                                 int covered = BuildArea( node, tryWidth, tryHeight );
  1434.                                 if (covered < 0)
  1435.                                 {
  1436.                                         Error( "Generate: Error - Data corrupt.\n" );
  1437.                                         return;
  1438.                                 }
  1439.  
  1440.                                 uncoveredNodes -= covered;
  1441.                         }
  1442.                 }
  1443.  
  1444.                 if (tryWidth >= tryHeight)
  1445.                         --tryWidth;
  1446.                 else
  1447.                         --tryHeight;
  1448.  
  1449.                 if (tryWidth <= 0 || tryHeight <= 0)
  1450.                         break;
  1451.         }
  1452.  
  1453.         if ( !TheNavAreaList.Count() )
  1454.         {
  1455.                 // If we somehow have no areas, don't try to create an impossibly-large grid
  1456.                 AllocateGrid( 0, 0, 0, 0 );
  1457.                 return;
  1458.         }
  1459.  
  1460.         Extent extent;
  1461.         extent.lo.x = 9999999999.9f;
  1462.         extent.lo.y = 9999999999.9f;
  1463.         extent.hi.x = -9999999999.9f;
  1464.         extent.hi.y = -9999999999.9f;
  1465.  
  1466.         // compute total extent
  1467.         FOR_EACH_LL( TheNavAreaList, it )
  1468.         {
  1469.                 CNavArea *area = TheNavAreaList[ it ];
  1470.                 const Extent &areaExtent = area->GetExtent();
  1471.  
  1472.                 if (areaExtent.lo.x < extent.lo.x)
  1473.                         extent.lo.x = areaExtent.lo.x;
  1474.                 if (areaExtent.lo.y < extent.lo.y)
  1475.                         extent.lo.y = areaExtent.lo.y;
  1476.                 if (areaExtent.hi.x > extent.hi.x)
  1477.                         extent.hi.x = areaExtent.hi.x;
  1478.                 if (areaExtent.hi.y > extent.hi.y)
  1479.                         extent.hi.y = areaExtent.hi.y;
  1480.         }
  1481.  
  1482.         // add the areas to the grid
  1483.         AllocateGrid( extent.lo.x, extent.hi.x, extent.lo.y, extent.hi.y );
  1484.  
  1485.         FOR_EACH_LL( TheNavAreaList, git )
  1486.         {
  1487.                 AddNavArea( TheNavAreaList[ git ] );
  1488.         }
  1489.  
  1490.  
  1491.         ConnectGeneratedAreas();
  1492.         MergeGeneratedAreas();
  1493.         SquareUpAreas();
  1494.         MarkJumpAreas();
  1495.  
  1496.         /// @TODO: incremental generation doesn't create ladders yet
  1497.         if ( m_generationMode != GENERATE_INCREMENTAL )
  1498.         {
  1499.                 FOR_EACH_LL( m_ladderList, lit )
  1500.                 {
  1501.                         m_ladderList[lit]->ConnectGeneratedLadder();
  1502.                 }
  1503.         }
  1504. }
  1505.  
  1506.  
  1507. //--------------------------------------------------------------------------------------------------------------
  1508. /**
  1509.  * Initiate the generation process
  1510.  */
  1511. void CNavMesh::BeginGeneration( bool incremental )
  1512. {
  1513.         IGameEvent *event = gameeventmanager->CreateEvent( "nav_generate" );
  1514.         if ( event )
  1515.         {
  1516.                 gameeventmanager->FireEvent( event );
  1517.         }
  1518.  
  1519.         engine->ServerCommand( "bot_kick\n" );
  1520.  
  1521.         // Right now, incrementally-generated areas won't connect to existing areas automatically.
  1522.         // Since this means hand-editing will be necessary, don't do a full analyze.
  1523.         if ( incremental )
  1524.         {
  1525.                 nav_quicksave.SetValue( 1 );
  1526.         }
  1527.  
  1528.         m_generationState = SAMPLE_WALKABLE_SPACE;
  1529.         m_sampleTick = 0;
  1530.         m_generationMode = (incremental) ? GENERATE_INCREMENTAL : GENERATE_FULL;
  1531.         lastMsgTime = 0.0f;
  1532.  
  1533.         // clear any previous mesh
  1534.         DestroyNavigationMesh( incremental );
  1535.  
  1536.         SetNavPlace( UNDEFINED_PLACE );
  1537.  
  1538.         // build internal representations of ladders, which are used to find new walkable areas
  1539.         if ( !incremental ) ///< @incremental update doesn't build ladders to avoid overlapping existing ones
  1540.         {
  1541.                 BuildLadders();
  1542.         }
  1543.  
  1544.         // start sampling from a spawn point
  1545.         CBaseEntity *spawn = gEntList.FindEntityByClassname( NULL, GetPlayerSpawnName() );
  1546.  
  1547.         if (spawn && !incremental)
  1548.         {
  1549.                 // snap it to the sampling grid
  1550.                 Vector pos = spawn->GetAbsOrigin();
  1551.                 pos.x = TheNavMesh->SnapToGrid( pos.x );
  1552.                 pos.y = TheNavMesh->SnapToGrid( pos.y );
  1553.  
  1554.                 Vector normal;
  1555.                 if (GetGroundHeight( pos, &pos.z, &normal ))
  1556.                 {
  1557.                         m_currentNode = new CNavNode( pos, normal, NULL );
  1558.                 }
  1559.         }
  1560.         else
  1561.         {
  1562.                 // the system will see this NULL and select the next walkable seed
  1563.                 m_currentNode = NULL;
  1564.         }
  1565.  
  1566.         // if there are no seed points, we can't generate
  1567.         if (m_walkableSeedList.Count() == 0 && m_currentNode == NULL)
  1568.         {
  1569.                 m_generationMode = GENERATE_NONE;
  1570.                 Msg( "No valid walkable seed positions.  Cannot generate Navigation Mesh.\n" );
  1571.                 return;
  1572.         }
  1573.  
  1574.         // initialize seed list index
  1575.         m_seedIdx = m_walkableSeedList.Head();
  1576.  
  1577.         Msg( "Generating Navigation Mesh...\n" );
  1578. }
  1579.  
  1580.  
  1581. //--------------------------------------------------------------------------------------------------------------
  1582. /**
  1583.  * Re-analyze an existing Mesh.  Determine Hiding Spots, Encounter Spots, etc.
  1584.  */
  1585. void CNavMesh::BeginAnalysis( void )
  1586. {
  1587.         // Remove and re-add elements in TheNavAreaList, to ensure indices are useful for progress feedback
  1588.         NavAreaList tmpList;
  1589.         {
  1590.                 FOR_EACH_LL( TheNavAreaList, it )
  1591.                 {
  1592.                         tmpList.AddToTail( TheNavAreaList[it] );
  1593.                 }
  1594.         }
  1595.         TheNavAreaList.RemoveAll();
  1596.         {
  1597.                 FOR_EACH_LL( tmpList, it )
  1598.                 {
  1599.                         TheNavAreaList.AddToTail( tmpList[it] );
  1600.                 }
  1601.         }
  1602.  
  1603.         DestroyHidingSpots();
  1604.         m_generationState = FIND_HIDING_SPOTS;
  1605.         m_generationIndex = TheNavAreaList.Head();
  1606.         m_generationMode = GENERATE_ANALYSIS_ONLY;
  1607.         lastMsgTime = 0.0f;
  1608. }
  1609.  
  1610.  
  1611. //--------------------------------------------------------------------------------------------------------------
  1612. void ShowViewPortPanelToAll( const char * name, bool bShow, KeyValues *data )
  1613. {
  1614.         CRecipientFilter filter;
  1615.         filter.AddAllPlayers();
  1616.         filter.MakeReliable();
  1617.  
  1618.         int count = 0;
  1619.         KeyValues *subkey = NULL;
  1620.  
  1621.         if ( data )
  1622.         {
  1623.                 subkey = data->GetFirstSubKey();
  1624.                 while ( subkey )
  1625.                 {
  1626.                         count++; subkey = subkey->GetNextKey();
  1627.                 }
  1628.  
  1629.                 subkey = data->GetFirstSubKey(); // reset
  1630.         }
  1631.  
  1632.         UserMessageBegin( filter, "VGUIMenu" );
  1633.                 WRITE_STRING( name ); // menu name
  1634.                 WRITE_BYTE( bShow?1:0 );
  1635.                 WRITE_BYTE( count );
  1636.                
  1637.                 // write additional data (be carefull not more than 192 bytes!)
  1638.                 while ( subkey )
  1639.                 {
  1640.                         WRITE_STRING( subkey->GetName() );
  1641.                         WRITE_STRING( subkey->GetString() );
  1642.                         subkey = subkey->GetNextKey();
  1643.                 }
  1644.         MessageEnd();
  1645. }
  1646.  
  1647.  
  1648. //--------------------------------------------------------------------------------------------------------------
  1649. static void AnalysisProgress( const char *msg, int ticks, int current, bool showPercent = true )
  1650. {
  1651.         const float MsgInterval = 10.0f;
  1652.         float now = Plat_FloatTime();
  1653.         if ( now > lastMsgTime + MsgInterval )
  1654.         {
  1655.                 if ( showPercent && ticks )
  1656.                 {
  1657.                         Msg( "%s %.0f%%\n", msg, current*100.0f/ticks );
  1658.                 }
  1659.                 else
  1660.                 {
  1661.                         Msg( "%s\n", msg );
  1662.                 }
  1663.  
  1664.                 lastMsgTime = now;
  1665.         }
  1666.  
  1667.         KeyValues *data = new KeyValues("data");
  1668.         data->SetString( "msg", msg );
  1669.         data->SetInt( "total", ticks );
  1670.         data->SetInt( "current", current );
  1671.  
  1672.         ShowViewPortPanelToAll( PANEL_NAV_PROGRESS, true, data );
  1673.  
  1674.         data->deleteThis();
  1675. }
  1676.  
  1677.  
  1678. //--------------------------------------------------------------------------------------------------------------
  1679. static void HideAnalysisProgress( void )
  1680. {
  1681.         KeyValues *data = new KeyValues("data");
  1682.         ShowViewPortPanelToAll( PANEL_NAV_PROGRESS, false, data );
  1683.         data->deleteThis();
  1684. }
  1685.  
  1686.  
  1687. //--------------------------------------------------------------------------------------------------------------
  1688. /**
  1689.  * Process the auto-generation for 'maxTime' seconds. return false if generation is complete.
  1690.  */
  1691. bool CNavMesh::UpdateGeneration( float maxTime )
  1692. {
  1693.         double startTime = Plat_FloatTime();
  1694.  
  1695.         switch( m_generationState )
  1696.         {
  1697.                 //---------------------------------------------------------------------------
  1698.                 case SAMPLE_WALKABLE_SPACE:
  1699.                 {
  1700.                         AnalysisProgress( "Sampling walkable space...", 100, m_sampleTick / 10, false );
  1701.                         m_sampleTick = ( m_sampleTick + 1 ) % 1000;
  1702.  
  1703.                         while ( SampleStep() )
  1704.                         {
  1705.                                 if ( Plat_FloatTime() - startTime > maxTime )
  1706.                                 {
  1707.                                         return true;
  1708.                                 }
  1709.                         }
  1710.  
  1711.                         // sampling is complete, now build nav areas
  1712.                         m_generationState = CREATE_AREAS_FROM_SAMPLES;
  1713.  
  1714.                         return true;
  1715.                 }
  1716.  
  1717.                 //---------------------------------------------------------------------------
  1718.                 case CREATE_AREAS_FROM_SAMPLES:
  1719.                 {
  1720.                         Msg( "Creating navigation areas from sampled data...\n" );
  1721.  
  1722.                         CreateNavAreasFromNodes();
  1723.                         DestroyHidingSpots();
  1724.  
  1725.                         // Remove and re-add elements in TheNavAreaList, to ensure indices are useful for progress feedback
  1726.                         NavAreaList tmpList;
  1727.                         {
  1728.                                 FOR_EACH_LL( TheNavAreaList, it )
  1729.                                 {
  1730.                                         tmpList.AddToTail( TheNavAreaList[it] );
  1731.                                 }
  1732.                         }
  1733.                         TheNavAreaList.RemoveAll();
  1734.                         {
  1735.                                 FOR_EACH_LL( tmpList, it )
  1736.                                 {
  1737.                                         TheNavAreaList.AddToTail( tmpList[it] );
  1738.                                 }
  1739.                         }
  1740.  
  1741.                         m_generationState = FIND_HIDING_SPOTS;
  1742.                         m_generationIndex = TheNavAreaList.Head();
  1743.                         return true;
  1744.                 }
  1745.  
  1746.                 //---------------------------------------------------------------------------
  1747.                 case FIND_HIDING_SPOTS:
  1748.                 {
  1749.                         while( m_generationIndex != TheNavAreaList.InvalidIndex() )
  1750.                         {
  1751.                                 CNavArea *area = TheNavAreaList[ m_generationIndex ];
  1752.                                 m_generationIndex = TheNavAreaList.Next( m_generationIndex );
  1753.  
  1754.                                 area->ComputeHidingSpots();
  1755.  
  1756.                                 // don't go over our time allotment
  1757.                                 if( Plat_FloatTime() - startTime > maxTime )
  1758.                                 {
  1759.                                         AnalysisProgress( "Finding hiding spots...", 100, 100 * m_generationIndex / TheNavAreaList.Count() );
  1760.                                         return true;
  1761.                                 }
  1762.                         }
  1763.  
  1764.                         Msg( "Finding hiding spots...DONE\n" );
  1765.  
  1766.                         m_generationState = FIND_APPROACH_AREAS;
  1767.                         m_generationIndex = TheNavAreaList.Head();
  1768.                         return true;
  1769.                 }
  1770.  
  1771.                 //---------------------------------------------------------------------------
  1772.                 case FIND_APPROACH_AREAS:
  1773.                 {
  1774.                         while( m_generationIndex != TheNavAreaList.InvalidIndex() )
  1775.                         {
  1776.                                 CNavArea *area = TheNavAreaList[ m_generationIndex ];
  1777.                                 m_generationIndex = TheNavAreaList.Next( m_generationIndex );
  1778.  
  1779.                                 area->ComputeApproachAreas();
  1780.  
  1781.                                 // don't go over our time allotment
  1782.                                 if( Plat_FloatTime() - startTime > maxTime )
  1783.                                 {
  1784.                                         AnalysisProgress( "Finding approach areas...", 100, 100 * m_generationIndex / TheNavAreaList.Count() );
  1785.                                         return true;
  1786.                                 }
  1787.                         }
  1788.  
  1789.                         Msg( "Finding approach areas...DONE\n" );
  1790.  
  1791.                         m_generationState = FIND_ENCOUNTER_SPOTS;
  1792.                         m_generationIndex = TheNavAreaList.Head();
  1793.                         return true;
  1794.                 }
  1795.  
  1796.                 //---------------------------------------------------------------------------
  1797.                 case FIND_ENCOUNTER_SPOTS:
  1798.                 {
  1799.                         while( m_generationIndex != TheNavAreaList.InvalidIndex() )
  1800.                         {
  1801.                                 CNavArea *area = TheNavAreaList[ m_generationIndex ];
  1802.                                 m_generationIndex = TheNavAreaList.Next( m_generationIndex );
  1803.  
  1804.                                 area->ComputeSpotEncounters();
  1805.  
  1806.                                 // don't go over our time allotment
  1807.                                 if( Plat_FloatTime() - startTime > maxTime )
  1808.                                 {
  1809.                                         AnalysisProgress( "Finding encounter spots...", 100, 100 * m_generationIndex / TheNavAreaList.Count() );
  1810.                                         return true;
  1811.                                 }
  1812.                         }
  1813.  
  1814.                         Msg( "Finding encounter spots...DONE\n" );
  1815.  
  1816.                         m_generationState = FIND_SNIPER_SPOTS;
  1817.                         m_generationIndex = TheNavAreaList.Head();
  1818.                         return true;
  1819.                 }
  1820.  
  1821.                 //---------------------------------------------------------------------------
  1822.                 case FIND_SNIPER_SPOTS:
  1823.                 {
  1824.                         while( m_generationIndex != TheNavAreaList.InvalidIndex() )
  1825.                         {
  1826.                                 CNavArea *area = TheNavAreaList[ m_generationIndex ];
  1827.                                 m_generationIndex = TheNavAreaList.Next( m_generationIndex );
  1828.  
  1829.                                 area->ComputeSniperSpots();
  1830.  
  1831.                                 // don't go over our time allotment
  1832.                                 if( Plat_FloatTime() - startTime > maxTime )
  1833.                                 {
  1834.                                         AnalysisProgress( "Finding sniper spots...", 100, 100 * m_generationIndex / TheNavAreaList.Count() );
  1835.                                         return true;
  1836.                                 }
  1837.                         }
  1838.  
  1839.                         Msg( "Finding sniper spots...DONE\n" );
  1840.  
  1841.                         m_generationState = FIND_EARLIEST_OCCUPY_TIMES;
  1842.                         m_generationIndex = TheNavAreaList.Head();
  1843.                         return true;
  1844.                 }
  1845.  
  1846.                 //---------------------------------------------------------------------------
  1847.                 case FIND_EARLIEST_OCCUPY_TIMES:
  1848.                 {
  1849.                         while( m_generationIndex != TheNavAreaList.InvalidIndex() )
  1850.                         {
  1851.                                 CNavArea *area = TheNavAreaList[ m_generationIndex ];
  1852.                                 m_generationIndex = TheNavAreaList.Next( m_generationIndex );
  1853.  
  1854.                                 area->ComputeEarliestOccupyTimes();
  1855.  
  1856.                                 // don't go over our time allotment
  1857.                                 if( Plat_FloatTime() - startTime > maxTime )
  1858.                                 {
  1859.                                         AnalysisProgress( "Finding earliest occupy times...", 100, 100 * m_generationIndex / TheNavAreaList.Count() );
  1860.                                         return true;
  1861.                                 }
  1862.                         }
  1863.  
  1864.                         Msg( "Finding earliest occupy times...DONE\n" );
  1865.  
  1866.                         m_generationState = SAVE_NAV_MESH;
  1867.                         m_generationIndex = TheNavAreaList.Head();
  1868.                         return true;
  1869.                 }
  1870.  
  1871.                 //---------------------------------------------------------------------------
  1872.                 case SAVE_NAV_MESH:
  1873.                 {
  1874.                         // generation complete!
  1875.                         Msg( "Generation complete!\n" );
  1876.                         m_generationMode = GENERATE_NONE;
  1877.                         m_isLoaded = true;
  1878.  
  1879.                         HideAnalysisProgress();
  1880.  
  1881.                         if ( nav_restart_after_analysis.GetBool() )
  1882.                         {
  1883.                                 // save the mesh
  1884.                                 if (Save())
  1885.                                 {
  1886.                                         Msg( "Navigation map '%s' saved.\n", GetFilename() );
  1887.                                 }
  1888.                                 else
  1889.                                 {
  1890.                                         const char *filename = GetFilename();
  1891.                                         Msg( "ERROR: Cannot save navigation map '%s'.\n", (filename) ? filename : "(null)" );
  1892.                                 }
  1893.  
  1894.                                 engine->ChangeLevel( STRING( gpGlobals->mapname ), NULL );
  1895.                         }
  1896.  
  1897.                         return false;
  1898.                 }
  1899.         }
  1900.  
  1901.         return false;
  1902. }
  1903.  
  1904. //--------------------------------------------------------------------------------------------------------------
  1905. /**
  1906.  * Define the name of player spawn entities
  1907.  */
  1908. void CNavMesh::SetPlayerSpawnName( const char *name )
  1909. {
  1910.         if (m_spawnName)
  1911.         {
  1912.                 delete [] m_spawnName;
  1913.         }
  1914.  
  1915.         m_spawnName = new char [ strlen(name) + 1 ];
  1916.         strcpy( m_spawnName, name );
  1917. }
  1918.  
  1919.  
  1920. //--------------------------------------------------------------------------------------------------------------
  1921. /**
  1922.  * Return name of player spawn entity
  1923.  */
  1924. const char *CNavMesh::GetPlayerSpawnName( void ) const
  1925. {
  1926.         if (m_spawnName)
  1927.                 return m_spawnName;
  1928.  
  1929.         // default value
  1930.         return "info_player_start";
  1931. }
  1932.  
  1933. //--------------------------------------------------------------------------------------------------------------
  1934. /**
  1935.  * Add a nav node and connect it.
  1936.  * Node Z positions are ground level.
  1937.  */
  1938. CNavNode *CNavMesh::AddNode( const Vector &destPos, const Vector &normal, NavDirType dir, CNavNode *source )
  1939. {
  1940.         // check if a node exists at this location
  1941.         CNavNode *node = CNavNode::GetNode( destPos );
  1942.        
  1943.         // if no node exists, create one
  1944.         bool useNew = false;
  1945.         if (node == NULL)
  1946.         {
  1947.                 node = new CNavNode( destPos, normal, source );
  1948.                 useNew = true;
  1949.         }
  1950.  
  1951.         // connect source node to new node
  1952.         source->ConnectTo( node, dir );
  1953.  
  1954.         // optimization: if deltaZ changes very little, assume connection is commutative
  1955.         const float zTolerance = 50.0f;
  1956.         if (fabs( source->GetPosition()->z - destPos.z ) < zTolerance)
  1957.         {
  1958.                 node->ConnectTo( source, OppositeDirection( dir ) );
  1959.                 node->MarkAsVisited( OppositeDirection( dir ) );
  1960.         }
  1961.  
  1962.         if (useNew)
  1963.         {
  1964.                 // new node becomes current node
  1965.                 m_currentNode = node;
  1966.         }
  1967.  
  1968.         node->CheckCrouch();
  1969.  
  1970.         return node;
  1971. }
  1972.  
  1973. //--------------------------------------------------------------------------------------------------------------
  1974. inline CNavNode *LadderEndSearch( const Vector *pos, NavDirType mountDir )
  1975. {
  1976.         Vector center = *pos;
  1977.         AddDirectionVector( &center, mountDir, HalfHumanWidth );
  1978.  
  1979.         //
  1980.         // Test the ladder dismount point first, then each cardinal direction one and two steps away
  1981.         //
  1982.         for( int d=(-1); d<2*NUM_DIRECTIONS; ++d )
  1983.         {
  1984.                 Vector tryPos = center;
  1985.  
  1986.                 if (d >= NUM_DIRECTIONS)
  1987.                         AddDirectionVector( &tryPos, (NavDirType)(d - NUM_DIRECTIONS), 2.0f*GenerationStepSize );
  1988.                 else if (d >= 0)
  1989.                         AddDirectionVector( &tryPos, (NavDirType)d, GenerationStepSize );
  1990.  
  1991.                 // step up a rung, to ensure adjacent floors are below us
  1992.                 tryPos.z += GenerationStepSize;
  1993.  
  1994.                 tryPos.x = TheNavMesh->SnapToGrid( tryPos.x );
  1995.                 tryPos.y = TheNavMesh->SnapToGrid( tryPos.y );
  1996.  
  1997.                 // adjust height to account for sloping areas
  1998.                 Vector tryNormal;
  1999.                 if (TheNavMesh->GetGroundHeight( tryPos, &tryPos.z, &tryNormal ) == false)
  2000.                         continue;
  2001.  
  2002.                 // make sure this point is not on the other side of a wall
  2003.                 const float fudge = 2.0f;
  2004.                 trace_t result;
  2005.                 UTIL_TraceLine( center + Vector( 0, 0, fudge ), tryPos + Vector( 0, 0, fudge ), MASK_PLAYERSOLID_BRUSHONLY, NULL, COLLISION_GROUP_NONE, &result );
  2006.                 if (result.fraction != 1.0f || result.startsolid)
  2007.                         continue;
  2008.  
  2009.                 // if no node exists here, create one and continue the search
  2010.                 if (CNavNode::GetNode( tryPos ) == NULL)
  2011.                 {
  2012.                         return new CNavNode( tryPos, tryNormal, NULL );
  2013.                 }
  2014.         }
  2015.  
  2016.         return NULL;
  2017. }
  2018.  
  2019.  
  2020. //--------------------------------------------------------------------------------------------------------------
  2021. /**
  2022.  * Search the world and build a map of possible movements.
  2023.  * The algorithm begins at the bot's current location, and does a recursive search
  2024.  * outwards, tracking all valid steps and generating a directed graph of CNavNodes.
  2025.  *
  2026.  * Sample the map one "step" in a cardinal direction to learn the map.
  2027.  *
  2028.  * Returns true if sampling needs to continue, or false if done.
  2029.  */
  2030. bool CNavMesh::SampleStep( void )
  2031. {
  2032.         // take a step
  2033.         while( true )
  2034.         {
  2035.                 if (m_currentNode == NULL)
  2036.                 {
  2037.                         // sampling is complete from current seed, try next one
  2038.                         m_currentNode = GetNextWalkableSeedNode();
  2039.  
  2040.                         if (m_currentNode == NULL)
  2041.                         {
  2042.                                 // search is exhausted - continue search from ends of ladders
  2043.                                 FOR_EACH_LL( m_ladderList, it )
  2044.                                 {
  2045.                                         CNavLadder *ladder = m_ladderList[ it ];
  2046.  
  2047.                                         // check ladder bottom
  2048.                                         if ((m_currentNode = LadderEndSearch( &ladder->m_bottom, ladder->GetDir() )) != 0)
  2049.                                                 break;
  2050.  
  2051.                                         // check ladder top
  2052.                                         if ((m_currentNode = LadderEndSearch( &ladder->m_top, ladder->GetDir() )) != 0)
  2053.                                                 break;
  2054.                                 }
  2055.  
  2056.                                 if (m_currentNode == NULL)
  2057.                                 {
  2058.                                         // all seeds exhausted, sampling complete
  2059.                                         return false;
  2060.                                 }
  2061.                         }
  2062.                 }
  2063.  
  2064.                 //
  2065.                 // Take a step from this node
  2066.                 //
  2067.                 for( int dir = NORTH; dir < NUM_DIRECTIONS; dir++ )
  2068.                 {
  2069.                         if (!m_currentNode->HasVisited( (NavDirType)dir ))
  2070.                         {
  2071.                                 // have not searched in this direction yet
  2072.  
  2073.                                 // start at current node position
  2074.                                 Vector pos = *m_currentNode->GetPosition();
  2075.  
  2076.                                 // snap to grid
  2077.                                 int cx = SnapToGrid( pos.x );
  2078.                                 int cy = SnapToGrid( pos.y );
  2079.  
  2080.                                 // attempt to move to adjacent node
  2081.                                 switch( dir )
  2082.                                 {
  2083.                                         case NORTH:             cy -= GenerationStepSize; break;
  2084.                                         case SOUTH:             cy += GenerationStepSize; break;
  2085.                                         case EAST:              cx += GenerationStepSize; break;
  2086.                                         case WEST:              cx -= GenerationStepSize; break;
  2087.                                 }
  2088.  
  2089.                                 pos.x = cx;
  2090.                                 pos.y = cy;
  2091.  
  2092.                                 m_generationDir = (NavDirType)dir;
  2093.  
  2094.                                 // mark direction as visited
  2095.                                 m_currentNode->MarkAsVisited( m_generationDir );
  2096.  
  2097.                                 // test if we can move to new position
  2098.                                 trace_t result;
  2099.                                 Vector from, to;
  2100.  
  2101.                                 // modify position to account for change in ground level during step
  2102.                                 to.x = pos.x;
  2103.                                 to.y = pos.y;
  2104.                                 Vector toNormal;
  2105.                                 if (GetGroundHeight( pos, &to.z, &toNormal ) == false)
  2106.                                 {
  2107.                                         return true;
  2108.                                 }
  2109.  
  2110.                                 from = *m_currentNode->GetPosition();
  2111.  
  2112.                                 Vector fromOrigin = from + Vector( 0, 0, HalfHumanHeight );
  2113.                                 Vector toOrigin = to + Vector( 0, 0, HalfHumanHeight );
  2114.  
  2115.                                 CTraceFilterWalkableEntities filter( NULL, COLLISION_GROUP_NONE, WALK_THRU_EVERYTHING );
  2116.                                 UTIL_TraceLine( fromOrigin, toOrigin, MASK_PLAYERSOLID_BRUSHONLY, &filter, &result );
  2117.  
  2118.                                 bool walkable;
  2119.  
  2120.                                 if (result.fraction == 1.0f && !result.startsolid)
  2121.                                 {
  2122.                                         // the trace didnt hit anything - clear
  2123.  
  2124.                                         float toGround = to.z;
  2125.                                         float fromGround = from.z;
  2126.  
  2127.                                         float epsilon = 0.1f;
  2128.  
  2129.                                         // check if ledge is too high to reach or will cause us to fall to our death
  2130.                                         if (toGround - fromGround > JumpCrouchHeight + epsilon || fromGround - toGround > DeathDrop)
  2131.                                         {
  2132.                                                 walkable = false;
  2133.                                         }
  2134.                                         else
  2135.                                         {
  2136.                                                 // check surface normals along this step to see if we would cross any impassable slopes
  2137.                                                 Vector delta = to - from;
  2138.                                                 const float inc = 2.0f;
  2139.                                                 float along = inc;
  2140.                                                 bool done = false;
  2141.                                                 float ground;
  2142.                                                 Vector normal;
  2143.  
  2144.                                                 walkable = true;
  2145.  
  2146.                                                 while( !done )
  2147.                                                 {
  2148.                                                         Vector p;
  2149.  
  2150.                                                         // need to guarantee that we test the exact edges
  2151.                                                         if (along >= GenerationStepSize)
  2152.                                                         {
  2153.                                                                 p = to;
  2154.                                                                 done = true;
  2155.                                                         }
  2156.                                                         else
  2157.                                                         {
  2158.                                                                 p = from + delta * (along/GenerationStepSize);
  2159.                                                         }
  2160.  
  2161.                                                         if (GetGroundHeight( p, &ground, &normal ) == false)
  2162.                                                         {
  2163.                                                                 walkable = false;
  2164.                                                                 break;
  2165.                                                         }
  2166.  
  2167.                                                         // check for maximum allowed slope
  2168.                                                         if (normal.z < nav_slope_limit.GetFloat())
  2169.                                                         {
  2170.                                                                 walkable = false;
  2171.                                                                 break;
  2172.                                                         }
  2173.  
  2174.                                                         along += inc;                                  
  2175.                                                 }
  2176.                                         }
  2177.                                 }
  2178.                                 else    // TraceLine hit something...
  2179.                                 {
  2180.                                         if (IsEntityWalkable( result.m_pEnt, WALK_THRU_EVERYTHING ))
  2181.                                         {
  2182.                                                 walkable = true;
  2183.                                         }
  2184.                                         else
  2185.                                         {
  2186.                                                 walkable = false;
  2187.                                         }
  2188.                                 }
  2189.  
  2190.                                 // if we're incrementally generating, don't overlap existing nav areas
  2191.                                 CNavArea *overlap = GetNavArea( to, HumanHeight );
  2192.                                 if ( overlap )
  2193.                                 {
  2194.                                         walkable = false;
  2195.                                 }
  2196.  
  2197.                                 if (walkable)
  2198.                                 {
  2199.                                         // we can move here
  2200.                                         // create a new navigation node, and update current node pointer
  2201.                                         AddNode( to, toNormal, m_generationDir, m_currentNode );
  2202.                                 }
  2203.  
  2204.                                 return true;
  2205.                         }
  2206.                 }
  2207.  
  2208.                 // all directions have been searched from this node - pop back to its parent and continue
  2209.                 m_currentNode = m_currentNode->GetParent();
  2210.         }
  2211. }
  2212.  
  2213.  
  2214. //--------------------------------------------------------------------------------------------------------------
  2215. /**
  2216.  * Add given walkable position to list of seed positions for map sampling
  2217.  */
  2218. void CNavMesh::AddWalkableSeed( const Vector &pos, const Vector &normal )
  2219. {
  2220.         WalkableSeedSpot seed;
  2221.  
  2222.         seed.pos = pos;
  2223.         seed.normal = normal;
  2224.  
  2225.         m_walkableSeedList.AddToTail( seed );
  2226. }
  2227.  
  2228. //--------------------------------------------------------------------------------------------------------------
  2229. /**
  2230.  * Return the next walkable seed as a node
  2231.  */
  2232. CNavNode *CNavMesh::GetNextWalkableSeedNode( void )
  2233. {      
  2234.         if (!m_walkableSeedList.IsValidIndex( m_seedIdx ))
  2235.                 return NULL;
  2236.  
  2237.         WalkableSeedSpot spot = m_walkableSeedList.Element( m_seedIdx );
  2238.  
  2239.         m_seedIdx = m_walkableSeedList.Next( m_seedIdx );
  2240.  
  2241.         return new CNavNode( spot.pos, spot.normal, NULL );
  2242. }
  2243.  
  2244.  
  2245. //--------------------------------------------------------------------------------------------------------------
  2246. /**
  2247.  * Check LOS, ignoring any entities that we can walk through
  2248.  */
  2249. bool IsWalkableTraceLineClear( Vector &from, Vector &to, unsigned int flags )
  2250. {
  2251.         trace_t result;
  2252.         CBaseEntity *ignore = NULL;
  2253.         Vector useFrom = from;
  2254.  
  2255.         CTraceFilterWalkableEntities traceFilter( NULL, COLLISION_GROUP_NONE, flags );
  2256.  
  2257.         result.fraction = 0.0f;
  2258.  
  2259.         const int maxTries = 50;
  2260.         for( int t=0; t<maxTries; ++t )
  2261.         {
  2262.                 UTIL_TraceLine( useFrom, to, MASK_PLAYERSOLID, &traceFilter, &result );
  2263.  
  2264.                 // if we hit a walkable entity, try again
  2265.                 if (result.fraction != 1.0f && IsEntityWalkable( result.m_pEnt, flags ))
  2266.                 {
  2267.                         ignore = result.m_pEnt;
  2268.  
  2269.                         // start from just beyond where we hit to avoid infinite loops
  2270.                         Vector dir = to - from;
  2271.                         dir.NormalizeInPlace();
  2272.                         useFrom = result.endpos + 5.0f * dir;
  2273.                 }
  2274.                 else
  2275.                 {
  2276.                         break;
  2277.                 }
  2278.         }
  2279.  
  2280.         if (result.fraction == 1.0f)
  2281.                 return true;
  2282.  
  2283.         return false;
  2284. }
  2285.  
clone this paste RAW Paste Data