AI Post Mortem (Game: Nexus)

Overview

I started early fall on a game team called Paragon where we built a top down networked multi-player shooter in a custom 3D game engine developed by our team. Using a component based engine and some previous knowledge from a past game I had worked on I was tasked with writing a bot system for our game. From this I had to learn and understand the following things that I had never tackled before: Path finding, converting 2D steering into a 3D world, writing AI with components, creating behaviors with actions, and my first chance to create a AI architecture. I'm going to explain what challenges I faced, how I solved them, and how I would / will change things in the future. 

A website to our game can be found here www.enterthenexus.net

No Guts No Glory

So when I first accepted my position on the team as a dedicated AI programmer I had literally had no experience with a lot of the systems I mentioned above, in fact the only thing I had really worked on before was some simple steering behaviors and a few enemy behaviors. So you may be asking well how did you implement all of these features over the course of a couple months with school work and everything else going on, and I will tell you right now it wasn't easy.

The first step was always research, find out what you can and look at games or people who have done this kind of work before. Some of the material I was looking at the time was some of Killzone's pathfinding work, articles on path finding, and simply just watching bot matches of games I owned like Gears of War 3 and Call of Duty Black Ops II. This was crucial to see how bots in these games worked and gave me a starting point as reference of where I should be heading.

Second talk to people about what they have done or implemented before. For me I was in a very fortunate position at Digipen to have professors like Ben Ellinger or Steve Rabin to help out and reference when I needed help. As well as fellow students enrolled in our masters program. But really if you can find anyone who has implemented anything at all related to what your doing it can help you a lot to talk to them.

Lastly as the title explains guts and passion. Taking on a huge task of finding out all of this personally drove me to work and learn as much as possible, so having a passion for writing game AI definitely helped me out there.

Path finding

The path finding in Nexus wasn't anything to write home about because after all it was my first time writing it after all, but many things were learned and discovered along the way.

First was to determine on whether or not to use a grid or mesh structure for representing the world. This was being passed around the team for a while until a helpful alumni mentioned that it would be easier to set up and get a grid based solution running faster, and since we didn't have a truly 3D world there wasn't a need to over complicate things.


So discovering this I decided on a grid based system that I then wrote and A* algorithm to run on the grid and find destinations. If your not aware of what A* and are just getting into game programming Google A* or Dijkstra's algorithm as a start, and there also some good AI books like Artificial Intelligence for Games by Ian Millington that can help you out. Once that was working we need a way to add in the environment objects into the grid and I wanted it to work with anything we threw at it. So actually taking a lesson from graphics I needed to transform the vertices of the environment obstacles into my AI's grid space and then I used a line algorithm to fill in the grid spaces that where marked by those objects, for this you can look up Bresenham's line algorithm. This was a great solution because when the map was loaded in, the objects that affect the AI were then loaded into the grid one object at a time and I didn't have to know exactly where all the piece were so it was completely data driven.

The last thing that we ran into now that we had working path finding and obstacles being successfully generated we needed a way for the AI to find its way around the map independently. To solve this a waypoint system was created for our level editor where we would manually place the points in the map that could potentially be high traffic areas or places to just cover the entire map. This allowed some control over where the bots could go to find other player and stopped them from trying to accidentally go out side the map.

2D to 3D problems

One of the more interesting challenges was learning to write steering in 3D. Ironically most of the math turned out to be the same or similar, so you might be wondering, Justin why is there a section for 2D to 3D then? All I have to say to that is Quaternions.

I personally had never worked with a Quaternion in my life and that was the case for my whole team it was a new concept to all of us, so trying to understand a structure that rotates things and is composed of imaginary numbers was a little difficult to grasp. Most of the steering behavior were easily made in our 3D world until things needed to be rotated.  For this we had multiple different functions to handle things using Vectors, Quaternions, and Matrices. In the end the best thing we ended up with and with the help of masters students we got linear interpolation or Lerp which would provide smooth rotation of anything that needed to be rotated. Moral of this story if you are going to use Quaternions make sure you do your research.

Writing AI for a Component Based Engine

This was one of the more interesting things I learned writing AI for Nexus. If you are unfamiliar with a component based engine I can give you a quick rundown on how it works and how ours generally works. Basically instead of writing an inheritance chain of objects you have a single object that adds components. Well what do you mean by that you might be asking? Basically everything is an entity and you add the components you need to make it work. So for example in Nexus we have tanks, well every tank needs physics, graphics, a method of control, a gun or turret, and sound emitters, so those are the components that get registered to the tank. If some thing ever needs more functionality we just make a component and just attach it to the entity. Our Engine runs by having a series of systems and components that work together. Systems handle the components and the entire engine handles the systems, but this is an AI post mortem so enough about engines :p


Writing this into our AI engine it boiled down to actually 3 major components (there is a much better way to do this and I will explain it later in this post) Steering, Data, and Logic.
Steering handled all of the movement for that AI, Logic handled all of it's behaviors, and the Data held all of the information that the AI would need to know like it's current target, how fast it can move or rotate... etc. All of these components were then manage by and AI system that updated each component with the right information and handled any shared data between the components. This worked well for Nexus and got the job done for what we needed it to do.

Building Bot Behaviors

This was probably what I had spent most of my time doing for Nexus was trying to make challenging bots for our game, and of course it was the part that ran into the most problems.


