I'm working on a simple RTS that uses a point structure that looks like this: Vector3 Position int Id; int ConnectedId[4]; //What other point IDs is this connected to? I'm just having the NPC spawn if the point type is a spawn and they are basically going to look for the point type that is the flag that the NPCs have to go for. I'm new to AI and I understand how to set up my AI and not use collision system for them making discussions and instead use a waypoint array to make things move faster, but I don't see anything on waypoint searching then grid searching. Is it difficult in a way and is there anywhere I can look to see some code? Thank you, Ajm.

Quote: Original post by ajm113
grid searching

Almost there, graph searching is probably what you want. Look up algorithms like A* (A star), Dijkstra's Algorithm etc. These algorithms are commonly used to implement path finding etc.

Hey thanks! Dijkstra's Algorithm does give me a good idea on setting up my code to get the NPC to get to the flag.

Thanks again, Ajm113.

A* is a slicker version of Dijkstra and is more commonly used.

The use of waypoints is an optomization where the points can be prebuilt offline (you want them defined with clear paths between them and their connected waypoints). That save you the extra processing of paths tile to tile (or whatever a minimum movement increment is) and lets you only pathfind a simpler path (ie- A*) on a much smaller node network (the waypoint network rather than every tile).

Often the waypoint map is prebuilt (in some terrain systems there are tools or they can be hand placed) but you could also have the local waypoint-to-adjacent waypoint path calculated once/verified and then the result cached. You then can then 'divide and conquer' repeatedly only having to do the simpler between adjacent waypoint pathfind (or none if they are clear 'line of site').


Selecting where the predefined waypoints are is usually a trickier part and assessing/picking them on a given map can be extremely costly processing wise
( as in best done offline ). Why the object wants to go to the waypoint is also something that has to be defined at a higher level matching your game mechanics,
as is the usual 'cost' evaluation of the traversals.