//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose:
//
// $NoKeywords: $
//
//=============================================================================//
// nav.h
// Data structures and constants for the Navigation Mesh system
// Author: Michael S. Booth (mike@turtlerockstudios.com), January 2003

#ifndef _NAV_H_
#define _NAV_H_

#include "doors.h"
#include "modelentities.h"  // for CFuncBrush

/**
 * Below are several constants used by the navigation system.
 * @todo Move these into TheNavMesh singleton.
 */
const float GenerationStepSize =
    25.0f;  // (30) was 20, but bots can't fit always fit
const float JumpHeight =
    41.8f;  // if delta Z is less than this, we can jump up on it

#if defined(CSTRIKE_DLL)
const float JumpCrouchHeight = 58.0f;  // (48) if delta Z is less than or equal
                                       // to this, we can jumpcrouch up on it
#else
const float JumpCrouchHeight = 64.0f;  // (48) if delta Z is less than or equal
                                       // to this, we can jumpcrouch up on it
#endif

// There are 3 different definitions of StepHeight throughout the code, waiting
// to produce bugs if the 18.0 is ever changed.
const float StepHeight =
    18.0f;  // if delta Z is greater than this, we have to jump to get up

// TERROR: Increased DeathDrop from 200, since zombies don't take falling damage
#if defined(CSTRIKE_DLL)
const float DeathDrop =
    200.0f;  // (300) distance at which we will die if we fall - should be about
             // 600, and pay attention to fall damage during pathfind
#else
const float DeathDrop =
    400.0f;  // (300) distance at which we will die if we fall - should be about
             // 600, and pay attention to fall damage during pathfind
#endif

#if defined(CSTRIKE_DLL)
const float ClimbUpHeight =
    JumpCrouchHeight;  // CSBots assume all jump up links are reachable
#else
const float ClimbUpHeight = 200.0f;  // height to check for climbing up
#endif

const float CliffHeight =
    300.0f;  // height which we consider a significant cliff which we would not
             // want to fall off of

// TERROR: Converted these values to use the same numbers as the player bounding
// boxes etc
#define HalfHumanWidth 16
#define HalfHumanHeight 35.5
#define HumanHeight 71
#define HumanEyeHeight 62
#define HumanCrouchHeight 55
#define HumanCrouchEyeHeight 37

#define NAV_MAGIC_NUMBER 0xFEEDFACE  // to help identify nav files

/**
 * A place is a named group of navigation areas
 */
typedef unsigned int Place;
#define UNDEFINED_PLACE 0  // ie: "no place"
#define ANY_PLACE 0xFFFF

enum NavErrorType {
    NAV_OK,
    NAV_CANT_ACCESS_FILE,
    NAV_INVALID_FILE,
    NAV_BAD_FILE_VERSION,
    NAV_FILE_OUT_OF_DATE,
    NAV_CORRUPT_DATA,
    NAV_OUT_OF_MEMORY,
};

enum NavAttributeType {
    NAV_MESH_INVALID = 0,
    NAV_MESH_CROUCH = 0x00000001,  // must crouch to use this node/area
    NAV_MESH_JUMP = 0x00000002,    // must jump to traverse this area (only used
                                   // during generation)
    NAV_MESH_PRECISE =
        0x00000004,  // do not adjust for obstacles, just move along area
    NAV_MESH_NO_JUMP = 0x00000008,  // inhibit discontinuity jumping
    NAV_MESH_STOP = 0x00000010,     // must stop when entering this area
    NAV_MESH_RUN = 0x00000020,      // must run to traverse this area
    NAV_MESH_WALK = 0x00000040,     // must walk to traverse this area
    NAV_MESH_AVOID =
        0x00000080,  // avoid this area unless alternatives are too dangerous
    NAV_MESH_TRANSIENT = 0x00000100,  // area may become blocked, and should be
                                      // periodically checked
    NAV_MESH_DONT_HIDE =
        0x00000200,  // area should not be considered for hiding spot generation
    NAV_MESH_STAND = 0x00000400,        // bots hiding in this area should stand
    NAV_MESH_NO_HOSTAGES = 0x00000800,  // hostages shouldn't use this area
    NAV_MESH_STAIRS =
        0x00001000,  // this area represents stairs, do not attempt to climb or
                     // jump them - just walk up
    NAV_MESH_NO_MERGE =
        0x00002000,  // don't merge this area with adjacent areas
    NAV_MESH_OBSTACLE_TOP = 0x00004000,  // this nav area is the climb point on
                                         // the tip of an obstacle
    NAV_MESH_CLIFF = 0x00008000,  // this nav area is adjacent to a drop of at
                                  // least CliffHeight

