First version of the SOurce SDK 2013

1 files changed, 285 insertions, 0 deletions

diff --git a/mp/src/game/server/nav_simplify.cpp b/mp/src/game/server/nav_simplify.cpp
new file mode 100644
index 00000000..025c31d0
--- /dev/null
+++ b/mp/src/game/server/nav_simplify.cpp
@@ -0,0 +1,285 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//

+//

+// Purpose: 

+//

+// $NoKeywords: $

+//

+//=============================================================================//

+// nav_simplify.cpp

+

+#include "cbase.h"

+#include "nav_mesh.h"

+#include "nav_node.h"

+

+// NOTE: This has to be the last file included!

+#include "tier0/memdbgon.h"

+

+extern ConVar nav_snap_to_grid;

+extern ConVar nav_split_place_on_ground;

+extern ConVar nav_coplanar_slope_limit;

+extern ConVar nav_coplanar_slope_limit_displacement;

+

+//--------------------------------------------------------------------------------------------------------

+static bool ReduceToComponentAreas( CNavArea *area, bool addToSelectedSet )

+{

+	if ( !area )

+		return false;

+

+	bool splitAlongX;

+	float splitEdge;

+

+	const float minSplitSize = 2.0f; // ensure the first split is larger than this

+

+	float sizeX = area->GetSizeX();

+	float sizeY = area->GetSizeY();

+

+	CNavArea *first = NULL;

+	CNavArea *second = NULL;

+	CNavArea *third = NULL;

+	CNavArea *fourth = NULL;

+

+	bool didSplit = false;

+

+	if ( sizeX > GenerationStepSize )

+	{

+		splitEdge = RoundToUnits( area->GetCorner( NORTH_WEST ).x, GenerationStepSize );

+		if ( splitEdge < area->GetCorner( NORTH_WEST ).x + minSplitSize )

+			splitEdge += GenerationStepSize;

+		splitAlongX = false;

+

+		didSplit = area->SplitEdit( splitAlongX, splitEdge, &first, &second );

+	}

+

+	if ( sizeY > GenerationStepSize )

+	{

+		splitEdge = RoundToUnits( area->GetCorner( NORTH_WEST ).y, GenerationStepSize );

+		if ( splitEdge < area->GetCorner( NORTH_WEST ).y + minSplitSize )

+			splitEdge += GenerationStepSize;

+		splitAlongX = true;

+

+		if ( didSplit )

+		{

+			didSplit = first->SplitEdit( splitAlongX, splitEdge, &third, &fourth );

+			didSplit = second->SplitEdit( splitAlongX, splitEdge, &first, &second );

+		}

+		else

+		{

+			didSplit = area->SplitEdit( splitAlongX, splitEdge, &first, &second );

+		}

+	}

+

+	if ( !didSplit )

+		return false;

+

+	if ( addToSelectedSet )

+	{

+		TheNavMesh->AddToSelectedSet( first );

+		TheNavMesh->AddToSelectedSet( second );

+		TheNavMesh->AddToSelectedSet( third );

+		TheNavMesh->AddToSelectedSet( fourth );

+	}

+

+	ReduceToComponentAreas( first, addToSelectedSet );

+	ReduceToComponentAreas( second, addToSelectedSet );

+	ReduceToComponentAreas( third, addToSelectedSet );

+	ReduceToComponentAreas( fourth, addToSelectedSet );

+

+	return true;

+}

+

+

+//--------------------------------------------------------------------------------------------------------

+CON_COMMAND_F( nav_chop_selected, "Chops all selected areas into their component 1x1 areas", FCVAR_CHEAT )

+{

+	if ( !UTIL_IsCommandIssuedByServerAdmin() || engine->IsDedicatedServer() )

+		return;

+

+	TheNavMesh->StripNavigationAreas();

+	TheNavMesh->SetMarkedArea( NULL );

+

+	NavAreaCollector collector;

+	TheNavMesh->ForAllSelectedAreas( collector );

+

+	for ( int i=0; i<collector.m_area.Count(); ++i )

+	{

+		ReduceToComponentAreas( collector.m_area[i], true );

+	}

+

+	Msg( "%d areas chopped into %d\n", collector.m_area.Count(), TheNavMesh->GetSelecteSetSize() );

+}

+

+

+//--------------------------------------------------------------------------------------------------------

+void CNavMesh::RemoveNodes( void )

+{

+	FOR_EACH_VEC( TheNavAreas, it )

+	{

+		TheNavAreas[ it ]->ResetNodes();

+	}

+

+	// destroy navigation nodes created during map generation

+	CNavNode::CleanupGeneration();

+}

+

+

+//--------------------------------------------------------------------------------------------------------

+void CNavMesh::GenerateNodes( const Extent &bounds )

+{

+	m_simplifyGenerationExtent = bounds;

+	m_seedIdx = 0;

+

+	Assert( m_generationMode == GENERATE_SIMPLIFY );

+	while ( SampleStep() )

+	{

+		// do nothing

+	}

+}

+

+

+//--------------------------------------------------------------------------------------------------------

+// Simplifies the selected set by reducing to 1x1 areas and re-merging them up with loosened tolerances

+void CNavMesh::SimplifySelectedAreas( void )

