Tuesday, October 9, 2007

Avoiding Ten Common Game AI Mistakes

1) Moonwalking into walls or objects

Often this is a symptom of the interface between the AI and the game world being too complex, and therefore hard to debug. Sometimes it can simply mean that you have no path finding in the game at all, but we will ignore that for now.

Look for differences in the way that the animation moves and the way it queries the collision system. For example, the AI may do a ray cast to see if there is an object in front of it, but the character control system may move a larger object such as a cylinder, which then collides with the world unexpectedly.

Other problems may be that the general movement code does not handle the collision when it is detected resulting in continuous attempts to move when the physics and collision system will not allow it. Sometimes the movement code fails, switches to an idle state, which then immediately attempts to move again, see item 4 below.

2) Turning "the long way around" to face a target

For some reason this bug often survives until late in a project; sometimes it even ships! It seems like a simple thing to calculate... should I turn left or right to face a target.

Typically people start out getting the X and Z distance to the target and figuring out that as an angle using atan2. Then they take the X and Z components of the facing vector to get that angle via the same route. Finally you just take the difference between those angles.

What usually happens is that if you're not careful when manipulating these angles there are mistakes made when converting between radians of degrees, or when figuring out whether to turn left or right, or when wrapping angles around at 360 degrees.

Let's look at a solution that avoids having to convert and do arithmetic with angles, which is where most of the bugs I see come from.

Firstly take a dot product of the vector to your target and the characters facing direction (just the X and Z components). This gives you the cosine of the angle between the two vectors. Take an acos of that to get the angle in radians. What's nice about that compared to the atan2 route is that it immediately gives you the angle you want, the angle between the facing direction and the target position. You don't have to do anything more to make sure it's the shortest way around.

Then we want to know whether to turn left or right. Again looking only at the X and Z vectors, we can simply figure out whether the target is to our left or right. First we need to get the 2d cross product of our facing direction. If the facing vector is (x,y,z), a vector at right angles to this in 2d is just (-z, x).

If you then take the dot product of this and the vector to the target, the sign of that is whether you should turn left or right! Simple.

3) All the enemies on screen doing the same idle animation in perfect synchronization

This is a very common when a bunch of enemies get spawned at the same time, with the same behaviour and their animations end up perfectly synchronised. Also it happens when the AI's are all hit by some weapon at the same time.

It looks lame, and there's a couple of ways to help this along with making a major impact on your engine. You can play animations at irregular speeds. Play the idle animations at variances of just a few percent, and they won't look wrong, and they will be out of sync with each other. Use sets of random animations as often as you can, especially looping ones. At a higher level you can also make sets of states behave differently. If you have a state machine which has random elements for choosing the next state, then use that to vary the AI's.

4) Enemy behaving unpredictably

However you set up your AI system it will always end up complicated. At it's worst AI code is a mass of "if X then do Y" type statements, and unless you manage it correctly you won't be able to understand what is going on.

Firstly you need to abstract the state actions and state decisions as much as you can. Seperate concepts such as "doing an action" from "perceiving the world" and "deciding to do something". As much as you can allow the AI to be set up in the game data, not in the game code.

Doing so also makes concurrency easier, since if you encapsulate all of your queries about the world, you can execute them in parallel with other game systems, then in a later stage of execution you get the deferred results of those queries and act on them.

But the ultimate solution to unpredictability is debugging tools. You want to be able to store the last few states the AI was in, what transitions got him into that state, and what states it is considering transitioning to. If you can show this stuff on screen, at will, while the game is running, then you're golden. Spend lots of time on this kind of stuff, because I guarantee there will be a time near the end project when someone will come and stand behind you and ask you why something on the screen is doing X instead of Y. If you have no idea, then you're not doing job as an AI programmer.

5) Enemy is vibrating, flipping rapidly between two animations

This happens often in state machines. If you get a state A which transitions to state B, and then on the next update, state B transitions back to A again. Assuming, as often people do, the AI states also trigger animations, then you have the horrible flickering between the two first frames of each.

Ulimately the AI designers can avoid state cycles by not making them, but there are bound to be some that slip through. At which point it, it would be nice to have some mechanism to avoid them. You could flag an error or warning when a state immediately returns to the previous state, or you could have a time within which you cannot return to the previous state.

