Earning Your Pathfinding Merit Badge: How Game Characters Navigate Their Game World. A µ post.

As most gamers probably have, I've pondered what mechanism must games use to allow the NPCs in the game to find their way around the game world. Why did games like F.E.A.R. and Halo seem to exhibit more realistic NPC movements?

I was exposed more deeply to the problem when I embarked on building a simple FPS game from scratch including AI, rendering, and netcode. I'd originally planned on a game that mirrored my neighborhood so my friends and I could run around familiar territory and maim each other. It ended up being a shoot-the-aliens sci-fi game: I'm no artist, and it was easier for me to make characters that didn't look like pale imitations of humans.

I'd pulled out all my references in preparation for writing a blog entry outlining the basics of the techniques used for pathfinding in games, when I happened upon a most excellent overview written by a game developer.

They do a much better job than I think I could have, you can view the overview at Fixing Pathfinding Once and For All at the Game/AI blog. Nice graphical explanations, with videos demonstrating the differences in pathfinding strategies.

Other useful background information can be found at A* Pathfinding for Beginners and a short entry at Wikipedia.

My own personal references are the superb four volumes of AI Game Programming Wisdom, and the equally excellent Game Programming Gems, now up to eight volumes with the most recent 2010 release. I was heavily influenced by reading the more academic treatments found in both Artificial Intelligence for Games by Ian Millington by and Behavioral Mathematics for Game AI by Dave Mark.

If you have any interest in how realistic character movement is accomplished in games, I highly recommend taking a look at the links, and if you decide to program your own, I can't think of better reference works than the book series I've used.

I Know What You Did Last Summer: Omniscient Debugging.

I've been doing some coding using the recently released Visual Studio 2010 from Microsoft to experiment with some of the new features and capabilities added since the release of version 2008, my day to day coding platform.

One of the more interesting and very useful features added (only in the Ultimate edition, unfortunately) is IntelliTrace historical debugging. The ability to debug an application while in effect manipulating time (going backwards in the execution history, for example) is known as Omniscient Debugging. The term is properly used when referring to the eponymous open source debugger by Bill Lewis, a computer scientist at Lambda Computer Science and Tufts University, but has become part of the vernacular and a synecdoche for such debuggers.

For readers that are not programmers, the "debugging" of programs is part of the life of any developer. Any sufficiently complex application is likely to have a few "bugs", cases where the expected behavior of the application is not observed to happen. This can be caused by any number of things, from incorrect specification of the design, mistakes in translating the design into program code, use cases that were not considered, bugs in the very tools used to produce the application, etc.

By way of example, let us consider the following tiny application (written in a form of psuedocode):

(define add_two_numbers using Number1, Number2 as (return Number1 * Number2))

The developer hands this off to the users, who start using the new routine add_two_numbers:

add_two_numbers 0,0  →  0

add_two_numbers 2,2  →  4

add_two_numbers 4,4  →  16

Oops! The first two test cases return the proper expected results, but the third returns 16 instead of the expected 8. In our admittedly trival example, we can see from visual inspection the programmer mistakenly put the multiplication operator "*" where the addition operator "+" should have been.

In real applications, mistakes may be buried in hundreds of thousands of lines of program code, and visual inspection is seldom practical. This is where the traditional debugger comes into play for the developer.

A debugger allows the programmer to observe the execution of the application under consideration, by showing exactly where in the execution stream the application is, and allowing the viewing and changing of variables and storage for the application, setting "breakpoints" where the programmer wishes to temporarily halt the execution,  stepping through the execution one step at a time, stopping when certain conditions are met, and in some cases even allowing the changing of the program's state.

Workspace for a typical debugger, in this case  the WinPDB debugger debugging itself.

These capabilities greatly assist the developer in the determination and correction of problem cases. In our example, one could imagine the developer has determined the problem lies in the add_two_numbers routine (imagine of course that the routine is sufficiently large that simple inspection is not an option). By utilizing the debugger, the developer could execute the application, requesting that execution be paused when the add_two_numbers routine is entered.