+{

+	// Save off somve cvars: we need to place nodes on ground, we need snap to grid set, and we loosen slope tolerances

+	m_generationMode = GENERATE_SIMPLIFY;

+	bool savedSplitPlaceOnGround = nav_split_place_on_ground.GetBool();

+	nav_split_place_on_ground.SetValue( 1 );

+

+	float savedCoplanarSlopeDisplacementLimit = nav_coplanar_slope_limit_displacement.GetFloat();

+	nav_coplanar_slope_limit_displacement.SetValue( MIN( 0.5f, savedCoplanarSlopeDisplacementLimit ) );

+

+	float savedCoplanarSlopeLimit = nav_coplanar_slope_limit.GetFloat();

+	nav_coplanar_slope_limit.SetValue( MIN( 0.5f, savedCoplanarSlopeLimit ) );

+

+	int savedGrid = nav_snap_to_grid.GetInt();

+	nav_snap_to_grid.SetValue( 1 );

+

+	StripNavigationAreas();

+	SetMarkedArea( NULL );

+

+	NavAreaCollector collector;

+	ForAllSelectedAreas( collector );

+

+	// Select walkable seeds and re-generate nodes in the bounds

+	ClearWalkableSeeds();

+

+	Extent bounds;

+	bounds.lo.Init( FLT_MAX, FLT_MAX, FLT_MAX );

+	bounds.hi.Init( -FLT_MAX, -FLT_MAX, -FLT_MAX );

+	for ( int i=0; i<collector.m_area.Count(); ++i )

+	{

+		Extent areaExtent;

+		CNavArea *area = collector.m_area[i];

+		area->GetExtent( &areaExtent );

+		areaExtent.lo.z -= HalfHumanHeight;

+		areaExtent.hi.z += 2 * HumanHeight;

+		bounds.Encompass( areaExtent );

+

+		Vector center = area->GetCenter();

+		center.x = SnapToGrid( center.x );

+		center.y = SnapToGrid( center.y );

+

+		Vector normal;

+		if ( FindGroundForNode( &center, &normal ) )

+		{

+			AddWalkableSeed( center, normal );

+

+			center.z += HumanHeight;

+			bounds.Encompass( center );

+		}

+	}

+	RemoveNodes();

+	GenerateNodes( bounds );

+	ClearWalkableSeeds();

+

+	// Split nav areas up into 1x1 component areas

+	for ( int i=0; i<collector.m_area.Count(); ++i )

+	{

+		ReduceToComponentAreas( collector.m_area[i], true );

+	}

+

+	// Assign nodes to each component area

+	FOR_EACH_VEC( m_selectedSet, it )

+	{

+		CNavArea *area = m_selectedSet[ it ];

+

+		Vector corner = area->GetCorner( NORTH_EAST );

+		Vector normal;

+		if ( FindGroundForNode( &corner, &normal ) )

+		{

+			area->m_node[ NORTH_EAST ] = CNavNode::GetNode( corner );

+			if ( area->m_node[ NORTH_EAST ] )

+			{

+				area->m_node[ NORTH_WEST ] = area->m_node[ NORTH_EAST ]->GetConnectedNode( WEST );

+				area->m_node[ SOUTH_EAST ] = area->m_node[ NORTH_EAST ]->GetConnectedNode( SOUTH );

+				if ( area->m_node[ SOUTH_EAST ] )

+				{

+					area->m_node[ SOUTH_WEST ] = area->m_node[ SOUTH_EAST ]->GetConnectedNode( WEST );

+

+					if ( area->m_node[ NORTH_WEST ] && area->m_node[ SOUTH_WEST ] )

+					{

+						area->AssignNodes( area );

+					}

+				}

+			}

+		}

+

+		Assert ( area->m_node[ NORTH_EAST ] && area->m_node[ NORTH_WEST ] && area->m_node[ SOUTH_EAST ] && area->m_node[ SOUTH_WEST ] );

+		if ( !( area->m_node[ NORTH_EAST ] && area->m_node[ NORTH_WEST ] && area->m_node[ SOUTH_EAST ] && area->m_node[ SOUTH_WEST ] ) )

+		{

+			Warning( "Area %d didn't get any nodes!\n", area->GetID() );

+		}

+	}

+

+	// Run a subset of incremental generation on the component areas

+	MergeGeneratedAreas();

+	SquareUpAreas();

+	MarkJumpAreas();

+	SplitAreasUnderOverhangs();

+	MarkStairAreas();

+	StichAndRemoveJumpAreas();

+	HandleObstacleTopAreas();

+	FixUpGeneratedAreas();

+

+	// Re-select the new areas

+	ClearSelectedSet();

+	FOR_EACH_VEC( TheNavAreas, i )

+	{

+		CNavArea *area = TheNavAreas[i];

+		if ( area->HasNodes() )

+		{

+			AddToSelectedSet( area );

+		}

+	}

+

+#ifndef _DEBUG

+	// leave nodes in debug for testing

+	RemoveNodes();

+#endif

+

+	m_generationMode = GENERATE_NONE;

+	nav_split_place_on_ground.SetValue( savedSplitPlaceOnGround );

+	nav_coplanar_slope_limit_displacement.SetValue( savedCoplanarSlopeDisplacementLimit );

+	nav_coplanar_slope_limit.SetValue( savedCoplanarSlopeLimit );

+	nav_snap_to_grid.SetValue( savedGrid );

+}

+

+

+//--------------------------------------------------------------------------------------------------------

+CON_COMMAND_F( nav_simplify_selected, "Chops all selected areas into their component 1x1 areas and re-merges them together into larger areas", FCVAR_CHEAT )

+{

+	if ( !UTIL_IsCommandIssuedByServerAdmin() || engine->IsDedicatedServer() )

+		return;

+

+	int selectedSetSize = TheNavMesh->GetSelecteSetSize();

+	if ( selectedSetSize == 0 )

+	{

+		Msg( "nav_simplify_selected only works on the selected set\n" );

+		return;

+	}

+

+	TheNavMesh->SimplifySelectedAreas();

+

+	Msg( "%d areas simplified - %d remain\n", selectedSetSize, TheNavMesh->GetSelecteSetSize() );

+}

+