Non-Player Character AI in RPG Elements

     One of the most important parts of my RPG game engine is non-playable characters, also known as NPCs. Interacting with these characters is one of the most important parts of the game, and the more realistic these characters behave the more believable the virtual world becomes.

     I want to design a system for describing behavior that is at first simplistic but can gracefully extend to include more advanced behaviors. Initially I want to be able to describe a behavior of a couple random or sequential actions. For example, a character that paces around randomly and then occasionally jumps. Designing a system to handle this simple behavior is trivial, but it may not extend well when I want to implement more complicated behaviors. For example, I want to eventually add tasks and goal oriented actions. These actions will not describe a sequence of individual actions but require the character to choose a sequence of actions to achieve a described goal.

     I plan to solve this by using having an action queue. The queue is populated with the current action and the next actions the character plans to preform. Some actions correspond directly to an atomic physical action like preforming an animation or moving. Other actions are made up of many atomic actions generated dynamically. When the first action in a characters queue is one of these more complicated actions it break this action down into its atomic actions. So the solution is a queue of actions where an action can be an atomic action or a more abstract complex action.

     I have so far come up with a four types of complex actions. The first is a simple sequence of actions the character preforms in order. The second is a weighted set of actions preformed in a random order with preferences to a particular action based on the weights. The third is a goal oriented action were all that is described is a goal and the character must generate a set of atomic actions that will allow it to complete the goal, it must also re-evaluate its decision at each step to consider changes in the world that invalidate the plan. The last type of action is a utility oriented action, this type of action is the most abstract since it only specifies some need that they character must satisfy, such as satisfying its hunger, and this action can be composed of many goal-oriented actions.

     Each one of these action types gets progressively more abstract and requires the character, rather than the game designed, to do more of the decision making. Well it is possible for the character to have complete information about the world this would not be the most realistic. A possible extension I have thought about for this system is to have the character build up its own model of the world which includes imperfect and erroneous information about the world. Characters would then benefit by interacting with each other to learn and complete goals. While this would be an interesting experiential I anticipate that this feature is still a long way off.

     In the meantime I have implemented the first parts of this description in my game engine. I have atomic actions, sequences and weighted sets working. Since each level of action gets progressively more abstract it is necessary to describe some lower level actions before the higher level ones can use them.

     In the near future I intend to start writing some goal oriented actions, specifically related to moving a character from one map to another. I talked about how I am able to build a graph of my maps based their connections. My characters will plan a route from a point on one map to a point on another map first by calculating a least cost path through this map graph, then as they arrive at each map they will calculate a path from the entrance door to the exit door, making this a two tiered search technique. There is one issue I still need to resolve, currently the map graph does not show which doors in a map are unreachable from other doors. If a character plans to enter a map through one door and exit through another but there is no way to reach the exit door the search algorithm will fail. This problem is made more complicated by the fact that objects in the world could possibly move and block the path after it has planned its route.

The diagram shows that a character can not simply find a solution by considering what maps are connected, it must also know what connections are reachable from each other

     There is one other component of NPC behavior that I plan to implement, which is how the player interacts with the them. In some of the original RPG games NPCs would respond with a single message every time the player talked to them. This style has persisted in many newer games but a few recent games, like those in the elders scrolls series, have come up with much better ways of handling these interactions. In games like Morrowind, the player is presented with a list of questions that they can ask an NPC, and the NPCs responses vary based on how much they like the player. This may seem like a large amount of dialogue that the designer must write but much of it is shared between characters. Some conversation topics are global, which means every NPC can be asked this topic and gives the same response, the responses can then be customized based on the attributes of the NPC and the topic can be qualified to be only ask-able of specific NPCs. My plan is to implement a conversation system that is similar to this but I also hope to develop ways of generating some simple conversation topics to reduce the amount of work required by the designer. Another problem I realize with this system is that eventually the list of topics will grow to be large, and I will eventually need to develop a way to search it quickly and intuitively.

     I believe that NPC behavior and interaction will be one of the most interesting features going forward with my project. I also believe it will be a very challenging process with the potential for many exciting innovations. Despite the challenge, I am confident that by simulating more realistic NPCs my virtual worlds will seem more alive.

