Programming Game AI by Example

Mat Buckland

Mentioned 10

Provides an introduction to AI game techniques used in game programming.

More on Amazon.com

Mentioned in questions and answers.

Programming Collective Intelligence is an awesome way to get your feet wet in Machine learning. I am looking for similar books which has small but interesting programming projects. Do you have any recommendations?

Edit: It need not be related to machine learning. It could be any programming project-based books. Thanks.

Edit2: Collective Intelligence in Action is one more book that looks at some interesting CS stuffs. Do you guys have any similar recommendations?

Programming Game AI by Example by Mat Buckland has a lot of little cool AI related projects in it.

alt text

Programming Game AI by Example provides a comprehensive and practical introduction to the bread and butter AI techniques used by the game development industry, leading the reader through the process of designing, programming, and implementing intelligent agents for action games using the C++ programming language. Techniques covered include state- and goal-based behavior, inter-agent communication, individual and group steering behaviors, team AI, graph theory, search, path planning and optimization, triggers, scripting, scripted finite state machines, perceptual modeling, goal evaluation, goal arbitration, and fuzzy logic.

Might be up your alley. Take a look at the Table of Contents.

I would check out Programming Pearls by John Bentley. It has lots of smaller problems to get your programming brain going.

While Project Euler is not a book per se, it does contain a large number of "small but interesting programming projects". It's a great way to expand your math skills as well as try out new languages. (Code Kata seems similar but more CS-oriented; I've not yet dived into it.)

I also have fond memories of Parallel and Distributed Simulation Systems; the book itself may be a bit dry, but it's very example-driven, and applies to everything from cellphone tower switching to airport scheduling to weather simulation to video games. It's uncannily fun to write rollback-capable code, too.

Best of Ruby Quiz is a book of a bunch of small interesting projects such as create a self learning Tic Tac Toe AI. The projects can definitely be done in any language, so don't let the fact that it says Ruby in the title deter you from it.

Making Things Talk: Practical Methods for Connecting Physical Objects by Tom Igoe

It is a great way to expand your programming knowledge in how to communicate with hardware. The book has lots of fun and interesting projects with good code examples. It's a great starting point for future projects that you may want to do on your own.

There are several relevant answers at this SO question:

  • Peter Norvig, Paradigms of AI Programming
  • Mark Jason Dominus, Higher-Order Perl
  • Abelson and diSessa, Turtle Geometry
  • Kernighan and Plauger, Software Tools in Pascal
  • Paul Graham, On Lisp
  • Peter Seibel, Practical Common Lisp

