# 3D Waypoints

This topic is 4874 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
Did you read this?
http://www.gamasutra.com/features/20010912/sterren_01.htm

##### Share on other sites
"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.

##### Share on other sites
Quote:
 Original post by dwfaitI 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

##### Share on other sites
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

##### Share on other sites
Quote:
 Original post by ahwActually, 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

##### Share on other sites
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?

##### Share on other sites
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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634091
• Total Posts
3015433
×