Are Waypoint Graphs Outnumbered? Not in AlienSwarm!

If you've been following recent trends in game AI, you could think of navigation meshes as an angry horde set to kill off waypoint graphs. Meshes are everywhere: from the various middleware libraries presented in Paris last month like Autodesk's Kynapse, PathEngine, or Havok's to open-source implementations like Recast as well. Some veteran developers have even declared waypoint-based approaches to be obsolete...

Yet, waypoint graphs are still regularly used in the games industry. I personally often recommend them — especially to independent developers — since they're a simple and effective approach to navigation, and if you're going to implement something yourself for a game, you might as well use waypoints and save yourself the torment of writing a robust navigation mesh that you may never make the most of!

The recent release of AlienSwarm (free on Steam) is a perfect illustration of how waypoints are still used in practice, and are supported by Valve's Source engine. In this post, you'll find some insights into the code from the SDK (also available) as well as screenshots from the game itself. Oh, and be sure to join our official AiGameDev.com Group on the Steam Community!

Instructions...

If you'd like to follow along with this article, you need to do a couple things once you have the game installed. Keep in mind you can click on all the images below to view the large version!

1. In the AlienSwarm keyboard configuration menu, you have to enable the developer console.

2. When you need it, you can activate the console using the tilde (~) key below the ESC key.

3. You may want to setup god mode by typing asw_god 1, which should prevent you from dying while you're exploring.

4. Also, for screenshots disable the heads-up display (HUD) using asw_draw_hud 0.

The SDK is installed via your TOOLS tab in the Library within Steam, and the source code is stored on disk in your Steam folder, for example C:\Games\Steam\steamapps\common\alien swarm\sdk_src\game\server.

AI Nodes

Technically speaking, the graph in AlienSwarm is made up of "nodes" and the term "waypoint" is used to describe the path that results from the pathfinding. Nodes are essentially points in space with additional information such as an identifier, type, additional information, a zone, etc. The data-structure used to store these nodes can be found in #/sdk_src/game/server/ai_node.[h,cpp].

enum NodeType_e
{
    NODE_ANY,
    NODE_DELETED,
    NODE_GROUND,     
    NODE_AIR,       
    NODE_CLIMB,  
    NODE_WATER     
};

enum NodeInfoBits_e
{
    bits_NODE_CLIMB_BOTTOM    = (1 << 0),
    bits_NODE_CLIMB_ON        = (1 << 1),
    // ...
    bits_NODE_CLIMB_OFF_RIGHT = (1 << 4),
    bits_NODE_CLIMB_EXIT      = // ...
    NODE_ENT_FLAGS_SHIFT      = 5, 

    /* Flags for default and custom hulls. */
};

class CAI_Node
{
public:
    int                   m_iID;
    Vector                m_vOrigin;
    float                 m_flVOffset[NUM_HULLS];
    float                 m_flYaw;
    NodeType_e            m_eNodeType;
    int                   m_eNodeInfo;
    int                   m_zone;
    CUtlVector<CAI_Link*> m_Links;
    float                 m_flNextUseTime;
    CAI_Hint*             m_pHint;
    int                   m_iFirstShuffledLink;
};

The nodes in the levels can be placed manually using the map editing facilities from the console.

AI Links

Nodes are connected together via links, which implicitly creates a graph. Each node stores a set of links, and the links hold two identifiers to point towards its end nodes. The links are specified in #/sdk_src/game/server/ai_link.[h,cpp] and the resulting graph is #/sdk_src/game/server/ai_network.[h,cpp].

/* Edited for conciseness. */
enum Link_Info_t
{
    bits_LINK_STALE_SUGGESTED   = 0x01,
    bits_LINK_OFF               = 0x02,
    bits_LINK_PRECISE_MOVEMENT  = 0x04,
    bits_PREFER_AVOID           = 0x08,
    bits_LINK_ASW_BASHABLE      = 0x10,
};

class CAI_Link
{
public:
	short	m_iSrcID;
	short	m_iDestID;
	byte 	m_iAcceptedMoveTypes[NUM_HULLS];
	byte	m_LinkInfo;
	float m_timeStaleExpires;
	int m_nDangerCount;
	CAI_DynamicLink *m_pDynamicLink;
};

You can display the links from the console using the command ai_show_connect.

There are two types of links: static links like in the screenshots above, which don't change during the game and can be stored very efficiently in memory. However, since some parts of the world may change, dynamic links are also required. These are hooked into the graph by having each static link store an optional pointer to a dynamic link. The dynamic links are full entities capable of receiving game events to deal with the changes around it. See the files #/sdk_src/game/server/ai_dynamiclink.[h,cpp] for details!

In the standard campaign, dynamic links are used when infected biomass is burned with the flamethrower, or rocks that are in the way are destroyed using the mining laser.

AI Hulls

The links in the graph seems to be connected via brute force, as shown in the images below. There are many links that are created which will never be used at runtime. However, these are marked as disabled — shown in red.

The links are disabled using a convex hull collision test. If the hull around a link collides with geometry, then it's deemed to be in-traversable at runtime and the link is turned off. You can see the hulls from the console using the variable ai_show_hull 1.

There are different convex hull types for the different link types, in this case ground units and air units. The hulls for both those unit types are rendered in a different color within the game.

Another Example

Conclusion

Waypoints have picked up a bad reputation over the years, but AlienSwarm is an example of a game that seems perfectly fine with this approach. The navigation of the aliens is certainly not perfect, but this is mostly due to human-placed dynamic obstacles like turrets.

Navigation meshes wouldn't resolve this problem directly either, you still need local avoidance for that... Arguably though, a navmesh would make it easier to resolve these problems and support dynamic obstacles, but getting this right is far from trivial!

What's your take on waypoints and their use in AlienSwarm? Let us know and post a comment in the forums!