A Translation from 2D

  Dig Dug 3D’s AI system is nearly entirely made from the ground up.  It does interface with Unity’s physics system when determining if an enemy is ghosting through a wall, and also when modifying an enemy’s velocity.  This, however, is about the extent of where Unity’s base systems assist with an enemy’s actual pathfinding or decisionmaking.  Why would I design an entire complicated AI from the ground up then, when Unity already has built-in AI tools?  My first reason is that the environment is both highly complex, and constantly changing, so I would need to develop a system that can easily account for such changes.  My second reason is, I want to remain as true as possible to the original game’s AI as possible.  The goal of sticking to the source material isn’t entirely feasible due to both the limitations of the original game’s movement, and the lack of a 3rd dimension in the original game.  However, what I ended up with is an AI that can be thought of as an expansion of its 1982 counterpart.

Pathfinding

  Before I talk about the different AI states, or differences between the Pooka or Fygar enemy types, it is important to know how enemies navigate through the tunnels.  In the original game, the map worked off of a 2D tile system, which allows for both quick map data processing, and a quick way for enemies to find the player.   Dig Dug 3D isn’t afforded this luxury.  If I was to use a tile-based approach, that would mean that I would have to scan the 6,480,000 voxels that comprise the map every time an enemy wanted to pathfind.  This combined with the fact that an enemy occupies around 1m3 while a voxel occupies around 0.2m3 of space, means that pathfinding would both be absurdly slow and memory inefficient.

  My solution to this problem starts with the implementation of the Navigation Tree (NavTree) data structure, found in the file “NavTree.cs.”  The goal of this structure is to create an organized network of nodes that enemies can pathfind between.  The structure also supports the addition of new nodes into the data structure, linking it up with nodes already in the network.  The NavTree structure at its core, is a list of NavChunk objects.  Each NavChunk divides up the entire map into small cubic domains containing their own navigation nodes.  Dividing up the map into NavChunks serves to reduce memory overhead and optimize the node addition process by only allowing nodes within NavChunks and the adjacent chunks to connect with each other.  Navigation nodes themselves are just points in space that contain a hash set of connections to other nodes along with the distances to those nodes.  Whenever I add a node to the tree, provided that it lies within the bounds of the map and isn’t too close to any existing nodes, I will assign that node to whatever NavChunk it lies in.  The NavChunk will then recalculate all of the connections between nodes within itself and draw connections to nodes in adjacent NavChunks.  Connections cannot be drawn between 2 nodes that are obscured by level geometry in such a way that an enemy could not pass through.  Whenever caves are naturally generated, or whenever the player digs in a particular location, nav nodes are created, allowing enemies to pathfind through them.

As the player digs, they introduce new nodes to the NavTree
White boxes represent the boundaries of a navigation chunk
Green lines show nodes being created and linked in real time

  Now that there is a navigation tree in place for enemies to get from Point A to Point B, it raises the question: “How do enemies navigate the NavTree?” I utilize a modified version of the A* Pathfinding algorithm. A lot of papers have been written on the algorithm itself, so I won’t go into the exact steps of the algorithm. The reason I chose this algorithm over another, was due to its heuristic approach to pathfinding. This approach allows me to generally take less steps, because it prioritizes processing nodes that bring me closer to the goal rather than processing nodes arbitrarily. This implementation takes the form of a function called “Pathfind.” The Pathfind function is a method that any enemy can use, and returns a queue of points the enemy should follow to reach a target.

Decision Making

  In deciding how the enemies should work, I examined the original game very closely. The original AI works as follows:

At the start of a round, enemies patrol around their starting caves for a short amount of time. After that short amount of time, the enemy will get the tile that the player is currently standing within, and start to ghost through the soil to that position. If the enemy happens to intersect a cave (either the destination cave, or an intermediary), they will return to their normal form. They will then see if they can reach the player by walking. If not, then they will patrol for a short amount of time before attempting to ghost to the player again. If they can reach the player, they will try to chase the player. This loop of patrolling, ghosting, and chasing continues until one enemy remains. When one enemy remains, they will attempt to escape to the surface of the map, and run off from the screen.

Flowchart represents the AI from Dig Dug 1982

  Dig Dug 3D's AI emulates that of the original game pretty closely. the following sections detail how the base AI functions in the game.

Note: The AI for enemies starts with the base class, "BaseEnemyAI.cs."

Chase State

The chase state is divided into 2 phases: the “pathfinding” phase and the “pursue” phase. While in the pathfinding phase, the enemy will call the Pathfind function, attempting to reach the player. While in the pursue phase, the enemy will traverse the path generated during the pathfinding phase. It will also check to see if it has been following a path too long, in which case it will enter the pathfinding phase again. The enemy will continue to do this until it gets bored. If either the enemy gets bored, or can no longer reach the player, it will enter the wander state.

Wander State

While in the wander state, the enemy will find the nearest navigation node, and randomly pick one of its connections. It will then call Pathfind to that node and follow the generated path to that node. It continues to do this for a short amount of time, after which it enters the ghost state.

Ghost State

The ghost state is deceptively complex, because enemies must understand when they have started to phase through a wall, and when they have re-entered another cave. The ghost state has 2 phases: the entry phase, and the exit phase. While in the entry phase, the enemy will set its destination to a node nearest to the player, set its collider to a trigger, and start moving towards that destination. The moment its trigger overlaps with a wall, it will enter the exit phase. During the exit phase, the enemy will continue to move towards its destination, until it gets close enough to it, or another pathfinding node. After this it will exit the ghost state, and begin the chase state once again. In older versions of the game, the AI would ghost towards the player’s position directly as opposed to a node. This was changed so that it would be more accurate to the original game.

Escape State

This is a special state that is only triggered on the last remaining enemy of a level by the game manager. While in the escape state, the enemy will accomplish various tasks in sequence. First, the enemy will try to reach the central cave, this is the cave the player spawns in, and is always generated with a shaft that leads to the surface. If the enemy cannot reach the central cave by walking, they will ghost there instead. When the enemy has reached the central cave, they will then escape through the shaft to the surface of the map. When the enemy has reached the surface, they will then try to escape the map by running towards the border of the map. If they successfully reach the border, the game manager will end the level, and begin loading the next level.

Any AI state can be interrupted through the enemy being inflated, popped, or squashed by a rock.

Flowchart represents the AI from Dig Dug 3D

  To finish off this analysis of the AI, I will describe the differences between the Pooka and Fygar enemies. A Pooka is much faster than a Fygar, moving at the same speed as the player normally, and moving faster than the player when the player is digging. Aside from when it is ghosting, it is also a completely silent enemy, making it great for sneaking up behind the player while they are focused on digging or fighting other enemies. The Pooka awards the player with 200-500 points, depending on how deep the enemy is, relative to the surface. The Fygar, while slower, is able to breathe fire periodically. When breathing fire, the Fygar will stop moving, flash white for a bit, and then breathe fire before returning to its normal AI routines. The Fygar awards the player with the same amount of points as the pooka, when the player is above, or below it. If the player is right beside the Fygar, the player is awarded with double those points (400-1000), as it’s riskier to fight a Fygar where it can breathe fire.