At that point, the developer could step through the execution of the routine, observing the flow through the source code step-by-step. The source of the problem would of course become apparent, and could be quickly remedied.

In the case of severe bugs, an application may "crash". In some cases, a "crash dump" will be produced by the execution environment. This contains information about the state of the application at the time of the crash. This information can be used by the developer with the debugger to analyze the state of the application when it crashed, and observer the contents of variables, the place in the source code the execution was at the moment of the crash, and basic information about the path by which the application came to that place.

A core problem with this model of debugging, however, is that detailed information about the execution path and program states leading up to the bug or crash is generally not available, even in a detailed crash dump file. This forces the developer to deduce where the problem might be and then test that hypothesis with the debugger by setting conditions and breakpoints while analyzing the application flow. This will usually lead to a more refined hypothesis, leading to further debugging, leading to a more refined hypothesis, nearly ad infinitum (or at least it can feel that way) until the problem is found. In cases where the bug is sporadic, the programmer may have difficulty even reproducing the problem.

This can be a very time consuming and taxing practice for the programmer involved!

Ideally, the programmer would be able to observe the state of execution for the application at any point in time of the execution lifetime.

That is precisely the capability that omniscient debugging brings to the tool set of the programmer. The concept of such historical debugging has been around for decades, but implementations proved impractical for most of this time. The first truly practical and usable example is surely the Omniscient Debugger (ODB) of Bill Lewis. A very detailed paper by Bill can be seen in Debugging Backwards in Time, and a most interesting video lecture of the same name is hosted by Google.  You can view these to garner details on how this functionality is achieved, with examples of the kinds of bugs that are vastly simpler to find by taking advantage of this kind of technology.

With Visual Studio 2010, Microsoft has incorporated and extended this capability and technology, calling it IntelliTrace. Supporting the historical debugging of managed C# and Visual Basic, with experimental support for F#, the product promises to make the work of developers on the Microsoft platform vastly more productive. Details of the new capabilities can be found in the MSDN articles Debugging With IntelliTrace and Debugging Applications with IntelliTrace.

Open source developers can avail themselves of historical debugging with the aforementioned ODB, TOD and GDB debuggers.

I know what you're thinking. More importantly, I know what you were thinking...

Life Goes On: Further Ruminations on Conway's Game of Life.

Conway's Game of Life, as I noted in an earlier blog entry An Alien Message? is an utterly fascinating example of Cellular Automata, capable of mind boggling complexity from an incredibly simple set of base rules.

As a further example of how the game can "compute" in the same way that a traditional computer and programming language can be used to execute programs that compute, I loaded up the recently created seed pattern by Jason Summers for a new type of "Primer" pattern. These patterns in the game will in some fashion "output" the sequence of prime numbers. This particular pattern emits the type of prime number most familiar to us: 2, 3, 5, 7, 11,13... ad infinitum.

Start the video, and observe the area where the "gate" is in the lower left middle. Passing through it will be Life "Spaceships" spaced precisely as the sequence of primes.

As discussed in my earlier entry, patterns for the game exist that create a Universal Turing Machine, meaning the game can "compute" in the same way that any program can. If it can be done in any programming language, so it can be done in the Game of Life using such a pattern. Mind blowing!

Stephen Wolfram, polymath extraordinaire and creator of the widely used mathematical, programming, and graphing workbench Mathematica has written extensively on the subject of cellular automata in his book A New Kind of Science.

In all fairness, while well received overall the book was the target of some rather excoriating reviews by experts in the various related fields, and accusations of intellectual thievery have been raised. Perhaps the most scathing of these and an interesting read on its own can be found in Quantum Information & Computation with the review by Scott Aaronson, a theoretical computer scientist and member of the MIT Electrical Engineering and Computer Science department.

The book is good read nonetheless for a view into the wide applicability of cellular automata, and the five pound nearly 1300 page tome will make a fine doorstop if you find it not to your fancy.

Wolfram extensively discusses the relationship of these objects to nature, modeling complex behaviors and results with simple basic starting seeds. A good example is that of certain seashells, where the complex patterns of their shell is generated by natural cellular automata.

