#pragma once
#include "Polygon3D.h"
#include <map>
#include "Clipper.h"

#define MAX_MAP_CLIPNODE_LEAVES 65536 // doubled to account for each clipnode's child contents having its own ID
#define NAV_INVALID_IDX 65535

#define NAV_STEP_HEIGHT 18
#define NAV_JUMP_HEIGHT 44
#define NAV_CROUCHJUMP_HEIGHT 63	// 208 gravity 50%
#define NAV_CROUCHJUMP_STACK_HEIGHT 135
#define NAV_AUTOCLIMB_HEIGHT 117

#define NAV_BOTTOM_EPSILON 1.0f // move waypoints this far from the bottom of the node

#define NAV_LEAF_PARENT 1 // node was split by entity leaves and should not be used
#define NAV_LEAF_CHILD 2 // node was created by splitting a world leaf by an entity

class Bsp;
class Entity;
class LeafOctree;
class VertexBuffer;

struct LeafLink {
	uint16_t node; // which leaf is linked to
	vec3 pos; // link position
	float baseCost; // flat cost for using this path
	float costMultiplier; // cost applied to length of path
	
	// for debugging
	Polygon3D linkArea; // region in which leaves are making contact
};

struct EntState {
	vec3 origin;
	vec3 angles;
	uint16_t model; // 0 = point entity box as hull
};

struct LeafNode {
	vector<LeafLink> links;
	uint16_t id;
	uint16_t leafIdx; // leaf index in the BSP data
	vec3 origin; // the best position for pathing (not necessarily the center)
	int16_t entidx; // 0 for world leaves, else an entity leaf which may be relocated, enabled, or disabled
	uint16_t parentIdx; // parent leaf idx if this node is the child of another leaf, else 65535
	uint16_t childIdx; // first child idx if this node contains split leaves, else 65535

	vector<EntState> splittingEnts; // entities which are splitting this node

	CMesh clipMesh; // cached clip mesh for faster splitting

	// for debugging
	vec3 center;
	vec3 mins, maxs; // for octree insertion, not needed after generation
	vector<Polygon3D> leafFaces;
	VertexBuffer* face_buffer;
	VertexBuffer* wireframe_buffer;

	LeafNode();

	// linkAtFloor = move link position to the floor for human pathing
	bool addLink(int node, Polygon3D linkArea, bool linkAtFloor);

	bool addLink(int node, vec3 linkPos);

	// returns true if point is inside leaf volume
	bool isInside(vec3 p, float epsilon=0.0f);

	bool intersects(Polygon3D& poly);
};


class LeafNavMesh {
public:
	vector<LeafNode> nodes;
	LeafOctree* octree; // finds nearby leaves from any point in space, even outside of the BSP tree
	uint16_t leafMap[MAX_MAP_CLIPNODE_LEAVES]; // maps a BSP leaf index to nav mesh node index
	vector<vector<LeafNode>> bspModelLeaves; // cached entity model leaves
	vector<LeafNode> bspModelNodes; // cached entity model nodes
	int hull; // which hull this mesh represents
	bool forHumans; // nav mesh is for human navigation, not just a linked graph of leaves

	LeafNavMesh();

	~LeafNavMesh();

	LeafNavMesh(vector<LeafNode> polys, LeafOctree* octree);

	bool addLink(int from, int to, Polygon3D linkArea);

	void clear();

	vector<int> AStarRoute(int startNodeIdx, int endNodeIdx);

	vector<int> dijkstraRoute(int start, int end);

	float path_cost(int a, int b);

	int getNodeIdx(Bsp* map, Entity* ent);

	// accounts for leaves that have been split by entities
	uint16_t getNodeIdx(Bsp* map, vec3 pos);

	// unsplits a node that was divided by one or more entities
	// use when the entities that did the splitting have moved/rotated
	void unsplitNode(uint16_t idx);

	// splits nodes again when entities change
	void refreshNodes(Bsp* map);

	// verifies all node ids and links are valid
	bool validate();

	LeafNode* findEntNode(int entidx);

private:	
};