One nice way to handle this is to make the data about how long you should stay in a state explicit. For example, if an enemy is rolling along the floor then it makes sense that you cannot interrupt that action once it starts, so we have the concept of an interrupt time, before which you cannot break to a different state. Tying states to animations achieves this too, but I don't recommend a one-to-one match of animations to state for reasons that I will cover later.

Having interrupt times that are at least 1/2 a second is a simple way to avoid state thrashing, but you still have to solve the problem at the design level.

6) Irratic running on the spot and sudden direction changes.

Have you ever seen AI's running to a point in the world, then when they get there they overshoot? Or maybe they just keep stopping and running again. Or maybe they spin on the spot.

The problem here is nearly always to do with managing movement and distances to points. There are many ways to get this wrong. For example, if you use a bone or root node on a model as the absolute position of the character, then his distance from a point may vary over time as he animates. Meaning that you keep moving too far from the target point, triggering a new movement state.

Another issue is how close do you have to be to the point to stop trying to move there? If it is 1cm then how accurate is your character movement system? can you move someone with an accuracy of 1cm? If not then you need to enlarge your arrival distance until it is large enough that you can guarantee accurate arrival.

If you couple movement to animation you need to spend a lot of time thinking about where the character is, and a good way is to use a root node that is carefully animated to be well behaved. Then I recommend that you store the displacement of animations, so that you know exactly how far they will move the root node when played.

For ultra slick AI's that walk or run to a point then do a smooth stop animation and end up exactly on the target, you just need to play your walk animation until you get to the point when the transition to stop animation would get you exactly to the target. The you need to play that animation at the right point. You also need to consider where the foot steps are. You can then determine whether to transition to a left or right footed stop.

Finally, it's nice if you can manipulate your animations so that you can vary the distance covered by your walk cycle, just enough so that the transition to stop can be executed at a perfect boundary.

If animation is just something you play in the background and doesn't affect your movement, then things are easier. It comes down to fixing the issues above as best you can, but you don't have to fix them, you will just get sliding and popping now and then. But you won't get the kind of animation driven movement problems that cause you to overshoot.

One final issue is turning. Make sure your characters have a turn speed, that varies with running speed. You can turn on the spot when you're stationary, for example. When running your turning circle is limited.

7) Enemy doing nothing at all

This is pretty much a design level issue, but it's common enough to mention. Sometimes AI's are just dead. They have no idea what to do next and this looks pretty stupid.

Usually this occurs when AI have no valid transition from an idle state. So have your designers think about things the AI should do if everything they typically think he should be able to do cannot be done.

One possiblity is that the path finder is failing. Perhaps the AI spawned in an unreachable area by mistake, or was pushed there, or fell there. If your AI's can get into a situation where they cannot move, then perhaps have them animate now and then so they look puzzled, or are looking around wondering what to do.

Look though transitions from idle and make sure that there is something interested there that can be transitioned to if everything else fails.

This also comes down to good AI system debugging tools. If you can immediately bring up a display showing which transitions the dead entity is considering, you will be able to figure out what to do.

8) Movement deadlocks (doors, bridges)

Choke points happen in AI. Narrow corridors, doors, bridges, tunnels. Sometimes we are even clever enough to come up with a system for handling them. AI's that want to enter the choke point take a queue number, and they go through one by one for example.

Whether you do something like that, or do nothing at all, there needs to be some way to avoid deadlock. One way to do that is by giving your AI's different priorities for movement, so that they can move AI's out of the way. Often a player is able to move AI's about, sometimes simply because he moves first.

If you have a physics based engine for character movement this is easy, just set the mass to be greater on characters that you want to have the highest priority. Otherwise you'll probably have some kind of collision resolution system, and you need to feed in the priority from the AI into that.

9) Using A* for everything

I run a web site which teaches A*, and yet when I come to write a pathfinding or other search program I don't always use A*, and when I do I never do A* on a fine mesh or grid. Why? Because it uses a lot of memory and processing power that is totally unneccesary.

