**0**

###
#1
Members - Reputation: **122**

Posted 19 May 2006 - 01:48 AM

###
#2
Members - Reputation: **220**

Posted 19 May 2006 - 04:00 AM

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:

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.

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.

###
#4
Members - Reputation: **864**

Posted 22 May 2006 - 03:21 PM

Does that make sense?

Cheers,

Timkin

###
#5
Members - Reputation: **122**

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

###
#6
Members - Reputation: **122**

Posted 22 May 2006 - 10:00 PM

Quote:

Original post by figQuote:

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.

###
#7
Members - Reputation: **864**

Posted 23 May 2006 - 01:50 PM

Quote:

Original post by fig

I 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 gorogoro

But 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:

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

###
#9
Moderators - Reputation: **7867**

Posted 23 May 2006 - 02:41 PM

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

###
#10
Members - Reputation: **122**

Posted 23 May 2006 - 09:39 PM

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

###
#11
Members - Reputation: **864**

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.

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

###
#12
Members - Reputation: **122**

Posted 24 May 2006 - 10:59 PM

Quote:

Original post by TimkinQuote:

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

###
#13
Members - Reputation: **1110**

Posted 24 May 2006 - 11:26 PM

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

Posted 25 May 2006 - 12:18 AM

I'm very interested to try out the k-d tree stuff.

Can you please share your implemenation of it?

Thanks.

Bob

###
#15
Members - Reputation: **864**

Posted 29 May 2006 - 08:52 PM

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 *

* *

* 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

**treetype_utility.h**

/*

**************************************************************************

* *

* 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;

}

};

**bin.h**

/*

**************************************************************************

* *

* 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();

}

**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:

Posted 01 June 2006 - 01:35 AM

I will work my way through it.

Bob

###
#17
Members - Reputation: **864**

Posted 01 June 2006 - 02:26 PM

Quote:

Original post by Anonymous Poster

I 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