Links and descriptions over there. Also, Etudes for Programmers was the original CS project book, still worth sampling even at over 30 years old. (It isn't listed at the other question because it presents no source code of its own for the projects, except one.)

I want to get into some simple AI Programming on any subject really. My programming language of choice is C#.Net.

Where is the best place to get started? (Preferably free)

I really liked Programming Game AI by Example which C++ however you can easily translate that to C# the author has a web site too. ai-junkie

I've searched over the posts I could find on "What's the best AI book" and I found all the responses I expected to see, but I did not find what I was looking for.

I'm interested in a book that I can use in a teaching environment that explains AI topics such as Neural Networks, Genetic Algorithms, Decision Tree learning, Inductive learning, etc. using code samples that are in C++ or very similar to it.

The students have a C++ backround, and we are focusing on gaming and simulation development. The AI books from Matt Buckland are good, but I would like to know if there are any other books that may be similar.

This may be an impossible task, but I'm trying to stay away from Lisp or Prolog and I'm looking for examples that would be directly applicable to game development.

If anyone has actually read a book like this, please let me know!

I use Buckland's Programming Game AI By Example and it has proven very effective.

http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

I also supplement with the popular AI a Modern Approach:

http://www.amazon.com/Artificial-Intelligence-Approach-Stuart-Russell/dp/0131038052

I am trying to wrap my mind around the best way to implement nested state transitions in a single threaded programming language (Actionscript). Say I have a structure like this behavior tree: behavior tree

Now imagine that each leaf node is a destination point on a website, like an image in a gallery, or a comment nested in a post view nested in a page view... And the goal is to be able to run animated transitions from leaf node to leaf node, by animating out the previous tree (from bottom to top), and animating in the current tree (from top to bottom).

So, if we were at the bottom-left-most leaf node, and we wanted to go to the bottom-right-most leaf node, we would have to:

  • transition out bottom-left-node
  • on complete (say after a second of animation), transition out it's parent,
  • on complete, transition out it's parent
  • on complete, transition IN the right-most parent
  • on complete, transition in right most-child
  • on complete, transition in leaf

My question is:

If you imagine each of these nodes as HTML views (where the leaves are 'partials', borrowing the term from rails), or MXML views, where you're nesting sub components, and you don't necessarily know the nest levels from the application root, what is the best way to animate the transition as described above?

One way is to store all possible paths globally, and then to say "Application, transition out this path, transition in this path". That works if the application is very simple. That's how Gaia does it, an Actionscript framework. But if you want it to be able to transition in/out arbitrarily nested paths, you can't store that globally because:

  1. Actionscript couldn't handle all that processing
  2. Doesn't seem like good encapsulation

So this question can be reworded as, how do you animate out the left-most-leaf node and it's parents, starting from the leaf, and animate in the right-most-leaf node, starting with the root? Where is that information stored (what to transition in and out)?

Another possible solution would be to just say "Application, transition out previous child node, and when that's complete, transition in the current child node", where the "child node" is the direct child of the application root. Then the left-most child of the application root (which has two child nodes, which each have two child nodes), would check if it's in the right state (if it's children are 'transitioned out'). If not, it would call "transitionOut()" on them... That way everything would be completely encapsulated. But it seems like that'd be pretty processor intensive.

What do you think? Do you have any other alternatives? Or can you point me to any good resources on AI Behavior Trees or Hierarchical State Machines that describe how they practically implement asynchronous state transitions:

  • From where do they call "transitionOut" on an object? From the root or a specific child?
  • Where is the state stored? Globally, locally? What is the scope defining what calls "transitionIn()" and "transitionOut()"?

I have seen/read many articles/books on AI and State Machines, but I have yet to find something describing how they actually implement asychronous/animated transitions in a complex MVC Object Oriented Project with 100s of Views/Graphics participating in the behavior tree.

Should I call the transitions from the parent-most object, or from the child?

Here are some of the things I've examined:

While this is not necessarily an AI problem, there are no other resources describing how to apply nested state architectures to websites; these are the closest things.

Another way to word the question: How do you broadcast state changes to the application? Where do you keep the event listeners? How do you find what view to animate when it's arbitrarily nested?

Note: I am not trying to build a game, just trying to build animated websites.

I'll try to simplify the problem before suggesting a possible approach. The transitions seem related to the views, and not the model. If I were to skip the transitions and go straight to some other leaf node, the application still works but there is not visual clue for the users. So I'd suggest you use a view-controller specifically to hold the current branch and the transitions of various views.

It's probably a better approach to split the two types of transitions into a sort of stack where a pop transition is to go back to a previous node, while a push transition goes forward in the hierarchy. Apple uses a similar technique to manage navigational applications using a navigation view controller. It basically maintains a stack of view controllers that the user followed to get to a particular node. When a user goes back, the top item is popped off the stack, and the user sees the previous item. If the user goes deeper in the hierarchy, a new view controller is pushed onto the stack.

You would still need a global way to represent the hierarchies in a flyweight manner, while the navigation stack only stores the currently visible branch down to the leaf node.

If a user went from one leaf node to another, the current stack will be popped out upto the common parent. Then the global tree structure will be asked to get the path from that parent upto the new leaf node. This path of nodes is pushed into the current navigation stack, and as each item is pushed, the transition is shown.

