Jump to content
  • Advertisement
Sign in to follow this  
dwfait

3D Waypoints

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
"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 this post


Link to post
Share on other sites
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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!