Artificial Intelligence: Graphs, PathFinder and the Windows Phone 7

How is the BestFirst search for a path in PathFinder work?  How does the A* algorithm work?  Good questions, and how do we discuss this without making this whole blog even more boring than it is already.  Thanks for reading this by the way, and if you celebrate Thanksgiving, I am very thankful for the few readers that I have.  Really I should figure out a way to include Lindsay Lohan or Mel Gibson in this conversation about data structures and graphs, but as I understand both parties are currently dealing with substance abuse.  Which makes them way more interesting than Data Structures in game design.

Graphs, at least the types of graphs that are of interest to the designer, might be called Data Structure Graphs or topological graphs, do differentiate them from graphs that are used to present data.  In the world of Math, they are of the kinds of graph, but to keep things straight, let’s call what we are discussing DS Graphs, so that I can keep them straight in my mind.

So what are DS Graphs and how do they differ from regular graphs using X,Y and sometimes Z?  The difference is that there isn’t any difference, it is just that the X,Y, and sometimes Z one you like to use to represent cash flow over time is a simple one.  The cash flow uses points, referred to as waypoints in the DS Graphs that are plotted against time.  The time variation is dependent on when the data about the cash flow is entered.  Let’s say my manager expects me to enter my expenses every Friday, which is a good strategy, but one I sometimes ignore, unwisely.  This lack of data waypoints could lead to a discontinuity and the graph prior to the Friday that I didn’t do my expense reports would not be connected to the graph of the expense reports up to that time.  For me, a terse message from my manager gets a “waypoint” or datapoint put in on Monday and the graph is reconnected.

Anexample of a disconnected DS graph:

An example of a connected DS Graph

DS Graphs are made up of waypoints which are referred to as Nodes and sometimes Vectors, although in my blogs, they will be referred to as Nodes, and the line (sometimes writers will refer to them as footpaths) that connects them are called edges.

DS Graphs are used in the analysis of communications networks, electronic circuits (such as routing of connections with is 3 dimensional), and artificial neural networks.

In game AI graphs are used to help the game engine make decisions about the environment.  Think about Halo Forge (if you haven’t used it, then you should, it is fun to work with), with the Halo Forge, you can build “maps” in the game and share them with your friends.  This changes the environment of the game and the game engine must be able to adapt to the modifications.  In some games Mods can be extensive, changing the very basis of the game. 

For the next blog, we will continue to examine the concept of DS Graphs and how to use them in your game design.

NNNN