Wolfram's central point in the book is that complex behaviors and results do not require a complex system for their production.

This culminates in the core of his "new science", the "Principle of computational equivalence".

As eloquently described in the Wikipedia entry for the book, "The principle states that systems found in the natural world can perform computations up to a maximal ("universal") level of computational power. Most systems can attain this level. Systems, in principle, compute the same things as a computer. Computation is therefore simply a question of translating inputs and outputs from one system to another. Consequently, most systems are computationally equivalent. Proposed examples of such systems are the workings of the human brain and the evolution of weather systems."

To get your own hands-on feel for how simple systems can generate incredibly complex results, get yourself a copy of the most excellent Golly cellular automata application where you can explore Conway's Game of Life and other types of cellular systems.

You may find yourself as addicted and fascinated as I am!

A Bathroom Reader for Computer Science. A µ post.

Poking around for some pictures for my blog entry that talked about the programming language APL and showcasing an implementation of Conway's Game of Life in one line of the language, I came across an implementation of the Universal Turing Machine in The Game of Life.

As I outlined in that entry, the implications for this are deep. The game, a prime example of cellular automata, consists of a tiny rule set of just four rules yet it can 'compute' anything that can be done by any program you could write for a traditional computing environment using more familiar programming languages. I am honestly awestruck every time I think about this.

The author of this particular pattern for the game has a piece in the book Collision-Based Computing edited by Andrew Adamatzky. The description of the book, published by the top notch academic publisher Springer:

Collision-Based Computing presents a unique overview of computation with mobile self-localized patterns in non-linear media, including computation in optical media, mathematical models of massively parallel computers, and molecular systems.

It covers such diverse subjects as conservative computation in billiard ball models and its cellular-automaton analogues, implementation of computing devices in lattice gases, Conway's Game of Life and discrete excitable media, theory of particle machines, computation with solitons, logic of ballistic computing, phenomenology of computation, and self-replicating universal computers.

Collision-Based Computing will be of interest to researchers working on relevant topics in Computing Science, Mathematical Physics and Engineering. It will also be useful background reading for postgraduate courses such as Optical Computing, Nature-Inspired Computing, Artificial Intelligence, Smart Engineering Systems, Complex and Adaptive Systems, Parallel Computation, Applied Mathematics and Computational Physics.

