DevExpress Newsletter 31: Message from the CTO

29 July 2010

A fun message this time — Pac-Man, yay! — with a serious underlying theme: sometimes the obvious objects in your class model of the real world are not the most optimal. Welcome to antiobject programming...

What Pac-Man can tell us about Object-Oriented Programming

We've been doing object-oriented design and programming for getting on for 20 years now, more if you come from the Smalltalk world. You'd think we all know how it works, how we identify the possible objects in our model of the real-world, how we work out the interactions between them, the inheritance patterns, the polymorphism, and so on, so forth.

Sometimes though all this knowledge and experience can lead us astray.

Let's take an example from Pac-Man. If you recall there's a maze containing dots for the Pac-Man -- whom you control -- to eat. To make the game harder and and more exciting, there are four ghosts, Blinky, Pinky, Inky, and Clyde, who wander around the maze and suddenly get a whiff of the Pac-Man and start to chase him. Get caught and one of your lives is lost. However, there are four pellets that, if eaten, give you the opportunity to eat the ghosts for a short period of time.

If you were going to model this in an object-oriented program, you'd probably create a Pac-Man class and a Ghost class, with presumably some kind of maze class to draw the maze. The dots and pellets might be classes too.

The problem with this scenario is that the Ghost class becomes hard to write. Consider its behavior: it wanders around the maze until it gets "close" to Pac-Man, when it suddenly starts tracking him. But how to calculate "close"? It's not a Euclidean closeness because the ghost can only move along the maze, not hop through the walls. It's a "path closeness". The ghost has to know where Pac-Man is, and calculate the minimal path to him. Calculating that for each ghost at each cycle of the game play on the low-end processor of the time would have been way too slow.

Instead of trying to design a complex ghost object — the foreground, if you like — we flip our focus to the background: the maze. We give the Pac-Man the ability to leave a smell, an integer value, on the squares of the maze as he moves. Each cycle, the smell evaporates — each maze square decrements its smell value — until it reaches zero. 

The ghost object then does not have to work out where Pac-Man is and calculate the minimal path to get there, it just instead sniffs out the smell on the adjacent squares. If none, it continues on the path it was travelling. If there is, it just moves to the adjacent square with the stronger concentration.

This technique is known as antiobject programming. Instead of designing the obvious "real-world" object with its complex behaviors, we design an object that essentially does the opposite of what we originally thought. The new ghost object follows scent and has no knowledge of Pac-Man; the maze squares, instead of not existing at all or being simple static objects sitting there, suddenly have behavior.

The complexity of the original objects has instead been changed to simple behavior of the antiobjects.

The video is available here.

The original source of antiobject programming is from Collaborative Diffusion: Programming Antiobjects by Alex Repenning of the University of Colorado. The whole paper is well worth reading: there’s lots of fascinating information and discussion about the AI aspects of game programming in there, including the introduction of antiobjects.

1 comment(s)
richard morris

That reminds me - I once built a simulation of ant pathing using a similar technique that was remarkably realistic at modelling a colony finding a food source and returning it to the nest.  All the actual work is done by the terrain maintaining a decaying scent of either the food or the nest - ants simply head toward one or the other depending on whether they are carrying a morsel of food.  I was able to model thousands of ants on a modest system, which would have been impossible if the calculation was being done in the ant objects.  

I had no idea the technique was called antiobjects - nice to know.

30 July, 2010

Please login or register to post comments.