Firstly if you're searching only small data sets, like an AI state graph, or a dozen or so path nodes in a room, you can use Dijkstra's algorithm, which is particularly effective when all the AI's in the room will path find to the same node, since the algorithm will fill out data for the whole network rather than just the start and end nodes. Sometimes even a breadthfirst search is enough.

In general you want the path finding data to be as high level as possible whilst still allowing movement to all possible gameplay areas.

One approach is hierarchical path finding, which really needs to work at engine level. If you divide your game world up into regions, buildings, floors and rooms, for example, an AI can path find at all those levels before finally pathfinding on a grid or mesh level inside the current room it is in.

10) Being too clever

Good AI is often based on quite simple systems. It almost always is built up using good tools and good design, rather than clever algorithms.

Things to watch out for are learning algorithms, unless they are directly related to gameplay, which tend to make it hard to get the behaviour you want. I don't want to sound like I'm stifling innovation, but don't use a back propagating neural network when a simple table would do the job.

At all times make the systems workings clear via debugging tools, and as best you can allow rapid iteration of AI changes, ideally allow real time changes while the game is running.

Thursday, September 27, 2007

11 Visual Studio tricks in Emacs

Recently I read the blog post "11 Visual Studio 2005 IDE Tips and Tricks to Make You a More Productive Developer" which has some neat tips indeed. I thought I would investigate which of the tips can be replicated in emacs, which are easier or more powerful in emacs and vice versa.

I've been using Visual Studio for over 10 years though I'm certainly not a power user, and recently I only use it for building and occasional code editing. I do more editing in emacs. I'm not writing this post to prove that one is better than the other, it is more for the learning experience for myself, and hopefully somebody will find something interesting here.

(1) Express Yourself with Regular Expressions

The example is to convert

, last_name
, ssn
, employee_id


+ "last_name"
+ "ssn"
+ "employee_id"

using a regex. Well, I'd probably record a keyboard macro to do that, but let's do the regex replace instead.

The syntax of the regex is a little different in emacs, but the basic sequence looks like this:

Alt-x replace-regexp
\(, \)\(.*$\)
, "\2"

Notice you need slashes for the brackets to make the groups.

Verdict: Visual Studio lets you use Regex's in script, and emacs lets you do it in elisp code... and they both have the functionality needed for the tip. Draw.

(2) Take (Keyboard) Shortcuts

This tip is to simply use keyboard shortcuts. Well in fact you won't get anywhere with emacs without using them. So this is kind of a mute point.

But I'll list some random keyboard short cuts for completeness...

Alt z runs zap-to-char, kills everything up until the character you enter.

Alt . runs find-tag. Finds the next occurence of current tag in the tags table, for finding function and variable declarations for example.

Ctrl U Alt . finds previous tag

Ctrl < goes to the start of a buffer

Ctrl > goes to the end

Ctrl H m describes the current mode, which is handy if you just downloaded a new editing mode and you want to see what the keys are and so on

Alt t runs transpose. You can flip two words around.

Verdict: Another draw.

(3) Make New Shortcuts

This is straight forward in emacs...

