StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSparse world structures in Erlang
text
Body
copied!<p>I'm thinking of how to property port a "ant-farm simulator" from to Erlang. Here's the basic rundown:</p> <p>1) Define a 100x100 world of "slots"</p> <p>2) Ants occupy one slot</p> <p>3) The ant colony occupies location 50,50</p> <p>4) Food is placed randomly around the map</p> <p>5) Ants move one space at a time to seek food and bring it back to the colony</p> <p>6) Only one object can be in a slot at a time. </p> <p>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. </p> <p>It's that global state that I keep thinking about. How do we go about constructing the "game world"?</p> <p>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:</p> <p>1) The ant tells it's current slot "I want to move North"</p> <p>2) The slot calls the slot to the north and says "Please update your contents to now contain ant "pid""</p> <p>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.</p> <p>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. </p> <p>Can anyone suggest a better solution?</p> <p>---EDIT----</p> <p>Let me step through the deadlock problem:</p> <p>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</p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload