Sign in to follow this  

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.

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

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


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

Loading a map file and rendering it.

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


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


Link to post
Share on other sites
thanks for your reply! Yes, i do have those components done up already.

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


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


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


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


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


Link to post
Share on other sites
Quote:
Original post by maxzonex
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.


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 iterator
it = mymap['A'].find('B');

//Print the next (fastest) waypoint from A to B
cout << 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 this post


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

I hope this is helpfull!
Ben.

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

Share this post


Link to post
Share on other sites
Quote:
Original post by fujitsu
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.


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


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

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this