(global-set-key [M-f2] 'zap-to-char)

... sets Alt-F2 to do zap-to-char

You can override keys globally like that, or you can do local-set-key to change that key only for the current editing mode.

Verdict: emacs and Visual Studio both allow remapping anything they can do to a key, and they both allow you to redefine a key differently for different modes. Another draw!

(4) Use Code Snippets

I wasn't aware of this feature for Visual Studio so I checked it out briefly. So it lets you dump out text, such as automatically creating empty for loops or adding set and get fields given a field name.

Well in emacs there are abbreviations. So for example let's say I want for( to automatically expand to for(int i; ithen I can make an abreviation, by going into the mode I want this to be active, and typing

Alt-x abbrev-mode (turn the mode on)
Alt-X define-mode-abbrev (interactively add a new abbreviation for this mode)
for(int i; i
and now when I type for and space, it will expand automatically.

If you don't want it to expand then you type Ctrl-Q before you complete the abbreviation.

But snippets let you do more advanced stuff like take a field name and create the get, set fields. Well I would write elisp code for that kind of thing, or again use a keyboard macro.

Abbreviations are nice and easy to use, but they don't have the power of snippets.

Verdict: Visual Studio code snippets don't seem to map directly to emacs. In emacs you can use the more basic abbreviations, or roll your own solution for wrapping text in more dynamic ways.

(5) State Your Preferences

Not a lot to say here. emacs is fully configurable through the startup file .emacs, so you can do configure everything as you want it to be.

Verdict: Draw.

(6) "Attach to Process" to Start Debugging ASP.NET

Emacs doesn't support windows debugging, of course, but you can use gdb to debug processes. So the same functionality would be :

Alt-x gdb
attach [process ID]

Verdict: Draw.

7) Stop Conditionally (Conditional Breakpoints)

Again, this is a windows only thing... you can run gdb and type

break [LOCATION]


condition [COND]

to set up a conditional breakpoint.

Verdict: Draw. You can't debug windows processes from emacs, and you can't debug linux processes from Windows, but both offer debugging from within the IDE.

(8) Employ Task List Tokens

This is an odd feature. By typing // TODO in C++ code, for example, you can view the TODO's in a task list window for that file.

Emacs lets you do this with say the 'occur' function.

Alt-X occur

Will give a list of lines containing TODO.

You could make an elisp function to wrap this up into a task list function:

(defun task-list()
(occur "TODO"))

Verdict: Not much of a feature really, but yeah, another draw.

(9) Go Directly to Any File with the Find Combo Box

I couldn't get this tip to work, but Alt-Shift O seems to be the one he is talking about. A very nice list of files, and you can quickly open a file by typing part of the filename.

emacs doesn't include the files in your current project, so we don't have a direct comparison, but let's assume you have a root directory containing your source and you want to find files matching a regex:

Alt-x find-dired
-regex ".*SEARCHTEXT.*"

This will open a dired window (like a file manager dialog box but lets you do lots more things to the files) containing the matching files.

Verdict: emacs is a bit better than studio in that you can search using all the power of the unix find command, but it's more fiddly to use, and there's no equivalent to Studio managing all the files in each project. (That I know of).

(10) Type Ahead (Incremental Search) in Lists

So for example in Studio, do Ctrl-O and you get a file dialog. Typing letters gradually filters the available files until you get the one you want.

Emacs has exactly the same thing.

Ctrl-X Ctrl-F to visit a file for example (although this works with anything that asks you for a file.)

Firstly you can use the buffer history to find files you opened and closed earlier, and also you can edit this, so if you just opened a .cpp file, you can change it to .h and load that easily.

Secondly hitting tab will cycle through possible files based on what you typed so far, but also open a buffer with the current valid files, so you can switch and select from there.

Finally, if you open the wrong file by mistake you can run 'find-alternate-file' and load a different file into the buffer you opened.

Verdict: emacs wins by a nose. More flexibility.

(11) Automate with Macros and Visual Studio Automation

emacs also has very cool macro recording...

Ctrl-X ( starts recording

do your thing

Ctrl-X ) ends recording

Ctrl-X e runs the macro

If you make a useful macro that runs on one line, you can then run it multiple times:

Ctrl-U 10 Ctrl-X e

runs the macro 10 times for example.

You can also edit the macro with edit-last-kbd-macro, which brings up an editor.

Well that's it, I'm sure I've missed out a lot of emacs features, I've been using it for about 4 years and I know there is still a lot of stuff in there I haven't discovered!

Saturday, September 22, 2007

Word numbers programming puzzle

Reading Reddit last week I came across an interesting programming puzzle.


I've written a straightforward Common Lisp solution which is pasted below. What is interesting about this problem, and what would make it a good interview question, is that coding up the basic solution as I have here only poses more problems.

None of the Lisp environments I've tried have enough heap space to complete this problem, even though in terms of time complexity it is O(n). Judging by how long it takes to run on a few hundred thousand numbers, and then several million, it would take about 20 hours on my 2Ghz PC to solve for 1 billion numbers.

Even if I used the file system to hold the numbers, assuming each number fits in 50 chars of text, 4 bytes for the value and a further 4 to hold the length of the string, that is still in the order of 50Gb. You would then need to sort that file a bit at a time in memory, using a merge sort, and finally do a linear run through the file until you get the 51,000,000,000nth number.

Some clever folk have presented a more intelligent solution here...


Here is my solution so far:

Word Numbers

This is a partial solution to the problem found at http://www.itasoftware.com/careers/puzzles07.html
by Justin Heyes-Jones

I say partial because it does actually work, and if you had a lisp environment with enough memory, it would finish
in about a day. But the real solution seems to be either to spot patterns so you don't have to generate and sort
all 1 billion numbers, or to use the file system to cope with what your computer memory cannot.

"If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?"

To be precise: if the integers from 1 to 999,999,999 are expressed in words
(omitting spaces, 'and', and punctuation[1]), and sorted alphabetically so that the first six integers are

* eight
* eighteen
* eighteenmillion
* eighteenmillioneight
* eighteenmillioneighteen
* eighteenmillioneighteenthousand

and the last is

* twothousandtwohundredtwo

then reading top to bottom, left to right, the 28th letter completes the spelling of the integer "eighteenmillion".

The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?

[1] For example, 911,610,034 is written "ninehundredelevenmillionsixhundredtenthousandthirtyfour"; 500,000,000 is written "fivehundredmillion"; 1,709 is written "onethousandsevenhundrednine".


; (load (compile-file "wordnumbers.lisp"))
; (solve 999999999 51000000000) ; unlikely to finish unless you have a massive memory heap
; (solve 10 26) ; will work, but may not get you the job ;-)