I'm going to start out by saying our game wasn't always just team deathmatch in fact it was supposed to be exclusively a game where you capture crates. I spent a long time writing code for bots to path to a crate and get them to successfully push them back to base so they would then be captured for points. Unfortunately, but in reality it was a much better decision, by the time I got this working in the game we scrapped the idea due to it's lack of fun. Turns out nobody wants to push crates around the map and it's not fun... that was a duh moment for our entire team when we found that out and we had to  re write the AI for the game.


So what happened and what went wrong in this crate pushing bot? You might be wondering in case you want bots to push stuff. Well here is what we tired, the first attempt we wrote a tracking system that when a bot would see a crate it would save that object into it's data and then generate a path from the crate to the capture point then we calculated the direction the crate had to travel to get to the zone and flipped it so it would point behind it and found the point behind the box to which the bot would travel to. The bot would then upon reaching that spot move along the crate path until the crate was captured. Seems good right now, but there were lots of edge cases. For example what if the crate is in the corner and you can't get behind it? Or when the bot gets to the crate what if some one moved it? Or what happens if the AI loses the crate or is to far away from it? Some of these were fixed by adding timers or distance checks with the crate to see if it was worth re-pathing to the crate or not or if they should just ignore the crate and fight people if the crate was lost. The most difficult one was actually crates in corners, not only was this a problem for AI but for players as well. We ended up adding a "magnet" that would pull crates into your tank sticking to the front of them. This also made the pathing easier because once an AI had control of the crate he could path back himself and I didn't need to generate a path from the crate anymore. This did end up working, but like I said it all got scapped anyway and sometimes you just have to watch your babies die :/


Once that idea was scrapped all I had to do is write deathmatch bots which were much simpler. We used a series of actions to handle this along side of signals for line of sight and taking damage. These actions were boiled down to path find, find target, attack target, and use ability. This allowed the AI to do multiple things at the same time in a action list with multiple lanes. To keep things fair as well we added gaussian aiming for the which is a fancy way of saying the aiming accuracy was pulled from a normal distribution. This allows for a more controlled random and realistic looking shot for the AI. With the abilities we wrote a utility system to score each ability according to variable like health, distance from the target, and the damage or threat level of the target. If you don't know what utility is there is a great book called Behavioral Mathematics for Game AI by Dave Mark that I read while working on the game that explains all you need to know about it.

Now one thing that I personally felt wrong about doing for Nexus, but in turn it happened to make the game more fun for some people was I was required to change the bots from being more human to more AI. Once again you are probably saying wait but don't you want it to be AI? What's wrong about it being more AI? Well bots are supposed to be random and you want them to best simulate things that players would do and not what AI does. So part of a design constraint forced us or rather me to write the AI to be more predictable, so now each bot has a distinct play style if you will rather than keeping it more random. However, if it makes your players happy then it must have been the right change.

The Future and Fixes

So here are the real lessons learned from this experience I guess the things I would change and why I would change them or how things could have been better now knowing how naive I was when I started this project.

Fix 1: Waypoints and path finding

For one my path finding was never time sliced and would sometimes hog lots of processing power from the game and mistake I will never make again. Not that this killed our game, but if we had maybe 16 -20 players or bots rather it could potentially have killed the game's frame rate, so if you can time slice your path finding do it.


Waypoints were good but the problem was it relied on someone manually placing them into the map for the AI to work if there were no waypoints the AI can't go anywhere. There are 2 quick solutions I thought of one of which still involves waypoints and automatically generating them a little more complex, but at least no one has to place them manually. The second more effective solution I came up with is use influence maps, and these could be anything. For example move towards locations with high influences of death, opponent team density, or even just places that have had traffic in a while and that would make the AI more believable than travel to set places in the map.

Fix 2: Components and structure

In retrospect almost everything should have a timed update or delay because the AI doesn't have to be calculated every single frame in fact why not every second or half second the player wont even notice and your saving some processing power good job you :D

Also some components got bloated really fast the logic component was over 1000 lines of code and it could have been split into a better architecture such as follows: Steering component, pathing component, sensor component, behavior/ logic component, data component, and utility component. This would keep the code more modular and makes it clearer what is going on. If you take the time to really plan out and examine what your AI will be doing it will be easier to write the System structure of how it will all work and make it easier to understand.

Fix 3: Utility and Actions

Although utility was a very late addition to the game it was done in a messy way, and could be improved because it was really only used for abilities. The system itself was a rushed extension as well so even though it worked it could have been done better. The first thing I would change was to apply it to all of the actions and not just the ability this would have made for some more interesting AI. For example just adding it to the AI targeting action would have chosen more interesting targets, and a little quick restructuring of the action to handle the score for all of the them would have made things more interesting to. Also I didn't have the time to make it, but if you can make a tool to visualize your utility functions it will be much easier to create and manage your functions and tweak your values for each action you are scoring.


That pretty much sums up my experience working on the AI system for Nexus if anyone who reads this has any questions you can e-mail me at justinmaio01@gmail.com
Also if anyone is interested in a more in depth detailing of any concepts or system described above or one anyone would like to more about let me know and I'll write up whatever knowledge I can about the topic. :)

Also in the next couple of months I will be doing some independent AI projects as well as starting work on my next project which is a co-op networked game that I plan to implement nav meshes, squad tactics, and player modeling to so I will have some information about that over the next couple months.

Justin Maio