Thursday, 28 November 2013

Navigation Mesh, Path Finding and Implementation in Resistance 3

Artificial intelligence is creating the illusion of intelligent agents.

In class we discussed that a navigation mesh is a simplified version of the complex level mesh. We also talked about Recast which is a handy tool that will import the mesh of your level and will create a nav mesh from that. Now how does it do that? The image below outlines the process at a very high level:

Figure 1: Recast's Navigation mesh generation algorithm. Source: Insomniac Game's GDC 2011
I wanted to talk about something that we sort of touched on in class but didn`t go into too much detail about: so you setup Recast, generate your Nav Mesh…now what?

What algorithms and data structures do you use to store this data and once you store this data, how do you use it to create “intelligent” agents?

You may say “just put it in a graph and traverse the graph using the A* algorithm”, and that’s correct but what type of graph implementation should you use and how do you implement A* traversal? In this post I will talk about a couple different ways to store graph data and the A* graph traversal algorithm. I will also briefly talk about Insomniac Game’s implantation of these things in Resistance 3.

Storing The Data

Well let’s reflect on the data we have from our nav mesh. We have nodes, which are the vertices which make up the triangles and edges which are the lines that connect the vertices together. Consider the following example:
How would you, the human capable of thought go from the green square to the red square? Nothing is blocking you so you would simply say “just go in a straight line”, which is absolutely correct. But the real question is how would the computer perform this task? The computer knows which node it is currently on (the green one) and which node it needs to get to (the red one) and that’s it. We must define a relationship between the nodes. These relationships are known as edges. An edge connects two nodes and defines that if I am on node X I may travel to node Y. The question now is how do we do this? Well we could just have a giant matrix and store Boolean values which specify whether two nodes are connected or not. This is known as an adjacency matrix.
Example of an adjacency matrix. Source: Programming Game AI by Example by Mat Buckland

In the example above, the matrix stores which nodes a given node is connected to and which nodes it isn’t connected too. A "1" defines that there is a valid connection and a "0" defines that there is not a valid connection. This is a perfectly valid data structure but it wastes quite a bit of memory. Another more memory efficient data structure are adjacency lists. Adjacency lists allow you to deduce the same relationship between nodes but use significantly less memory. This is done by simply storing which nodes a given node is connected too and making the assumption that any other node not on the adjacency list is not connected.

Example of an adjacency list. Source: Programming Game AI by Example by Mat Buckland

For each node, you must specify which nodes it is connected to. Storing an adjacency matrix for each node would be a memory massacre so use an adjacency list instead. Below is how you could go about storing your navigation data.

How I stored data for navigation in a past project
Each node has an ID which I use as an index into the two lists in the code above. For example: Data about Node 0 is stored in index 0 of the _nodes list and the adjacency list for Node 0 is stored in index 0 of the _edges list.

Traversing the Graph

Now that you have your data organized in a nice graph, you can finally traverse the graph. There are many algorithms to traverse a graph, if you are interested in learning about these algorithms I highly recommend the book “Programming Game AI By Example” by Mat Buckland, this book goes into great detail about each traversal method and provides excellent examples. The A* algorithm really is the best of the bunch, not only does it find the most efficient path from A to B, it’s also the fastest.
Suppose I place some obstacles in our example above:

The blue path is the most optimal route returned by the algorithm. Those red branches are all of the paths that the algorithm once considered. Clearly from this visualization, you should be able to see that the computer’s method of finding the most optimal path varies significantly from a human’s. The A* algorithm is a cost based search. This means each edge has a cost associated with it. It also means that the most optimal path may not necessarily be the one with the least amount of nodes.

Resistance 3

In the Insomniac Game’s GDC 2011 talk about navigation they discussed that the Recast library was used to generate their navigation meshes. Their usage of AI using navigation meshes is rather straight forward, it is outlined below:

First they are requesting and setting the requirements that an agent needs, then they are finding and smoothing a path. Smoothing a path is done to create a more natural movement of an agent as the follow a path. An exaggerated example of this can be seen below.

They are then using an obstacle avoidance steering behaviour to ensure the agent does not get stuck. The obstacle avoidance steering behaviour is not very difficult, you essentially just cast a sphere around your agent and test for collision, if there is no collision then carry on if there is the obstacle avoidance function will return a direction vector pointing away from the obstacle. Since steering behaviours can be summed together (via weighted average), if you are performing both avoidance and path following on an agent, the direction will point away from the obstacle and will still guide your agent to the next node in it’s path. In the most simple implementation of steering behaviours, this direction will be multiplied by your agent’s speed and therefore move your agent in that direction.

Since the agent is not just sliding along the path, its also animating so they may have special animations when specific obstacles are encountered. For example if there is a knee high obstacle, instead of making the agent awkwardly run around it, they may just play a “stepping over” animation.

I asked this question before, but I’ll ask it again: You the human see a knee high obstacle, what do you do? You just step over it. Now how will the computer know that an obstacle is knee high? The way Insomniac solved this problem was by having a designer go in and place identfiers on specific obsticales in the world and when an enemy encourters one of these identifiers, they would handle it accordingly. For example there is an enemy who is able to jump onto roof tops and there is another enemy who must go around. Both enemies use the same nav mesh, by placing identifiers around the world, and giving each AI a type, you could do a condition:

If (obstacleIdentifier == Building && agent.Type == roofJumper)
If (obstacleIdentifier == Building && agent.Type == roofJumper)

Now ofcourse this is just a simple example, but hopefully it gets the point across.

Tuesday, 12 November 2013

Compiling PhyreEngine’s Collada Plugin for Maya 2014

In the previous post we went over PhyreEngine’s setup process, the previous post was more of a tutorial and with this post I’m going to take a different approach and try to walk you through my thought process. If you are not interested in my thought process and just want to see how to compile the plugin for Maya 2014, scroll down to the TLDR at the bottom of this post.*space*
The asset pipeline in PhyreEngine at a very high level is as follows:

   I.    Create asset in Maya or 3DS Max  
  II.     Export asset in Collada (.dae) file format 
 III.  Convert asset data to platform specific runtime asset
    This is a heavily simplified version of Phyre’s asset pipeline, in a future blog post I will get down and dirty with Phyre’s asset pipeline and go into a lot more detail about it.

    When we installed PhyreEngine, there was an option to install exporters for Maya. So that means Phyre installed the Collada plug-in for us…right?

    So I went into Maya 2014 and of course, the exporter wasn’t there. First thing I did was try looking for the exporter in the Phyre directory.

    Image 1. Versions of Maya PhyreEngine 3.4 installs the exporter for
     It turns out PhyreEngine 3.4 installs the exporter for every version of Maya…except the version we’re using, Maya 2014.

    Collada files have the .dae file extension. I noticed that Maya has a .dae exporter so I figured it wouldn’t hurt to give it a shot. Long story short, it didn’t work. The engine would complain and wants us to export models using their exporter.

    So at this point, the way I see things, I have two options:
    1.    Use Maya 2013
    2.    Solve the problem

    Spoilers: I solved the problem.

    Jumping to Maya 2013 would be taking the easy way out and was considered the last resort. Now I am going to go through my process of solving this problem. The first thing that came to mind when I saw all these different versions of the same plugin for the different versions of Maya was “has the creators of Collada written a version for Maya 2014?” so I went to the Google and searched for “Collada”, of course I went straight to Wikipedia. To my dismay I saw that the latest version of Collada was created in August 2008, 5 years ago. So I immediately started to wonder: “how could it be that a plugin that was written in 2008 is able to work with a program created in 2014?”

    My first thought was: maybe all of the Collada plugin files are the same and Phyre’s install just simply copies the plugin into the appropriate Maya directory (defined by an environment variable), but since Maya 2014 wasn’t released when this version of PhyreEngine (3.4) was built, Phyre doesn’t know the name of the Maya 2014 environment variable and therefore cannot put the plugin in the appropriate folder. So I tried simply copying the Maya 2013 plugin into the Maya 2014 plugin directory.

    Maya’s plugin manager was able to find the plugin. However enabling the plugin resulted in several errors, so obviously this means each version of the Collada plugin for Maya is in some way different. Let’s try and figure out how.

    Fortunately PhyreEngine gives us the source for the Collada plugin for Maya. I opened the source and I had no idea where to start. So I tried to just build the project, and it failed. Never in my life have I been so thankful for a project to fail compiling.

    Image 2. Errors when attempting to compile Maya exporter

    The compiler is very clearly telling us that it cannot find a file. Also we see that the directory it is looking for is using angled brackets, rather than quotes. This means that the directory that the project is looking for was added to the “Additional Include Directories” project property.

    Navigating to the Additional Include Directories property (Under C/C++) and inspecting the values we see:

    Image 3. Include directories for Maya 2013 plug-in. Note the "2013" in the file path.
    In the image above we see that the project is looking for the Maya 2013 environment variable which defines Maya 2013’s directory. Very, very interesting. Let’s look at Maya 2012’s property pages.

    Image 4. Include directories for Maya 2013 plug-in. Note the "2012" in the file path.
    We see the exact same thing. This means my first thought wasn’t that far off. Each of these Phyre build configurations were manually made by the PhyreEngine team to specify the install directory of a specific Maya Version. Since Maya 2014 wasn’t out when this version of Phyre was released, they could not make a configuration for it.

    So how do we fix this? I created a new build configuration for Maya 2014 in the configuration manager. I also chose to copy the settings from the Maya 2013 build configuration.

    Image 5. Visual Studio Configuration Manager. I am creating a new config named Maya 2014.

    Now lets set the correct include directory for the newly created configuration. The error says it was looking for MBoundingBox.h, well where the heck is MBoundingBox.h? There is this very useful program called “Everything” which very quickly searches every file on your computer so I simply entered “MBoundingBox.h” into Everything and sure enough, it found it in the Maya 2014 directory. 

    Image 6. I used the handy program "Everything" to locate the location of the file on my computer. Observe that the file path is the exact same as the paths for the Maya 2013 and 2012 versions with the only difference being "2014"
    Now that we know where the file is located, lets simply add its directory to the VC property page. Let’s try rebuilding the project, and of course it fails.

    Image 7. Now the compiler is telling us it cannot find a library file.

    Can’t find a library file…well is there a lib folder in the Maya directory? Why yes there is. Let’s go ahead and add that.

    Now the solution builds successfully. Going back to the exporter directory, we see our newly built Maya 2014 plugin. 
    Image 8. Observe that a 2014 version of the exporter has been built.
    Now the question is, will it work?

    We install the plugin by putting the generted .mll file in the Maya plugin directory:

    And putting the associated scripts in the scripts folder:

    C:\Users\%USERNAME%\Maya2014\bin\plug-ins\My Documents\ maya\2014-64x\scripts

    We can now go back into Maya and successfully load the Collada plugin and export without error.

    Now that we finally have a model exported in a format Phyre likes, let’s import it and render it in engine…actually lets save that for another day.


    PhyreEngine 3.4 does not install the Collada plugin for Maya 2014, I am not sure if PhyreEngine 3.5 does or not, but if it doesn't I am confident that these same steps will apply.

    Steps to build PhyreEngine's exporter for Maya 2014:
    1. Build a new configuration in the configuration manager, copying settings from Maya 2013. (Image 5)
    2. Update the Visual Studio Project include property (C/C++ > Additional Include Directories) to the include folder in Maya 2014's path (%MAYA_INSTALL_DIR%\include)
    3. Update the Visual Studio Project Library directory (VC++ Directories > Library Directories) to include the lib folder in Maya 2014's path (%MAYA_INSTALL_DIR%\lib)
    4. Copy the generated .mll (located at %SCE_PHYRE\Tools\Exporters\ColladaMaya\*YOUR CONFIG NAME*) file
      to: %MAYA_INSTALL_DIR%/bin\plug-ins
    5. Copy the mel scripts associated with the exporter (located at %SCE_PHYRE%\Tools\Exporters\ColladaMaya\Scripts)
      to: C:\Users\%USERNAME%\Maya2014\bin\plug-ins\My Documents\ maya\2014-64x\scripts
    6. Enable the Plug-in in Maya's plugin manager.

    Note: %MAYA_INSTALL_DIR% is the path where you installed Maya, you may not have a environment variable with this name. Fore example, my install directory for Maya is: C:\Program Files\Autodesk\Maya2014

    IMO It's always fun to list the steps after you solve a problem like this, comparing how simple the solution is to all the things you tried. It's kinda funny, you can spend a few hours trying to figure out something that only takes a minute to to.  As usual, if you have any questions tweet me at @MikeGameDev and I'll try my best to help you out.

    Sunday, 10 November 2013

    Installing PhyreEngine and the PSVita and PS3 SDKs

    This year we have the amazing opportunity to use PhyreEngine and develop a game for the Playstation 3. This is the first of many posts relating to the development of our game. One of the first challenges we faced was installing the engine, in this post I will describe the process with detail.

    Installing PhyreEngine is rather straight forward, but it took quite a bit of figuring out get right. In this post I will outline all the steps required to get PhyreEngine 3.4 up and running and deploying samples to the PS Vita and PS3.

    Before we start, I want to throw in a bit of a disclaimer and mention that I realize that some of these steps may seem redundant but I wanted to ensure that each one of my team mates and I had the exact same setups. So if you do choose to use this guide just know that this is what worked for me and my teammates on our machines.

    This setup assumes Visual Studio 2010 is already installed, it will cover installation of Visual Studio 2010 Service Pack One, the Windows SDK (which was a bit of a pain), the DirectX SDK, the CGToolKit and finally, PhyreEngine itself. Once we have PhyreEngine up and running some samples, we will then install the PSVita and PS3 SDKs and get the samples running on those platforms.

    Step One: Setting up the requirements for PhyreEngine
    a)    If you do not already have it, download and install Visual Studio 2010 SP1:
    b)    Uninstall the following if you have it installed (don’t worry, we’ll reinstall them later):
                                  I.        Microsoft Visual C++ 2010 x64 Designtime
                                II.        Microsoft Visual C++ 2010 x64 Redistributable
                               III.        Microsoft Visual C++ 2010 x64 Runtime
                              IV.        Microsoft Visual C++ 2010 x86 Redistributable
                               V.        Microsoft Visual C++ 2010 x86 Runtime
    c)    Install the Windows SDK (the reason why we uninstalled the above)
                                  I.        Download the Windows SDK:
                                II.        Make sure you uncheck Visual C++ Compilers and Microsoft Visual C++ 2010 (important!)
                               III.        Download and install this Windows SDK patch:
    d)    Download and reinstall the Visual C++ 2010 Redistributable Packages (click repair if it says you already have it)
                                  I.        x86:
                                II.        x64:
    e)    Download and Install the DirectX SDK:
    f)     Download and install the CGToolKit

    Step Two: Installing PhyreEngine
    a)    Extract PhyreEngine zip to HDD root
    b)    Run PhyreInstaller.exe

    Its that simple! At this point PhyreEngine should be up and running for the Windows platform. You may be wondering why I told you to uninstall all those Microsoft Visual C++ files, only to have you reinstall them later. The reason for this is that I was having issues getting the Windows SDK to install successfully and found that uninstalling these files solved the problem. To set up PhyreEngine for the PS3 and PS Vita platforms you must do the following:

    Step Three: Installing PSVita SDK
    Step Four: Installing the PS3 SDK

    Both SDKs have similar installers and the instructions to install them are the exact same. When you first run the installers, you will be greeted with a screen asking you to choose a path. This screen is not your install path, but is just a path where the installer will extract files to. I believe you may safely delete the path after installation of the SDK (I haven’t noticed any problems).

    Once the files are extracted, you will be asked to select which features you want as well as your install directory. We just chose to install everything and used the default directories chosen by the installers should be fine. Now a little note about the install directory, technically you could install it anywhere, but I wouldn’t recommend that, unless you are big on tinkering with environment variables and Visual Studio project properties. The PhyreEngine documentation has a list of environment variables and “sample” values for the variables; however I found that there were some issues with parts of the engine if the environment variables weren’t set to the exact same values in the table. I would post the table here but I do not think I am allowed to, if you have PhyreEngine this table can be found in the getting started document. Now you should be able to build PhyreEngine projects for Windows, PSVita and PS3. Note that the Playstation platforms have a bunch of tools you may want to install  (ie. PSVita Debugger, PS3 Target Manager etc.), these tools aren't required but may make your life easier.

    Anyways, that’s all for now. Now you know how to install PhyreEngine! If you have any problems you can Tweet me at @MikeGameDev and I’ll try my best to help you out.