Character State Management

   When making a game how should the program decide when the player should be walking? Well, maybe if they press the arrow keys. But, then what if the character is crouching and you would like the arrow keys to make them crawl. Also, what if you want the character to jump when the up button is pressed but only if the character is standing and not walking. One way is to have a variable for jump and another for walk and one for crouch, and by using a large combinations of if-statements you can determine the animation that should be played.

   Anyone that has followed this way of thinking before will know that eventually this if-statement will get large and the number of state related variables grows quickly. Once the number of variables becomes too large, handling the various exceptional cases becomes nearly impossible.

   When I started I too faced this problem, however I have since found a much more elegant solution. I have found that all of these states can be described as a finite state machine. Game developers can benefit from this approach by clearly defining which states can transition to others and by abstracting the transition logic away from keyboard inputs.

   To start a programmer needs to describe a simple generic finite state machine. A finite state machine consists of a graph of nodes representing states and directed edges representing actions. The state machine keeps track of its current state and when it receives an action it move to a new state only if it has an out going edge with the same action. Then, Once we have a generic finite state machine we simply draw whatever animation we want to associate with a particular state.

   One thing to note in the design of my state machines is that I never make the action refer to user inputs. This is because not all of the characters in my game are controlled by the player, so for non-player characters it does not sense to think of actions as user inputs. This also gives me the flexibility to change the inputs later if I want to run it on another platform, like the Xbox360 which has buttons and joysticks rather than a mouse and keyboard.

A partial character state diagram from my RPG game engine

   I have used this technique in my RPG game engine and have found it extremely elegant. I no longer need massive if statements for determining what character animation should be drawn. I have also found it has enabled me to have more complicated character actions, like action combos, that I used to find very difficult to program.

RPG Elements: Console Improvements

     Back in February I wrote a blog entry about an RPG game engine that I was working on called RPG Elements. I have been busy with university, however I have found some time for implementing interesting new features. I am most excited about some of the new features I have added to the map editing tools recently. These tools allow me to create maps much more quickly and even generate hundreds of simple maps in mere seconds.

     I mentioned in my last blog entry that the main editing tool is an in-game console with commands for adding new objects and creating new maps. As my engine has evolved many features had become merged with the console that really should not have been, for example the actual logic of the console commands in many cases needed to be separate functions. With all of the unrelated logic in one place, adding new commands became increasingly difficult. To fix this problem, I refactored the console by moving these features into more appropriate modules, I also separated the console commands into there own classes. Now the console module is complete independent of the commands which it runs.

     When I refactored the console I realized that I needed to redesign the settile hotkey. In my RPG engine, the map is represented by an array of tiles, the user can set the type of the tile their player is standing on by typing "settile <type>" into the console. Because this is such a common operation, it is not practical to make the user type this command in every time, so I had the console remember the last arguments passed to this command and then all the player would need to do was press the "w" key to execute the same command again. However, now I made the commands independent of the console I no longer wanted the console to be storing the arguments of a specific command. Well I was thinking about how to fix this I suddenly thought that it might be nice to have this hotkey feature for other commands or have hotkeys for different arguments. So I came up with a new console command that can assign any console command to any of the number keys. For example, "hotkey 1 settile;sand" sets the tile under the player to sand when the 1 key is pressed. Another advantage of this feature is that I can assign "sand" to the 1 key and "grass" to the 2 key, where before I would have to type in a console command every time I wanted to switch between the two tile types.

     For my next feature I wanted to be able to write a list of console commands in an external file and then have them executed sequentially. When I refactored my console I realized that this would not be very difficult to add and would help easily accomplish what I had originally designed my engine to do, generate a large amount of content with minimal high level user input. One difficult I was confronted with was that loading maps took a couple milliseconds to load and scripts executed in a separate thread. I solved this by adding a command to tell them to wait a certain number of milliseconds to give the map a chance to load. Another problem was that because I am executing hundreds of commands at once I more frequently come across some of the race conditions that I had noticed occasionally in the past. While at the moment these race conditions seem an annoyance, I think of this as an opportunity to find and fix these serious bugs that would not have been possible with manual testing. I am excited about how quickly I was able to add console scripting and I believe it will be very useful going forward.

     With the addition of console scripting I can now generate hundreds of maps and add doorways between them. I thought it would be interesting to visualize all of these maps and their connections, so I wrote a console command that would query the list of doors to identify the directed edges between the maps. The program then outputs a file with a list of these directed edges in a format that I can input into a graph making program called Graphviz. Well this graph is interesting to see now, it will be very useful for some of my planned features. One feature that will require a graph of directed edges is non-player character (NPC) path finding, eventually I want to program NPCs to walk between maps, and by analyzing graphs like this they will be able to identify the best path.

