Software Development Portfolio
David Pittman, Application ID ####
Sentry AI Demo

Description:
    This game was written as a demonstration of a simple artificial intelligence. A player must navigate a maze to a gem, being careful not to be caught by a sentry. The sentry will move to investigate noises (caused by stepping on creaky floorboards) and distant sightings of the player. If he catches the player, he will retreat to sound the alarm, ending the game. Although this game only has one sentry, it would be trivial to add a list of Sentry objects for multiple guards (of course, they would each act individually rather than behaving realistically and working together). This program uses SDL and the STL List class.

    The AI for the sentry is fairly simple. He operates in one of three discrete states: standing guard/returning to post (no stimuli provided), investigating a potential threat (sounds or distant sightings provided), or moving to sound an alarm (nearby sighting provided). Given a destination (typically either a potential threat, the alarm box, or his initial post), the sentry's path is determined by the A* algorithm. The guard will always move towards the source of the most recently provided stimulus. Upon reaching that node and finding nothing, he will return to seeking the second most recent stimulus, and so forth until every potential threat has been checked. At that point, his state reverts to its lowest level and he returns to his post.

    For simplicity's sake, "sound" events triggered by stepping on noisy tiles are heard throughout a map. Sighting of the player must be checked by casting a ray along the line of sight until either the player or a wall is reached.

    The A* algorithm is a popular choice for pathfinding which works especially well for this sort of grid-based map. A good article explaining the algorithm can be found at http://www.gamedev.net/reference/articles/article2003.asp. The implementation for this AI is as follows:

  1. Add the starting node to an "open" list of nodes.
  2. Until a path is found or there are no nodes remaining on the open list, do the following:
    1. Sort the open list by F cost (F = G + H, where G is the cost to move to the given node, and H is the heuristic, the estimated cost from the given node to the destination).
    2. Pop the node with the lowest F cost off the open list and push in onto a "closed" list of nodes. This is now called the "current node."
    3. For the nodes in each of the 4 cardinal directions from the current node, do the following:
      1. If the node is a wall, ignore it. Else, continue.
      2. If the node is in the closed list, ignore it. Else, continue.
      3. If the node is already in the open list, compare the G value from this path to the G value already associated with this node. If the new G value is smaller, set the node's parent to the current node and update the G cost.
      4. Else, if the node is not already on the open list, add it. Give it a G cost equal to the current node's G cost + 1, an H cost equal to the "Manhattan" distance (distance along straight lines only) to the destination node, and the current node as a parent. If this node is the destination node, then a path has been found.
  3. Starting from the destination, build a path list of nodes by retracing the path backwards from each node to its parent until the starting node is reached.

    The following example is a very simple case, but it may help to illustrate how the algorithm works.


Example 1

    In the example above, the red square represents the starting node and the green square is the destination. Grey tiles are walls. The first step is to add the starting node to the open list.


Example 2

    Now the node with the lowest F cost is added to the closed list. In this case, there is only the starting node, so it is added (the yellow border indicates its presence in the closed list). Although not illustrated, this node has values G = 0, H = 3, and F = 3. The available movement directions are up, right, and down. The nodes in these directions are added to the open list with the values indicated.


Example 3

    The node to the right had the smallest F cost, so it is added to the closed list. From here, only vertical movement is possible (to the left and right are a closed node and a wall, respectively).


Example 4

    At this point, there is a tie in the F costs of the two most-recently added nodes (as well as the nodes added in Example 2). Since the bottom one was added last, the tie is broken in its favor. (Technically, this happens because it was pushed to the front of the list, and because the sort operation is stable, it remains in front of the other nodes with equal F cost.) Possibles moves are to the left and down. The node to the left is already on the open list, and since the new G cost would be greater (3), it is left untouched. (Were the new G value lower, the new value would be applied and the parent node changed to the current node.) The node below the current node is added.


Example 5

    Of the remaining nodes with F = 5, the one added to the top in Example 3 is the most-recently added, so it is pushed onto the closed list. Again, the node to the left is checked and ignored, and the node to the right is added. This process will continue for two more cycles, until the destination node is eventually added to the closed list.


Example 6

    Now the path can be built by following the each node back to its parent (tracing the arrows backwards from the destination).

Controls:
    Game mode:
        Arrow keys: move player
        Space bar: wait (if in turn-based mode)

    Map editing mode:
        Left-click: toggle wall on/off
        Right-click: toggle noisy tile on/off
        Ctrl + left-click: move player start
        Shift + left-click: move gem
        Ctrl + right-click: move sentry station
        Shift + right-click: move alarm
        S: save map to "map.txt"
        Space bar: begin game

    Command line options:
        editor: Start in map editing mode
        turn: Turn-based gameplay

Code files:
    ai.cpp
        Main program
    event.cpp
        Event class, contains data and methods for event (AI stimulus) objects
    event.h
        Event class header
    gfx.cpp
        Graphics primitives library (points, lines, circles, etc.)
    pathnode.cpp
        PathNode class, contains data and methods for path node objects (used in both finding and following a path)
    pathnode.h
        PathNode class header
    sentry.cpp
        Sentry class, contains data and methods for sentry AI objects
    sentry.h
        Sentry class header

All example content by David Pittman. HTML by J. Kyle Pittman and David Pittman.