    NAV_MESH_FIRST_CUSTOM = 0x00010000,  // apps may define custom app-specific
                                         // bits starting with this value
    NAV_MESH_LAST_CUSTOM =
        0x04000000,  // apps must not define custom app-specific bits higher
                     // than with this value

    NAV_MESH_FUNC_COST = 0x20000000,     // area has designer specified cost
                                         // controlled by func_nav_cost entities
    NAV_MESH_HAS_ELEVATOR = 0x40000000,  // area is in an elevator's path
    NAV_MESH_NAV_BLOCKER =
        0x80000000  // area is blocked by nav blocker ( Alas, needed to hijack a
                    // bit in the attributes to get within a cache line
                    // [7/24/2008 tom])
};

extern NavAttributeType NameToNavAttribute(const char *name);

enum NavDirType {
    NORTH = 0,
    EAST = 1,
    SOUTH = 2,
    WEST = 3,

    NUM_DIRECTIONS
};

/**
 * Defines possible ways to move from one area to another
 */
enum NavTraverseType {
    // NOTE: First 4 directions MUST match NavDirType
    GO_NORTH = 0,
    GO_EAST,
    GO_SOUTH,
    GO_WEST,

    GO_LADDER_UP,
    GO_LADDER_DOWN,
    GO_JUMP,
    GO_ELEVATOR_UP,
    GO_ELEVATOR_DOWN,

    NUM_TRAVERSE_TYPES
};

enum NavCornerType {
    NORTH_WEST = 0,
    NORTH_EAST = 1,
    SOUTH_EAST = 2,
    SOUTH_WEST = 3,

    NUM_CORNERS
};

enum NavRelativeDirType {
    FORWARD = 0,
    RIGHT,
    BACKWARD,
    LEFT,
    UP,
    DOWN,

    NUM_RELATIVE_DIRECTIONS
};

struct Extent {
    Vector lo, hi;

    void Init(void) {
        lo.Init();
        hi.Init();
    }

    void Init(CBaseEntity *entity) {
        entity->CollisionProp()->WorldSpaceSurroundingBounds(&lo, &hi);
    }

    float SizeX(void) const { return hi.x - lo.x; }
    float SizeY(void) const { return hi.y - lo.y; }
    float SizeZ(void) const { return hi.z - lo.z; }
    float Area(void) const { return SizeX() * SizeY(); }

    // Increase bounds to contain the given point
    void Encompass(const Vector &pos) {
        for (int i = 0; i < 3; ++i) {
            if (pos[i] < lo[i]) {
                lo[i] = pos[i];
            } else if (pos[i] > hi[i]) {
                hi[i] = pos[i];
            }
        }
    }

    // Increase bounds to contain the given extent
    void Encompass(const Extent &extent) {
        Encompass(extent.lo);
        Encompass(extent.hi);
    }

    // return true if 'pos' is inside of this extent
    bool Contains(const Vector &pos) const {
        return (pos.x >= lo.x && pos.x <= hi.x && pos.y >= lo.y &&
                pos.y <= hi.y && pos.z >= lo.z && pos.z <= hi.z);
    }

    // return true if this extent overlaps the given one
    bool IsOverlapping(const Extent &other) const {
        return (lo.x <= other.hi.x && hi.x >= other.lo.x &&
                lo.y <= other.hi.y && hi.y >= other.lo.y &&
                lo.z <= other.hi.z && hi.z >= other.lo.z);
    }

    // return true if this extent completely contains the given one
    bool IsEncompassing(const Extent &other, float tolerance = 0.0f) const {
        return (
            lo.x <= other.lo.x + tolerance && hi.x >= other.hi.x - tolerance &&
            lo.y <= other.lo.y + tolerance && hi.y >= other.hi.y - tolerance &&
            lo.z <= other.lo.z + tolerance && hi.z >= other.hi.z - tolerance);
    }
};

struct Ray {
    Vector from, to;
};

