• Create Account

Old topic!

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.

16 replies to this topic

### #1gorogoro  Members   -  Reputation: 122

Like
0Likes
Like

Posted 19 May 2006 - 01:48 AM

Hi! I'm using a navigation mesh for my A* path Finding! Everything is set up and working.. My problem now is how do I do the mapping between my agents in the pathFinding structure and the game world?? I mean, I have the nodes conected to another nodes, building a graph system with pointers. Every node has an unique ID, it's position, and the triangle from the mesh, and other stuff.. My pathFinding algorithm accepts two id's the id where the agent is, and the id to where it wants to go. My question is in the game world, the entity only have a position, How can I now wich node of the graph it belongs??? Ideas please.......

### #2Steadtler  Members   -  Reputation: 220

Like
0Likes
Like

Posted 19 May 2006 - 04:00 AM

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.

### #3 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 22 May 2006 - 05:15 AM

Quote:
 Original post by SteadtlerIdeally, 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.

I'm thinking of using an octree.. Now I don't how can I contruct such a tree :s..I have to map the nodes ids to it's positions and costruct the Octree accordingly. Argh..

Is this the correct procedure? How do ppl usually do this kind of stuff?
I can't find any usefull information on the books and papers.

### #4Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 22 May 2006 - 03:21 PM

As Staedtler pointed out, a tree based nearest neighbour search would be appropriate. At compile time you can construct a tree decomposition of your game world surface ('map'). Then, when you want to find the nearest mesh element to the agent (presumably the one it is standing on ;) ) you perform a nearest neighbour search using your tree. A k-d tree is an efficient data structure for performing this search. 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.

Does that make sense?

Cheers,

Timkin

### #5fig  Members   -  Reputation: 122

Like
0Likes
Like

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.

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. :)

### #6gorogoro  Members   -  Reputation: 122

Like
0Likes
Like

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. :)

Yeas Yeasterday I remembered that problem: "what if, I have a room on the top of the other room?? Ahh.. Fuck..". Guess quad-tree is better just for terrain.

But the same problem persist. How should I split the space? Since I just have some nodes connected performing a search graph.

### #7Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 23 May 2006 - 01:50 PM

Quote:
 Original post by figI think you may be getting confused with a quad-tree.

Hehe... not confused... just one of those days where you're thinking one thing and writing another. Call it a brain fart! Thanks for picking up the error. 8)

Quote:
 Original post by gorogoroBut the same problem persist. How should I split the space? Since I just have some nodes connected performing a search graph.

Okay, lets take a step back for a moment and consider the problem from an external perspective. You have a (presumably 2-d) surface (lets call it the map) embedded in a 3-d space and you want to overlay this surface with a navigation mesh for pathfinding. Having done this, you want any object/agent/etc situated at a known location on the map to be able to use the mesh to find a path to any other location.

Issues concerning mesh creation. If the surface is not 2-d but instead is a representation of say a building with multiple floors connected by stairs and elevators, then you have two ways of handling this. The first is perhaps the simplest, portals, while the second is more elegant (but not worth doing for many problems), 3-d map with transition constraints.

Portals are just as they sound. Points on a map where you can transition to another point on the map. You essentially split your 3-d surface into a set of minimally connected 2-d maps with portals acting as connections between them. So, you have two rooms connected by stairs? The stairs become a portal connecting 2 meshes, one for each room. Portals may be 1-way or 2-way.

Map constraints act similar to portals, but are not as binary. You can still represent your surface as a 3-d map, but you must constrain the connectivity nav-mesh nodes while pathfinding based on map surface constraints (like surface gradient, existance of barriers, etc). In most instances, such a constraint can be precomputed and handled using the portals method.

Issues concerning using the mesh
Once you have a mesh, then you decompose the mesh nodes based on a tree decomposition. For a given location on the map, use that location as a query to a nearest neighbour search using the tree. If you're using portals, then you'll need to treat portals as mesh nodes. If you're using map constraints, then you need to perform a constrained nearest neighbour search (the neighbour must satisfy local constraints for the agent to be able to move to it). You do the same thing for the goal location; find it's nearest neighbour in the tree.

You now have two nodes on your nav mesh as the focus of your pathfinding query.

As for finding nearest neighbours on a k-d tree... there's plenty of literature and code snippets available. Try [google] using 'k d tree nearest neighbour algorithm'.

Good luck,

Timkin

[Edited by - Timkin on May 23, 2006 8:50:13 PM]

### #8 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 23 May 2006 - 02:16 PM

A navmesh is often a seperate structure -- it can be a simplification of the rendered mesh (fewer triangles will speed up your A* significantly).

