Part 5-Data Structures and PathFinder app: List, structs and AI
As a reader, I want to share with you my view of a blog as a type of practice writing. That is: nothing is absolute, and you should always question anything that I write, make sure to test the ideas by writing code, talking to others or simply commenting on my blog. Unlike many writers who feel that a blog should be well written and completely proven out, I don’t. It isn’t that I don’t care about the reader, but in a world that loves to drive everything over to perfection and high numbers, I just like to read, write, explore and experiment. I hope you like to read, write, explore and experiment. If you are reading this blog, it is likely that you do enjoy the exploration of code.
Now that we have explored List<T> generic extensively and used it in a simple but boring Windows Phone 7 application, in this blog we will take a look at the PathFinder Artificial Intelligence example and it’s use of the List<T>. In the Pathfinder, a number of lists are used to generate data that is treated like humans might treat experience. In this article you gain a better understanding of how the generic List<T> is utilized in artificial intelligence and generally how a List<T> is used in general. We will have to explore the use of a structure and why a structure was chosen over other approaches, this will done in a later blog.
If you have downloaded the PathFinder example from AppHub, if you haven’t then the URL is:
If you are like me, you may have missed the html file that is also downloaded that can help you with getting started with the PathFinder project, the document is not a big help, but worth a look: Pathfinding.htm
When you look at the solution explorer, it looks like a boatload of code. And frankly it is. If you are used to having a professor guide you through your learning, and carefully auditing your effort, then it looks like Kings Canyon National Park and you were ready for a walk in the neighborhood park. Well as the students who suffer through my classes at CSU Dominguez Hills find out, auditing your knowledge and making sure that you walk the path to enlightenment is not how the world works when you are outside of school.
So with that comment, let’s get started again with the PathFinder code, and by the way, the past blogs on Data Structures was the way that I taught myself enough about List<T> to be able to discuss it in my blog. If you want to use a similar process, get a blog and start writing about your explorations of an area of knowledge. Try to be unique, you could focus on developing knowledge about Playboy models over the years, and that might get traffic, but it isn’t unique. If you want to build games, it might be a better idea to work on a different body of knowledge related to game design.
In the image below, is a diagram generated using the Visual Studio 2010 Architecture Version, available to college students, professors and for use in labs for classes in Science, Technology, Engineering and Math/Design Labs for no cost to the school.
In this diagram we can see how the XNA game methods are formed, and we can see that the Initialize method has two methods that are utilized (the generics are shows as methods): List and Dictionary.
Let’s focus on Initialize method where the List<T> is utilized:
- In the class definition, a “field” or variable is declared, (remember class definition is the area after the class name (the following is an image, so code can’t be cut and pasted, it is in the program)
These two lines (which can be cut and pasted, but is included in the code), define the List<T> where T is the struct SearchNode and there is one declared as openList and closedList.
// Holds search nodes that are avaliable to search
private List<SearchNode> openList;
// Holds the nodes that have already been searched
private List<SearchNode> closedList;
// Holds all the paths we've creted so far
The struct is located in the class definition under the toggle, if you have your code toggled up like the image shown above, in the code below shows you the struct. What is a struct?
- A struct type is a value type that is typically used to encapsulate small groups of related variables, such as the coordinates of a rectangle or the characteristics of an item in an inventory.
Structs can also contain constructors, constants, fields, methods, properties, indexers, operators, events, and nested types, although if several such members are required, you should consider making your type a class instead.
Structs can implement an interface but they cannot inherit from another struct. For that reason, struct members cannot be declared as protected.
Structs share most of the same syntax as classes, although structs are more limited than classes:
Within a struct declaration, fields cannot be initialized unless they are declared as const or static.
A struct may not declare a default constructor (a constructor without parameters) or a destructor.
Structs are copied on assignment. When a struct is assigned to a new variable, all the data is copied, and any modification to the new copy does not change the data for the original copy. This is important to remember when working with collections of value types such as Dictionary<string, myStruct>.
Structs are value types and classes are reference types.
Unlike classes, structs can be instantiated without using a new operator.
Structs can declare constructors that have parameters.
A struct cannot inherit from another struct or class, and it cannot be the base of a class. All structs inherit directly from System.ValueType, which inherits from System.Object.
A struct can implement interfaces.
A struct can be used as a nullable type and can be assigned a null value.
In the PathFinding example, a struct is created for use to work with the SearchNode:
class PathFinder
{
#region Search Node Struct
/// <summary>
/// Reresents one node in the search space
/// </summary>
private struct SearchNode
{
/// <summary>
/// Location on the map
/// </summary>
public Point Position;
/// <summary>
/// Distance to goal estimate
/// </summary>
public int DistanceToGoal;
/// <summary>
/// Distance traveled from the start
/// </summary>
public int DistanceTraveled;
public SearchNode(Point mapPosition,
int distanceToGoal,
int distanceTraveled)
{
Position = mapPosition;
DistanceToGoal = distanceToGoal;
DistanceTraveled = distanceTraveled;
}
}
#endregion
Finally, in the Initialize method, the variables openList and closedList are constructed
public void Initialize(Map mazeMap)
{
searchStatus = SearchStatus.Stopped;
openList = new List<SearchNode>();
closedList = new List<SearchNode>();
paths = new Dictionary<Point, Point>();
map = mazeMap;
}
We see that in our Artificial Intelligence application, the variable openList and closedList are constructed using the previously declared variable in the class definition. Now, you can utilize the openList in other methods within this class module. The List utilitzes the SearchNode struct to expand its functionality. You might ask: Since the list has so many methods, why do you want to expand the capabilites of List<T>, would that make it harder to maintain or to turn over the code? The answer is yes, for sanity sake, make sure to attempt to use the List<T> or other default generics to keep your code sane, after all, do you really understand what the purpose of the SearchNode is right now? Do you want to reuse the code if you don’t? Keep in mind, employers like people who write code that can be maintained.
In this case the struct SearchNode makes sense, it makes it easier to work with the modifications to the game environment by determing the location of the blocks on the “map”.
Well, I could spend hours on explaining how this project works, like any software that does interesting things, it is difficult to “deconstruct” the process to build it. There are people who are good at that, and if you are that type of person, great, but the reality is that most people struggle reading other people’s code. With the current thought that comments are to be kept to a minimum makes it more difficult to figure out what is going on. Bottom line, you have to keep at it when you have a new piece of code. If you just got a new job and the boss gives you time to review the existing code, make good use of the time.
NNNN