diff options
Diffstat (limited to 'extern/recastnavigation/Detour/Source/DetourNode.cpp')
-rw-r--r-- | extern/recastnavigation/Detour/Source/DetourNode.cpp | 140 |
1 files changed, 140 insertions, 0 deletions
diff --git a/extern/recastnavigation/Detour/Source/DetourNode.cpp b/extern/recastnavigation/Detour/Source/DetourNode.cpp new file mode 100644 index 00000000000..1a2305fcede --- /dev/null +++ b/extern/recastnavigation/Detour/Source/DetourNode.cpp @@ -0,0 +1,140 @@ +// +// Copyright (c) 2009 Mikko Mononen memon@inside.org +// +// 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. +// + +#include "DetourNode.h" +#include <string.h> + +////////////////////////////////////////////////////////////////////////////////////////// +dtNodePool::dtNodePool(int maxNodes, int hashSize) : + + m_nodes(0), + m_first(0), + m_next(0), + m_maxNodes(maxNodes), + m_hashSize(hashSize), + m_nodeCount(0) +{ + m_nodes = new dtNode[m_maxNodes]; + m_next = new unsigned short[m_maxNodes]; + m_first = new unsigned short[hashSize]; + memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize); + memset(m_next, 0xff, sizeof(unsigned short)*m_maxNodes); +} + +dtNodePool::~dtNodePool() +{ + delete [] m_nodes; + delete [] m_next; + delete [] m_first; +} + +void dtNodePool::clear() +{ + memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize); + m_nodeCount = 0; +} + +const dtNode* dtNodePool::findNode(unsigned int id) const +{ + unsigned int bucket = hashint(id) & (m_hashSize-1); + unsigned short i = m_first[bucket]; + while (i != 0xffff) + { + if (m_nodes[i].id == id) + return &m_nodes[i]; + i = m_next[i]; + } + return 0; +} + +dtNode* dtNodePool::getNode(unsigned int id) +{ + unsigned int bucket = hashint(id) & (m_hashSize-1); + unsigned short i = m_first[bucket]; + dtNode* node = 0; + while (i != 0xffff) + { + if (m_nodes[i].id == id) + return &m_nodes[i]; + i = m_next[i]; + } + + if (m_nodeCount >= m_maxNodes) + return 0; + + i = (unsigned short)m_nodeCount; + m_nodeCount++; + + // Init node + node = &m_nodes[i]; + node->pidx = 0; + node->cost = 0; + node->total = 0; + node->id = id; + node->flags = 0; + + m_next[i] = m_first[bucket]; + m_first[bucket] = i; + + return node; +} + + +////////////////////////////////////////////////////////////////////////////////////////// +dtNodeQueue::dtNodeQueue(int n) : + m_heap(0), + m_capacity(n), + m_size(0) +{ + m_heap = new dtNode*[m_capacity+1]; +} + +dtNodeQueue::~dtNodeQueue() +{ + delete [] m_heap; +} + +void dtNodeQueue::bubbleUp(int i, dtNode* node) +{ + int parent = (i-1)/2; + // note: (index > 0) means there is a parent + while ((i > 0) && (m_heap[parent]->total > node->total)) + { + m_heap[i] = m_heap[parent]; + i = parent; + parent = (i-1)/2; + } + m_heap[i] = node; +} + +void dtNodeQueue::trickleDown(int i, dtNode* node) +{ + int child = (i*2)+1; + while (child < m_size) + { + if (((child+1) < m_size) && + (m_heap[child]->total > m_heap[child+1]->total)) + { + child++; + } + m_heap[i] = m_heap[child]; + i = child; + child = (i*2)+1; + } + bubbleUp(i, node); +} |