DetourNode.h

Go to the documentation of this file.

//
// Copyright (c) 2009-2010 Mikko Mononen [email protected]
//
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
// arising from the use of this software.
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
// 1. The origin of this software must not be misrepresented; you must not
// claim that you wrote the original software. If you use this software
// in a product, an acknowledgment in the product documentation would be
// appreciated but is not required.
// 2. Altered source versions must be plainly marked as such, and must not be
// misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//

#ifndef DETOURNODE_H
#define DETOURNODE_H

#include "DetourNavMesh.h"

enum dtNodeFlags
{
 DT_NODE_OPEN = 0x01,
 DT_NODE_CLOSED = 0x02,
 DT_NODE_PARENT_DETACHED = 0x04, // parent of the node is not adjacent. Found using raycast.
};

typedef unsigned short dtNodeIndex;
static const dtNodeIndex DT_NULL_IDX = (dtNodeIndex)~0;

struct dtNode
{
 float pos[3]; 
 float cost; 
 float total; 
 unsigned int pidx : 24; 
 unsigned int state : 2; 
 unsigned int flags : 3; 
 dtPolyRef id; 
};


static const int DT_MAX_STATES_PER_NODE = 4; // number of extra states per node. See dtNode::state



class dtNodePool
{
public:
 dtNodePool(int maxNodes, int hashSize);
 ~dtNodePool();
 inline void operator=(const dtNodePool&) {}
 void clear();

 // Get a dtNode by ref and extra state information. If there is none then - allocate
 // There can be more than one node for the same polyRef but with different extra state information
 dtNode* getNode(dtPolyRef id, unsigned char state=0); 
 dtNode* findNode(dtPolyRef id, unsigned char state);
 unsigned int findNodes(dtPolyRef id, dtNode** nodes, const int maxNodes);

 inline unsigned int getNodeIdx(const dtNode* node) const
 {
 if (!node) return 0;
 return (unsigned int)(node - m_nodes)+1;
 }

 inline dtNode* getNodeAtIdx(unsigned int idx)
 {
 if (!idx) return 0;
 return &m_nodes[idx-1];
 }

 inline const dtNode* getNodeAtIdx(unsigned int idx) const
 {
 if (!idx) return 0;
 return &m_nodes[idx-1];
 }
 
 inline int getMemUsed() const
 {
 return sizeof(*this) +
 sizeof(dtNode)*m_maxNodes +
 sizeof(dtNodeIndex)*m_maxNodes +
 sizeof(dtNodeIndex)*m_hashSize;
 }
 
 inline int getMaxNodes() const { return m_maxNodes; }
 
 inline int getHashSize() const { return m_hashSize; }
 inline dtNodeIndex getFirst(int bucket) const { return m_first[bucket]; }
 inline dtNodeIndex getNext(int i) const { return m_next[i]; }
 inline int getNodeCount() const { return m_nodeCount; }
 
private:
 
 dtNode* m_nodes;
 dtNodeIndex* m_first;
 dtNodeIndex* m_next;
 const int m_maxNodes;
 const int m_hashSize;
 int m_nodeCount;
};

class dtNodeQueue
{
public:
 dtNodeQueue(int n);
 ~dtNodeQueue();
 inline void operator=(dtNodeQueue&) {}
 
 inline void clear()
 {
 m_size = 0;
 }
 
 inline dtNode* top()
 {
 return m_heap[0];
 }
 
 inline dtNode* pop()
 {
 dtNode* result = m_heap[0];
 m_size--;
 trickleDown(0, m_heap[m_size]);
 return result;
 }
 
 inline void push(dtNode* node)
 {
 m_size++;
 bubbleUp(m_size-1, node);
 }
 
 inline void modify(dtNode* node)
 {
 for (int i = 0; i < m_size; ++i)
 {
 if (m_heap[i] == node)
 {
 bubbleUp(i, node);
 return;
 }
 }
 }
 
 inline bool empty() const { return m_size == 0; }
 
 inline int getMemUsed() const
 {
 return sizeof(*this) +
 sizeof(dtNode*)*(m_capacity+1);
 }
 
 inline int getCapacity() const { return m_capacity; }
 
private:
 void bubbleUp(int i, dtNode* node);
 void trickleDown(int i, dtNode* node);
 
 dtNode** m_heap;
 const int m_capacity;
 int m_size;
}; 


#endif // DETOURNODE_H