2 ms·
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
by nerdy 11y ago
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?
- jheriko 11y agoit 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...
- 33a 11y agoThere 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.