Implementing a waypoint system
Author
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).
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.
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.
Then, you can have a waypoint class as such:
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.
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.
Author
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?
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?
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.
Author
wouldn't the algorithm need the waypoints to be in a adjacent manner (or rather know what other waypoint it is connected to?)
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.
Author
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*.
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*.
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*
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*
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
