Pathfinding: Jan Paul van Waveren style

[pbmax]

does anyone here have experience in creating a pathfinding system that is akin to mr. elusive's quake3 aas system? i.e., creating empty convex hulls via spatial partitioning.

as a "fun" project, i'd like to create one for quake wars that would support bots and ai. the engine and the game assets would make an awesome single player mod! i'm going crazy just thinking how awesome a sp mod could be. think farcry but only 10x better .

but i'm doing this completely from scratch and i do not have any prior coding experience in spatial partitioning or pathfinding for that matter. so needless to say, its slow going. oh yeah, i don't want manual waypoint placement. i'm aiming for a fully automated system.

i was kinda bummed to find out that id might already be working on bots for quake wars, but i'm gonna proceed nonetheless. at the very least, its a good learning experience.

[DrEvil]

Usually those types of algorithms pull data directly from the bsp, which modders don't have access to much of the time. There are bsp tools for HL and probably quake, but given that ET:QW is heavily terrain based, and AAS sucks on terrain, you would need some method to handle terrain better.

I'm working on a navigation mesh that gets built without bsp access, which I can't rely on since my bot is cross engine/mod, and I want to better support terrain. I don't get to spend a ton of time on it since I'm also working on FF bots, but if u want to read a bit about it visit here:
http://www.omni-bot.de/e107/e107_plu...topic.php?4142

AI Wisdom and Game Gems books talk extensively about nav meshes, which is essentially what AAS is.

[pbmax]

oh yeah, terrain... you don't think a kd-tree would work well? i've done some research on this. i've found an interesting ray tracing algorithm that use kd-trees for optimization. the kd-tree is combined with a heuristic that maximizes empty spaces (convex hulls). this is different then most trees because the hueristic makes the tree unbalanced which normally you don't want. but for ray tracing (and pathfinding?) this results in a large performance increase.

i emailed jan Paul a few weeks ago about various pathfinding methods. he hinted that ideally, i should use a method that fully represents the configuration space in 3d. i think this would eliminate navmeshes and other 2d (or 2.5d) methods.

i dunno if he was referring to quake wars or thier new game, but it seemed to me that he thought navigation in 3 dimensions is important. this would make sense for quake wars since it has numerous flying vehicles and flying npc's.

he also said that he is ditching the q3 aas for another technique. now i'm all confused! lol.

i'm going to check out probabilistic roadmaps, a pathfinding method used quite a bit in robotics.... this is starting to drive me crazy.

[DrEvil]

Nav meshes are 3d. They can have overlapping surfaces and all that. They are basically an optimized copy of the world geometry minus the non walkable surfaces. Personally I would treat flying differently anyways. Flyers have a vast empty space to navigate, they don't really need to use A*. Ground vehicles and infantry are restricted to walkable surfaces for the most part, and a nav mesh is perfect to represent that. The air above the ground is typically empty enough where you don't need to perform searches on it.

[SamPlay]

Hy,
May be you will find useful ideas at http://www.gamebotfactory.com/gdtoolbox/
under the "waypoint-less nav" chapter.

[pbmax]

Originally Posted by SamPlay

Hy,
May be you will find useful ideas at http://www.gamebotfactory.com/gdtoolbox/
under the "waypoint-less nav" chapter.

thanks, i'll check that out.

i've already started on a method to accurately describe the free configuration space. basically, i'm going to decompose it into a set of connected convex polyhdra. thus, this will be a fully 3 dimensional path finding system. why 3d? becauce i'd like to have flying and crawling npc's be able to navigate in a complex environment.

the problem is that this has not been done in video games yet as far as i know. i had a very hard time finding info in the the field of robotics as well. out of thousands of research papers, i found one robot guy that did something very similar. most other 3d robot pathfinding is done with probablistic road maps...