/*
** Command & Conquer Renegade(tm)
** Copyright 2025 Electronic Arts Inc.
**
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation, either version 3 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program. If not, see .
*/
/***********************************************************************************************
*** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S ***
***********************************************************************************************
* *
* Project Name : LevelEdit *
* *
* $Archive:: /Commando/Code/Tools/LevelEdit/PathfindSectorBuilder.cpp $Modtime:: 5/27/00 4:10p $*
* *
* $Revision:: 56 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#include "stdafx.h"
#include "pathfindsectorbuilder.h"
#include "phys3.h"
#include "editorassetmgr.h"
#include "humanphys.h"
#include "phys3.h"
#include "boxrobj.h"
#include "pathfind.h"
#include "pscene.h"
#include "physcoltest.h"
#include "filemgr.h"
#include "_assetmgr.h"
#include "utils.h"
#include "nodemgr.h"
#include "filelocations.h"
#include "transitionnode.h"
#include "collisiongroups.h"
#include "pathfindportal.h"
#include "GeneratingPathfindDialog.h"
#include "terrainnode.h"
#include "sceneeditor.h"
#include "staticanimphys.h"
#include "elevator.h"
#include "doors.h"
#include "soldier.h"
#include "humanphys.h"
#include "combatchunkid.h"
//////////////////////////////////////////////////////////////////////////
// Local Prototypes
//////////////////////////////////////////////////////////////////////////
UINT fnPathfindDialogThread (DWORD dwparam1, DWORD dwparam2, DWORD, HRESULT *, HWND *);
///////////////////////////////////////////////////////////////////////////
// Local inlines
///////////////////////////////////////////////////////////////////////////
static inline bool
Clip_Point (Vector3 *point, const AABoxClass &box)
{
Vector3 temp_point = *point;
//
// Clip the temporary point
//
temp_point.X = max (temp_point.X, box.Center.X - box.Extent.X);
temp_point.Y = max (temp_point.Y, box.Center.Y - box.Extent.Y);
temp_point.Z = max (temp_point.Z, box.Center.Z - box.Extent.Z);
temp_point.X = min (temp_point.X, box.Center.X + box.Extent.X);
temp_point.Y = min (temp_point.Y, box.Center.Y + box.Extent.Y);
temp_point.Z = min (temp_point.Z, box.Center.Z + box.Extent.Z);
//
// Did the clip change the point?
//
bool retval = (point->X != temp_point.X);
retval |= (point->Y != temp_point.Y);
retval |= (point->Z != temp_point.Z);
//
// Pass the new point back to the caller
//
(*point) = temp_point;
return retval;
}
//////////////////////////////////////////////////////////////////////////
// Local constants
//////////////////////////////////////////////////////////////////////////
const float ONE_SEC_FALL_DIST = 4.9F;
class SimDirInfoClass
{
public:
SimDirInfoClass (void) { }
SimDirInfoClass (float _heading, float _speed, const Vector3 &_move, const Vector3 &_quadmove)
: heading (_heading), speed (_speed), move (_move), quad_move (_quadmove) { }
float heading;
float speed;
Vector3 move;
Vector3 quad_move;
};
//
// Note: The vector members are in "percentage of bounding box" units.
//
static const SimDirInfoClass DIR_INFO[DIR_MAX] =
{
SimDirInfoClass ( 0.0F, 0, Vector3 ( 1.0F, 0, 0), Vector3 ( 1.5F, -0.5F, 0) ),
SimDirInfoClass ( (float)DEG_TO_RAD (90), 0, Vector3 ( 0, 1.0F, 0), Vector3 ( 0.5F, 1.5F, 0) ),
SimDirInfoClass ( (float)DEG_TO_RAD (180), 0, Vector3 (-1.0F, 0, 0), Vector3 (-1.5F, 0.5F, 0) ),
SimDirInfoClass ( (float)DEG_TO_RAD (270), 0, Vector3 ( 0, -1.0F, 0), Vector3 (-0.5F, -1.5F, 0) )
};
static HumanPhysClass *_PhysSimObj = NULL;
static SoldierGameObj *_GameSimObj = NULL;
//////////////////////////////////////////////////////////////////////////
//
// PathfindSectorBuilderClass
//
//////////////////////////////////////////////////////////////////////////
PathfindSectorBuilderClass::PathfindSectorBuilderClass (void)
: m_CurrentSector (NULL),
m_SimBoundingBox (Vector3 (0.5F, 0.5F, 1.8F)),
m_SimBoxExtents (Vector3 (0.25F, 0.25F, 0.9F)),
m_DirInfo (NULL),
m_StepHeight (0),
m_TotalBoxCount (0),
m_TotalBoxGuess (0),
m_BeforeUpdateCount (0),
m_AllowWaterFloodfill (false),
m_MaxSectorDim (28000.0F)
{
RenderObjClass *commando_obj = NULL;
//
// Create an instance of the commando render object we can
// use to simulate character movement
//
SoldierGameObjDef *definition = (SoldierGameObjDef *)DefinitionMgrClass::Find_Typed_Definition ("Commando", CLASSID_GAME_OBJECT_DEF_SOLDIER, false);
if (definition != NULL) {
SoldierGameObj *game_obj = new SoldierGameObj;
game_obj->Init (*definition);
REF_PTR_SET (commando_obj, game_obj->Peek_Model ());
game_obj->Set_Delete_Pending ();
}
if (commando_obj != NULL) {
//
// Attempt to find the collision box for this physics object
//
RenderObjClass *collision_box = NULL;
if (commando_obj->Class_ID () == RenderObjClass::CLASSID_DISTLOD) {
RenderObjClass *lod0 = commando_obj->Get_Sub_Object(0);
collision_box = lod0->Get_Sub_Object_By_Name ("WORLDBOX");
REF_PTR_RELEASE (lod0);
} else {
collision_box = commando_obj->Get_Sub_Object_By_Name ("WORLDBOX");
}
//
// Store the exents of the collision box for use in our simulation
//
if (collision_box != NULL) {
const AABoxClass &box = collision_box->Get_Bounding_Box ();
m_SimBoundingBox = box.Extent;
m_SimBoundingBox.Z = (box.Extent.Z * 2);
m_SimBoxExtents = m_SimBoundingBox * 0.5F;
m_StepHeight = 0.25F;
REF_PTR_RELEASE (collision_box);
}
//
// Build an array of simulation information (specific to this
// physics object).
//
m_DirInfo = new SimDirInfoClass[DIR_MAX];
for (int index = 0; index < DIR_MAX; index ++) {
m_DirInfo[index] = DIR_INFO[index];
m_DirInfo[index].move.X *= m_SimBoundingBox.X;
m_DirInfo[index].move.Y *= m_SimBoundingBox.Y;
m_DirInfo[index].move.Z *= m_SimBoundingBox.Z;
m_DirInfo[index].quad_move.X *= m_SimBoundingBox.X;
m_DirInfo[index].quad_move.Y *= m_SimBoundingBox.Y;
m_DirInfo[index].quad_move.Z *= m_SimBoundingBox.Z;
m_DirInfo[index].speed = m_DirInfo[index].move.Length ();
}
REF_PTR_RELEASE (commando_obj);
//
// Configure the body box culling system
//
Vector3 lev_min;
Vector3 lev_max;
PhysicsSceneClass::Get_Instance ()->Get_Level_Extents (lev_min, lev_max);
m_BodyBoxCullingSystem.Initialize (m_SimBoxExtents, lev_min, lev_max);
//
// Setup the simulation constants
//
m_SimMovement = Vector3 (0, 0, -(ONE_SEC_FALL_DIST + (m_SimBoundingBox.Z * 0.75F)));
m_SimSweepBox.Extent = m_SimBoxExtents;
}
Detect_Level_Features ();
/*AABoxClass collision_box;
collision_box.Center.Set (0, 0, 0);
collision_box.Extent = m_SimBoxExtents;
_PhysSimObj->Set_Collision_Box (collision_box);*/
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// ~PathfindSectorBuilderClass
//
//////////////////////////////////////////////////////////////////////////
PathfindSectorBuilderClass::~PathfindSectorBuilderClass (void)
{
/*if (_GameSimObj != NULL) {
_GameSimObj->Destroy ();
_GameSimObj = NULL;
}*/
if (m_DirInfo != NULL) {
delete [] m_DirInfo;
m_DirInfo = NULL;
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Prepare_Level
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Prepare_Level (void)
{
::Get_Scene_Editor ()->Display_Static_Anim_Phys (true);
//
// Get the list of all static objects from the physics scene
//
RefPhysListIterator iterator = ::Get_Scene_Editor ()->Get_Static_Object_Iterator ();
for (iterator.First (); !iterator.Is_Done (); iterator.Next ()) {
//
// Is this object a static anim phys?
//
PhysClass *phys_obj = iterator.Peek_Obj ();
StaticAnimPhysClass *static_phys_obj = phys_obj->As_StaticAnimPhysClass ();
if (static_phys_obj != NULL) {
//
// Should we disable collisions with this object during pathfind?
//
StaticAnimPhysDefClass *definition = static_phys_obj->Get_StaticAnimPhysDef ();
if (definition->Does_Collide_In_Pathfind () == false) {
phys_obj->Inc_Ignore_Counter ();
} else {
while (phys_obj->Is_Ignore_Me ()) {
phys_obj->Dec_Ignore_Counter ();
}
}
}
}
//
// Make sure that tile's use collision group 15...
//
for ( NodeClass *node = NodeMgrClass::Get_First (NODE_TYPE_TILE);
node != NULL;
node = NodeMgrClass::Get_Next (node, NODE_TYPE_TILE))
{
PhysClass *phys_obj = node->Peek_Physics_Obj ();
if (phys_obj != NULL) {
phys_obj->Set_Collision_Group (15);
}
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Restore_Level
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Restore_Level (void)
{
//
// Restore each tile's collision group...
//
for ( NodeClass *node = NodeMgrClass::Get_First (NODE_TYPE_TILE);
node != NULL;
node = NodeMgrClass::Get_Next (node, NODE_TYPE_TILE))
{
PhysClass *phys_obj = node->Peek_Physics_Obj ();
if (phys_obj != NULL) {
phys_obj->Set_Collision_Group (EDITOR_COLLISION_GROUP);
}
}
//
// Get the list of all static objects from the physics scene
//
RefPhysListIterator iterator = ::Get_Scene_Editor ()->Get_Static_Object_Iterator ();
for (iterator.First (); !iterator.Is_Done (); iterator.Next ()) {
//
// Is this object a static anim phys?
//
PhysClass *phys_obj = iterator.Peek_Obj ();
StaticAnimPhysClass *static_phys_obj = phys_obj->As_StaticAnimPhysClass ();
if (static_phys_obj != NULL) {
//
// Do we need to re-enable collisions with this object?
//
StaticAnimPhysDefClass *definition = static_phys_obj->Get_StaticAnimPhysDef ();
if (definition->Does_Collide_In_Pathfind () == false) {
phys_obj->Dec_Ignore_Counter ();
}
}
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Initialize
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Initialize (void)
{
Prepare_Level ();
//
// Turn off sector display
//
PathfindClass::Get_Instance ()->Display_Sectors (false);
PathfindClass::Get_Instance ()->Display_Portals (false);
//
// Initialize the dynamic vector array's so they will resize
// in appropriate size steps (to decrease the total number of resizes)
//
m_FloodFillProcessList.Set_Growth_Step (20000);
m_PossiblePortalList.Set_Growth_Step (20000);
m_BodyBoxReleaseList.Set_Growth_Step (100000);
//
// Make a guess at the total number of boxes in the world based on
// its size
//
Vector3 lev_min;
Vector3 lev_max;
PhysicsSceneClass::Get_Instance ()->Get_Level_Extents (lev_min, lev_max);
int width = (lev_max.X - lev_min.X) / m_SimBoundingBox.X;
int height = (lev_max.Y - lev_min.Y) / m_SimBoundingBox.Y;
m_TotalBoxGuess = width * height;
//
// Show some UI
//
Show_Dialog ();
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Shutdown
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Shutdown (void)
{
//
// Do some cleanup
//
Free_Floodfill_Boxes ();
Cleanup_Level_Features ();
//
// Make sure we re-partition the sector culling system so
// it does us some good... :)
//
PathfindClass::Get_Instance ()->Re_Partition_Sector_Tree ();
//
// Shutdown the UI and restore any level objects we modified
//
Close_Dialog ();
Restore_Level ();
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Compress_Sectors_For_Dyna_Culling
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Compress_Sectors_For_Dyna_Culling (void)
{
const float MAX_DYNAMIC_VIS_CELL_DIMENSION = 20.0f;
//
// Change the dialog's checkmark so the user knows we are comprssing sectors
//
m_pDialog->Set_State(GeneratingPathfindDialogClass::STATE_COMPRESS);
//
// Floodfill the level and compress the floodfill into sectors
//
DynamicVectorClass sectors;
Set_Max_Sector_Size(MAX_DYNAMIC_VIS_CELL_DIMENSION);
Compress_Sectors(§ors);
//
// Hand the sectors into the scene (NOTE: this will have to reset the
// VIS system)
//
PhysicsSceneClass::Get_Instance()->Re_Partition_Dynamic_Culling_System(sectors);
return;
}
//////////////////////////////////////////////////////////////////////////
//
// Compress_Sectors_For_Pathfind
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Compress_Sectors_For_Pathfind (void)
{
//
// Discard any previously generated data
//
PathfindClass::Get_Instance ()->Reset_Sectors ();
PathfindClass::Get_Instance ()->Reset_Portals ();
//
// Change the dialog's checkmark so the user knows we are comprssing sectors
//
m_pDialog->Set_State (GeneratingPathfindDialogClass::STATE_COMPRESS);
//
// Compress the sectors into the largest possible rectangular regions
//
DWORD before_ticks = ::GetTickCount ();
Post_Process_Floodfill_For_Level_Features ();
Compress_Sectors ();
Generate_Portals ();
DWORD after_ticks = ::GetTickCount ();
WWDEBUG_SAY(("Time spent compressing: %d secs.\r\n", (after_ticks-before_ticks)/1000));
//
// Loop through the level and create any portals around
// ladders, doors, etc that may be needed.
//
Apply_Level_Features ();
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Generate_Sectors
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Generate_Sectors (void)
{
//
// Start floodfilling from each of the start points
//
for (int index = 0; index < m_StartPointList.Count (); index ++) {
Vector3 start_pos = m_StartPointList[index];
//
// Normalize the starting position. We do this so that all the different
// generation points will match up perfectly.
//
start_pos.X = (int(start_pos.X / m_SimBoundingBox.X)) * m_SimBoundingBox.X;
start_pos.Y = (int(start_pos.Y / m_SimBoundingBox.Y)) * m_SimBoundingBox.Y;
start_pos.Z += (m_SimBoundingBox.Z * 0.5F);
//
// Start floodfilling from this position
//
AABoxClass new_box;
if (Try_Standing_Here (start_pos, &new_box)) {
m_CurrentSector = Mark_Sector (new_box);
Floodfill (start_pos);
}
}
//
// Process all the floodfill boxes that have been queued up
//
int compress_count = 0;
while (m_FloodFillProcessList.Count () > 0) {
//
// Pop a floodfill box off the list and process its neighbors
//
m_CurrentSector = m_FloodFillProcessList[0];
m_FloodFillProcessList.Delete (0);
AABoxClass box = Get_Body_Box_Bounds (m_CurrentSector);
Vector3 pos = box.Center;
pos.Z = box.Center.Z - box.Extent.Z + (m_SimBoundingBox.Z * 0.5F);
Floodfill (pos);
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Find_Ground
//
//////////////////////////////////////////////////////////////////////////
bool
PathfindSectorBuilderClass::Find_Ground (const Vector3 &pos, float *ground_pos)
{
bool retval = false;
AABoxClass sweep_box;
sweep_box.Center = pos;
sweep_box.Center.Z += m_StepHeight;
sweep_box.Extent = m_SimBoxExtents;
sweep_box.Extent.Z = 0.1F;
//
// Sweep a very short box downwards to see where the ground is
//
CastResultStruct result;
Vector3 sweep_vector (0, 0, -6.5F);
PhysAABoxCollisionTestClass test( sweep_box,
sweep_vector,
&result,
STATIC_OBJ_COLLISION_GROUP,
COLLISION_TYPE_PHYSICAL);
PhysicsSceneClass::Get_Instance ()->Cast_AABox (test);
//
// Check to see if we found a floor, and its valid to stand on.
//
if ( (result.StartBad == false) &&
(result.Fraction < 1.0F) &&
(result.Normal.Z > 0.71F) &&
(m_AllowWaterFloodfill || (result.SurfaceType != SURFACE_TYPE_WATER)))
{
//
// Calculate what z-position the ground is
//
(*ground_pos) = (sweep_box.Center.Z + (sweep_vector.Z * result.Fraction)) - sweep_box.Extent.Z;
retval = true;
}
return retval;
}
//////////////////////////////////////////////////////////////////////////
//
// Find_Ceiling
//
//////////////////////////////////////////////////////////////////////////
bool
PathfindSectorBuilderClass::Find_Ceiling (const Vector3 &pos, float *ceiling_pos)
{
bool retval = false;
AABoxClass sweep_box;
sweep_box.Center = pos;
sweep_box.Center.Z += m_StepHeight;
sweep_box.Extent = m_SimBoxExtents;
sweep_box.Extent.Z = 0.1F;
//
// Sweep a very short box downwards to see where the ground is
//
CastResultStruct result;
Vector3 sweep_vector (0, 0, 6.5F);
PhysAABoxCollisionTestClass test( sweep_box,
sweep_vector,
&result,
STATIC_OBJ_COLLISION_GROUP,
COLLISION_TYPE_PHYSICAL);
PhysicsSceneClass::Get_Instance ()->Cast_AABox (test);
//
// Check to ensure we didn't start the cast intersecting a poly
//
if (result.StartBad == false) {
//
// Calculate what the z-position of the ceiling is
//
(*ceiling_pos) = (sweep_box.Center.Z + (sweep_vector.Z * result.Fraction)) + sweep_box.Extent.Z;
retval = true;
}
return retval;
}
//////////////////////////////////////////////////////////////////////////
//
// Try_Moving_Here
//
//////////////////////////////////////////////////////////////////////////
bool
PathfindSectorBuilderClass::Try_Moving_Here
(
const Vector3 & start_pos,
const Vector3 & expected_pos,
AABoxClass * real_pos
)
{
bool is_valid = false;
float start_ground_pos = start_pos.Z - m_SimBoxExtents.Z;
float curr_ground_pos = 0;
//
// Find the ground level where we were standing and the ground level where
// we want to be standing
//
if (Find_Ground (expected_pos, &curr_ground_pos)) {
//
// Check to see if the character can step from the old position to the new one
//
float step_height = curr_ground_pos - start_ground_pos;
if (step_height < m_StepHeight) {
//
// Find the ceiling
//
float curr_ceiling_pos = curr_ground_pos;
Find_Ceiling (expected_pos, &curr_ceiling_pos);
//
// Can the character fit between the floor and ceiling without crouching?
//
if ((curr_ceiling_pos - curr_ground_pos) > m_SimBoundingBox.Z) {
//
// Success! Build a bounding box for the new position
//
real_pos->Extent.X = m_SimBoxExtents.X;
real_pos->Extent.Y = m_SimBoxExtents.Y;
real_pos->Extent.Z = m_SimBoxExtents.Z;
real_pos->Center.X = expected_pos.X;
real_pos->Center.Y = expected_pos.Y;
real_pos->Center.Z = curr_ground_pos + m_SimBoxExtents.Z + WWMATH_EPSILON;
is_valid = true;
}
}
}
return is_valid;
}
//////////////////////////////////////////////////////////////////////////
//
// Try_Standing_Here
//
//////////////////////////////////////////////////////////////////////////
bool
PathfindSectorBuilderClass::Try_Standing_Here
(
const Vector3 & expected_pos,
AABoxClass * real_pos
)
{
bool is_valid = false;
AABoxClass sweep_box;
sweep_box.Center = expected_pos;
sweep_box.Center.Z += m_StepHeight;
sweep_box.Extent = m_SimSweepBox.Extent;
sweep_box.Extent.Z -= m_StepHeight;
//
// Do a box cast to see if we can 'stand' here.
//
CastResultStruct result;
PhysAABoxCollisionTestClass test( sweep_box,
m_SimMovement,
&result,
STATIC_OBJ_COLLISION_GROUP,
COLLISION_TYPE_PHYSICAL);
test.CheckStaticObjs = true;
test.CheckDynamicObjs = false;
PhysicsSceneClass::Get_Instance ()->Cast_AABox (test);
//
// Is the start of the cast valid and is the polygon we
// landed on flat enough to stand on?
//
if ((result.StartBad == false) && (result.Normal.Z > 0.71F)) {
//
// Are we standing on the ground? Is the ground a valid type?
//
bool on_ground = (result.Fraction < 1.0F);
if (on_ground && (m_AllowWaterFloodfill || (result.SurfaceType != SURFACE_TYPE_WATER))) {
//
// Snap the x and y positions and calculate the z position
// of the new box.
//
real_pos->Extent.X = sweep_box.Extent.X;
real_pos->Extent.Y = sweep_box.Extent.Y;
real_pos->Extent.Z = ((-m_SimMovement.Z * result.Fraction) * 0.5F) + (m_SimBoundingBox.Z * 0.5F);
real_pos->Center.X = expected_pos.X;
real_pos->Center.Y = expected_pos.Y;
real_pos->Center.Z = (sweep_box.Center.Z + (m_SimBoundingBox.Z * 0.5F) - real_pos->Extent.Z) + 0.001F;
is_valid = true;
}
}
return is_valid;
}
//////////////////////////////////////////////////////////////////////////
//
// Do_Physics_Sim
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Do_Physics_Sim
(
const Vector3 & start_pos,
PATHFIND_DIR direction
)
{
//
// Determine where the next cell should be
//
Vector3 expected_pos = start_pos + m_DirInfo[direction].move;
//
// Do a quick-and-dirty test to see if we already 'know' about a
// body-box in the requested direction.
//
bool found = false;
FloodfillBoxClass *neighbor = m_CurrentSector->Peek_Neighbor (direction, false);
if (neighbor != NULL) {
m_SimSweepBox.Center = expected_pos;
//
// If the neighbor's bounding box completely CONTAINS the bounding
// box we would have cast, then we can skip the cast and simply
// mark the direction as 'traversible'
//
AABoxClass bounding_box = Get_Body_Box_Bounds (neighbor);
found = bounding_box.Contains (m_SimSweepBox);
float min1 = bounding_box.Center.Z - bounding_box.Extent.Z;
float max1 = bounding_box.Center.Z + bounding_box.Extent.Z;
float min2 = m_SimSweepBox.Center.Z - m_SimSweepBox.Extent.Z;
float max2 = m_SimSweepBox.Center.Z + m_SimSweepBox.Extent.Z;
found = (min1 <= min2) && (max1 >= max2);
if (found) {
m_CurrentSector->Set_Neighbor (direction, neighbor, true);
}
}
//
// Did the quick-and-dirty check fail? If so, then do the full box-cast
//
if (found == false) {
Vector3 move_vector = (m_DirInfo[direction].move);
Vector3 new_pos = start_pos + move_vector;
AABoxClass new_box;
//if (Try_Standing_Here (new_pos, &new_box)) {
if (Try_Moving_Here (start_pos, new_pos, &new_box)) {
Submit_Box (m_CurrentSector, new_box, direction);
}
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Do_Real_Physics_Sim
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Do_Real_Physics_Sim
(
const Vector3 & start_pos,
PATHFIND_DIR direction
)
{
//
// Determine where the next cell should be
//
Vector3 expected_pos = start_pos + m_DirInfo[direction].move;
//
// Do a quick-and-dirty test to see if we already 'know' about a
// body-box in the requested direction.
//
bool found = false;
FloodfillBoxClass *neighbor = m_CurrentSector->Peek_Neighbor (direction, false);
if (neighbor != NULL) {
m_SimSweepBox.Center = expected_pos;
//
// If the neighbor's bounding box completely CONTAINS the bounding
// box we would have cast, then we can skip the cast and simply
// mark the direction as 'traversible'
//
AABoxClass bounding_box = Get_Body_Box_Bounds (neighbor);
found = bounding_box.Contains (m_SimSweepBox);
float min1 = bounding_box.Center.Z - bounding_box.Extent.Z;
float max1 = bounding_box.Center.Z + bounding_box.Extent.Z;
float min2 = m_SimSweepBox.Center.Z - m_SimSweepBox.Extent.Z;
float max2 = m_SimSweepBox.Center.Z + m_SimSweepBox.Extent.Z;
found = (min1 <= min2) && (max1 >= max2);
if (found) {
m_CurrentSector->Set_Neighbor (direction, neighbor, true);
}
}
//
// Did the quick-and-dirty check fail? If so, then do the full box-cast
//
if (found == false) {
Vector3 move_vector = (m_DirInfo[direction].move);
Vector3 new_pos = start_pos + move_vector;
AABoxClass test_box (start_pos, m_SimBoxExtents);
test_box.Add_Box (AABoxClass (new_pos, m_SimBoxExtents));
test_box.Center.Z += 0.1F;
NonRefPhysListClass obj_list;
PhysicsSceneClass::Get_Instance ()->Collect_Collideable_Objects (test_box, COLLISION_TYPE_PHYSICAL, true, false, &obj_list);
if (obj_list.Count () == 0) {
AABoxClass new_box;
if (Try_Standing_Here (new_pos, &new_box)) {
Submit_Box (m_CurrentSector, new_box, direction);
}
return ;
} else {
bool did_intersect = false;
NonRefPhysListIterator it (&obj_list);
for (it.First(); !it.Is_Done(); it.Next()) {
PhysClass *phys_obj = it.Peek_Obj ();
if (phys_obj != NULL) {
RenderObjClass *model = phys_obj->Peek_Model ();
AABoxIntersectionTestClass int_test (test_box, COLLISION_TYPE_PHYSICAL);
if (model->Intersect_AABox (int_test)) {
did_intersect = true;
break;
}
}
}
if (did_intersect == false) {
AABoxClass new_box;
if (Try_Standing_Here (new_pos, &new_box)) {
Submit_Box (m_CurrentSector, new_box, direction);
}
return ;
}
}
_PhysSimObj->Set_Position (start_pos);
_PhysSimObj->Set_Velocity (Vector3 (0, 0, 0));
for (int attempt = 0; attempt < 20; attempt ++) {
if (_PhysSimObj->Is_In_Contact ()) {
break;
}
_PhysSimObj->Timestep (0.1F);
}
bool keep_going = true;
for (attempt = 0; keep_going && (attempt < 20); attempt ++) {
Vector3 curr_pos = _PhysSimObj->Get_Position ();
Vector3 delta = (new_pos - curr_pos);
delta.Z = 0;
float delta_len = delta.Length ();
if (delta_len < 0.05F && _PhysSimObj->Is_In_Contact ()) {
AABoxClass new_box;
new_box.Center = new_pos;
new_box.Center.Z = curr_pos.Z;
new_box.Extent = m_SimBoxExtents;
Submit_Box (m_CurrentSector, new_box, direction);
keep_going = false;
} else {
Vector3 x_axis = (new_pos - curr_pos);
Vector3 z_axis = Vector3 (0, 0, 1);
x_axis.Normalize ();
Vector3 y_axis = Vector3::Cross_Product (x_axis, z_axis);
Matrix3D new_tm (x_axis, y_axis, z_axis, curr_pos);
_PhysSimObj->Set_Transform (new_tm);
_PhysSimObj->Get_Controller ()->Reset ();
_PhysSimObj->Get_Controller ()->Set_Move_Forward (0.09F);
_PhysSimObj->Timestep (0.075F);
}
}
/*AABoxClass new_box;
if (Try_Standing_Here (new_pos, &new_box)) {
Submit_Box (m_CurrentSector, new_box, direction);
}*/
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Submit_Box
//
//////////////////////////////////////////////////////////////////////////
FloodfillBoxClass *
PathfindSectorBuilderClass::Submit_Box
(
FloodfillBoxClass * from_obj,
const AABoxClass & new_box,
PATHFIND_DIR direction
)
{
//
// Is this cell already marked?
//
Vector3 position = new_box.Center;
position.Z = new_box.Center.Z - new_box.Extent.Z + (m_SimBoundingBox.Z * 0.5F);
FloodfillBoxClass *occupant = Get_Sector_Occupant (position);
if (occupant == NULL) {
//
// Mark this cell and add it to the list of sectors
// that need to be recursed.
//
occupant = Mark_Sector (new_box);
m_FloodFillProcessList.Add (occupant);
//
// Let the new occupant know where it came from (even if it can't get there itself).
//
occupant->Set_Neighbor (::Inverse_Pathfind_Dir (direction), from_obj, false);
m_TotalBoxCount ++;
}
//
// Let the sector know who its new neighbor is
//
if (occupant != from_obj) {
from_obj->Set_Neighbor (direction, occupant, true);
}
return occupant;
}
//////////////////////////////////////////////////////////////////////////
//
// Floodfill
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Floodfill (const Vector3 &start_pos)
{
//
// Do a simulation in each of the four directions from the
// current cell.
//
if (m_pDialog->Was_Cancelled () == false) {
//
// Loop through and check any neighbors we don't already know about
//
for (int index = 0; index < DIR_MAX; index ++) {
if (m_CurrentSector->Peek_Neighbor (PATHFIND_DIR(index)) == NULL) {
Do_Physics_Sim (start_pos, PATHFIND_DIR(index));
m_BeforeUpdateCount ++;
}
}
//
// Check to see if we need to climb up any ladders, open doors, etc...
//
Check_For_Level_Feature (m_CurrentSector);
//
// Let the current sector 'know' its been completely processed
//
m_CurrentSector->Needs_Processing (false);
//
// Update the UI
//
if (m_BeforeUpdateCount > 512) {
CString message;
message.Format ("Floodfilled %d boxes. Approx total boxes: %d", m_TotalBoxCount, m_TotalBoxGuess);
m_pDialog->Set_Status (message, float (m_TotalBoxCount) / float (m_TotalBoxGuess));
m_BeforeUpdateCount = 0;
}
}
//
// Allow windows messages to be processed
//
static int message_pump = 0;
message_pump++;
if (message_pump > 5000) {
General_Pump_Messages ();
message_pump = 0;
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Get_Sector_Occupant
//
//////////////////////////////////////////////////////////////////////////
FloodfillBoxClass *
PathfindSectorBuilderClass::Get_Sector_Occupant (const Vector3 &pos)
{
//
// If we found any objects in the culling system, then the sector is occupied
//
return m_BodyBoxCullingSystem.Find_Box (pos);
}
//////////////////////////////////////////////////////////////////////////
//
// Mark_Sector
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Mark_Sector (FloodfillBoxClass *body_box)
{
//
// Add the culling object to our culling system. (This
// effectively marks the cell as 'occupied').
//
body_box->Add_Ref ();
m_BodyBoxCullingSystem.Add_Box (body_box);
FloodfillBoxClass::Add (body_box);
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Mark_Sector
//
//////////////////////////////////////////////////////////////////////////
FloodfillBoxClass *
PathfindSectorBuilderClass::Mark_Sector (const AABoxClass &bounding_box)
{
//
// Create a culling system object to represent this 'sector' and
// add it to our AABTree culling system. (This effectively marks
// the cell as 'occupied').
//
FloodfillBoxClass *body_box = new FloodfillBoxClass;
body_box->Set_Position (bounding_box.Center);
Mark_Sector (body_box);
body_box->Release_Ref ();
return body_box;
}
///////////////////////////////////////////////////////////////////////////
//
// Determine_Height
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Determine_Height
(
FloodfillBoxClass * start_box,
float * min_z_pos,
float * max_z_pos
)
{
AABoxClass box = Get_Body_Box_Bounds (start_box);
float z_extent = box.Extent.Z;
box.Extent.X -= WWMATH_EPSILON;
box.Extent.Y -= WWMATH_EPSILON;
box.Extent.Z = 500.0F;
//
// Loop over all the body-boxes that exist above or below the starting box
//
m_BodyBoxCullingSystem.Collect_Boxes (box);
DynamicVectorClass &list = m_BodyBoxCullingSystem.Get_Collection_List ();
for (int index = 0; index < list.Count (); index ++) {
FloodfillBoxClass *body_box = list[index];
//
// Only check 'other' boxes
//
if (body_box != start_box) {
AABoxClass curr_box = Get_Body_Box_Bounds (body_box);
//
// Determine the min and max z-positions of the current box
//
float curr_min_z = curr_box.Center.Z - (curr_box.Extent.Z + WWMATH_EPSILON);
float curr_max_z = curr_box.Center.Z + (curr_box.Extent.Z + WWMATH_EPSILON);
//
// Return new minimum and maximum
//
if (curr_max_z < box.Center.Z && curr_max_z > (*min_z_pos)) {
(*min_z_pos) = curr_max_z;
}
if (curr_min_z > box.Center.Z && curr_min_z < (*max_z_pos)) {
(*max_z_pos) = curr_min_z;
}
}
}
/*float delta_up = (*max_z_pos) - box.Center.Z;
float delta_down = box.Center.Z - (*min_z_pos);
delta_up = max (delta_up / 2.0F, (z_extent + WWMATH_EPSILON));
delta_down = max (delta_down / 2.0F, (z_extent + WWMATH_EPSILON));
(*max_z_pos) = box.Center.Z + delta_up;
(*min_z_pos) = box.Center.Z - delta_down;*/
//
// Make sure a box's min position is at least the
// bottom of its box.
//
float box_bottom = (box.Center.Z - z_extent);
if ((*min_z_pos) > (box_bottom - 0.5F)) {
(*min_z_pos) = (box_bottom - 0.5F);
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Build_Height_Values
//
//////////////////////////////////////////////////////////////////////////
int
PathfindSectorBuilderClass::Build_Height_Values (void)
{
int before_ticks = ::GetTickCount ();
int total_box_count = 0;
int box_count = 0;
//
// Backup the body-box list to ensure we delete them all...
//
for ( FloodfillBoxClass *body_box = FloodfillBoxClass::Get_First ();
body_box != NULL;
body_box = body_box->Get_Next ())
{
m_BodyBoxReleaseList.Add (body_box);
Vector3 pos = body_box->Get_Position ();
float min_z = pos.Z - (m_SimBoundingBox.Z * 500.0F);
float max_z = pos.Z + (m_SimBoundingBox.Z * 500.0F);
Determine_Height (body_box, &min_z, &max_z);
body_box->Set_Min_Z_Pos (min_z);
body_box->Set_Max_Z_Pos (max_z);
total_box_count ++;
}
int after_ticks = ::GetTickCount ();
WWDEBUG_SAY(("Time spent generating z-values: %d secs.\r\n", (after_ticks-before_ticks)/1000));
return total_box_count;
}
//////////////////////////////////////////////////////////////////////////
//
// Can_Traverse
//
//////////////////////////////////////////////////////////////////////////
inline bool
Can_Traverse (FloodfillBoxClass *cell, PATHFIND_DIR dir)
{
//
// Make sure the cell passes the basic 'traverse-requirements'
// to move in the given direction
//
return ( cell != NULL &&
cell->Needs_Processing () == false &&
cell->Is_Taken () == false);
}
//////////////////////////////////////////////////////////////////////////
//
// Check_Directions
//
//////////////////////////////////////////////////////////////////////////
inline bool
Check_Directions (FloodfillBoxClass *cell, int dir_mask)
{
bool is_valid = true;
//
// Check to make sure we can walk from the cell to its
// adjacent boxes (Only checking the requested directions).
//
for (int mask = 1; mask < MASK_MAX; mask <<= 1) {
if (dir_mask & mask) {
PATHFIND_DIR check_dir = ::Mask_to_Dir (DIRECTION_MASK(mask));
is_valid &= cell->Is_Two_Way_Traversible (check_dir);
}
}
return is_valid;
}
//////////////////////////////////////////////////////////////////////////
//
// Move_Dir
//
//////////////////////////////////////////////////////////////////////////
inline FloodfillBoxClass *
PathfindSectorBuilderClass::Move_Dir (FloodfillBoxClass *start_box, PATHFIND_DIR dir, int dir_mask)
{
//
// Peek a the cell in the given direction
//
FloodfillBoxClass *retval = NULL;
FloodfillBoxClass *new_cell = start_box->Peek_Neighbor (dir);
//
// Does this cell pass our traversal requirements?
//
if ( start_box->Is_Two_Way_Traversible (dir) &&
Can_Traverse (new_cell, dir) &&
Check_Directions (new_cell, dir_mask))
{
//
// Add this cell's min and max heights to the height-watcher.
// This is done so we can break the sector before it intersects
// a sector above or below it
//
m_HeightWatcher.Add_Lower_Bound (new_cell->Get_Min_Z_Pos ());
m_HeightWatcher.Add_Upper_Bound (new_cell->Get_Max_Z_Pos ());
//
// Is this cell within the min and max height values?
//
AABoxClass box = Get_Body_Box_Bounds (new_cell);
if ( m_HeightWatcher.Is_Current_Pos_Valid (box.Center.Z - box.Extent.Z) &&
m_HeightWatcher.Is_Current_Pos_Valid (box.Center.Z + box.Extent.Z))
{
retval = new_cell;
}
}
return retval;
}
//////////////////////////////////////////////////////////////////////////
//
// Check_Edge
//
//////////////////////////////////////////////////////////////////////////
inline bool
PathfindSectorBuilderClass::Check_Edge
(
FloodfillBoxClass * start_box,
int count_left,
int count_right,
int count_up,
int count_down,
PATHFIND_DIR move_dir
)
{
bool retval = false;
//
// Check the first cell, can we move in the requested direction?
//
int dir_mask = 0;
dir_mask |= (count_left > 0) ? MASK_LEFT : 0;
dir_mask |= (count_right > 0) ? MASK_RIGHT : 0;
dir_mask |= (count_up > 0) ? MASK_UP : 0;
dir_mask |= (count_down > 0) ? MASK_DOWN : 0;
if (Move_Dir (start_box, move_dir, dir_mask) != NULL) {
retval = true;
}
//
// Check the given number of cells in the left direction
//
FloodfillBoxClass *curr_cell = start_box;
for (int x = 0; retval && x < count_left; x++) {
//
// Can we move one step in this direction?
//
curr_cell = Move_Dir (curr_cell, DIR_LEFT, 0);
if (curr_cell != NULL) {
//
// Can this new cell move in the movement direction AND
// can its new cell move right and, if necessary, left?
//
dir_mask = MASK_RIGHT;
dir_mask |= ((x + 1) < count_left) ? MASK_LEFT : 0;
retval = (Move_Dir (curr_cell, move_dir, dir_mask) != NULL);
} else {
retval = false;
}
}
//
// Check the given number of cells in the left direction
//
curr_cell = start_box;
for (x = 0; retval && x < count_right; x++) {
//
// Can we move one step in this direction?
//
curr_cell = Move_Dir (curr_cell, DIR_RIGHT, 0);
if (curr_cell != NULL) {
//
// Can this new cell move in the movement direction AND
// can its new cell move left and, if necessary, right?
//
dir_mask = MASK_LEFT;
dir_mask |= ((x + 1) < count_right) ? MASK_RIGHT : 0;
retval = (Move_Dir (curr_cell, move_dir, dir_mask) != NULL);
} else {
retval = false;
}
}
//
// Check the given number of cells in the up direction
//
curr_cell = start_box;
for (int y = 0; retval && y < count_up; y++) {
//
// Can we move one step in this direction?
//
curr_cell = Move_Dir (curr_cell, DIR_UP, 0);
if (curr_cell != NULL) {
//
// Can this new cell move in the movement direction AND
// can its new cell move down and, if necessary, up?
//
dir_mask = MASK_DOWN;
dir_mask |= ((y + 1) < count_up) ? MASK_UP : 0;
retval = (Move_Dir (curr_cell, move_dir, dir_mask) != NULL);
} else {
retval = false;
}
}
//
// Check the given number of cells in the down direction
//
curr_cell = start_box;
for (y = 0; retval && y < count_down; y++) {
//
// Can we move one step in this direction?
//
curr_cell = Move_Dir (curr_cell, DIR_DOWN, 0);
if (curr_cell != NULL) {
//
// Can this new cell move in the movement direction AND
// can its new cell move up and, if necessary, down?
//
dir_mask = MASK_UP;
dir_mask |= ((y + 1) < count_down) ? MASK_DOWN : 0;
retval = (Move_Dir (curr_cell, move_dir, dir_mask) != NULL);
} else {
retval = false;
}
}
return retval;
}
//////////////////////////////////////////////////////////////////////////
//
// Find_Perimeter
//
//////////////////////////////////////////////////////////////////////////
FloodfillBoxClass *
PathfindSectorBuilderClass::Find_Perimeter (FloodfillBoxClass *start_box, BOX_PERIMETER *perimeter)
{
FloodfillBoxClass *up_cell = start_box;
FloodfillBoxClass *down_cell = start_box;
FloodfillBoxClass *left_cell = start_box;
FloodfillBoxClass *right_cell = start_box;
//
// Determine what the maximum number of cells in a given direction can be
//
int max_dim = m_MaxSectorDim / max (m_SimBoundingBox.X, m_SimBoundingBox.Y);
//
// Create an object that will allow us to break the sector if
// it would intersect with a sector above or below us.
//
Vector3 pos = start_box->Get_Position ();
m_HeightWatcher.Initialize (pos.Z - (m_SimBoundingBox.Z * 500.0F), pos.Z + (m_SimBoundingBox.Z * 500.0F), pos.Z);
do
{
//
// Expand the box 'up' one row (if possible)
//
if (perimeter->stop_up == false) {
perimeter->stop_up = true;
FloodfillBoxClass *new_cell = Move_Dir (up_cell, DIR_UP, 0);
if (new_cell != NULL) {
if (Check_Edge (up_cell, perimeter->count_left, perimeter->count_right, 0, 0, DIR_UP)) {
up_cell = new_cell;
perimeter->count_up ++;
perimeter->stop_up = false;
}
}
}
//
// Expand the box 'down' one row (if possible)
//
if (perimeter->stop_down == false) {
perimeter->stop_down = true;
FloodfillBoxClass *new_cell = Move_Dir (down_cell, DIR_DOWN, 0);
if (new_cell != NULL) {
if (Check_Edge (down_cell, perimeter->count_left, perimeter->count_right, 0, 0, DIR_DOWN)) {
down_cell = new_cell;
perimeter->count_down ++;
perimeter->stop_down = false;
}
}
}
//
// Expand the box 'left' one column (if possible)
//
if (perimeter->stop_left == false) {
perimeter->stop_left = true;
FloodfillBoxClass *new_cell = Move_Dir (left_cell, DIR_LEFT, 0);
if (new_cell != NULL) {
if (Check_Edge (left_cell, 0, 0, perimeter->count_up, perimeter->count_down, DIR_LEFT)) {
left_cell = new_cell;
perimeter->count_left ++;
perimeter->stop_left = false;
}
}
}
//
// Expand the box 'right' one column (if possible)
//
if (perimeter->stop_right == false) {
perimeter->stop_right = true;
FloodfillBoxClass *new_cell = Move_Dir (right_cell, DIR_RIGHT, 0);
if (new_cell != NULL) {
if (Check_Edge (right_cell, 0, 0, perimeter->count_up, perimeter->count_down, DIR_RIGHT)) {
right_cell = new_cell;
perimeter->count_right ++;
perimeter->stop_right = false;
}
}
}
//
// Check to see if we are going to exceed the maximum sector size in either
// direction.
//
if (perimeter->count_left + perimeter->count_right >= max_dim) {
perimeter->stop_left = true;
perimeter->stop_right = true;
}
if (perimeter->count_up + perimeter->count_down >= max_dim) {
perimeter->stop_up = true;
perimeter->stop_down = true;
}
}
while ( perimeter->stop_up == false || perimeter->stop_down == false ||
perimeter->stop_left == false || perimeter->stop_right == false);
//
// Some debug checking to make sure we built the region
// correctly.
//
FloodfillBoxClass *upper_left1 = up_cell;
FloodfillBoxClass *upper_left2 = left_cell;
for (int index = 0; index < perimeter->count_left; index ++) {
upper_left1 = upper_left1->Peek_Neighbor (DIR_LEFT);
}
for (index = 0; index < perimeter->count_up; index ++) {
upper_left2 = upper_left2->Peek_Neighbor (DIR_UP);
}
WWASSERT (upper_left1 == upper_left2);
if (upper_left1 != upper_left2) {
CString message;
message.Format ("upper_left1 = %d\nupper_left2 = %d\nup_cell = %d\nleft_cell = %d", upper_left1, upper_left2, up_cell, left_cell);
::MessageBox (NULL, message, "Info", MB_OK);
}
return upper_left1;
}
//////////////////////////////////////////////////////////////////////////
//
// Compress_Sectors
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Compress_Sectors (DynamicVectorClass *box_list)
{
//
// Generate a set of maximum and minimum height values
// for each box
//
int total_box_count = Build_Height_Values ();
int box_count = 0;
bool keep_going = true;
FloodfillBoxClass *start_box = NULL;
FloodfillBoxClass *old_start_box = NULL;
BOX_PERIMETER old_perimeter = { 0 };
//
// Loop over all the boxes and compress them into rectangular regions
//
while (keep_going && ((start_box = FloodfillBoxClass::Get_First ()) != NULL)) {
//
// Don't compress any boxes that still need processing
//
if (start_box->Needs_Processing ()) {
start_box->Remove ();
continue;
}
//
// Perform a simple check to make sure we don't keep getting the same
// box off the top of the list (this should never, ever, ever, happen).
//
if ( (start_box == old_start_box) &&
(FloodfillBoxClass::Get_First () != FloodfillBoxClass::Get_Last ()))
{
::MessageBox (::AfxGetMainWnd ()->m_hWnd, "Found the same box twice...", "Compression Error", MB_OK | MB_ICONERROR);
keep_going = false;
}
old_start_box = start_box;
//
// Find the largest rectangular region that this box can be part of
//
BOX_PERIMETER perimeter = { 0 };
FloodfillBoxClass *upper_left_cell = Find_Perimeter (start_box, &perimeter);
old_perimeter = perimeter;
//
// How big is the new rectangular region?
//
int width = (perimeter.count_left + perimeter.count_right) + 1;
int height = (perimeter.count_up + perimeter.count_down) + 1;
//
// If the area is of an exceptable size, then compress it into a sector
//
if (width > 2 || height > 2) {
int skipped_count = start_box->Get_Compress_Skipped_Count ();
int min_dim = min (width, height);
//
// Should we skip this box in hopes that we find a better sector later?
//
if (skipped_count <= (12 - min_dim)) {
start_box->Inc_Compress_Skipped_Count ();
start_box->Remove ();
FloodfillBoxClass::Add (start_box);
} else {
//
// Compress the region into a new pathfinding sector
//
PathfindSectorClass *sector = Build_Sector (upper_left_cell, width, height);
if (sector != NULL) {
//
// Sumbit this sector
//
if (box_list != NULL) {
AABoxClass bbox = sector->Get_Bounding_Box ();
box_list->Add (bbox);
MEMBER_RELEASE (sector);
} else {
PathfindClass::Get_Instance ()->Add_Sector (sector);
}
}
//
// Update the UI
//
box_count += (width * height);
CString message;
message.Format ("Compressed %d of %d boxes.", box_count, total_box_count);
m_pDialog->Set_Status (message, ((float)box_count) / ((float)total_box_count));
}
} else {
//
// Sector is too small, so remove the box
// from the system.
//
start_box->Set_Taken ();
start_box->Remove ();
}
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Filter_Useless_Sectors
//
//////////////////////////////////////////////////////////////////////////
/*void
PathfindSectorBuilderClass::Filter_Useless_Sectors (DynamicVectorClass §or_list)
{
DynamicVectorClass final_sector_list;
for (int index = 0; index < sector_list.Count (); index ++) {
PathfindSectorClass *sector = sector_list[index];
bool found_usefull_portal = false;
int portal_count = sector->Get_Portal_Count ();
for (int portal_index = 0; portal_index < portal_count; portal_index ++) {
}
if (found_usefull_portal) {
final_sector_list.Add (sector);
}
}
//
// Add all the sectors to the pathfind system
//
for (index = 0; index < final_sector_list.Count (); index ++) {
}
return ;
}*/
//////////////////////////////////////////////////////////////////////////
//
// Scan_Edge
//
//////////////////////////////////////////////////////////////////////////
void
Scan_Edge
(
FloodfillBoxClass * start_obj,
int cell_count,
PATHFIND_DIR check_dir,
PATHFIND_DIR move_dir,
int * best_count
)
{
FloodfillBoxClass * best_first_cell = 0;
FloodfillBoxClass * first_cell = NULL;
int count = 0;
//
// Go along the edge
//
FloodfillBoxClass *box_obj = start_obj;
for (int box_index = 0; box_index < cell_count; box_index ++) {
//
// Can we traverse to the left and back?
//
if (box_obj->Is_Two_Way_Traversible (check_dir)) {
//
// Start recording this run
//
if (first_cell == NULL) {
first_cell = box_obj;
count = 1;
} else {
count ++;
}
} else {
//
// Is this the best run we've found?
//
if (count > (*best_count)) {
best_first_cell = first_cell;
(*best_count) = count;
}
//
// Reset
//
first_cell = NULL;
count = 0;
}
//
// Move to the next edge cell
//
box_obj = box_obj->Peek_Neighbor (move_dir);
}
//
// Is this the best run we've found?
//
if (count > (*best_count)) {
best_first_cell = first_cell;
(*best_count) = count;
}
return ;
}
//////////////////////////////////////////////////////////////////////////
//
// Is_Valid_Sector
//
//////////////////////////////////////////////////////////////////////////
bool
PathfindSectorBuilderClass::Is_Valid_Sector
(
FloodfillBoxClass ** upper_left_ptr,
int & cells_right,
int & cells_down
)
{
bool retval = true;
//
// Is this sector to small?
//
if (cells_right < 3 || cells_down < 3) {
retval = false;
if (cells_right < 3) {
FloodfillBoxClass *ul_ptr = (*upper_left_ptr);
FloodfillBoxClass *ur_ptr = (*upper_left_ptr)->Find_Relative (cells_right - 1, 0);
//
// Determine if either edge can enter an adjacent sector. This
// would make the sector walkable
//
int best_count = 0;
Scan_Edge (ul_ptr, cells_down, DIR_LEFT, DIR_DOWN, &best_count);
Scan_Edge (ur_ptr, cells_down, DIR_RIGHT, DIR_DOWN, &best_count);
//
// Was this run good enough?
//
retval = (best_count >= 3);
} else {
FloodfillBoxClass *ul_ptr = (*upper_left_ptr);
FloodfillBoxClass *ll_ptr = (*upper_left_ptr)->Find_Relative (0, cells_down - 1);
//
// Determine if either edge can enter an adjacent sector. This
// would make the sector walkable
//
int best_count = 0;
Scan_Edge (ul_ptr, cells_right, DIR_UP, DIR_RIGHT, &best_count);
Scan_Edge (ll_ptr, cells_right, DIR_DOWN, DIR_RIGHT, &best_count);
//
// Was this run good enough?
//
retval = (best_count >= 3);
}
}
return retval;
}
//////////////////////////////////////////////////////////////////////////
//
// Build_Sector
//
//////////////////////////////////////////////////////////////////////////
PathfindSectorClass *
PathfindSectorBuilderClass::Build_Sector
(
FloodfillBoxClass * upper_left_ptr,
int cells_right,
int cells_down
)
{
Vector3 min_point (100000.0F, 100000.0F, 100000.0F);
Vector3 max_point (-100000.0F, -100000.0F, -100000.0F);
//
// Check to see if this sector meets are minimum requirements
//
bool is_valid = true;//Is_Valid_Sector (&upper_left_ptr, cells_right, cells_down);
//
// Allocate a new sector
//
PathfindSectorClass *sector = NULL;
if (is_valid) {
sector = new PathfindSectorClass;
}
//
// Remove all the cells that compose this area from the list
//
FloodfillBoxClass *curr_cell = upper_left_ptr;
for (int right = 0; (right < cells_right); right ++) {
FloodfillBoxClass *down_obj = curr_cell;
for (int down = 0; (down < cells_down); down ++) {
AABoxClass bounding_box = Get_Body_Box_Bounds (down_obj);
min_point.X = min (min_point.X, bounding_box.Center.X - bounding_box.Extent.X);
min_point.Y = min (min_point.Y, bounding_box.Center.Y - bounding_box.Extent.Y);
min_point.Z = min (min_point.Z, bounding_box.Center.Z - bounding_box.Extent.Z);
max_point.X = max (max_point.X, bounding_box.Center.X + bounding_box.Extent.X);
max_point.Y = max (max_point.Y, bounding_box.Center.Y + bounding_box.Extent.Y);
max_point.Z = max (max_point.Z, bounding_box.Center.Z + bounding_box.Extent.Z);
WWASSERT (down_obj->Is_Taken () == false);
if (is_valid) {
down_obj->Set_Sector (sector);
}
down_obj->Remove ();
down_obj->Set_Taken ();
//
// Is this an edge case? (If so its a possible portal)
//
if ( (down == 0) ||
(right == 0) ||
(down == (cells_down - 1)) ||
(right == (cells_right - 1)))
{
if (is_valid) {
m_PossiblePortalList.Add (down_obj);
}
}
//
// Advance to the next box down
//
down_obj = down_obj->Peek_Neighbor (DIR_DOWN);
}
//
// Advance to the next box right
//
curr_cell = curr_cell->Peek_Neighbor (DIR_RIGHT);
}
//
// Calculate this sector's bounding box
//
if (is_valid) {
AABoxClass bounding_box;
bounding_box.Center = min_point + ((max_point - min_point) * 0.5F);
bounding_box.Extent.X = (max_point.X - min_point.X) * 0.5F;
bounding_box.Extent.Y = (max_point.Y - min_point.Y) * 0.5F;
bounding_box.Extent.Z = (max_point.Z - min_point.Z) * 0.5F;
sector->Set_Bounding_Box (bounding_box);
}
return sector;
}
//////////////////////////////////////////////////////////////////////////
//
// Generate_Portals
//
//////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Generate_Portals (void)
{
//
// Loop through all the body-boxes that are possible portals
//
for (int index = 0; index < m_PossiblePortalList.Count (); index ++) {
FloodfillBoxClass *cull_obj = m_PossiblePortalList[index];
PathfindSectorClass *sector = cull_obj->Peek_Sector ();
if ((sector != NULL) && sector->Is_Valid ()) {
const AABoxClass &box = sector->Get_Bounding_Box ();
Vector3 portal_size = m_SimBoundingBox;
portal_size.Z = box.Extent.Z * 2;
float z_pos = box.Center.Z - box.Extent.Z;
//
// Make portals out of this box for any of the four directions
//
for (int dir = 0; dir < DIR_MAX; dir ++) {
if (cull_obj->Is_New_Portal ((PATHFIND_DIR)dir)) {
//
// Create the portal
//
cull_obj->Make_Portal ((PATHFIND_DIR)dir, portal_size, z_pos, 0.75F);
}
}
}
}
m_PossiblePortalList.Delete_All ();
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Free_Floodfill_Boxes
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Free_Floodfill_Boxes (void)
{
//
// Loop over all the floodfill boxes
//
for (int index = 0; index < m_BodyBoxReleaseList.Count (); index ++) {
//
// Remove the floodfill box from the culling system and
// free our hold on it
//
FloodfillBoxClass *body_box = m_BodyBoxReleaseList[index];
body_box->Reset_Portal_Info ();
body_box->Set_Taken (false);
body_box->Set_Sector (NULL);
body_box->Remove ();
REF_PTR_RELEASE (body_box);
}
//
// Reset our systems
//
m_BodyBoxCullingSystem.Reset ();
m_BodyBoxReleaseList.Delete_All ();
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Cleanup_Level_Features
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Cleanup_Level_Features (void)
{
//
// Loop over all the transition objects and remove them from the
// culling system
//
int count = m_LevelFeatureList.Count ();
for (int index = 0; index < count; index ++) {
LevelFeatureClass *cull_obj = m_LevelFeatureList[index];
m_LevelFeatureCullingSystem.Remove_Object (cull_obj);
MEMBER_RELEASE (cull_obj);
}
m_LevelFeatureList.Delete_All ();
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Detect_Level_Features
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Detect_Level_Features (void)
{
//
// Detect the different types of level features
//
Detect_Doors ();
Detect_Elevators ();
Detect_Level_Transitions ();
//
// Optimize the level feature culling system
//
m_LevelFeatureCullingSystem.Re_Partition ();
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Detect_Elevators
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Detect_Elevators (void)
{
//
// Get the list of all static objects from the physics scene
//
RefPhysListIterator iterator = ::Get_Scene_Editor ()->Get_Static_Object_Iterator ();
for (iterator.First (); !iterator.Is_Done (); iterator.Next ()) {
//
// Is this object an elevator?
//
PhysClass *phys_obj = iterator.Peek_Obj ();
ElevatorPhysClass *elevator = phys_obj->As_ElevatorPhysClass ();
if (elevator != NULL) {
const ElevatorPhysDefClass *definition = elevator->Get_ElevatorPhysDef ();
//
// Get information about the elevator
//
OBBoxClass lower_call;
OBBoxClass upper_call;
OBBoxClass lower_inside;
OBBoxClass upper_inside;
const Matrix3D &tm = elevator->Get_Transform ();
OBBoxClass::Transform (tm, definition->Get_Zone (ZONE_LOWER_CALL), &lower_call);
OBBoxClass::Transform (tm, definition->Get_Zone (ZONE_UPPER_CALL), &upper_call);
OBBoxClass::Transform (tm, definition->Get_Zone (ZONE_LOWER_INSIDE), &lower_inside);
OBBoxClass::Transform (tm, definition->Get_Zone (ZONE_UPPER_INSIDE), &upper_inside);
//
// Create a box that bounds the area the unit will actually be 'moving' in
//
AABoxClass bottom_box;
AABoxClass top_box;
bottom_box.Center = lower_inside.Center;
top_box.Center = upper_inside.Center;
top_box.Center.Z += m_SimBoxExtents.Z;
lower_inside.Compute_Axis_Aligned_Extent (&bottom_box.Extent);
upper_inside.Compute_Axis_Aligned_Extent (&top_box.Extent);
AABoxClass teleport_zone = bottom_box;
teleport_zone.Add_Box (top_box);
//
// Create a level feature for going UP the elevator
//
LevelFeatureClass *up_feature = new LevelFeatureClass;
up_feature->Set_Type (LevelFeatureClass::TYPE_ELEVATOR);
up_feature->Set_Start (lower_call);
up_feature->Set_End (upper_call);
up_feature->Set_End_TM (Matrix3D (upper_call.Center));
up_feature->Set_Teleport_Zone (teleport_zone);
up_feature->Set_Mechanism_ID (elevator->Get_ID ());
//
// Create a level feature for going DOWN the elevator
//
LevelFeatureClass *down_feature = new LevelFeatureClass;
down_feature->Set_Type (LevelFeatureClass::TYPE_ELEVATOR);
down_feature->Set_Start (upper_call);
down_feature->Set_End (lower_call);
down_feature->Set_End_TM (Matrix3D (lower_call.Center));
down_feature->Set_Teleport_Zone (teleport_zone);
down_feature->Set_Mechanism_ID (elevator->Get_ID ());
//
// Add the level features to the culling system
//
m_LevelFeatureCullingSystem.Add_Object (up_feature);
m_LevelFeatureCullingSystem.Add_Object (down_feature);
m_LevelFeatureList.Add (up_feature);
m_LevelFeatureList.Add (down_feature);
}
}
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Detect_Doors
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Detect_Doors (void)
{
//
// Get the list of all static objects from the physics scene
//
RefPhysListIterator iterator = ::Get_Scene_Editor ()->Get_Static_Object_Iterator ();
for (iterator.First (); !iterator.Is_Done (); iterator.Next ()) {
//
// Is this object an elevator?
//
PhysClass *phys_obj = iterator.Peek_Obj ();
DoorPhysClass *door = phys_obj->As_DoorPhysClass ();
if ( door != NULL &&
door->Get_DoorPhysDef () != NULL &&
door->Get_DoorPhysDef ()->Is_Vehicle_Door () == false)
{
const DoorPhysDefClass *definition = door->Get_DoorPhysDef ();
//
// Get the door's trigger zones
//
const Matrix3D &tm = door->Get_Transform ();
OBBoxClass trigger_zone1;
OBBoxClass trigger_zone2;
OBBoxClass::Transform (tm, definition->Get_Trigger_Zone1 (), &trigger_zone1);
OBBoxClass::Transform (tm, definition->Get_Trigger_Zone2 (), &trigger_zone2);
//
// Create a box that bounds the area the unit will actually be 'moving' in
//
AABoxClass box1;
AABoxClass box2;
box1.Center = trigger_zone1.Center;
box2.Center = trigger_zone2.Center;
trigger_zone1.Compute_Axis_Aligned_Extent (&box1.Extent);
trigger_zone2.Compute_Axis_Aligned_Extent (&box2.Extent);
AABoxClass teleport_zone = box1;
teleport_zone.Add_Box (box2);
//
// Create a level feature for going one direction through the door
//
LevelFeatureClass *feature1 = new LevelFeatureClass;
feature1->Set_Type (LevelFeatureClass::TYPE_DOOR);
feature1->Set_Start (trigger_zone1);
feature1->Set_End (trigger_zone2);
feature1->Set_End_TM (Matrix3D (trigger_zone2.Center));
feature1->Set_Teleport_Zone (teleport_zone);
feature1->Set_Mechanism_ID (door->Get_ID ());
//
// Create a level feature for going the other direction through the door
//
LevelFeatureClass *feature2 = new LevelFeatureClass;
feature2->Set_Type (LevelFeatureClass::TYPE_DOOR);
feature2->Set_Start (trigger_zone2);
feature2->Set_End (trigger_zone1);
feature2->Set_End_TM (Matrix3D (trigger_zone1.Center));
feature2->Set_Teleport_Zone (teleport_zone);
feature2->Set_Mechanism_ID (door->Get_ID ());
//
// Add the level features to the culling system
//
m_LevelFeatureCullingSystem.Add_Object (feature1);
m_LevelFeatureCullingSystem.Add_Object (feature2);
m_LevelFeatureList.Add (feature1);
m_LevelFeatureList.Add (feature2);
}
}
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Detect_Level_Transitions
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Detect_Level_Transitions (void)
{
int ladder_index = 0;
//
// Loop through all the transitions in the level
//
TransitionNodeClass *node = NULL;
for (node = (TransitionNodeClass *)NodeMgrClass::Get_First (NODE_TYPE_TRANSITION);
node != NULL;
node = (TransitionNodeClass *)NodeMgrClass::Get_Next (node, NODE_TYPE_TRANSITION))
{
//
// Loop through all the different transitions in this node
//
bool need_new_ladder_index = true;
int count = node->Get_Transition_Count ();
for (int index = 0; index < count; index ++) {
TransitionInstanceClass *transition = node->Get_Transition (index);
if (transition != NULL) {
//
// Build an AABox from the zone this transition uses
//
OBBoxClass zone = transition->Get_Zone ();
//
// We handle each type of transition differently
//
switch (transition->Get_Type ())
{
//
// For ladders, we need to find the 'exit' point
//
case TransitionDataClass::LADDER_ENTER_TOP:
case TransitionDataClass::LADDER_ENTER_BOTTOM:
{
Vector3 pos = zone.Center;
//
// Insert this transition into our culling system
//
LevelFeatureClass *level_feature = new LevelFeatureClass;
level_feature->Set_Start (zone);
//
// Search for the exit transition
//
TransitionInstanceClass *exit_transition = NULL;
TransitionNodeClass *exit_node = NULL;
if (transition->Get_Type () == TransitionDataClass::LADDER_ENTER_BOTTOM) {
exit_transition = Find_Transition (TransitionDataClass::LADDER_EXIT_TOP, pos, 100.0F, &exit_node);
} else {
exit_transition = Find_Transition (TransitionDataClass::LADDER_EXIT_BOTTOM, pos, -100.0F, &exit_node);
}
//
// Pass the exit zone onto the level feature object
//
if (exit_transition != NULL) {
level_feature->Set_End (exit_transition->Get_Zone ());
level_feature->Set_End_TM (exit_transition->Get_Ending_TM ());
AABoxClass box;
box.Center = pos;
box.Extent = m_SimBoxExtents;
box.Extent.X *= 4.0F;
box.Extent.Y *= 4.0F;
//
// Create a box that encompasses the start position and end position
//
AABoxClass teleport_box (box);
box.Center = exit_transition->Get_Ending_TM ().Get_Translation ();
box.Center.Z += m_SimBoxExtents.Z;
teleport_box.Add_Box (box);
//
// Pass the teleport area onto the level feature
//
level_feature->Set_Teleport_Zone (teleport_box);
}
//
// Set the level feature's type
//
if (transition->Get_Type () == TransitionDataClass::LADDER_ENTER_BOTTOM) {
level_feature->Set_Type (LevelFeatureClass::TYPE_LADDER_BOTTOM);
} else {
level_feature->Set_Type (LevelFeatureClass::TYPE_LADDER_TOP);
}
int new_ladder_index = -1;
//
// Can we reuse the same ladder index that the exit portal uses?
//
if (exit_node != NULL && exit_node->Get_Transition_Game_Obj () != NULL) {
new_ladder_index = exit_node->Get_Transition_Game_Obj ()->Get_Ladder_Index ();
if (new_ladder_index != -1) {
need_new_ladder_index = false;
}
}
//
// Increment the ladder counter as necessary
//
if (need_new_ladder_index) {
need_new_ladder_index = false;
ladder_index ++;
new_ladder_index = ladder_index;
}
//
// Give the level feature a unique identifier
//
level_feature->Set_Mechanism_ID (ladder_index);
if (node->Get_Transition_Game_Obj () != NULL) {
node->Get_Transition_Game_Obj ()->Set_Ladder_Index (ladder_index);
}
//
// Attempt to tie the bottom and top transitions to the same value
//
if (exit_node != NULL && exit_node->Get_Transition_Game_Obj () != NULL) {
exit_node->Get_Transition_Game_Obj ()->Set_Ladder_Index (ladder_index);
}
//
// Add the level feature to the culling systems
//
m_LevelFeatureCullingSystem.Add_Object (level_feature);
m_LevelFeatureList.Add (level_feature);
}
break;
default:
break;
}
}
}
}
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Post_Process_Floodfill_For_Level_Features
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Post_Process_Floodfill_For_Level_Features (void)
{
//
// Loop over all the level features
//
for (int index = 0; index < m_LevelFeatureList.Count (); index ++) {
LevelFeatureClass *level_feature = m_LevelFeatureList[index];
if (level_feature != NULL) {
//
// Get the area where the player will be moving
//
AABoxClass box = level_feature->Get_Teleport_Zone ();
//
// Loop over all the body-boxes that exist in this area
//
m_BodyBoxCullingSystem.Collect_Boxes (box);
DynamicVectorClass &list = m_BodyBoxCullingSystem.Get_Collection_List ();
for (int index = 0; index < list.Count (); index ++) {
FloodfillBoxClass *body_box = list[index];
//
// Force the test to pass in the z-component
//
box.Extent.Z = 1000.0F;
//
// Remove this box from the system if its completely contained
// inside the teleport zone
//
AABoxClass test_box = Get_Body_Box_Bounds (body_box);
if (CollisionMath::Overlap_Test (box, test_box) == CollisionMath::INSIDE) {
//
// Remove the box from the possible portal list (if necessary)
//
int portal_list_index = m_PossiblePortalList.ID (body_box);
if (portal_list_index != -1) {
m_PossiblePortalList.Delete (portal_list_index);
}
//
// Remove this box from the system
//
m_BodyBoxReleaseList.Add (body_box);
body_box->Unlink ();
m_BodyBoxCullingSystem.Remove_Box (body_box);
}
}
}
}
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Apply_Level_Features
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Apply_Level_Features (void)
{
//
// Loop over all the level features and create sectors and portals
// for them
//
for (int index = 0; index < m_LevelFeatureList.Count (); index ++) {
LevelFeatureClass *level_feature = m_LevelFeatureList[index];
if (level_feature != NULL) {
//
// Integrate this feature into the pathfind data
//
Build_Sector_For_Level_Feature (level_feature);
}
}
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Find_Transition
//
///////////////////////////////////////////////////////////////////////////
TransitionInstanceClass *
PathfindSectorBuilderClass::Find_Transition
(
TransitionDataClass::StyleType transition_type,
const Vector3 & start_pos,
float z_delta,
TransitionNodeClass ** transition_node
)
{
TransitionInstanceClass *retval = NULL;
(*transition_node) = NULL;
float start_z = start_pos.Z;
float closest_z = 1000000;
//
// Loop over all the transitions in the level and find the one
// that most closely matches what we are looking for
//
TransitionNodeClass *node = NULL;
for (node = (TransitionNodeClass *)NodeMgrClass::Get_First (NODE_TYPE_TRANSITION);
node != NULL;
node = (TransitionNodeClass *)NodeMgrClass::Get_Next (node, NODE_TYPE_TRANSITION))
{
//
// See if we can find a transition game object inside the node
// that is the type we are looking for.
//
int index = node->Find_Transition (transition_type);
if (index >= 0) {
//
// Get the transition game object
//
TransitionInstanceClass *transition = node->Get_Transition (index);
if (transition != NULL) {
const OBBoxClass &zone = transition->Get_Zone ();
//
// Determine how 'far' we are from this transition
//
float curr_z_min = zone.Center.Z - zone.Extent.Z;
float curr_z_max = zone.Center.Z + zone.Extent.Z;
float curr_delta = min (WWMath::Fabs (start_z - curr_z_min), WWMath::Fabs (start_z - curr_z_max));
//
// Is this transition zone the one we are looking for?
//
if ( (curr_delta < closest_z) &&
(WWMath::Fabs (start_pos.X - zone.Center.X) < 1.0F) &&
(WWMath::Fabs (start_pos.Y - zone.Center.Y) < 1.0F))
{
(*transition_node) = node;
retval = transition;
closest_z = curr_delta;
}
}
}
}
return retval;
}
///////////////////////////////////////////////////////////////////////////
//
// Find_Sector
//
///////////////////////////////////////////////////////////////////////////
PathfindSectorClass *
PathfindSectorBuilderClass::Find_Sector
(
const Vector3 & point,
const AABoxClass & box
)
{
PathfindSectorClass *sector = PathfindClass::Get_Instance ()->Find_Sector (point, 1.0F);
if (sector == NULL) {
sector = PathfindClass::Get_Instance ()->Find_Sector (box.Center, 1.0F);
}
if (sector == NULL) {
Vector3 box_point = box.Center;
box_point.X += box.Extent.X;
box_point.Y += box.Extent.Y;
sector = PathfindClass::Get_Instance ()->Find_Sector (box_point, 1.0F);
}
if (sector == NULL) {
Vector3 box_point = box.Center;
box_point.X -= box.Extent.X;
box_point.Y -= box.Extent.Y;
sector = PathfindClass::Get_Instance ()->Find_Sector (box_point, 1.0F);
}
if (sector == NULL) {
Vector3 box_point = box.Center;
box_point.X += box.Extent.X;
box_point.Y -= box.Extent.Y;
sector = PathfindClass::Get_Instance ()->Find_Sector (box_point, 1.0F);
}
if (sector == NULL) {
Vector3 box_point = box.Center;
box_point.X -= box.Extent.X;
box_point.Y += box.Extent.Y;
sector = PathfindClass::Get_Instance ()->Find_Sector (box_point, 1.0F);
}
return sector;
}
///////////////////////////////////////////////////////////////////////////
//
// Build_Sector_For_Level_Feature
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Build_Sector_For_Level_Feature (LevelFeatureClass *level_feature)
{
if (level_feature == NULL) {
return ;
}
//
// Get the starting and ending positions
//
Matrix3D end_tm = level_feature->Get_End_TM ();
Vector3 end_pos = end_tm.Get_Translation ();
Vector3 start_pos = level_feature->Get_Start ().Center;
//
// Get the starting and ending AABox's for this feature
//
AABoxClass start_box;
AABoxClass end_box;
level_feature->Get_Start_AABox (start_box);
level_feature->Get_End_AABox (end_box);
Vector3 sector_end_pos = end_pos;
//
// Assume the player will want to exit "away" from where (s)he entered
//
if (level_feature->Get_Type () == LevelFeatureClass::TYPE_DOOR) {
Vector3 offset = end_box.Center - start_box.Center;
offset.Normalize ();
sector_end_pos = end_pos + offset;
Clip_Point (§or_end_pos, end_box);
}
//
// Are there any pathfinding sectors intersecting the
// start and ending regions?
//
PathfindSectorClass *start_sector = Find_Sector (start_pos, start_box);
PathfindSectorClass *end_sector = Find_Sector (sector_end_pos, end_box);
if ( level_feature->Get_Type () == LevelFeatureClass::TYPE_LADDER_BOTTOM ||
level_feature->Get_Type () == LevelFeatureClass::TYPE_LADDER_TOP)
{
if (end_sector != NULL) {
end_box = end_sector->Get_Bounding_Box ();
}
}
//
// Expand the end box by a little bit
//
/*end_box.Extent.X += 0.25F;
end_box.Extent.Y += 0.25F;
end_box.Extent.Z += 0.25F;
//
// Build a list of sectors that the exit should connect to
//
DynamicVectorClass end_sector_list;
PathfindClass::Get_Instance ()->Collect_Sectors (end_sector_list, end_box, start_sector);*/
//
// Were we successful?
//
if ((start_sector != NULL) && (end_sector != NULL)) {
//
// Create a sector from scratch
//
PathfindSectorClass *new_sector = new PathfindSectorClass;
new_sector->Set_Bounding_Box (AABoxClass (Vector3 (0, 0, 0), Vector3 (0, 0, 0)));
PathfindClass::Get_Instance ()->Add_Sector (new_sector);
new_sector->Release_Ref ();
//
// Create the starting portal
//
PathfindActionPortalClass *enter_portal = new PathfindActionPortalClass;
enter_portal->Set_Bounding_Box (start_box);
enter_portal->Add_Dest_Sector (new_sector);
enter_portal->Set_Destination (end_pos);
//
// Create the ending portal
//
PathfindActionPortalClass *exit_portal = new PathfindActionPortalClass;
exit_portal->Set_Bounding_Box (end_box);
exit_portal->Add_Dest_Sector (end_sector);
//
// Determine which type of action should be performed at this portal
//
switch (level_feature->Get_Type ())
{
case LevelFeatureClass::TYPE_LADDER_BOTTOM:
case LevelFeatureClass::TYPE_LADDER_TOP:
{
AABoxClass end_trigger_zone;
level_feature->Get_End_AABox (end_trigger_zone);
enter_portal->Set_Destination (end_trigger_zone.Center);
enter_portal->Set_Action_Type (PathClass::ACTION_LADDER);
enter_portal->Set_Mechanism_ID (level_feature->Get_Mechanism_ID ());
exit_portal->Set_Action_Type (PathClass::ACTION_NONE);
break;
}
case LevelFeatureClass::TYPE_DOOR:
case LevelFeatureClass::TYPE_ELEVATOR:
enter_portal->Set_Action_Type (PathClass::ACTION_MECHANISM);
enter_portal->Set_Mechanism_ID (level_feature->Get_Mechanism_ID ());
exit_portal->Set_Action_Type (PathClass::ACTION_NONE);
break;
}
//
// Let the enter portal "know" where its going to end up...
//
enter_portal->Set_Exit_Portal (exit_portal);
exit_portal->Set_Enter_Portal (enter_portal);
//
// Register the new portals with the pathfinding system,
// and let the sectors know they can access these portals.
//
int enter_portal_index = PathfindClass::Get_Instance ()->Add_Portal (enter_portal);
int exit_portal_index = PathfindClass::Get_Instance ()->Add_Portal (exit_portal);
start_sector->Add_Portal (enter_portal_index);
new_sector->Add_Portal (exit_portal_index);
REF_PTR_RELEASE (enter_portal);
REF_PTR_RELEASE (exit_portal);
}
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Check_For_Level_Feature
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Check_For_Level_Feature (FloodfillBoxClass *body_box)
{
if (m_LevelFeatureCullingSystem.Object_Count () > 0) {
AABoxClass bounding_box = Get_Body_Box_Bounds (body_box);
//
// Find all level features that intersect our current position
//
m_LevelFeatureCullingSystem.Reset_Collection ();
m_LevelFeatureCullingSystem.Collect_Objects (bounding_box);
//
// Find all the features this body box intersects
//
DynamicVectorClass feature_list;
LevelFeatureClass *level_feature = NULL;
for ( level_feature = m_LevelFeatureCullingSystem.Get_First_Collected_Object ();
level_feature != NULL;
level_feature = m_LevelFeatureCullingSystem.Get_Next_Collected_Object (level_feature))
{
feature_list.Add (level_feature);
}
//
// Loop through all the features in our list and process any 'portals' (ladders, doors, etc)
//
for (int index = 0; index < feature_list.Count (); index ++) {
level_feature = feature_list[index];
//
// Get the bounding box for the pathfind object and the level feature's 'start-zone'
//
AABoxClass pathfind_box = Get_Body_Box_Bounds (body_box);
AABoxClass feature_box;
level_feature->Get_Start_AABox (feature_box);
//
// Do these boxe's intersect?
//
if ( (pathfind_box.Center.X + pathfind_box.Extent.X < feature_box.Center.X + feature_box.Extent.X) &&
(pathfind_box.Center.X - pathfind_box.Extent.X > feature_box.Center.X - feature_box.Extent.X) &&
(pathfind_box.Center.Y + pathfind_box.Extent.Y < feature_box.Center.Y + feature_box.Extent.Y) &&
(pathfind_box.Center.Y - pathfind_box.Extent.Y > feature_box.Center.Y - feature_box.Extent.Y))
{
//
// Continue our pathfind across this feature (i.e. up the ladder, down the elevator, etc)
//
Path_Across_Feature (level_feature);
}
}
}
return ;
}
///////////////////////////////////////////////////////////////////////////
//
// Path_Across_Feature
//
///////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Path_Across_Feature (LevelFeatureClass *level_feature)
{
//
// Get the point where we think this feature will 'teleport' us to
//
Vector3 expected_pos = level_feature->Get_End_TM ().Get_Translation ();
expected_pos.Z += m_SimBoxExtents.Z;
//
// Snap this position to our pathfind grid
//
Vector3 normalized_pos = expected_pos;
normalized_pos.X = (int(expected_pos.X / m_SimBoundingBox.X)) * m_SimBoundingBox.X;
normalized_pos.Y = (int(expected_pos.Y / m_SimBoundingBox.Y)) * m_SimBoundingBox.Y;
//
// Can we stand at this new position?
//
AABoxClass new_box;
if (Try_Standing_Here (normalized_pos, &new_box)) {
//
// Is this cell already marked?
//
Vector3 position = new_box.Center;
position.Z = new_box.Center.Z;
FloodfillBoxClass *occupant = Get_Sector_Occupant (position);
if (occupant == NULL) {
//
// Mark this cell and add it to the list of sectors
// that need to be recursed.
//
occupant = Mark_Sector (new_box);
m_FloodFillProcessList.Add (occupant);
}
}
return ;
}
/////////////////////////////////////////////////////////////////////////////
//
// fnPathfindDialogThread
//
////////////////////////////////////////////////////////////////////////////
UINT
fnPathfindDialogThread
(
DWORD dwparam1,
DWORD dwparam2,
DWORD /*dwparam3*/,
HRESULT* /*presult*/,
HWND* /*phmain_wnd*/
)
{
GeneratingPathfindDialogClass *dialog = new GeneratingPathfindDialogClass (::AfxGetMainWnd ());
dialog->ShowWindow (SW_SHOW);
//
// Return the dialog object to the caller
//
GeneratingPathfindDialogClass **return_val = (GeneratingPathfindDialogClass **)dwparam2;
if (return_val != NULL) {
(*return_val) = dialog;
}
return 1;
}
////////////////////////////////////////////////////////////////////////////
//
// Show_Dialog
//
////////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Show_Dialog (void)
{
::Create_UI_Thread (fnPathfindDialogThread, 0, (DWORD)&m_pDialog, 0, NULL, NULL);
return ;
}
////////////////////////////////////////////////////////////////////////////
//
// Close_Dialog
//
////////////////////////////////////////////////////////////////////////////
void
PathfindSectorBuilderClass::Close_Dialog (void)
{
if (m_pDialog != NULL) {
::PostMessage (m_pDialog->m_hWnd, WM_USER+101, 0, 0L);
}
return ;
}