Yummy! As with most Springer books, prepare to have your wallet 'Springered', in this case to the tune of $130.00. Ouch! I've spent enough already on their superb publications in computer science, physics, and mathematics to purchase a nice car, so I suppose I'll spring (ugh! I couldn't help myself!) for this one too.

I you're interested in computation by non-standard methods, some bordering on incredulousness, this sounds like a fun read.

I figure one chapter per visit.

She Blinded Me WIth Science: Tuning Up Your BS Detectors.

PCs, operating systems, specialized hardware, 'tweaks'. Just some of the pieces in the FPS gamer's world. Like any field with such esoterica, there's plenty of snake oil to go around.

Vendors of software tempt the player with promises of improved game performance, while hardware is presented as being able to improve your pings. Mice are made with DPI ratings that need to use scientific notation. The list goes on and on.

What is the intelligent FPS gamer to make of these, and how can they be sure that their money is well spent on things that really can make a difference in their gaming acumen?

We'll tear into a couple of examples in this blog entry, and show how a healthy dose of skepticism toward many of the claims bantered about the Internet by producers of these products and posters in forums could save the gamer time and money.

I've chosen two areas that have in particular pegged my BS detector.

• Game Booster, and other software that alleges to 'speed up' your PC for gaming.
• Specialized 'gaming' Network Cards, that make claims of reduced pings and latency.

When deciding whether something might be a worthwhile addition to their gaming arsenal, the educated gamer should ask themselves the following:

• Is there a valid reason this should improve my gaming experience?
• Is there a repeatable, scientific test and measurement to validate the claims, or are they largely anecdotal and subjective?
• Even if there is a measurable difference, does it make a difference for gaming?

Game Booster is a piece of software that claims to improve your gaming experience by "... defragmenting game directories, temporarily shutting down background processes, cleaning RAM, and intensifying processor performance...".

What? How exactly does this piece of free software know how to manage these things better than Microsoft's own OS? Each of the techniques used have been shown to have little if any merit.

It has been shown repeatedly that file fragmentation has little bearing on the performance of Windows and applications for any modern version of Windows. In the days of the FAT file system, defragmentation could make a noticeable difference, but that was because of a file system design that had outgrown its usefulness.

With modern file systems on Windows (NTFS), defragmentation is frankly a waste of time, and its biggest effect is likely physical wear and tear on your hard drive. Defragmentation is strictly a no-no for Solid State drives, and garners absolutely no benefit.

I am not saying defragmentation of the file system under certain corner cases cannot show some measurable change. It can. I am saying such a change will have no material impact in the performance of a game. I invite any reader that can show otherwise with a repeatable test that will pass muster for scientific validity to comment with references to such a test. I know of none.

The 'shutting down of background processes', whether done manually or with some program has long been a 'tweak' recommended in enthusiast forums. In particular, recommendations are made to disable Windows intrinsic services and processes. Utter BS! There is again no test I've ever seen that shows this to have any material effect on game performance. Messing with Windows facilities can have very deleterious effects on the performance and reliability of the OS, and should be considered off limits by any informed gamer.

Now doing this can certainly affect boot times: these Windows components are typically loaded during the boot processes, so this will take some time obviously. But once booted, Windows manages these components quite efficiently, moving them aside if an application such as a game needs resources. There is no material penalty leaving these alone for a gamer.

Of course, if the gamer has tons of junkware or other software installed on their gaming machine, these may cause issues. In these cases, shutting down or disabling these could benefit game play. But seriously, what sane gamer that cares about game performance plays on a machine burdened with junk?

The solution to problems like this is to have a proper gaming environment, and not install crud in the first place. See Swimming in the Septic Tank with my Gaming Buddies for how I set up my gaming machines, a model that I believe is ideal for the serious gamer.

I'm not even sure how to comment on the claim of  'cleaning RAM, and intensifying processor performance'. Windows manages memory. The way it should be managed. 'Memory Cleaners' and 'Extenders' have long been known to belong to the snake oil camp of PC 'tweaks'. Enough said.

Let's answer our three questions for this product.

• There's no valid reason this product should have any material affect for a properly configured gaming environment. If you have junk software baggage getting in the way of your gaming pleasure, uninstall it or just build a proper environment in the first place.
• I've seen no repeatable, scientifically valid test to validate the claims for this product when installed in a proper gaming environment. Only anecdotal claims, about as valid as the miracle cures claimed for colon cleansing.
• Since there does not appear to be a measurable difference on a properly setup PC, I'd expect the product to have no material effect. So it doesn't matter to the gamer.

Next, let's look at the specialized 'gaming specific' NIC hardware offered by Bigfoot Networks. This company burst into the PC gaming scene in 2006, offering a product called the "KillerNIC" with claims of improved pings and game performance. I mentioned them in my earlier blog entry Perplexed Execs Dissect PhysX.

The marketing materials and hype that surrounded this initial product were mind numbing. Oral Roberts, Tony Robbins, and Billy Mays combined. There was (and still is) however at the same time a suspicious lack of any tests with reasonable protocols and environments showing any material improvement. This kind of hype should always raise an eyebrow. Their current campaign is filled with outlandish testimonials (how many of these players paid for their cards, you might ask) that they remind me of a revival meeting. No scientifically testable numbers to be found anywhere. Big surprise.

The tests I've seen, both in-house and out, seemed to all have been done on hardware that was borderline at best for a serious gamer. While offloading the network processing from an overloaded OS and hardware platform with a mediocre on-board NIC chip may demonstrate measurable performance benefits in network response and even frame rates due to reduced CPU utilization, no gamer with the $300.00 to spend at the time was likely to be running games on such hobbled hardware. And if they were, the money could have been spent far more effectively elsewhere to improve hardware performance (RAM, CPU, add-in NIC, etc.)

I am not aware of any rigorous, scientifically valid test of these products on a modern gaming machine that show any material effect on performance in areas that matter to the gamer. Reviews by magazines and tech sites reflect this view.

In their most recent incarnation, the company has moved the performance metric to a measurement of their own creation, using tools defined and built by them. "Trust me. See the difference it makes in the flow rate of the Flux Capacitors?''  This is starting to smell like some of the marketing done in other hobbies with kook esoterica, like high-end audio products.

Let's look at our BS detector questions for this item:

• Pings are important to gamers. They're also largely out of the gamer's control. Once the gamer's packets are on the WAN, there's nothing they can do to improve pings. Probably the reason the company dropped this as their marketing silver bullet, and moved to new nonsense. There's no valid reason improvements in the new metric should result in a material improvement of the gaming experience.
• The only test with any sort of measurement for the current product ("Killer 2100") extant at this time is the in-house test of the in-house created metric using the in-house created tool. There have been no scientifically valid tests showing any material benefit to a gamer. Suspiciously, there are absolutely no details in the marketing diarrhea found on the company site describing the hardware configuration used for their comparison. Lots of "testimonials" though. Sound like a late night TV commercial to you?
• Even if the results of the in-house test are valid, that this would make any material difference to game play strains credulity. Like audio cable makers that charge tens of thousands of dollars for a pair of speaker cables, claiming the incredible improvements wrought by the 10 MHz bandwidth of their cable. Problem is, human hearing drops out orders of magnitude lower in the spectrum, and there has never been a scientifically valid test to show any benefit of such cables. The numbers look good in their own tests for the NIC, as they do for the speaker cables. They just don't matter.

The answers to all three of these should raise red flags for the gamer considering laying out their hard earned cash for a product such as this.

If the gamer applies these three simple questions when considering a new piece of hardware, software, or the application of some 'twaek' seen in a forum, I think they will save themselves time and money, and avoid going down the rabbit hole of nonsense.

I try to look at the PC and gaming world, and the world in general, through glasses colored by logic and rationality. Take a look at my thoughts on other areas where I think the manure is deep at I Can See CXLVI Frames Per Second!, I Read it in a National Enquirer Survey, it Must Be True!, Mutation on the Bounty, and Port Forwarding: Slaying the Mythical Dragon of Online PC Gaming.

For a great overview of how to think using logic, rationality, and healthy skepticism, check out the materials at The James Randi Educational Foundation and their Million Dollar Challenge, most recently applied to ultra-expensive high-end speaker cables (well, almost applied: the cable vendor chickened out!)

There's also an amusing snippet How to be a Skeptic on WikiHow, check it out!

Update:

After reviewing some of the grotesque marketing tactics at the pages of Bigfoot Networks, I have made a public challenge.

I invite readers to e-mail them with a link (I wanted to put a cool "mailto" link here, but strangely the contact information for the company headquarters doesn't have an e-mail. For that matter, it doesn't have a phone number. The "Texas Office" has a phone number, but I'm not clear if the address has a suite number or a self-storage shed number. In any case, no e-mail there either. If a reader finds one, let me know! I want to donate a PC to a worthy school.)

Their lawyers (must be pretty cheap, if "Grubby" the master Warcraft player they use as a reference "earns more in a year than your average lawyer.") can contact me and my lawyers for details.

In the spirit of my earlier "Bounty" blog entries Mutation on the Bounty and I Can See CXLVI Frames Per Second!, I will open this up to a public challenge at some future date. I first want to give the Bigfoots at Bigfoot a chance to accept it.

"Grubby". That's a good one. I wonder how much pings really matter for flashing pink hooves on the royal mount, or whatever they call them in those kind of games like Warcraft where cat-like reactions are required. Not!

The challenge has beeen moved to its own entry here.

As an aside, as per the earlier bounties, I'll not be posting any anecdotal comments from readers claiming they've "seen" this particular bigfoot. If you think you can meet this challenge and are able to demonstrate the ability and willingness to suffer the penalty of a loss, or if you have an idea for a challenge related to this that you want to propose, do so via a comment or email. Again, I'll not be posting any of the "Well, I can tell the difference 'cause my cat says so" genre of comments.