Sparse world structures in Erlang

Question

I'm thinking of how to property port a "ant-farm simulator" from to Erlang. Here's the basic rundown:

1) Define a 100x100 world of "slots"

2) Ants occupy one slot

3) The ant colony occupies location 50,50

4) Food is placed randomly around the map

5) Ants move one space at a time to seek food and bring it back to the colony

6) Only one object can be in a slot at a time.

The goal of this problem is to keep the system as concurrent as possible. In Clojure, the above problem is solved by having a thread pool of Agents that each run the AI for a single ant. Then these ants update the global state via a transaction.

It's that global state that I keep thinking about. How do we go about constructing the "game world"?

My first thought is to have a Erlang process for each ant, and then a process for each slot in the map. To move, a ant does the following:

1) The ant tells it's current slot "I want to move North"

2) The slot calls the slot to the north and says "Please update your contents to now contain ant "pid""

3) If the north slot already has an ant, it sends a "denied" response that trickles down to the slot containing the ant (and then to the ant). If the update works, then "granted" is sent down the chain and the ant updates its internal state.

The only thing I don't like about this method is that during a move process, the ant, its slot and the target slot are all "locked" until the whole transaction is completed. This then opens itself up for deadlocks. That is, two ants could be trying to swap places at the same time, each slot would be waiting for the other.

Can anyone suggest a better solution?

---EDIT----

Let me step through the deadlock problem:

1) Ant 1 asks slot A to "transfer north" to slot 2 2) Ant 2 asks slot B to "transfer south" to slot 1 3) Slot 1 sends a transfer request to slot 2 and waits for a reply 4) Slot 2 sends a transfer request to slot 1 and waits for a reply

From a code perspective this would be simple to implement but would also deadlock as each slot is only listening for replies from the other slot. I suppose the "correct way" might be to automatically reject all transfer requests while in the process of a transfer.

Answer 1

Have your ant make a cast to the slot he is moving to, asking for permission to move. The ant then waits for a cast response, telling it whether the move was successful or not. If the move was successful, the ant updates his own state to indicate that he is in the new slot. If it failed, he once again executes his search logic. If you end up with A and B trying to exchange slots, you won't have a deadlock, but they'll both think they have to look for other options.

If your grid is heavily occupied, you might want the slots to execute a polling logic, handing out permission to neighboring ants, telling them that if their logic leads them there, they may enter. (Imagine a grid with 50x50-2 ants on it, and you'll see why this would be a good change of logic.)

Never use calls unless you absolutely, positively, without question can't survive without them. And then, try very hard to get rid of them if there is a chance of processes of the same type calling each other, or of types that can make calls to each other.