In a simple algorithm, there'd be these two data structures and a way to get the entire branch that contains leaf node:

  1. a global representation of the tree
  2. a stack of the current branch

initially:

stack = []
tree = create-tree()

algorithm:

// empty current branch upto the common ancestor, root node if nothing else
until stack.peek() is in leaf-node.ancestors() {
    stack.pop() // animates the transition-out
}
parent = stack.peek();
// get a path from the parent to leaf-node
path = tree.get-path(parent, leaf-node)
for each node in path {
    stack.push(node) // animates the transition-in
}

Update:

The entire application could have a single navigation controller, or multiple such controllers. A navigation controller only needs to know that there is a tree which exposes certain operations. So you could create an interface with those operations and let concrete subclasses implement that.

I can only think of two operations that would need to be exposed (pseudo-Java syntax):

interface Tree {
    List<Node> getAncestors(node);
    List<Node> findPath(ancestorNode, descendantNode);
}

That should provide sufficient abstraction to keep the navigation controller poking inside the global tree structure. To take it to the next level, use dependency injection so the tree object is injected into the navigation controller, improving testability and breaking the tree connection completely.

I'm trying to figure out if there is any existing AI tools/frameworks/Library for Objective C or Cocos [well OpenGL + Obj C] in general that's good for a person who's never done any form of AI before [other than the simple checkers or tic-tac-toe AI's]. The scenario here is I've finished the basics control of a game for the iPad and works fine for multi-player. The AI just needs to move around, similar to the classic game snakes and somehow 'trap' a human player. I now want to write an AI for this.

I found a thing called http://opensteer.sourceforge.net/ which appears to be pretty good, however it was last updated in 2004. Which was 7 years ago, and not sure if I should use it if there are other ones.

If anyone have any other suggestions of things I should look at, please guide me to the right area.

Ai is usually very game specific and very hard to wrap in a reusable "Plug and play" sort of system. The AI libraries that do exist contain common things such as some mathematics, prediction, flocking, and path finding. I don't know of any libraries in Objective-C that cover this, but your game sounds like it would not really benefit from these because your AI requirements are fairly simple.

The best way may be to write your own AI from scratch. Start by breaking down the thought process for your AI into some kind of state machine (Make trees on paper, list steps, etc) and write it step by step.

Ai is not a fast moving field like graphics. Something from 2004 in terms of AI should still be very relevant. I would take a look at that library you talked about as well.

Here is an example in Objective-C on A* pathfinding:

http://humblebeesoft.com/blog/?p=18

Make a post on the Gamedev AI:

http://www.gamedev.net/forum/9-artificial-intelligence/

I strongly recommend reading this AI book:

http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

This book will teach you how to think through the AI process and will teach you how to write several systems that could become a part of an Ai framework.

I want to learn the basic concepts like collision detection, rendering and others in a general way (keeping the library usage minimum). I believe that once my basic concepts are clear, it would help me in learning different libraries easily, like OpenGL, etc.

I know without libraries it will take long time to build things. I am doing this for learning so I don't care about productivity.

I would love if the solution is using JavaScript (HTML5 Canvas) or C/C++ (DOS mode) since I believe I will have to deal with a bit of low level stuff which would help me in learning. Other solutions are also welcome. I know Java as well.

Note: 2D games are sufficient for me.

Good question - A decent place to start is

http://www.gameinstitute.com/

They have some pretty fun courses, no time limit and a decent forum. I actually met some good local dev's there and since have done some stuff together.

I'd also look at getting into the yearly Global Game Jam (http://globalgamejam.org/). It's a really great experience for novice and professional devs. You can also meet local people.

I mention "local people" cause sometimes its very difficult to do a game on your own - it really helps to have people to collaborate with. Though it brings in problems of its own (schedule conflicts, motivation, etc).

