# Implementing a waypoint system

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

## Recommended Posts

Hello, i'm making a 3D 3rd person shooter and am doing the AI for the game now. I'm thinking of using a waypoint system with A* algorithm to let my bots get to the destination in the shortest path. However i'm not very sure how to implement a waypoint system for the game. What i've done so far was placing nodes on a map and recording their IDs and 3D coords. So i'm wondering what should be my next step?Creating a waypoint class? If so, what functions should it have(perhaps one for connecting the waypoints together)? I'll really appreciate any help or reference to any tutorials(which i cant seem to find any).

##### Share on other sites
I presume you have the following working:

response to KB and Mouse

AI controlled characters, which are able to move or be moved, but can't follow anything.

Collision detection, including characters VS level geometry.

I recommend doing those things first, as they and their implemention affects how you would up the AI nodes. Once these things are working, you could put the nodes in an XML file and load it with a library such as TinyXML.

##### Share on other sites
Then, you can have a waypoint class as such:

class waypoint{private:  vector3 position;  some other properties, such as     how exposed is it,     how tight a squeeze is it    how many sniper positions can see it    how many hiding positions can see it    how safe is the ground?  std::vector<waypoint *> children;public:  void addChild(waypoint * w);  waypoint * getChild(unsigned int which_one);  unsigned int getNumChildren();}

then your AI characters can follow the waypoint list recursively to find the one they are after, starting with the one they are on. then, they set their state to the moving state. when they get close enough to their waypoint, they set their state to decision state, and choose another waypoint.

##### Share on other sites

hmm if i want to plug in an A* algorithm, wont i have to link up all the waypoints instead of a parent to child waypoint?

##### Share on other sites
No. If the idea is that you go from one waypoint to the next, you just run the algorithm to get from one to the next.

##### Share on other sites
wouldn't the algorithm need the waypoints to be in a adjacent manner (or rather know what other waypoint it is connected to?)

##### Share on other sites
Ah, sorry, for some reason I thought you meant the player placed the waypoints. Perhaps a better term for what you mean would be navigation nodes or something. I think the standard method is to produce a graph out of the nodes, by checking each one against all others for visibility (perhaps bounded by distance), and considering them adjacent if they can see each other. Typically you do this offline, as part of the map editing process, and save it as part of the map format. Then at run-time, you run the A* algorithm over those nodes just like you would with a grid map, except that unlike a grid, each node has a variable number of neighbour nodes, ie. the ones you calculated earlier.

##### Share on other sites
thanks for your reply! Well, i was held up by some other AI components of my game and now i'm back at this. So how should i represent my waypoint graph? Each waypoint having a vector container showing which other nodes it's connected to? or using multi map to store them?

I plan to manually add in the edges for each node since my game map isn't very big (therefore less navigation nodes around) so i'm not really worried about the algorithm to connect each node. I'm more interested in knowing how should i store them if i'm planning to use them with A*.

##### Share on other sites
I think this paper (on GameDev.net!!!) should really help you. If I'm not mistaken, this is pretty much what you're asking for.
Look on GD.Net the original Paper is somewhere in this site, but I can't find it now (the one I'm providing is the newest one though)

Hope this helps
Dark Sylinc

PS: Traditional (grid) A* is a terrible idea if your game allows different floor levels (not impossible, but hard)
I think the algorithm in the paper is a much better aproach than just using A*

##### Share on other sites
thanks for the reference, it was a really good read up! But still i'm looking more towards STL containers or structures on how do i actually store my navigation(waypoint) nodes and each of their respective connections to other nodes? Not forgetting that i also have to store the cost of each connection.

##### Share on other sites
Quote:
 Original post by maxzonexthanks for the reference, it was a really good read up! But still i'm looking more towards STL containers or structures on how do i actually store my navigation(waypoint) nodes and each of their respective connections to other nodes? Not forgetting that i also have to store the cost of each connection.

If I'm not mistaken, you're asking a begginer's question.
I think you're asking for the std::map container:
http://kengine.sourceforge.net/tutorial/g/stdmap-eng.htm (Tutorial)
http://www.cprogramming.com/tutorial/stl/stlmap.html (Tutorial)
http://www.sgi.com/tech/stl/Map.html (Tech Reference)
http://msdn2.microsoft.com/en-us/library/xdayte4c(VS.80).aspx (Tech & Samples)

If you follow the paper I told you about, you could use map to store the look-up table you need.
For example:

map<char,map<char, char>> mymap;map<char, char>::iterator it;mymap['A']['B'] = 'B';mymap['A']['C'] = 'C';mymap['A']['D'] = 'C';//Find the iteratorit = mymap['A'].find('B');//Print the next (fastest) waypoint from A to Bcout << mymap['A']['B'];

I'm not sure if there's a better, efficient way to do this but this will work.

Hope this helps
Dark Sylinc

##### Share on other sites
To be honest I've never thought of precalculated path finding before, Though it does seem ideal for a game with a relatively small amount of nodes over a large area.

Precalculated path finding:
- Dijkstra algorithm should be used.
- uses less cpu.
- faster.

Real-time path finding:
- A* algorithm should be used.
- uses less memory.
- speed unaffected by changes in the map.

WARNING: Theres one thing I don't like about Fine's algorithm is the way it handles dynamic maps, non-permanent changes like a door opening/closing or a large vehicle blocking a path cause a path finding algorithm to traverse EVERY node then EVERY node must be recalculated with EVERY other node. See where I'm going? Such a small change can cause drastic amounts of cpu usage.

I recommend using precalculated path finding on your way points, though you are going to have combine it with real-time path finding for the small scale stuff like unit movements.

You will need at least two data structures to implement waypoints:
- A waypoint class/struct for holding data about the waypoint with an array of pointers to other waypoints.
- An array for storing waypoints, unless you plan on it being resizable.

Ben.

[Edited by - fujitsu on February 25, 2008 10:20:22 PM]

##### Share on other sites
Quote:
 Original post by fujitsuWARNING: Theres one thing I don't like about Fine's algorithm is the way it handles dynamic maps, non-permanent changes like a door opening/closing or a large vehicle blocking a path cause a path finding algorithm to traverse EVERY node then EVERY node must be recalculated with EVERY other node. See where I'm going? Such a small change can cause drastic amounts of cpu usage.

D* (and it's variants) were designed to handle this very problem by propogating the effects of such changes only through the relevant nodes.

##### Share on other sites

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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628711
• Total Posts
2984341

• 23
• 11
• 10
• 13
• 14