;;;; Utilities

(defmacro with-string-words((str word) &body body)
"Utility macro to iterate over a string and return each word (anything between spaces)"
`(do* ((start 0 (if end (1+ end) nil))
(position #\Space ,str :start 0)
(if end (position #\Space ,str :start (1+ end)) nil))
(,word (subseq ,str start end) (if start (subseq ,str start end) nil)))
((null start))

;;;; Numbers are stores as the number in words, the length of this string and finally the numeric value

(defun get-words(lst)
(first lst))

(defun get-length(lst)
(second lst))

(defun get-value(lst)
(third lst))

(defun remove-and(str)
"remove occurences of 'and' from a string"
(let ((new-str (make-array 0 :element-type 'character :fill-pointer 0 :adjustable t)))
(with-string-words (str word)
(if (string/= "and" word)
(setf new-str (concatenate 'string new-str word))
(setf new-str (concatenate 'string new-str " ")))))

(defun char-space-or-hyphen-p(c)
(if (or (char= #\Space c) (char= #\- c))

(defun remove-spaces-and-hyphens(str)
"remove spaces and hyphens from a string"
(remove-if #'char-space-or-hyphen-p str))

(defun get-number-as-words(n)
"Use common lisps built in English text number output"
(format nil "~r" n))

(defun get-numbers-as-word-list(n)
"get the numbers from 1 to n and return as a list of strings and the lengths"
"of each string as a list of three items, words, length of word string and"
"actual numeric value"
(loop for n from 1 to n collect
(let* ((str (get-number-as-words n)) (len (length str)))
(list (convert-text str) len n))))

(defun compare-word-and-len(a b)
"given a string, length pair compare on alphabetical order"
(string< (get-words a) (get-words b)))

(defun sort-number-word-list-alphabetically(lst)
(sort lst #'compare-word-and-len))

(defun convert-text(str)
(remove-spaces-and-hyphens (remove-and str)))

(defun get-number-from-letter-index(lst target-index)
((number 0 (1+ number))
(index 0 (+ index (get-length (nth number lst)))))
((> number (1- (length lst))))
(if (<= target-index (+ index (get-length (nth number lst))))
(return-from get-number-from-letter-index number)))

(defun sum-to-n(lst n)
(if (>= n 0)
(+ (get-value (car lst))
(sum-to-n (cdr lst) (1- n)))

(defun solve(num n)
"Solve the problem for 'num' numbers, finding character position n"
(let ((lst
(get-numbers-as-word-list num))))
(format t "Made list~%")
(let ((number
(get-number-from-letter-index lst n)))
(format t "Found number~%")
(let ((value (get-value (nth number lst))))
(format t "Done.~%Number at character pos ~a is ~a. Sum to that number is ~a~%" n value (sum-to-n lst number))))))