Antiobjects

http://en.wikipedia.org/wiki/Antiobjects

by raganwald • 17 years ago

133 28 17 years ago

en.wikipedia.org

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.

anigbrowl• 17 years ago

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...

ludwig• 17 years ago

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

Confusion• 17 years ago

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)

joshu• 17 years ago

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

jordyhoyt• 17 years ago

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.

DannoHung• 17 years ago

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

eru• 17 years ago

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

allenp• 17 years ago

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

lmkg• 17 years ago

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.

RiderOfGiraffes2• 17 years ago

Now I remember why this seems so familiar ...

I used a similar method to the pacman solution to make a simulation of traffic. By modelling the road as well as the cars, I could measure the distance between cars by having the road remember when a car last passed over, and give that information to the next car that passes over. The simulation was enormously simpler by modelling the road and storing information in that, rather than just in the obvious objects - the cars.

In effect, cars left traces behind for the next cars to collect and process. Distances between cars could be calculated simply by knowing the times of transits and speeds of cars. Uncertainties needed to be taken into account, but the road could also contain pointers/references to the cars that had passed over.

In my case I distributed the simulation over 1024 processors and the messages were explicit. I find object-oriented programming largely to miss the point. As Alan Kay once said, the point was never the objects - it was always intended to be about the messages.

Of course, that's a religious argument, and probably better discussed elsewhere.

ADDED IN EDIT: I really ought to write up some of my experiences ...

BigZaphod• 17 years ago

Rambling thoughts your comment triggered:

When we model position of things in code, we often put the position within the thing being modeled - car, game character, window, etc. So you can do things like: aCar.position - but I think that might be conceptually wrong and have been thinking that for a long time but haven't had much chance to explore the idea.

The idea of putting the responsibility for (eg.) location of each object within the world into the world itself seems to fit better with reality, too. After all, in our physical reality there's rules that "the world" imposes on things within it. One big one is that only one physical object (atom or what-have-you) can exist in a given location in space at a given time. Having the location of an atom in space be stored in the atom itself would seemingly make it a lot more difficult to make sure that rule goes unbroken and, arguably, can't be how the universe works as we seemingly cannot "see" location encoded within physical objects in our universe (that I know of). Therefore the location of a thing is probably "stored" within the fabric of the universe itself...

Anyway... If you write up your experiences, please post them to HN - I'm betting they'd be interesting!

d0mine• 17 years ago

Whether or not more than one object may occupy the same place depends on kind of objects e.g., http://en.wikipedia.org/wiki/Boson

jrockway2• 17 years ago

But of course, you can have this API and delegate the responsibility of calculating the position:

   class Street {
       has 'cars';
       method add_car(){
           $car = Car->new( street => $self );
           $self->cars->add($car);
           return $car;
       }
    }

    class Car {
        has 'street';
        method position() {
            $self->street->position_of($self)
        }
    }

Now, given a random Car, you can still ask "$car->position", but the actual calculation is handled by something else.

(The deeper issue here is how consumers of Car are not coupling themselves to a particular position-calculation strategy. Change the storage of the position value from the Street to the Car, and consumers are none the wiser. This is the point of OOP.)

pmiller2• 17 years ago

I'm not surprised traffic simulation is amenable to this approach -- most traffic simulation visualizations I've seen look quite a lot like the movement of ant colonies, and this is precisely how ants navigate.

tybris• 17 years ago

My problem is, I need to implement this on real cars/roads.

smallblacksun2• 17 years ago

We already use pressure sensors in the road to control traffic lights, which works well (other than the high cost of installation/maintenance).

davidmathers• 17 years ago

This reminds me of Luca Cardelli's theory of objects:

http://books.google.com/books?id=4xT3LgCPP5UC&pg=PA7&...

According to Luca the correct way to think about objects is not as the entities of the software model, but as the construction materials for the software model. He uses the analogy of making a physical model of the solar system. In your model the planets don't move themselves, they're moved by gears, tracks, and motors.

So it could be entirely appropriate to think of the pacman board being made up of tiles and those being true, properly understood, OOP objects.

I think he would say that "The metaphor of objects can go too far by making us try to create objects that are too much inspired by the real world." is exactly how not to think about OOP in the first place.

bd• 17 years ago

That's actually a quite common pattern in artificial life community (inspired by real world behaviors from insects):

http://en.wikipedia.org/wiki/Stigmergy

http://en.wikipedia.org/wiki/Ant_colony_optimization

Also Sims had some "intelligence" embedded into objects instead of the agents:

http://www.gamedev.net/columns/events/coverage/feature.asp?f...

jrockway2• 17 years ago

This is not a new concept, but rather just exercising good programming technique. If you are modeling a collection of elements, and the elements need to be aware of themselves in relation to the other elements, then you need to model the container.

A simple example is an array. You don't ask an array element for the array's length or for the i-th array element; you model the container and let the container do that.

panic• 17 years ago

This duality shows up in fluid simulation as well: http://en.wikipedia.org/wiki/Lagrangian_and_Eulerian_specifi...

bham• 17 years ago

This reminds me of a funny Cracked skit about the 1979 game developer's conference wherein the birth of Frogger was reenacted. "Ok ok you are a truck driver and you try to run over frogs crossing the road". "No, no, you ARE the frog!" "Whoooa"

http://www.cracked.com/video_16019_video-game-pitch-meeting-...

bartl• 17 years ago

A major difference between the Pacman ghosts as described here, and cars in traffic, is that the ghosts will always be able to smell the pacman, no matter how far he is, and a driver in a car has a limited view on the traffic surrounding him.

The latter (limited) is easier if you use objects for the cars, the former (unlimited) is easier using antiobjects.

thomas11• 17 years ago

You could have tiles forget the scent/roads forget the traffic. With each simulation step, decrease it until it's gone after however long you want it to be remembered. Then, ghosts would have to be somewhat near pacman, and cars are only influenced by what goes on around them, not what happened a while ago.

Of course, simulating the actual view of a driver, i.e., excluding things behind the vehicle etc., takes a lot more work.

tome• 17 years ago

I would be tempted to call these "co-objects" since they are in some sense dual to your standard objects.

Antiobjects

Related Stories