class CNavArea;
class CNavNode;

//--------------------------------------------------------------------------------------------------------------
inline NavDirType OppositeDirection(NavDirType dir) {
    switch (dir) {
        case NORTH:
            return SOUTH;
        case SOUTH:
            return NORTH;
        case EAST:
            return WEST;
        case WEST:
            return EAST;
        default:
            break;
    }

    return NORTH;
}

//--------------------------------------------------------------------------------------------------------------
inline NavDirType DirectionLeft(NavDirType dir) {
    switch (dir) {
        case NORTH:
            return WEST;
        case SOUTH:
            return EAST;
        case EAST:
            return NORTH;
        case WEST:
            return SOUTH;
        default:
            break;
    }

    return NORTH;
}

//--------------------------------------------------------------------------------------------------------------
inline NavDirType DirectionRight(NavDirType dir) {
    switch (dir) {
        case NORTH:
            return EAST;
        case SOUTH:
            return WEST;
        case EAST:
            return SOUTH;
        case WEST:
            return NORTH;
        default:
            break;
    }

    return NORTH;
}

//--------------------------------------------------------------------------------------------------------------
inline void AddDirectionVector(Vector *v, NavDirType dir, float amount) {
    switch (dir) {
        case NORTH:
            v->y -= amount;
            return;
        case SOUTH:
            v->y += amount;
            return;
        case EAST:
            v->x += amount;
            return;
        case WEST:
            v->x -= amount;
            return;
        default:
            break;
    }
}

//--------------------------------------------------------------------------------------------------------------
inline float DirectionToAngle(NavDirType dir) {
    switch (dir) {
        case NORTH:
            return 270.0f;
        case SOUTH:
            return 90.0f;
        case EAST:
            return 0.0f;
        case WEST:
            return 180.0f;
        default:
            break;
    }

    return 0.0f;
}

//--------------------------------------------------------------------------------------------------------------
inline NavDirType AngleToDirection(float angle) {
    while (angle < 0.0f) angle += 360.0f;

    while (angle > 360.0f) angle -= 360.0f;

    if (angle < 45 || angle > 315) return EAST;

    if (angle >= 45 && angle < 135) return SOUTH;

    if (angle >= 135 && angle < 225) return WEST;

    return NORTH;
}

//--------------------------------------------------------------------------------------------------------------
inline void DirectionToVector2D(NavDirType dir, Vector2D *v) {
    switch (dir) {
        default:
            Assert(0);
        case NORTH:
            v->x = 0.0f;
            v->y = -1.0f;
            break;
        case SOUTH:
            v->x = 0.0f;
            v->y = 1.0f;
            break;
        case EAST:
            v->x = 1.0f;
            v->y = 0.0f;
            break;
        case WEST:
            v->x = -1.0f;
            v->y = 0.0f;
            break;
    }
}

//--------------------------------------------------------------------------------------------------------------
inline void CornerToVector2D(NavCornerType dir, Vector2D *v) {
    switch (dir) {
        default:
            Assert(0);
        case NORTH_WEST:
            v->x = -1.0f;
            v->y = -1.0f;
            break;
        case NORTH_EAST:
            v->x = 1.0f;
            v->y = -1.0f;
            break;
        case SOUTH_EAST:
            v->x = 1.0f;
            v->y = 1.0f;
            break;
        case SOUTH_WEST:
            v->x = -1.0f;
            v->y = 1.0f;
            break;
    }

    v->NormalizeInPlace();
}

//--------------------------------------------------------------------------------------------------------------
// Gets the corner types that surround the given direction
inline void GetCornerTypesInDirection(NavDirType dir, NavCornerType *first,
                                      NavCornerType *second) {
    switch (dir) {
        default:
            Assert(0);
        case NORTH:
            *first = NORTH_WEST;
            *second = NORTH_EAST;
            break;
        case SOUTH:
            *first = SOUTH_WEST;
            *second = SOUTH_EAST;
            break;
        case EAST:
            *first = NORTH_EAST;
            *second = SOUTH_EAST;
            break;
        case WEST:
            *first = NORTH_WEST;
            *second = SOUTH_WEST;
            break;
    }
}

