Hi. I know how nodes and waypoints work in 2D games, and how to perform A* on them, but on 3D is a little harder. I obviously can't have a node network for performance reasons, as i'd have to check if each node is colliding with anything. So how would be the best way to handle waypoints in a 3D game? It is a FPS btw.

Did you read this?
http://www.gamasutra.com/features/20010912/sterren_01.htm

"Hi. I know how nodes and waypoints work in 2D games, and how to perform A* on them, but on 3D is a little harder."

There's no difference between using A* on a 2D graph or a 3D graph (or a 1000000D graph)(a graph, btw, is a collection of waypoints/nodes and the connections between them)



"I obviously can't have a node network for performance reasons, as i'd have to check if each node is colliding with anything."

Of course you can. When graphs get large some sort of spatial partitioning must be used but you can still use that type of representation.

There are alternatives to waypoints, which are more efficient for some types of world representation. Navigation meshes for example.

Quote: Original post by dwfait
I obviously can't have a node network for performance reasons, as i'd have to check if each node is colliding with anything.

Actually, yes you can. See here this great little article
In a few words, you can very well "fill up" your world with nodes, then simply keep only the relevant ones.
Voronoi diagrams spring to mind, as well, although I don't know of a 3D equivalent (but since it's a geometric method, I assume it can be extended to 3 dimensions)

Philippe

In our last title, a FPS, we used a combination of Delaunay triangulation (check also Voronoi) for our navmesh creation for outdoors, and waypoints for our indoors. It would have been preferable to use navmeshes all the way (mostly for precision) but we didn't have time to implement them.

As Mat stated, wether its 2D or 3D doesn't change much.

Here's a few questions that might help us giving you a better answer:

- How did you find out that a node network caused performance problems? Is it just a wild guess?
- Have you tried to optimize your network by grouping nodes, quadtree style?
- Is your FPS "Decent" like or Quake like? I mean, are entities walking or freely flying around?
- If entities are walking, do you allow or disallow overlapping areas (from a top view perspective)? (if you disallow them, it becomes nothing more than 2D pathfinding as you're used to...)
- What do you mean by "check if each node is colliding with anything"? You're aware that you can preprocess your node network and load it at runtime?
- If you're checking for collisions as you could do in 2D, to mark nodes "used by an item", to force the pathfinder to avoid items, have you considered not marking nodes as used and use something like Steering Behaviors to guide your entities around obstacles?

Hope this helps

Eric

Quote: Original post by ahw
Actually, yes you can. See here this great little article

Please could you fix this link - because I don't think you set it up correctly!

Thanks - Danny

With properly set up nodes (and maybe a little collision detection by you) isn't it possible to have overlapping way points? The computer has no idea what the relationship is between the nodes, so how would defining overlapping ones from the top down confuse it?

This is my article on pathfinding:

http://www.geocities.com/bpj1138/shortest_path.html

you might also find the path editor useful (linked from my site)

--Bart