Josh Loveland | Software Developer

Overview

Project: Mothership Mayhem

Estimated Development Time: 30hrs

Lines Of Code: 1,400 (Including comments and spacing)

Description: The NavMesh is responsible for the creation and storing of paths within a given zone. It also is used for tracking enemy units and the paths they are taking in order to monitor zone flow.

Objectives:

        1. Create or load navigation points withing a given zone.

        2. Create and store a path from each navigation point within a given zone.

        3. Store and retrieve points of interest that are set within the level manager.

        4. Retrieve the shortest path upon request.

        5. Retrieve secondary paths upon request.

        6. Track non-player characters within a given zone.

Thought Process and Choices

Why I chose to use a Navigation Mesh:

The rooms(zones) in Mothership Mayhem are not terribly complex. The are only a handful of concave areas in the entire game. As a team we also quickly realized we would be limited AABB collision bounds. This means I most likely could have gotten away with some decent steering behaviors purely from the perspective of npc movement. However, it was the secondary uses of a NavMesh that won me over. I wanted an AI Director capable of managing the flow of these encounters, which meant I needed a way of keeping track of each of the bots and the routes they were taking. Setting specific information to NavNodes(I'll explain this further down) also allowed me to monitor choke-points and spawn zones.

Risks:

       1. It was only a 5 month long project, requiring us to create an engine from the ground up. I was also responsible for other core systems, but a NavMesh was something I beleived needed to be done in the early part of development to ensure smooth integration. This meant my teammates were dependent on my systems and could easily cause a bottleneck.

       2. Full Sail never exposed us to NavMeshs outside of a picture of what one looked like. I also had never researched or worked on one prior to that project, leaving both me and my team exposed since we were graded as a whole based on testable gameplay. However, I did have previous experience with A* and other path generation techniques.

      3. Due to #2, I had no idea how long it would take to develop a NavMesh, making it difficult for me to give accurate timelines when it came to sprint planing.

Results:

I managed to get 75% of the functionality complete in the first 2.5 weeks of development alongside of the my other core systems(State Manager and Input Manager) and some basic enemy AI. The pathing aspect worked perfect from a gameplay perspective(I discovered some subtle problems later on) and also had the 1st stage of npc tracking complete.

Some features were eventually cut such as cover tracking and choke-point detouring due to time constraints, but overall I and my producers were pleased with the results.

Design and Development

There are 2 main aspects to the NavMesh in Mothership Mayhem:

       1. The paths themselves are pregenerated and static, requiring the environment to stay static.

       2. Due to the nature of the rooms, the NavMesh treats the world as if it is 2d.

Because of these 2 factors, the overall implementation for the pathing aspect of the NavMesh was fairly simple and can be separated into 4 steps.

Step 1: A zone is created in the editor.

Step 2: The creator can then either place NavNodes by hand or use the generator. This is point in the process where points of interest can be set, such as choke-points or doors.

Step 3: Then the NavMesh makes 'legal' links between each node in the zone. For a link to be 'legal' it must have line-of-sight of each other, the line between the nodes must have a minimum width, and the nodes must be within range of each other.

Step 4: Lastly, a path between each node is created using A* and stored into a 2d array.

Links:

The lines in the pictures above, each connecting 2 nodes, is considered a 'link.' A link itself is made of multiple parts(2 nodes + 2 lanes). It is these extra parts that assist in the tracking aspect of the NavMesh. A Lane represents the connection between nodes going in a single direction.

Paths:

When you have 2 or more links you get a Path. It is this list of connected nodes that is ultimately pulled out of the 2d array when an npc needs to know how to get across the map.

Highways:

At the same time, these lanes within the links can also be connected together, creating a highway. A highway contains the data of movement going in a single direction, which is used for monitoring the flow of a zone.

Drivers:

Lastly, drivers are the way we keep track of who/what is going along these paths and highways. We can get a count of how many are on a particular lane and divert the flow if need be.

Think of them as a taxi driver transporting a npc. The npc tells the driver where it would like to go. It is the driver who knows the path, how far they are into the current lane, and how much distance is left until the reach the final destination. The npc only knows of which NavNode is coming up next.

Postmortem

Final Product:

I didn't get the chance to fully implement the highway system. I had some memory bugs that popped up in month 3, forcing me to remove the more fussy sections of the code so I could return my focus to other systems. The driver structure is there and the actual lanes are in place, both of which perform as described. However, only individual lanes are monitored, not entire highways.

This system ended up being quick and efficient, though. A user only has to pass in a start position and an end position, and the NavMesh will figure out the nearest NavNodes. Using the nearest nodes, a path is retrieved from the 2d array.

A secondary use of the NavMesh was finding looping paths, which was done at run time. These paths were used for bombing routes by the Flying Bots and wandering paths for the Light Bots. These secondary uses are explained in further detail on the 'Flying Bot' and 'Light Bot' pages within 'AI Experience. '

What I Would Have Done Differently:

I can definitely see the limitation of a purely link based system. A system using quadrants between environment objects could help alleviate movement between narrow entrances. Steering behaviors were used between nodes, but I still think a quadrant based system would give a more natural flow as an npc traversed a room. Instead of rubbing shoulders with a wall when turning a corner, in a quadrant based system, the npc could head towards the center of the opening. The main reason I got away with using links is the the simple room designs in Mothership Mayhem.