Hacker News Reader

Comment by RiderOfGiraffes | Hacker News Reader

Looking at the pacman solution, there's a problem when two ghosts end up on the same square, then they might tend to follow the same path, whereas programming them as objects (and not anti-objects) you can include avoidance strategies.

To get that from the scent-following, hill-climbing algorithm requires some work.

View on HN

They did mention that ghosts block the pac-scent, so the differential equation for the square would yield different values in the case of an adjacent ghost.

The specific case you mention is discussed in the paper on page 6 - http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobj... It's well-written and makes for an interesting read. As someone interested in AI but without much skill I found this approach much more intuitive, though I wonder about the CPU efficiency of simulating a dynamic environment.

Will Larson also discusses these ideas in a very nuts-and-bolts manner, albeit briefly: http://lethain.com/entry/2007/jun/07/anti-objects-and-reflex...

I think a distinction needs to be made. The anti-object seems to provide the environment in which the object moves. I don't think the point is for there to be absolutely no logic in the object itself, the logic should merely be simplified.

On the contrary, the ghost object in this example still has to implement the hill climbing algorithm. It could go down the hill (as it would do if pac man got one of the super pellets), or it could ignore the hill altogether. I think this also implies that it could avoid collisions with other ghosts, or even avoid grouping with other ghosts by paying attention to their scent as well. Seems like it would be trivial for a tile to further provide the scent value for all interesting objects in the maze.

More importantly, in Pac-Man, each ghost has a separate algorithm that each follows in their pursuit.

http://www.webpacman.com/ghosts.html

Yeah, because ghosts are physical corporeal entities that couldn't possibly be in the same place at once :-)

The point is that the challenge gets less if two ghosts merge, because they start following the exact same path. You could probably even abuse that to create effectively 1 ghost. (However, as others note, this problem does not actually arise, because ghosts block the pac-scent)

I wonder if there's an upper limit to the number of cospatial ghosts...

Modern scholasticism! :)

One of the biggest advantages of implementing the ghosts as objects is that they can actively work together to corner pac-man.

Never underestimate the power of emergent behavior of a small number of interacting rules. The ghosts do not have to explicitly interact in order for them to coordinate. The fact that a ghost blocks scent means that they influence each other in a way that leads to them covering multiple paths. I'm not an expert, but I would bet hard cash that such a strategy works better than any explicit coordination strategy that takes up to an order of magnitude more effort to implement, and I wouldn't be surprised if it's mathematically optimal.

Reply on news.ycombinator.com