An example map graph generated using test data based on a popular classic RPG game. At this point all of the maps are empty, aside from doors (represented in the graph by directed edges)

     By improving the tools in these ways, along with some other minor improvements, I have greatly reduced the amount of work I need to do to create a map and can now focus on higher level design decisions. Well these tool improvements are very interesting, they are not the only new feature that I have implemented since February. In one of my next blog entries I will talk about some of the other new features. I am also hoping I will have time to upload another video to demonstrate some of these new features. In the meantime I am adding new feature to this project and the next big area I need to improve is NPC behavior and interaction. So stay tuned!

New SimCity Engine

     A couple days ago I wrote a blog entry about a simulation game that I had written to learn SDL and improve my C++ programming skills. I showed this project off at the game developers club and it reminded them about the new SimCity game that was just announced. The game was announced at a recent game developers conference where they also explained a bit about their new simulation engine called GlassBox. The algorithm that the engine uses has a particularly elegant design which I find very interesting.

     The system defines five basic object types: resources, units, maps, globals and agents. Resources are variables such as people, money, electricity. They are organized into bins that can store a limited amount of a resource. Units are physical objects in the world like houses. They are defined as a collection of resource bins. Maps are used to represent the distribution of resources across the environment. They are essentially an array of resource bins with one associated to each map tile. Globals are like units, since they are a set of resource bins, but do not represent physical objects. Lastly, are these things called agents that move around the environment distributing resources between resource bins. Game developers represent these different types of objects using rules which they define in scripts. [1]

    Game developers are able to simulate various natural phenomenon using these simple constructs (as can be seen in this video). For example, a map can be used to represent resources like underground minerals or areas covered by forests. Agents are used to represent the distribution of electricity, pollution or the movement of cars and pedestrians. According to the article the company that makes SimCity believes this engine could be applied to their other simulation games like, one of my favorites, SimTower. [1]

     Although this design seems very elegant I feel that there many some potential problems which have been left out. One aspect that may pose a problem is that there may be tens of thousands of independent agents running in parallel at any given time. Well this seems beneficial in the era of multi-core computing, managing these agents and ensuring mutual exclusion is non-trivial. Another thing to consider is if so few constructs can accurately represent everything needed in a simulation game with over simplifying some aspects.

     I believe that this engine was very elegantly designed. This level of elegance is what I often strive for in my own programs which is why I appreciate how difficult it is to achieve. To create such an elegant engine, software developers often need to iterate and rewrite the program, each time removing unnecessary or redundant features.

     I would very much like to try and implement a similar engine one day and this engine it was interesting to read about. Game development companies are often very secretive so when they reveal this kind of information it is very valuable.

References:
[1] Frank Cifaldi. "GDC 2012: Breaking down SimCity's Glassbox engine" Internet: http://www.gamasutra.com/view/news/164870/gdc_2012_breaking_down_simcitys_.php, March 7, 2012 [March 21, 2012].

