Jump to content
  • Advertisement
Sign in to follow this  
maxzonex

Implementing a waypoint system

This topic is 3887 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
Advertisement
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
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 this post


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