Wolfram|Alpha: Systematic knowledge, immediately computable.

Thursday, May 13, 2010

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.

1 comment:

  1. "A µ post."

    µ = micro, correct? That's the most common use I could find.

    Anyway, AI is interesting to think about. What was that Will Smith movie? I Robot? yeah, pretty awesome to imagine. I suppose 10 years ago when I placed a bunch of waypoints in a MP game for Bots to follow does not constitute the level of AI you are referring to in those books. Interesting that you are not an artist, but wanted to create a game using your neighborhood. Coding is something I cannot do. I know basic HTML, that's about it. 3D modelling and level building is what I did mostly, made a lot of textures, and a bit of sound manipulation.