Factory Simulator

     Last time I mentioned that I was writing a game in C++ using the graphics library Simple DirectMedia Layer (SDL). The goal in writing this game is to practice C++ and explore some of the popular C++ libraries available.

     I discovered that SDL has many similarities to XNA and was not difficult to learn. I was able to start making my game within about an hour or two of learning SDL basics.

     I decided to make a simulation game, similar to games like SimCity, since this is a style of game that I enjoyed when I was younger but most of my favorite series have since become discontinued. I came up with an interesting idea for a factory simulator where the player owns a factory and must manage the happiness of the workers. Then I broke the problem down in to the simplest parts so that I could plan to implement it in roughly two days.

     In my game the player can build three types of buildings: houses, power plants and factories. The houses produce workers, the power plants produce power and the factories produce money. Also, The factories can only produce money if they have enough workers and power.

     So far I have implemented everything I mentioned but will refrain from showing any pictures just yet since it is still mostly text based with a few placeholder graphics.

     I plan to extend this by giving factories different kinds of input and output resources, for example a paper factory might require wood as an input and produce paper as an output. By doing this I can create chains of resources that the player needs to manage, for example a logging camp is required to produce wood for the paper factory. Also, since the game is about managing the workers happiness I need to keep track of the mood of each worker which will be affected by factors such as wages, safety, housing and environment.

     Overall I have enjoyed learning SDL and I think it is a useful graphics library. It handles most of the same aspects of drawing 2D sprites to the screen as XNA and has extension libraries for drawing text, handling input and playing music. To draw 3D graphics it is common to combine SDL with OpenGL which is something I may try in the future. In contrast to XNA, I have not yet figured out how to use pixel shaders but suspect that I may need to use OpenGL's GLSL shader language which I have heard is more complicated than XNA's HLSL.

     I plan to continue working on this game in, my free time, to practice my C++. If I get it to a more complete state I will post some pictures and videos in a future blog entry.

XNA Game: RPG Elements

    The projects that I have talked about so far have been ones that I worked on in the past. Today I will talk about a project I am currently working on. It is called "RPG Elements" and is the third major iteration of an RPG game engine that I have worked on for just over a year, although this iteration was rewritten pretty much from scratch in about a month. Through building and rebuilding this engine I have created many interesting features and today I will talk about the most fundamental, and leave some of the more advanced features for another time.

    My goal for this project was to design a tool that could create a game with minimal effort required by the designer. I identified that most of effort is spent in designing the levels so I wanted to make this as simple and intuitive as possible. In previous iterations I had tried making a variety of different editors but I found this to be a lot of extra work. In this iteration I took a different approach, I designed the engine so that all of the data can be edited while playing the game using a console. My biggest surprise was that this console was very easy to implement because of the data structures I had used for storing my data. Then to make editing easier I added shortcuts and hot-keys for common console commands to make editing quick and intuitive.

A Logo Graphic I Designed

    To demonstrate this I will explain step by step the creation of a level. First the user types in the console "newmap" and the dimensions of the tile map. Then they draw background tiles on the map using the player as the cursor. Then, in the console they type "addmapobject" and the name of the object, such as tree or house. The player can then grab onto this object, walk around and drop it where they want.

    In this style of the game, the player walks around a virtual world and interacts with objects. These interactions are known as events. An event is composed of a set of actions that are executed sequentially. There are many different types of event actions, such as teleporting the player to another map, displaying a dialog box, asking the user for some kind of input, etc. Event actions have flow control in the form of "if" statements and loops and multiple events can also execute in parallel. As a result, events are implemented almost like a mini scripting language. Common events, like doorways that teleport the character between maps, have been designed to be especially easy to create since they are so commonly used.

    With these two fundamental features I can design most of what I need for my game, and my more advanced features are typically composed of or supplement these features.

    At this point my engine is in a fairly complete state and I am in the process of using it to create a game. In a future blog entry I may talk specifically about this game, in addition to some advanced features, but it is still in the very early stages.

