"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

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