You can also add data like a list of adjacent triangles for each triangle -- to speed up position determination (you use a point-intersect-triangle calculation and a lazy optimization is to check the navmesh triangle the unit was previously on first, and then check against the short list of adjacent triangles before doing a wider search using quadtree, etc...

### #9hplus0603  Moderators   -  Reputation: 10320

Like
0Likes
Like

Posted 23 May 2006 - 02:41 PM

Just do a raycast from the center of your entity straight down for X meters to see what triangle it hits. Whatever triangle is nearest in the navigation mesh, is the triangle that your entity is on. If you hit no triangle, the entity is likely in freefall, or your nav mesh is not complete.

If you're using DirectX, there's a simple function to do raycast into a triangle mesh. It's kind-of slow for large meshes, though -- faster would be to put your triangles into a hash grid or a quadtree, to accelerate this ray query (easy when you know the query will always be done downwards).

### #10gorogoro  Members   -  Reputation: 122

Like
0Likes
Like

Posted 23 May 2006 - 09:39 PM

Thanks for the Help Guys! :)

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.

My NavMesh s not rendered. It is a simplificatoin of the floor, and each triangle is a nav node (instead of each vertice :)).

### #11Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 24 May 2006 - 01:10 PM

Quote:
 Original post by gorogoroGuess 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

### #12gorogoro  Members   -  Reputation: 122

Like
0Likes
Like

Posted 24 May 2006 - 10:59 PM

Quote:
Original post by Timkin
Quote:
 Original post by gorogoroGuess 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

Thanks a lot for the help guys!!!
I make it with an octree already.
Since it is done it was very easy. I have a struct called triangle wich have the indexes of the vertices of a given triangle and an index (the Navigation Graph indexes) struct Triangle{int A; int B; int C; int index:}
The Octree guards this triangle information (I think I've made it with 6 triangle per leaf or something like that). given a certain position the Octree gives me the leaves where it could be. Then I make an intersction using the bounding sphere of the agent to the leaves returned, and keep de smallest distance between the agent position and the leaves intersected by the bounding sphere. The smallest distance is the nearest cell, since I have the index of the cell in the triangle struct it's easy :)

Well when the things are done and working it seems easy. But in the beggining I wasn't really shure how I would do the thing.

We have to build a mini playable demo until july, so the kd tree is going to wait. Until then more problems are going to come :)

### #13DrEvil  Members   -  Reputation: 1128

Like
0Likes
Like

Posted 24 May 2006 - 11:26 PM

I have a nav mesh related question. A while back I was thinking a bit about a nav mesh implementation and what I was considering was letting opcode generate its AABB tree and simply doing ray queries with the tree as hplus0603 mentioned to find the node the agent is in. I figured it would be pretty efficient, and have good opportunity to use the temporal coherence functionality and such. Opcode supports 4 different tree types to build with. Any idea how this method might compare with the nearest neighbor tree search that you are speaking of Timkin?

### #14 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 25 May 2006 - 12:18 AM

Timkin,
I'm very interested to try out the k-d tree stuff.
Thanks.
Bob

### #15Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 29 May 2006 - 08:52 PM

Sorry for the delay in responding to the above request... I've been rather busy lately.

Okay, I've stripped out my kdtree implementation from one of my projects. What is presented herein is barebones stuff. To use it, you need to add functionality to the kdtree class appropriate to the task at hand. The code below is offered "as is" and no warranties or support are offered. Use it at your own risk. I've included a little test program that should run compile with 0 errors and 0 warnings under VC++ 7.0 and run cleanly with no memory leaks. It shows you some of the basic ways to create a tree using the supplied classes.

If you want a more full-blooded example of the use of this code (as in, for a nearest neighbour search) I might be prepared to share example code, but only if I know it is to be used for non-commericial or research purposes (but not for school assignments). Send me an email if you need this with an explanation as to why.

Anyway, here it is...

treetype_kdtree.h

/*
**************************************************************************
*                                                                        *
*    Module: kdtree.h                                                    *
*                                                                        *
*    Author: Tim Wilkin                                                  *
*            (c) March, 2004                                             *
*                                                                        *
*                                                                        *
*    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



treetype_utility.h

/*
**************************************************************************
*                                                                        *
*    Module: treetype_utility.h                                          *
*                                                                        *
*    Author: Tim Wilkin                                                  *
*            (c) March, 2004                                             *
*                                                                        *
*                                                                        *
*    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;
}
};



bin.h

/*
**************************************************************************
*                                                                        *
*    Module: bin.h                                                       *
*                                                                        *
*    Author: Tim Wilkin                                                  *
*            (c) March, 2004                                             *
*                                                                        *
*                                                                        *
*    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();
}



treetype_test.cpp

// 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;
}



### #16 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 01 June 2006 - 01:35 AM

Thank you very much Timkin! :)

I will work my way through it.

Bob

### #17Timkin  Members   -  Reputation: 864

Like
0Likes
Like

Posted 01 June 2006 - 02:26 PM

Quote:
 Original post by Anonymous PosterI will work my way through it.

If you have any questions about the code, its structure or my design thoughts, just holler.

Of course, what is posted above is only one of many ways to construct classes for tree construction... and I'm sure it's not the best one either! It does the job though and should be easy to follow. ;)

Cheers,

Timkin

Old topic!

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.

PARTNERS