This is insanely cool. I do game dev for a living, and pathfinding is one of the biggest hassles.
Right now, it's in a weird spot where it's sort of free, since you can offload to other cores that would otherwise remain idle. But as Mantle and other multithreading APIs take off, and engines get smarter about multi core, it's going to go back to being a big bottleneck.
This is the kind of thing that could create a truly EPIC game.
It's just one of the components. For EPIC game you need some extraordinary game mechanics or graphics or story. Well, probably a combination of at least two of those three.
We've seen a few grid A-star/grid-based pathfinding articles and tools now and they're really interesting but every time I see one I can't help but think, "how is pathfinding done for games which are not a grid?"
For example in an open-world type MMO or FPS game position is a floating point number. Does the game engine break the area down into smaller polygons?
If so is that mesh 3D? If so what happens if something isn't at the appropriate Z-axis? For example if AI is chasing a player and the player jumps how does the AI know the human player is on the same plane? And how does it differentiate that from the human being on another ground level slightly above/below it?
it varies from game to game. most often there is some kind of sparse 'navmesh' containing nodes in a 'grid' for doing the classical part of path finding. its possible to do this sort of thing automatically if you split the world into volumes as well, but its more difficult to get very fast, good results (i.e. you can't hack the data by hand so easily).
as well as that there will be some (usually quite off the cuff, hacky) logic to get a character from wherever they are to the nearest node (or its vicinity) and something to avoid them from hitting each other (too much)
there is nothing special about the 3d part, you just make the mesh in 3d and respect the constraints of gravity, player movement etc. so that you can't connect nodes badly
the floating point number thing is not important. any pathfinding can be made to have this 'extra complexity' if you simply go between the points over time smoothly...
There are different methods, but for many 3D games people use navmeshes for planning. Grids are kind of neat in that there are lots of little tricks you can use to speed things up and many geometric queries turn out to be way simpler.
Reminds me that most optimisation is an exercise in caching, although I'd be curious how this compares to even more cache-y approaches. (e.g. complete lookup as a naive example)
PVS/VSD applies to all kinds of problems, its nice to see someone else doing it. Split the world into convex volumes with connectivity information and suddenly the toolbox of algorithms at your disposal explodes... :)
still surprised that games developers don't do it more... there are physics, audio, networking and other optimisations to be had from splitting the world properly and having good connectivity information.
11 comments
[ 3.7 ms ] story [ 37.9 ms ] threadRight now, it's in a weird spot where it's sort of free, since you can offload to other cores that would otherwise remain idle. But as Mantle and other multithreading APIs take off, and engines get smarter about multi core, it's going to go back to being a big bottleneck.
This is the kind of thing that could create a truly EPIC game.
For example in an open-world type MMO or FPS game position is a floating point number. Does the game engine break the area down into smaller polygons?
If so is that mesh 3D? If so what happens if something isn't at the appropriate Z-axis? For example if AI is chasing a player and the player jumps how does the AI know the human player is on the same plane? And how does it differentiate that from the human being on another ground level slightly above/below it?
as well as that there will be some (usually quite off the cuff, hacky) logic to get a character from wherever they are to the nearest node (or its vicinity) and something to avoid them from hitting each other (too much)
there is nothing special about the 3d part, you just make the mesh in 3d and respect the constraints of gravity, player movement etc. so that you can't connect nodes badly
the floating point number thing is not important. any pathfinding can be made to have this 'extra complexity' if you simply go between the points over time smoothly...
PVS/VSD applies to all kinds of problems, its nice to see someone else doing it. Split the world into convex volumes with connectivity information and suddenly the toolbox of algorithms at your disposal explodes... :)
still surprised that games developers don't do it more... there are physics, audio, networking and other optimisations to be had from splitting the world properly and having good connectivity information.