//--------------------------------------------------------------------------------------------------------------
inline float RoundToUnits(float val, float unit) {
    val = val + ((val < 0.0f) ? -unit * 0.5f : unit * 0.5f);
    return (float)(unit * (((int)val) / (int)unit));
}

//--------------------------------------------------------------------------------------------------------------
/**
 * Return true if given entity can be ignored when moving
 */
#define WALK_THRU_PROP_DOORS 0x01
#define WALK_THRU_FUNC_DOORS 0x02
#define WALK_THRU_DOORS (WALK_THRU_PROP_DOORS | WALK_THRU_FUNC_DOORS)
#define WALK_THRU_BREAKABLES 0x04
#define WALK_THRU_TOGGLE_BRUSHES 0x08
#define WALK_THRU_EVERYTHING \
    (WALK_THRU_DOORS | WALK_THRU_BREAKABLES | WALK_THRU_TOGGLE_BRUSHES)
extern ConVar nav_solid_props;
inline bool IsEntityWalkable(CBaseEntity *entity, unsigned int flags) {
    if (FClassnameIs(entity, "worldspawn")) return false;

    if (FClassnameIs(entity, "player")) return false;

    // if we hit a door, assume its walkable because it will open when we touch
    // it
    if (FClassnameIs(entity, "func_door*")) {
#ifdef PROBLEMATIC  // cp_dustbowl doors dont open by touch - they use
                    // surrounding triggers
        if (!entity->HasSpawnFlags(SF_DOOR_PTOUCH)) {
            // this door is not opened by touching it, if it is closed, the area
            // is blocked
            CBaseDoor *door = (CBaseDoor *)entity;
            return door->m_toggle_state == TS_AT_TOP;
        }
#endif  // _DEBUG

        return (flags & WALK_THRU_FUNC_DOORS) ? true : false;
    }

    if (FClassnameIs(entity, "prop_door*")) {
        return (flags & WALK_THRU_PROP_DOORS) ? true : false;
    }

    // if we hit a clip brush, ignore it if it is not BRUSHSOLID_ALWAYS
    if (FClassnameIs(entity, "func_brush")) {
        CFuncBrush *brush = (CFuncBrush *)entity;
        switch (brush->m_iSolidity) {
            case CFuncBrush::BRUSHSOLID_ALWAYS:
                return false;
            case CFuncBrush::BRUSHSOLID_NEVER:
                return true;
            case CFuncBrush::BRUSHSOLID_TOGGLE:
                return (flags & WALK_THRU_TOGGLE_BRUSHES) ? true : false;
        }
    }

    // if we hit a breakable object, assume its walkable because we will shoot
    // it when we touch it
    if (FClassnameIs(entity, "func_breakable") && entity->GetHealth() &&
        entity->m_takedamage == DAMAGE_YES)
        return (flags & WALK_THRU_BREAKABLES) ? true : false;

    if (FClassnameIs(entity, "func_breakable_surf") &&
        entity->m_takedamage == DAMAGE_YES)
        return (flags & WALK_THRU_BREAKABLES) ? true : false;

    if (FClassnameIs(entity, "func_playerinfected_clip") == true) return true;

    if (nav_solid_props.GetBool() && FClassnameIs(entity, "prop_*"))
        return true;

    return false;
}

//--------------------------------------------------------------------------------------------------------------
/**
 *  Trace filter that ignores players, NPCs, and objects that can be walked
 * through
 */
class CTraceFilterWalkableEntities : public CTraceFilterNoNPCsOrPlayer {
   public:
    CTraceFilterWalkableEntities(const IHandleEntity *passentity,
                                 int collisionGroup, unsigned int flags)
        : CTraceFilterNoNPCsOrPlayer(passentity, collisionGroup),
          m_flags(flags) {}

    virtual bool ShouldHitEntity(IHandleEntity *pServerEntity,
                                 int contentsMask) {
        if (CTraceFilterNoNPCsOrPlayer::ShouldHitEntity(pServerEntity,
                                                        contentsMask)) {
            CBaseEntity *pEntity = EntityFromEntityHandle(pServerEntity);
            return (!IsEntityWalkable(pEntity, m_flags));
        }
        return false;
    }

   private:
    unsigned int m_flags;
};

extern bool IsWalkableTraceLineClear(const Vector &from, const Vector &to,
                                     unsigned int flags = 0);

#endif  // _NAV_H_