.:: Bots United ::. - View Single Post - Optimizing waypoint graph using an Octree

@$3.1415rin · **Re: Optimizing waypoint graph using an Octree -** 13-02-2005

i'm also using a hashtable, but only 2d, because you dont have too much diversity on the z axis for most maps. when a nearest waypoint is searched, the nearest bucket and all it's neighbours are searched, if nothing can be found, the old 'stupid' routine is called. but that shouldnt be the case too often, because when a player isnt near to a waypoint, a waypoint is added automatically.

An octtree would certainly be another good solution, but hashing was easier for me, because I didnt knew how to get the neighbouring buckets there fast (havnt worked much on it though), when i'm at a border of a big volume, i.e. the neighbour would be in quite another part of the tree, and we have to go down the tree because, I simply didnt like the idea of searching the other 'half' of the terrain.

	(#3)
@$3.1415rin Council Member, Author of JoeBOT Status: Offline Posts: 1,381 Join Date: Nov 2003 Location: Germany	Re: Optimizing waypoint graph using an Octree - 13-02-2005 i'm also using a hashtable, but only 2d, because you dont have too much diversity on the z axis for most maps. when a nearest waypoint is searched, the nearest bucket and all it's neighbours are searched, if nothing can be found, the old 'stupid' routine is called. but that shouldnt be the case too often, because when a player isnt near to a waypoint, a waypoint is added automatically. An octtree would certainly be another good solution, but hashing was easier for me, because I didnt knew how to get the neighbouring buckets there fast (havnt worked much on it though), when i'm at a border of a big volume, i.e. the neighbour would be in quite another part of the tree, and we have to go down the tree because, I simply didnt like the idea of searching the other 'half' of the terrain.