XNA Game: Tactics Game

     After working on Crazy Party Fight I decided to give another shot at developing a game in XNA. This time I tried to find a couple of my university classmates to help me with a bit of the coding.

     We decided to make a tactical turned based strategy game. For those not familiar with this genre it is basically like chess but with custom pieces and other role playing game elements added. In our game each player would move each character individually during the movement phase and then if they were within range of another character they could attack during the attack phase. The goal was to defeat all of the opponents pieces.

     We decided on a couple of interesting design features for this game, one was the use of an isometric board. Isometric is a type of camera projection that in 2D games basically results in angled diagonal tiles. This makes movement a bit more difficult to deal with because it is on a diagonal but gives the game a bit more of a 3D art style. Another difficulty was implementing the opponents AI. One simplification that we noticed with other commercial games of this genre was that the player always moved each piece during each turn, instead of one piece per turn like in chess. This simplification allowed us to consider a reasonably good move for each piece rather than trying to figure out which piece would be best to move. Although our AI is relatively simple compare to  some chess AI, the strategy of a tactics games is more based on the comparative strengths and weakness of the pieces rather than their positions on the board. There are also elements of randomness thrown in to determine if an attack is successful or results in a critical hit.

     Unfortunately, my attempt at making a project as a group fell apart just as we had finished implementing the core mechanics of the game. The failure was probably a result of the other group members not feeling any real obligation to work on the project. However, convinced that we had created something interesting, I decided to continue working on the project to get it to a stage where it was presentable. I replaced all of our place holder graphics with new ones I made in Inkscape, and created all of the menus for choosing a level and positioning pieces.

Screenshots and Characters from the Game

     After finishing all this work I created the YouTube video you see at the top of this article. Surprisingly this YouTube video has attracted a large number of hits, about 5500 at the time of this writing, which is large compared to the one or two hundred hits my videos usually get. Clearly, this is a genre of game that is particularly popular, especially among indie game developers.

     The final result is still a work in progress. I would really like to continue and finish this project, especially considering the YouTube popularity. However I have always been to afraid to, since I have a vague memory of just how much refactoring is required, especially of the parts I did not write. Another factor that holds me back is the amount of art content that I would need to create. Being a programmer I am not most efficient artist, and yet I am also a bit of a perfectionist when it comes to my personal game projects.

Procedural Maze Generator

Part of a Generated Maze

In my last blog entry I talked about my map generator. Shortly after making that generator I created a second one for generating mazes.

Mazes are a very fundamental part of video games. Most maps that the player actually plays through, be it a building, forest or cave, is really just a maze in disguise.

Part of a Maze with Multiple Solutions

The maze generation algorithm I choose is called the recursive subdivision algorithm. There are several different algorithms to choose from but this one seem the best for my needs since it could create a maze with hallways and rooms of varying sizes.

The algorithm is simple: Start with a rectangle, divide the rectangle in half with a wall and leave a gap or doorway somewhere along that wall. Then take each of the half rectangles created by this division and recursively divide them. Continue until the rectangle is the desired size.

A Maze with Wider Doors and Walls

This algorithm has many ways that it can be controlled to create different types of mazes. One way is to control the number of doors in each wall. If every wall has one door then the maze will have only one correct solution. If the walls can have more than one door the maze will have multiple solutions.

The most important part for me was the ability to control the size of the hallways and rooms. To create rectangular rooms I set it so that it would stop dividing rooms when they were between a certain size. To create long hallways, I set the width of the walls to be greater than one.

This algorithm is just a proof of concept for the moment, but I hope one day to use it along with my map generator to generate levels for a game.

Procedural Map Generator

 

    You might have wondered what inspired the title of my blog. It actually comes from a procedural map generator that I wrote two summers ago. It only took me one afternoon to write it and yet it can generate millions of unique maps in a very short time. It is based on two well know algorithms, Perlin Noise and A*.

    Procedurally generated content is a topic that I was particularly interested in at the time. I was fascinated by how you could write a quick program that produced nearly infinite meaningful combinations based on a few simple rules. One of my earlier projects was a procedural riddle generator which used template sentences and then inserted words of the right category to form a sentence that sounded like the question part of a riddle. Most of the time the riddles were nonsensical but often they were funny.

    The goal of the procedural map generator project was to create a map that could be used as a high level representation of a role playing style video game. The world would contain towns and the player would need to travel along pathways to get between the towns. The towns would be ordered so that the player visits the towns in order. The pathways would need to have ordering also, so that obstacles could be placed between towns to prevent the player from traveling to them out of order.

