Wednesday, February 11, 2015

What Does Pac-Man Smell Like?

Would This Smell Fruity?
Today I was talking to a friend about path-finding algorithms for how frogs in a game could find their way towards certain objects, and he suggested that I research "Pac-Man smell" as an example of a simpler method.

But then I began to wonder, what would Pac-Man smell like? For some reason, I theorize that he would smell like those candy hearts you get on Valentine's Day with the little messages written on them. I don't know why I think that, but I do.

That aside, I did look up the Pac-Man Smell system for path-finding. It is interesting enough that I thought I should share it. While smell is not mentioned at all in The Pac-Man Dossier, perhaps the definitive write-up on the game, Neal Ford talks about it in his book The Productive Programmer. When he discusses Anti-Objects, he uses Pac-Man as an example (see page 147 in the book).

Basically, the deal is that objects and object hierarchies, common in Object-Oriented Design, actually make some kinds of problems harder than they need to be. If you were to create a game like Pac-Man in Java, it's likely that you would have objects to represent Pac-Man, the ghosts, and the dots. So how would you make the ghosts chase Pac-Man? Obviously you'd put a lot of smarts into the ghost objects. But the algorithms needed in that case are complex and certainly beyond the computational capacity of the original Pac-Man arcade game. With today's hardware, we could make something work but, like Scrooge McDuck would always say, "Work smarter, not harder." If you turn the problem around, it can be solved in a much easier way.

In Ford's Anti-Object example, he states that the Pac-Man developers put more intelligence into the maze itself in order to make the ghosts dumber and yet still able to chase Pac-Man. When Pac-Man occupied a cell of the maze, that cell increased its "smell" value by one. When Pac-Man left a cell, its smell decreased by one and then continued decreasing by one every few clock ticks. For a ghost to track Pac-Man, it could now contain simple logic: move towards the cell with the highest Pac-Man smell.

And that is the essence of Anti-Object design. Sometimes thinking outside the object is the best and most efficient way to create the desired behavior. I would summarize this approach like this: do what works best even if it deviates from a perfect model. After all, the people playing the game won't appreciate how well the software is broken down into a perfect Object-Oriented Design. To them, it just has to work.

I'm still thinking about the best way to direct my frogs around. But the frogs are thinking about eggs, at least today.

Amphibian.com comic for 11 February 2015