Builtin Waypoint AI

The server loads a waypoint lookup along with the map, adds information gained by observing players and monsters at runtime, and saves it for reuse. The information is basically an adjacency graph based on a spatial subdivision hidden to the Game DLL, and additional information stored in edges and nodes.

Advantage:

• Improvements in AI.
• Statistics on killer/victim positions, feedback from playtesting.
• Provides a builtin support for both monster AI and server side bots.
• Could be used for navigational aids for players ("turn left").

Disadvantage:

Moderate memory and performance impact, maybe even compensated by faster AI. If Q3 uses no spatial subdivision at all, this would be obsolete.

Implementation:

In full, this is an overhaul of the current AI, trailing, and the Area/PHS code. However, there are intermediate steps that could be used for a smooth migration on the way to Trinity. Comments below:

• it needs to be BSP/map independend in terms of API. The geometry implementation should not be visible in the Game DLL. The Game DLL knows positions. It does not (not really) know BSP, PVS, PHS etc. - it knows the basic, abstract concept, but not the implementation.
• preprocessing a map might generate an initial set of information. Level designers might place waypoints manually, or a Shortest Path could be run after spatial subdivision.
• during-game sampling (plus read/write) would be an entirely new mechanism, taking workload of the level designer
• we need an adjacency matrix. That matrix has nodes (each representing a spatial partition, an area, BSP leaf, region), and edges (each edge telling us that there is a direct connection from area/node 1 to area/node 2). We can consult handing it a point, or two points.
• for efficiency, an area identifier for position for position is needed:

        int   (*getAreaID)( vec3_t pos )
      

  This would hide the actual details of the areas from the DLL. This is already present in the Q2 DLL. There are areanum fields in the edict_t.

          g_ai.c: if (!gi.AreasConnected(self->areanum, client->areanum))
     

• currently AreasConnected is an inquiry on the PHS, that means visibility, but not necessarily a path. The adjacency graph (paths) are time dependend. For waypoints, this means edge length might change (for moving platforms), so our graph is elastic. If the length exceeds a certain jump reach etc., the edge is not passable. For a walker, how high a step or how steep a fall has to be considered. For a floater, PHS is sufficient. Minimally, some flags and a more or less appropriate cost setting per edge is needed.
• to identify paths and query them, you might need flags and functions like:

    #define PATH_FASTEST
    #define PATH_EASIEST
    #define PATH_SHORTEST
    #define PATH_SAFEST
    #define PATH_NO_WATER_THROUGH
    #define PATH_NO_WATER_CLOSE
    #define PATH_NO_LAVA_CLOSE  // etc.
    #define PATH_FLYER
    #define PATH_NO_STEPS
    #define PATH_NO_FALLS
    #define PATH_IN_DARK  // stealthy
    #define PATH_NARROW_SPACES
    #define PATH_OPEN_SPACES
  
    // Get a path suggestion, depending on flags.
    int    (*getPathID)( vec3_t start, vec3_t end, int flags );
    
    // Get the overall costs, whatever units.
    float   (*getPathCosts)( int path_id );
  
    // Get waypoints to travel along.
    vec3_t*  (*getPath)( int path_id ); 
  
    // Get total path length lookahead.
    // Mask if you want under water path etc.
    float (*getPathLength)( ind path_id, int flags );
  
      

  The AI could get a path with some preferences, get the costs, reject them, get another one with changed preferences, and if acceptable, get the waypoints and start walking.
• all NPC's will share the same LUT, and the same knowledge. An exploring AI would need its own local copy of such a LUT, e.g. for a server-side bot. This does not seem feasible.
• Learning at runtime. The adjancency graph discussed so far is a more or less complicated generalization of the PHS/area mechanism. We could sample successfull player/monster movements (and those that went wrong) to identify safe pieces of paths ("player got from A to Z via B,...,Y, has to be a good path").
• Sampling spots on events. We could sample safe spots, dangerous spots, to find spawn points at runtime ("player survived 2 mins after being at spot A, spot A can be used as spawn spot", and "player was killed in spot C, close to four other death spots") or qualify paths (check each segment of path for shortest distance to dangerous spots).
• Sampling spot pairs on events. We could also sample "killer-victim" position pairs (projectile stores original spawn location, which is killer position, and we get the hit position when the target dies. That means we can lookup:

     vec3_t     (*getAmbush)( vec3_t me, vec3_t target ); 
  

  to get obviously good kill positions from past events for my and the targets current position.
• storing and distributing learned LUT's. If a server can learn things from past monster performance and observed player actions, it will be too valuable to discard this. So we need a mechanism to store such data. It is map dependend. But we might get several such LUT's from several servers. We might have offline tools to preprocess as much as possible (so monsters don't act too dumb), and we might want to merge results from different servers. We need a file format, and I/O.
• Query border points in Areas.

     vec3_t*     (getPointsInArea)( vec3_t pos );
     vec3_t*     (getAreaPoints)( int areaID );
      

  returns a list of valid points in the current area, or any area, reacheable, relatively close to the current position, but measuring the extent of the area: close to the walls, to obstacles. Application:

    Monster A sees player. Monster A is a melee
    attacker (berserk), or low on health, or
    a coward - for whatever reason, monster A
    wants to hide out of sight. So you get the
    points, and check them with trace to find one
    to hide out of sight. You move towards one
    picked, and stand still till the player gets
    in sight again.
  

• Query adjacent Areas.

    int*        (getAreasAdjacent)( vec3_t pos );
    

  Gives the areaID's of all ajacent areas.
• Query runtime sampled information:

     // get number of recent kills - a runtime counter
     // might distinguis deaths and gibs,
     //  for level of violence
     deaths_in_area   = gi.getAreaKills( areaID );
  
     // Here is your sense of smell.
     time_since_last  = gi.getAreaKillLastWhen( areaID );
     pos_of_last      = gi.getAreaKillLastWhere( areaID );
  
     // get number of monsters, players
     // different from gi.BoxEdicts
     entities_in_area = gi.getAreaEntities( areaID );
  
     // get items/powerups in that area
     items_in_area = gi.getAreaItems( areaID );
    

  You could even return lists. You could cheat, or clip against LOS, once you got all the items. As objects are stored per BSP leaf, the data should be readily available. You could also lookup small, compact bit flags.

     // any movements/noises in this area?
     qboolean  gi.getAreaMoves( areaID );
     qboolean  gi.getAreaNoises( areaID );
    

Related Proposals:

This proposal complemetes the "Map Markup" one. Ideally, the same internal data structure should be used here. It was inspired by discussions on the q2bots mailing list as well as AI improvement ideas mentioned on the q3suggest mailing list.

Submitted 980420, contact bk@gamers.org.