I'd take a look at the following books:

  1. http://www.amazon.com/Ultimate-Guide-Video-Writing-Design/dp/158065066X/ref=sr_1_2?ie=UTF8&qid=1306204693&sr=8-2

  2. http://www.amazon.com/Game-Design-Workshop-Second-Playcentric/dp/0240809742/ref=sr_1_8?ie=UTF8&qid=1306204693&sr=8-8

  3. http://www.amazon.com/Masters-Doom-Created-Transformed-Culture/dp/0812972155/ref=sr_1_2?ie=UTF8&s=books&qid=1306204765&sr=8-2

  4. http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782/ref=sr_1_1?ie=UTF8&qid=1306204779&sr=8-1

  5. http://www.amazon.com/Game-Engine-Architecture-Jason-Gregory/dp/1568814135/ref=sr_1_1?ie=UTF8&qid=1306204798&sr=8-1

This are just a few books on the top of my head that I've enjoyed in my travels.

I'd focus on a language like python that'll get you up and running quickly. Not C++ - I think you lose a lot of productivity on the language it self, templates, smart pointers, vtables, etc. And then you have all the different version of DX, Win32 GDI etc. I think you'll be more productive in a different language. Maybe lua + python?

Also, I'd seriously look into mastering an engine. I wrote my own, and it was a great journey, but we never completed the GAME! We spent 6 months writing the engine, 2 months writing the game and got burnt out. Next time I'd use an engine for sure!

  1. Unity3D works on iphone, web, desktop.

  2. Torque is another leader, though I didn't find this one as slick as Unity.

  3. Cocos2d is a iphone specific framework, based on a python framework. Really slick.

Another option is taking an existing game that allows Mods (HL2, Quake, etc) and build some mods for it. You can probably find tons of forums and groups already doing it and perhaps contribute to an existing project or start your own.

Another really gnalry idea would to be to get the Blue Book

  1. http://www.amazon.com/gp/product/0321498828/ref=pd_lpo_k2_dp_sr_2?pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=032117383X&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=01F2GM7XZD56GCFW0AJT

And don't stop till you understand and have worked through it!!! You'd be a pretty good openGL / C coder by the time you made it through that book (cover to cover). Set aside a few months...heh.

Don't forget - you can always start with paper-prototyping games, you don't have to start building computer games.

Good luck!

I am amateur Programmer looking to develop a game. I've decided to use Python and pygame. (I know, there are better options out there, but I really don't know C++ or java that well.) The issue I'm having is that I really have no idea how to create a decent AI. I'm talking about the sort of AI that has monsters move this way at this point, use a bow and arrow at that point, and use a long-range magic attack at another point (yes, its a top-down 2-d fantasy game). I really don't understand how it makes those decisions and how you program it to make those decisions. I've looked around everywhere, and either the resource gets so technical that I can't understand it at all, or it gives me no information whatsoever. I'm hoping someone here can give me some clear suggestions, or at least point me to some decent resources. Right now my bots just sort of wander randomly around the screen...

This is a great book about the topic. It has many examples included which are also explained in the book. The code is C++ but it's pretty straightforward to understand.

Here's a short description about the book taken from Amazon:

"Programming Game AI by Example" provides a comprehensive and practical introduction to the bread and butter AI techniques used by the game development industry, leading the reader through the process of designing, programming, and implementing intelligent agents for action games using the C++ programming language. Techniques covered include state- and goal-based behavior, inter-agent communication, individual and group steering behaviors, team AI, graph theory, search, path planning and optimization, triggers, scripting, scripted finite state machines, perceptual modeling, goal evaluation, goal arbitration, and fuzzy logic.

I've been into several tutorials and links for how to integrate scripting into games--but most of these don't start early enough in the process for me. I am trying to wrap my head around the basic structure of an effectively scripted game. Here are the basics:

I'm working on starting a basic 2d RTS game in C++. The mechanics of the game and the graphics are pretty standard/simple, rather the logic and data will be extremely complicated compared to a standard RTS. Obviously, I have a lot of planning to do--and really, the point of this is more to learn C++, scripting, game programming basics rather than actually complete my project.

