Thought Experiment: Drawing a Pond Simulation

[JEG2]

@terakilobyte

From the world process pulse an update call where each pad determines if the resident will move.

This is an interesting way to get “ticks” with the multi-process approach.

[gregvaughn]

@JEG2

My current solution has a lot less processes than some are recommending here.

I’d be interested in seeing what you wind up with.

[JEG2]

@gregvaughn

I’d be interested in seeing what you wind up with.

Of course, I am storing all experiments here.

The one we are discussing isn’t up there yet, because I need to push a library I extracted from it after I’m sure about the interface. It’ll be up soon though and there are more experiments to come.

[Qqwy]

@JEG2

@terakilobyte

From the world process pulse an update call where each pad determines if the resident will move.

This is an interesting way to get “ticks” with the multi-process approach.

Hmm…

I wonder what the pros and cons between pulsing from the World process are, vs. using Process.send_after internally on each Lilypad.

[peerreynders]

@JEG2

Draw a 64 lily pads wide by 128 lily pads high pond with 3,000 turtles and 3,000 frogs distributed randomly across them.

There seem to be two independent aspects of “scale” here, the volume of the critter population and area of the living space. The effects of the “occupation” derives from both aspects. I personally am reluctant to assign any responsibility to the lily pads beyond serving as a reference to a location grid.

@JEG2

If the same type count is less than 30% of the total number of neighbors (up to eight), the critter will try to move to an open pad in a random direction, some random distance between one and five steps away.

This seems to give rise to the concept of a critter neighborhood. The immediate neighborhood (adjoining lily pads) influences the decision to depart. The critter’s travel range determines the area of the critter neighborhood so that it can decide where to depart to.

In essence a critter can know/manage it’s own perception of it’s neighborhood for it’s own purposes. While stationary it only needs to communicate with the other critters in it’s own neighborhood and it can do it all right up to the point where it wants to depart to another location that it selected.

Critter Process

• The critter process receives a new location message (more on this below). The message also contains a list of the new resident critter neighbors (i.e. their process Ids). (1) The critter informs all of its old critter neighbors of its departure. (2) The critter informs all of its new neighbors of its arrival identifying its process id, species and location. (3) The new neighbors respond with a welcome message revealing their species (frog or turtle) and location.
• Upon receiving a welcome message the critter process regenerates the list of neighbor critters (and immediate index) to include the resident critter.
• Upon receiving an arrival message the critter process responds with a welcome message (process id, species, location) and regenerates the list of neighbor critters (and immediate index) to include the arrived critter.
• Upon receiving a departure message the critter process regenerates the list of neighbor critters (and immediate index) without the departed critter.
• When it’s time-to-move the critter process uses the list of neighbor critters to generate a list of empty locations in the neighborhood and picks one to move to. It dispatches a move message (process id, species, old location, new location) to the critter registry process.
• ??? (stop message - see below)

Critter Registry Process

• Upon receiving a move message the registry verifies that the new location is in fact empty. It may not be if just recently another critter from an overlapping neighborhood moved into that location first. If it turns out that the location is already occupied the registry responds with a stop message. By the time the requesting critter handles the stop message it will likely already have processed the arrival message of the newcomer. So the stop message should simply re-trigger the time-to-move logic to issue another move message.
• If the move message refers to an empty location the registry process assembles a list of critter processes that are in the neighborhood range of the location and responds with with a new location message after clearing the critter’s old location and recording it in the new location.

Clearly the Critter Registry Process is a potential bottleneck, depending on the size of the living area, size of the population and the frequency and volume of move requests which gives rise to a variation:

Critter District Registry Process

• A district registry serves only part of the entire living area. Some simplifying assumptions: (1) each district covers the same size living area (2) a critter in the center of the district doesn’t have a neighborhood that extends beyond the limits of that district.
• A location doesn’t just have coordinates but also a district which serves it. Essentially the critter only communicates with the district of the location it currently resides on, even when it intends to move into an adjoining district.
• Multiple (adjoining) districts have to coordinate activities to satisfy move requests, (1) to assemble the list of resident critters for a specific location in one district while the neighborhood overlaps other adjoining districts and possibly (2) to hand off the moving critter from one district to the next. For example, with a square grid a location in the corner of the district has a neighborhood that overlaps four separate districts (at which point a hexagonal grid may be an improvement).

Hexagon grids: coordinate systems and distance calculations
Hexagonal Grids

PS: Upon further consideration it is probably safer for the registry(ies) to issue leave/join messages (instead of the critter departure/arrival messages) as the registry has likely a more consistent view (in time) of the neighborhood(s). So really the critter is reduced to managing its neighborhood list based on received join/leave messages while stationary only for the purpose of generating a target location map when it comes time to move.

Given that message sequence isn’t deterministic, messages from the “old neighborhood” may arrive after a move just completed or messages from the “new neighborhood” could arrive before a requested move is complete (from the critter’s perspective) - so some safeguards are necessary to properly process late and early messages.

In terms of “drawing” the living area I think a separate (set of) process(es) is called for. For example the registry could in tandem with the new location message send a critter relocation event to an event queue. The drawing process fed by that queue is then responsible for managing the critter display information in such a way that (1) updating the location information is relatively fast and (2) the collective display information is advantageously sequenced for easy consumption by the display device (updating the display two lily pads per event vs. generating the entire pond in one pass “per display cycle”).

[JEG2]

@peerreynders

Upon receiving a move message the registry verifies that the new location is in fact empty. It may not be if just recently another critter from an overlapping neighborhood moved into that location first. If it turns out that the location is already occupied the registry responds with a stop message. By the time the requesting critter handles the stop message it will likely already have processed the arrival message of the newcomer. So the stop message should simply re-trigger the time-to-move logic to issue another move message.

I worry a lot about the coordination aspect of this approach. I personally believe that sometimes a bottleneck can be a good thing, because it can give you a single source of truth.

[peerreynders]

@JEG2

I worry a lot about the coordination aspect of this approach.

Not sure I follow - distribution of interacting activities requires coordination - unless we’re falling back onto an essentially single threaded approach.

And in terms of the experiment it can’t happen that - for example - two frogs jump towards the same lily pad and only one can stay?

[JEG2]

@peerreynders

And in terms of the experiment it can’t happen that - for example - two frogs jump towards the same lily pad and only one can stay?

One version of the simulation that I have seen allows them both to land, but makes critters sharing a pad seek to move.

[JEG2]

My code is now online. I could simplify the Pond datastructure quite a bit now though, due to changes I’ve made in interprocess communication.