1HEADmaster

1 files changed, 285 insertions, 0 deletions

diff --git a/game/server/nav_simplify.cpp b/game/server/nav_simplify.cpp
new file mode 100644
index 0000000..1e04cf4
--- /dev/null
+++ b/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() );
+}
+