I'm trying to figure out which elements of my project should be handled by scripting and which should be included in my core "game engine".

For instance, the all powerful "game loop" -- do I program this in C++ as part of the engine, or will my "engine" be solely what I use for displaying graphics (tiles, characters, etc...), processing the large amounts of data, and similar tasks--and these classes get "plugged into" the game loop, which is scripted?

I would like to use C# as a scripting language, from what I've read it offers good speed while still allowing to develop in VS, which I like. But really, I'm more concerned with how it's all supposed to get set up, more from a pseudo-code level than the actual coding. There's plenty of resources I can use when I get to this point, I'm just looking for advice on how to structure the whole thing.

Any tutorials, resources, advice would be greatly appreciated! Thanks!

The book Programming Game AI By Example is superb, and touches on just what you are looking for regarding game loops, using scripting (like LUA), and tons of examples of stuff that seem especially pertinent to you.

By the way, potentially relevant is the Unity3D game engine that lets you use C# for scripting. And there is also Garage Games engines, including the game builder kits that could help you create an RTS type game, and I believe you may be able to code in C# for Torque as well.

What would be your take on a xml file that contains certain elements, that reference n other elements. Background for this questions is a techtree (graph) serialized as a xml document. E.g. the tech "Cannons" prerequisite two other nodes (elements) "Iron" and "Gunpowder".

enter image description here Source: http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

By its very nature, XML introduces a tree structure into a document. If the relation between an element and its child nodes is considered to be an "allows you to create" definition, then you'll have a problem when you run into a situation where certain objects are referenced more than once. You'll end up having to specify them twice with no obvious way of telling they represent the same thing.

Let's take a look at the Iron from your example:

<iron>
    <cannons/>
    <guns/>
</iron>

No problem there, however, Wood will have...

<wood>
    <forge/>
    <arrows/>
    <guns/>
</wood>

The guns element appears here as well. The above representation is very simple, but maybe a lot more data will be associated with each element and you'll want to avoid repetition. You'll also get into trouble when your graph contains cycles, although I suppose that wouldn't be valid anyway given the semantics. Also note that wood is a direct requirement for guns, but guns also depend indirectly on wood via iron <- forge <- wood. This will become complicate to represent.

A number of things could be done. First of all, each element and the contained structure could be placed separately in the XML document, then referred in some way...

<guns itemId="1">
    <!-- embedded structure -->
</guns>
...
<iron>
    <item>1</item>
</iron>
<wood>
    <item>1</item>
</wood>

However, this leaves it up to you to programmatically resolve such references. The advantages of XML, being tools like parsers, XSLT and object binding, are partially lost.

Other options would be to link to elements via XLink, which seems like a natural fit here. Or use XInclude to define things only once, then include them in various places. Your "inlined" XML, with the inclusions resolved, will still have all the duplicate data. But at least it now no longer can become inconsistent.

But that's just one way of looking at it. Rather than trying to get the same directionality in the XML tree as in your graph, how about reversing things? Instead of an "allows you to create" relationship, you could make a "requires" relationship.

Going back to Iron:

<iron>
    <forge/>
</iron>

You'll now know that Iron requires a Forge. Guns:

<guns>
    <gunpowder/>
    <iron/>
    <wood/>
</guns>

But the problem remains the same: you can't just keep embedding one structure into the other, because at some point the same thing will be needed in more than one place. A Forge requires Wood, but so do Guns.

XML works for tree structures, but the moment your graph doesn't strictly adhere to such a structure, it becomes difficult to represent using XML. At least, difficult in the sense that you won't get any big advantages from it and will still need to program a lot yourself.

I don't know of any (de)serializable data representation that is a perfect fit for graphs of any kind. There's a software package called Graphviz which is intended specifically for graph rendering; it's open-source, so perhaps the documentation and/or code can deliver some good ideas.