Example of Perlin Noise

    To create most of the natural qualities of the world I have used perlin noise. Perlin noise creates a set of random numbers that have several local maximum and minimum values with a smooth gradient in between. If we create a 2D set of perlin noise and render these values as a black and white image we get something that looks very similar to a topographical map. Using such a map I can set a threshold value where any point less than the threshold is water and the rest is land. Using another two thresholds we can produce a map with deep water and mountains. Forests and deserts are placed using two newly generated sets of noise since they are not depended on terrain height.
 


     After I had generated the natural landscape I needed to add in the towns and road. The towns I simply added randomly, making sure that they were not placed on water and that they were at least a minimum distance apart. Then to connect the towns I used the A* path finding algorithm to calculate a least cost path between two cities, which I repeated until all of the cities were connected. It is important to note that the least cost path is not the shortest path since the shortest path might make the road cut through a large body of water or a large mountain range. Instead I assigned costs to different types of tiles with grass having a low cost and mountains and water having a high cost. As a result, roads generally travel around water and mountains unless they have no other choice or the alternative route is much longer.

A map generated using the algorithm

    Obviously this is a very simple algorithm and can easily be improved on. One feature I would be interested in adding is rivers, rivers generally travel from high land to low land so a hill climbing algorithm might be a possible solution. I have also though of adding the concept of resources, such as water sources, minerals, lumber, etc. I could then change the locations of towns to be in areas close to resources. Climate and weather are properties I could also try to simulate to have more naturally placed deserts and wetlands.

    In conclusion, this map generator was very simple to write yet produces something that seems very creative in a very short amount of time. Hopefully this gives a better idea of why I choose the blog title, "worlds per minute", especially considering that this was only the first in a series of projects that I am still currently working on that have the goal of creating a large and dynamic virtual world in a very short amount of time.

XNA Game: Crazy Party Fight

In my last entry I mentioned a YouTube video of a game I had made. I thought today I would explain a little bit about that game.

The game is called Crazy Party Fight and was written in C# using Microsoft's XNA Framework. XNA is a development kit for the Xbox360 and other Microsoft devices like the windows phone. During development of this game I actually ran and tested it on my Xbox 360.

Crazy Party Fight is a party battling game for 2 to 4 players. You get points by jumping on the other players heads. Also, occasionally items fall from the sky and if a character collects one it has an effect such as shrinking the player, making them run quickly, or jump really high. Something I put much of my time into was the in game character and level editors. The idea is that players can create their own characters and levels using a collection of pre-made parts.

This game was the first major game project I made using XNA. I worked on it in my free time for 4 months one summer during second year university. The goal was to submit it to a contest by the end of the summer, not that I had a hope of winning, just so that I something to work toward, hence why in the video you see a team name.

Characters created using the character editor

This was the first game I developed using the programming skills I learned from university. All the games I had made before this I made using a graphical tool or at the most involved writing a couple of simple scripts. Everything in this game was made by me, except for audio which I obtained from online game resource sites. All of the graphics I made using the open source program Inkscape which has since become my favorite drawing program for game projects.

I have often been asked why I never finished this game. The fact is that this was my first game project and by the time I got to this point in the project the code had become completely unmanageable. The amount of time to add each new feature was growing rapidly and it was no longer worth continuing. I felt I could learn so much more by starting other projects and trying new things, instead of spending months trying to refactor all of my code and fix all the bugs.

Through making this game I did learn from my mistakes. One of my biggest mistakes was that I did not realize that you had to release the memory for images and as a result had massive memory leaks by the end. Another thing was that I spent so much time making the level and character editors that the actual game turned out not to be very fun to play.

Crazy Party Fight was in many ways the beginning of my game development projects. I will talk about some of my other game projects in future posts.