GameDev.net Posting Guidelines (please read before posting)
Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 19 May 2006 - 01:48 AM
Posted 19 May 2006 - 04:00 AM
Posted 22 May 2006 - 05:15 AM
Quote:
Original post by Steadtler
Ideally, you should spawn your agents at a given node, and keep track of its closest node as the game run.
If, for some reason, you can't do that, then you need a way to find the closest node to an agent position. This can be done is several ways, depending on your game. Brute force is a possibility. A distance map will probably take too much memory. A KD-tree might work well.
Posted 22 May 2006 - 03:21 PM
Posted 22 May 2006 - 07:34 PM
Quote:
You could do it on an oct tree and this should give you roughly equivalent efficiency results in the limit that your map is perfectly flat.
Posted 22 May 2006 - 10:00 PM
Quote:
Original post by fig Quote:
You could do it on an oct tree and this should give you roughly equivalent efficiency results in the limit that your map is perfectly flat.
I think you may be getting confused with a quad-tree. Even then, the map doesn't have to be flat, you just can't have a room on top of another room for instance.
An Octree would be my choice as well. Mostly because I use them often and know how to code them. :)
Posted 23 May 2006 - 01:50 PM
Quote:
Original post by fig
I think you may be getting confused with a quad-tree.
Quote:
Original post by gorogoro
But the same problem persist. How should I split the space? Since I just have some nodes connected performing a search graph.
Posted 23 May 2006 - 02:16 PM
Posted 23 May 2006 - 02:41 PM
Posted 23 May 2006 - 09:39 PM
Posted 24 May 2006 - 01:10 PM
Quote:
Original post by gorogoro
Guess I'm going to use an Octree for now, since I think I don't have the time to do a k-d Tree. I think the K-d Tree is the best choice for now, but I have already an Octree coded, so I'm going to adapt it to my needs.
Posted 24 May 2006 - 10:59 PM
Quote:
Original post by Timkin Quote:
Original post by gorogoro
Guess I'm going to use an Octree for now, since I think I don't have the time to do a k-d Tree. I think the K-d Tree is the best choice for now, but I have already an Octree coded, so I'm going to adapt it to my needs.
If you already have an Oct tree coded, then morphing it into a k-d tree wouldnt be very hard. Here's how:
Presumably you have a tree node data structure with eight child (subtree) pointers. Change this to two pointers, but add in two other attributes: keyID and keyPartitionValue. At each level of the tree (each node) you're going to select one of the dimensions and assign this to the keyID attribute (so either x, y or z... 0,1 or 2). You'll then choose a value in that dimension and partition all of the data as either being left of, or right of that partition. If the data is left of, then it goes in the left subtree and if it's right of, it goes in the right subtree.
Now, to choose the keyID and keyPartition values.
keyID: a good metric to use is minimum variance. Compute the variance of the data in each dimension (so if each triangle has a centre coordinate given by (x,y,z) then compute the variance of each column of the matrix made up of all centres). Choose the dimension with the largest variance and set this as the keyID (the dimension on which to partition).
keyPartitionValue: as for this, a reasonable choice is the value of the median
(middle) datum in keyID dimension.
These choices will ensure that your data is evenly distributed in your tree, but that your leaf node bin sizes vary so as to give an approximately uniform density at the leaf depth.
If you have any trouble with this, give me a holler. I have some C++ classes for a k-d tree implementation that I'd be happy to share.
Cheers,
Timkin
Posted 24 May 2006 - 11:26 PM
Posted 25 May 2006 - 12:18 AM
Posted 29 May 2006 - 08:52 PM
/*
**************************************************************************
* *
* Module: kdtree.h *
* *
* Author: Tim Wilkin *
* (c) March, 2004 *
* *
* Last Modified: 20 Apr 2006 *
* *
* This header declares the templated data storage classes *
* kdnode *
* kdtree *
* *
**************************************************************************
*/
#pragma once
#include <algorithm>
#include "treetype_utility.h"
// define a (hopefully) unique namespace
namespace TreeTypes{
/*
******************************************************************************
* kdnode class *
******************************************************************************
*/
template <typename BinType>
struct kdnode{
typedef BinType bin_type;
typedef typename bin_type::value_type vector_type;
typedef typename vector_type::value_type scalar_type;
typedef typename bin_type::size_type size_type;
typedef typename bin_type::iterator iterator;
typedef typename bin_type::const_iterator const_iterator;
typedef typename bin_type::reverse_iterator reverse_iterator;
typedef typename bin_type::const_reverse_iterator const_reverse_iterator;
kdnode *left, * right;
bin_type *data;
size_type keyID;
scalar_type keyPartition;
static size_type leafSize;
kdnode():left(NULL),
right(NULL),
data(NULL),
keyID(0),
keyPartition(0){}
kdnode(bin_type* _bin);
~kdnode();
bool isLeaf() const { return !this->left && !this->right;}
}; //<== End kdnode class declaration
/*
******************************************************************************
* kdtree class *
******************************************************************************
*/
template <typename BinType>
class kdtree{
public:
typedef BinType bin_type;
typedef kdnode<bin_type> node_type;
typedef typename bin_type::value_type vector_type;
private:
node_type* root;
public:
kdtree();
kdtree(const bin_type& _data, const size_t& leafsize=10);
~kdtree();
}; // <== End kdtree class declaration
// define the kdnode static member leafSize
template <typename V> typename kdnode<V>::size_type kdnode<V>::leafSize;
/*
******************************************************************************
* kdnode methods *
******************************************************************************
*/
template <typename B>
kdnode<B>::kdnode(bin_type* _data){
this->keyID = size_type(0);
this->keyPartition = scalar_type(0);
if (_data->size()<=kdnode<B>::leafSize){
this->data = _data;
this->left = NULL;
this->right = NULL;
}
else{
vector_type mu = mean<bin_type>(_data->begin(),_data->end());
vector_type var = variance<bin_type>(_data->begin(),_data->end());
scalar_type m = 0;
for (size_type i=0;i<var.size();i++){
if (var[i]>m){
m=var[i];
this->keyID=i;
}
}
this->keyPartition = mu[this->keyID];
iterator spliceIter = std::partition(
_data->begin(),
_data->end(),
std::bind2nd(less<vector_type>(this->keyID),
this->keyPartition
)
);
bin_type* right = new bin_type();
right->splice(right->end(),*_data,spliceIter,_data->end());
if (right->size()==0){
this->data = _data;
this->left = NULL;
this->right = NULL;
}
else if (_data->size()==0){
this->data = right;
this->left = NULL;
this->right = NULL;
}
else{
this->data = NULL;
this->left = new kdnode(_data);
this->right = new kdnode(right);
}
}
} // <== end kdnode constructor definition
template <typename B>
kdnode<B>::~kdnode(){
if (this->isLeaf()){
if (!data->empty())
data->clear();
delete data;
}
else{
if (this->left){
delete this->left;
this->left = 0;
}
if (this->right){
delete this->right;
this->right = 0;
}
}
} // <== end kdnode destructor definition
/*
******************************************************************************
* kdtree methods *
******************************************************************************
*/
template <typename B>
kdtree<B>::kdtree(){
root = new node_type();
}
template <typename B>
kdtree<B>::kdtree(const typename kdtree<B>::bin_type& _data,
const size_t& leafsize){
node_type::leafSize = leafsize;
bin_type* pBin = new bin_type(_data);
root = new node_type(pBin);
}
template <typename B>
kdtree<B>::~kdtree(){
delete root;
}
} // <== End TreeTypes namespace declaration
/*
**************************************************************************
* *
* Module: treetype_utility.h *
* *
* Author: Tim Wilkin *
* (c) March, 2004 *
* *
* Last Modified: 30 May 2006 *
* *
* This header declares template utility functions and classes *
* for use in treetype_kdtree *
* *
**************************************************************************
*/
#pragma once
/*
******************************************************************************
* utility functions *
******************************************************************************
*
* These functions make certain assumptions about the type SetType::value_type,
* that is, the type herein called vector_type. This type must support the
* following operations:
* constructors:
* default - vector_type()
* sized - vector_type(const scalar_type &, const size_type&)
* copy - vector_type(const vector_type&)
*
* mathematical operators:
* operator+=
* operator-=
* operator/=
* operator*
*
* An example of a type that supports these methods is std::valarray
*/
template <typename SetType>
typename SetType::value_type mean(typename SetType::const_iterator& first, typename SetType::const_iterator& last){
typedef SetType::value_type vector_type;
typedef vector_type::value_type scalar_type;
SetType::difference_type d = std::distance(first,last);
if (d==0)
return vector_type();
else if (d==1)
return *first;
else{
size_t dim = first->size();
vector_type buffer(*first);
SetType::const_iterator setIter = first;
setIter++;
for (; setIter!=last; setIter++)
buffer += *setIter;
return buffer/=(scalar_type)d;
}
}
template <typename SetType>
typename SetType::value_type variance(typename SetType::const_iterator& first, typename SetType::const_iterator& last){
typedef SetType::value_type vector_type;
typedef vector_type::value_type scalar_type;
SetType::difference_type d = std::distance(first,last);
if (d==0)
return vector_type();
else{
size_t dim = first->size();
vector_type sum((scalar_type)0,dim);
if (d==1)
return sum;
else{
vector_type mu(mean<SetType>(first,last));
SetType::const_iterator setIter = first;
for (; setIter!=last; setIter++){
vector_type buffer(*setIter);
buffer -= mu;
sum += (buffer * buffer);
}
return sum/=(scalar_type)(d-1); // unbiased variance
}
}
}
/*
******************************************************************************
* utility classes *
******************************************************************************
*
* less<VectorType> is a simple functor providing an indexed less than operator
* for objects of a vector class. This functor assumes that VectorType supports
* subscripted indexing via VectorType::operator[](const size_t& i).
*
*/
template <typename VectorType>
class less: public std::binary_function<VectorType, typename VectorType::value_type, bool>{
public:
typedef VectorType vector_type;
typedef typename vector_type::value_type value_type;
private:
const size_t index;
public:
less(const size_t& i):index(i){};
bool operator()(const vector_type& vec, const value_type& val) const{
return vec[index]<val;
}
};
/*
**************************************************************************
* *
* Module: bin.h *
* *
* Author: Tim Wilkin *
* (c) March, 2004 *
* *
* Last Modified: 30 May 2006 *
* *
* This header declares the template data storage class kdbin *
* *
**************************************************************************
*/
#pragma once
// required headers, since kdbin is just an adaptor for std::list in this example
// You could do anything with this class, so long as it maintains this interface
// (or you appropriately change the kdnode class)
#include <list>
/*
******************************************************************************
* kdbin class *
******************************************************************************
*
* kdbin is an example of a custom bin class that could be used with the
* kdtree class. It shows the minimum interface required by the tree
* constructors
*/
template <typename VectorType>
class kdbin{
public:
typedef VectorType value_type;
typedef std::list<value_type> container_type;
typedef typename container_type::size_type size_type;
typedef typename container_type::iterator iterator;
typedef typename container_type::const_iterator const_iterator;
typedef typename container_type::reverse_iterator reverse_iterator;
typedef typename container_type::const_reverse_iterator const_reverse_iterator;
typedef typename container_type::difference_type difference_type;
private:
container_type bin;
public:
kdbin();
~kdbin();
kdbin(const kdbin& rhs);
kdbin& operator=(const kdbin& rhs);
const size_type size() const;
bool empty() const;
void insert(iterator _Where, const value_type& _Value);
void push_back(const value_type& _Value);
void splice(iterator _Where, kdbin& _Right, iterator _First, iterator _Last);
void erase(iterator _Where);
void clear();
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
}; //<== End class declaration
/*
******************************************************************************
* kdbin methods *
******************************************************************************
*/
// constructor (default)
template <typename V>
kdbin<V>::kdbin():bin(){}
// destructor
template <typename V>
kdbin<V>::~kdbin(){
bin.clear();
}
// constructor (copy)
template <typename V>
kdbin<V>::kdbin(const kdbin<V>& rhs){
if (&rhs!=this){
if (!this->bin.empty())
bin.clear();
const_iterator rhsIter = rhs.begin();
for (; rhsIter!=rhs.end(); rhsIter++)
bin.push_back(*rhsIter);
}
}
// operator (assignment)
template <typename V>
kdbin<V>& kdbin<V>::operator =(const kdbin<V>& rhs){
if (&rhs!=this){
this->bin = rhs.bin;
this->buf = rhs.buf;
}
return *this;
}
// method (size)
// returns number of elements in bin
template <typename V>
const typename kdbin<V>::size_type kdbin<V>::size() const{
return bin.size();
}
// method (empty)
// returns true if size==0
template <typename V>
bool kdbin<V>::empty() const{
return bin.empty();
}
// method (insert)
// insert a vector at the given position
template <typename V>
void kdbin<V>::insert(iterator _Where, const value_type& _Value){
bin.insert(_Where, _Value);
}
// method (push_back)
// insert a vector after the last vector currently stored
template <typename V>
void kdbin<V>::push_back(const value_type& _Value){
bin.push_back(_Value);
}
// method (splice)
// remove vectors from the argument bin (_right), starting at _first and ending
// at last vector before _last, then insert them into the target bin (this->bin)
template <typename V>
void kdbin<V>::splice(iterator _where, kdbin<V>& _right, iterator _first, iterator _last){
bin.splice(_where,_right.bin,_first,_last);
}
template <typename V>
void kdbin<V>::erase(iterator _Where){
bin.erase(_Where);
}
// method (clear)
// delete all vectors stored in the bin
template <typename V>
void kdbin<V>::clear(){
bin.clear();
}
// method (begin)
// return iterator pointing to first stored vector
template <typename V>
typename kdbin<V>::iterator kdbin<V>::begin(){
return bin.begin();
}
// method (end)
// return iterator pointing one beyond last stored vector
template <typename V>
typename kdbin<V>::iterator kdbin<V>::end(){
return bin.end();
}
// method (begin) (const)
// return a constant iterator pointing to first stored object
template <typename V>
typename kdbin<V>::const_iterator kdbin<V>::begin() const{
return bin.begin();
}
// method (end) (const)
// return constant iterator pointing one beyond last stored vector
template <typename V>
typename kdbin<V>::const_iterator kdbin<V>::end() const{
return bin.end();
}
// include time.h and stdio.h just for this example
#include <time.h>
#include <stdio.h>
#include <valarray>
// use either an STL container like std::list<>, or a custom container like kdbin<>
#include "bin.h"
#include <list>
// include kdtree.h for tree template classes
#include "treetype_kdtree.h"
int main(void){
typedef float value_type;
typedef std::valarray<value_type> vector_type;
// typedef kdbin<vector_type> bin_type;
typedef std::list<vector_type> bin_type;
typedef TreeTypes::kdtree< bin_type> tree_type;
bin_type data;
vector_type tmpVec(3);
srand( (unsigned)time( NULL ) );
for (size_t i=0; i<16; i++){
for (size_t j=0; j<tmpVec.size(); j++)
tmpVec[j] = (value_type)(2 * rand() - RAND_MAX) / (value_type)RAND_MAX;
data.push_back(tmpVec);
}
// test the creation and destruction of a dynamic tree object
tree_type *pTree = new tree_type(data,25);
delete pTree;
// test the use of the tree as a heap object
tree_type myTree(data);
// now test the ability to directly create a tree as a dynamic, recursivel constructed
// kdnode object
bin_type *pBin = new bin_type(data);
tree_type::node_type *pNode = new tree_type::node_type(pBin);
delete pNode;
// be careful here, since pBin is cleaned up when you delete the root node of the tree
// and hence pBin itself now points to inaccessible memory... trying to derefence it
// now would cause a segmentation fault... hence the use of the kdtree class to wrap
// the recursive creation of the tree from a static source object (data) safely
// now try building a tree using a std::list<> as the bin type!
//typedef std::list<vector_type> list_type;
//list_type myList(data.begin(),data.end());
//TreeTypes::kdtree<list_type> *pRoot = new TreeTypes::kdtree<list_type>(myList);
//delete pRoot;
return 0;
}
Posted 01 June 2006 - 01:35 AM
Posted 01 June 2006 - 02:26 PM
Quote:
Original post by Anonymous Poster
I will work my way through it.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.