Design system architecture

[hawkw]

We've agreed that we want to use the model-view-controller architecture, but I think there are still a lot of questions we need to work out. From my perspective, they're mostly related to how we want to model our simulation.

• [x] How will agents/particles be represented?
• [x] How do we represent the space?
• [ ] How do we communicate the space state/updates to the view?
• [ ] Can we use multi-threading to improve performance?
• [ ] How do we ensure that particle behavior is modular?

Also, I don't know very much about writing big apps in Python - I've mostly just used it for scripting. So we should look into that.

[yarbroughw]

"How will agents/particles be represented?"

My instinct is to have a master "particle" class, with x, y, and z coordinates and a movement vector, as well as some kind of shape representation for the View to render. Then all specific kinds of particles (agents, obstacles) would inherit from the class. So the View's job is simply to loop through the model's list of particles in the scene and render each one.

This is a super OOP way of writing it, and there's nothing wrong with it, but I always wonder how this sort of thing would best be done in a functional style. Probably with some method-less data structure and a bunch of functions that are designed to act on it... e.g., in Haskell:

move :: Point -> Vector -> Point
move (x,y,z) (dx,dy,dz) = (x + dx, y + dy, z + dz)

data Particle = { point :: Point, velocity :: Vector, shape :: Shape }
update :: Particle -> Particle
update p = p { point = move (point p) (velocity p) }

[hawkw]

I am super digging the Haskelloid example and this is super possible in Python. In Python a point can obviously be a 3-tuple or 2-tuple (depending on the number of dimensions), but as far as I know, there's no type aliasing so this kind of thing would be bereft of understandable names.

The particle structure could of course be a dict, but since the structure for a particle is always the same, there's really no reason not to make it a class instead. And when you're working with classes, there's no additional overhead to adding methods to them rather than letting the functions float around in the global namespace, so basically, what I'm saying is that the choice of Python as a language pushes us towards an OOP-y design.

[hawkw]

With that said, you could definitely make things immutable for some extra fp-ness, but I'm honestly not sure what the performance implications (good or bad) would be in this case.

[hawkw]

As a side note, I really like how the NSWC Haskell study represents regions as a function Point -> Bool that tells you if a point is in a region or not. They then construct different types of region, i.e. circle :: Radius -> Region. I dunno if this sort of thing is useful for our purposes but it seems really nifty and elegant to me.

[hawkw]

Maybe we do want to write the project in Haskell. I don't know, I don't know Haskell that well at all, but on the other hand, my primary way of learning languages is just to embark into something slightly too hard to do and bang my head into it until I learn it. I'm just concerned that if we used Haskell, you would right all the code and I would just kind of watch.

Sorry for leaving so many comments.

[yarbroughw]

Well, I think Alden would be pretty averse to using Haskell, and it's still enticing to me to have some degree of code reuse or interoperability between these two projects. Its not totally necessary though, and I love Haskell...

BTW, there is a way to do type aliasing (sort-of) for tuples in Python.

[yarbroughw]

I just realized that particles in the model having a "shape" variable is a violation of MVC, since the view should have sole responsibility over what the particles actually look like.

[hawkw]

I think Alden would be pretty averse to using Haskell

Oh, yeah, I had forgotten about the possibility of this project being compatible with your project in 250. Hmm. I wonder if there are any ways to make Python and Haskell talk, or to separate this project from your 250 project and have them communicate through some kind of serialization. Maybe not, given the things you guys are doing in 250 and how they'd fit together with this project.

BTW, there is a way to do type aliasing (sort-of) for tuples in Python.

That is wicked cool and I was not aware of it - thanks for pointing it out!

Functional programming in Python is definitely a thing that's possible. People tend to think of it as an OO language and write OO-style code in Python, but it definitely has all the basic functionality you need to write FP-style code. The main reasons I would like to move away from Python are just that a) I would like to learn Haskell and b) I'm concerned about it's performance (a large multi-particle simulation could definitely benefit from being compiled code and from GHC's quasi-magical optimizations).

[hawkw]

I just realized that particles in the model having a "shape" variable is a violation of MVC, since the view should be the sole determination of what the particles actually look like.

Maybe they could know what 'type' of object/particle they are and the view could figure out how to draw different types or whatever.

[yarbroughw]

Oh good idea. That would mean:

data ParticleType = Agent | Obstacle | Foo | Bar

and then in the model:

shapeOf :: ParticleType -> Shape
shapeOf (Agent)    = Triangle
shapeOf (Obstacle) = Cube

[yarbroughw]

shit... I keep writing everything in Haskell.

[hawkw]

Maybe we should just do that.

[yarbroughw]

Do you think we might have trouble writing an agent implementation in a pure-FP language? I'm struggling to think of what a non-OOP agent would look like.

[hawkw]

Isn't an agent essentially just a function of the form WorldState -> Action repeated ad nauseam?

Or, more accurately (WorldState,AgentState) -> Action?

[yarbroughw]

Maybe they can just be functions in the State monad. So each agent is

import Control.Monad.State
type Agent = State WorldState AgentState

State is defined as

newtype State s a = State { runState :: s -> (a,s) }

which is like a fancy version of

type State s a = s -> (a,s)

So my definition of Agent is basically

type Agent = WorldState -> (AgentState, WorldState)

but wrapped in the State constructor, so we can do all sorts of cool monadic wizardry (like MapM over a list of agents to pass some WorldState from one agent to the next).

[yarbroughw]

...and AgentState could be defined by

data AgentState = AgentState { location :: Point, velocity :: Vector }

and maybe some other stuff like learned parameters/weights for great good.

[hawkw]

I am not really sure why an Agent is defined as an ADT rather than a function? This is obviously a Haskell thing I don't know yet.

[yarbroughw]

Oops. Edited my comment to fix that -- I got data and type mixed up.

[yarbroughw]

OK so, instead:

data Perception = Perception { stuff :: Stuff }
type Action a = State WorldState a
type Agent = Perception -> Action

Not sure what WorldState will mean yet, but we'll figure it out.

[hawkw]

WorldState would have to be some kind of way of tracking where all of the particles are. Either a list of tuples or map of (Agent -> Point) or a bitmap/2d array of booleans indicating whether or not it's occupied - I'm not actually sure which would be more space-efficient, it probably depends on the number of agents, the size of the grid, and probably also if we want to track stuff like velocity in the world state.

[yarbroughw]

Alright, so: boids have three basic behavior rules:

• Separation: steer to avoid crowding local flockmates
• Alignment: steer towards the average heading of local flockmates
• Cohesion: steer to move toward the average position (center of mass) of local flockmates

We can add more behavior to this list for more complex behavior. But since this is a flocking simulation, I don't think our agents should adhere to the whole Perception -> Action model we were talking about before. That seems like overkill.

[yarbroughw]

Commit ade77b8fafe427af2505454fc1fd5d712b7976b2 adds a simple definition of a Boid. Note that the boid doesn't have any update function yet, since the three rules listed above require access to some form of WorldState.

[yarbroughw]

Which actually solves our first question! (How will agents/particles be represented?)

[hawkw]

Okay, awesome! I feel like fundamentally there has to be some form of Perception -> Action (which I still think is More or Less What An Agent Is); even if this is as simple as a boid looking at the nearby flock mates and steering itself according to the three behavior rules, this is still essentially a mapping of a particular environment state to an action.

But it need not be as complex as the WorldStates we were envisioning earlier...

[yarbroughw]

OK, next question: How do we represent the space?

Our World is a list of Boids right now (and thats fine), but we'll also need some way to define boundaries as well, and to enforce those boundaries.

We could:

• have the space be a 4D torus (by modding the locations at each time step), but that might look weird when rendered,
• have "hard" boundaries and reflect a Boids' velocity if it extends past the boundary (kinda tricky),
• not enforce boundaries at all (possible, if we render a lot of the 3D world)

[hawkw]

Why not make some kind of bounds behaviour a function of some kind passed as a parameter to Update? Modularity.

[hawkw]

So the out of bounds behavior is just a function Boid -> Boid that we pass in and map over self if we're out of bounds as part of the Update process (as per our discussion earlier).

The boundaries themselves can just be a Radius or something. Unless you want to allow for, like, a cubic space, 'cause then it would have to be rather more complex (Bounds :: Boid -> Bool or some such).

[hawkw]

Okay, so abd6afb70f0a0f1e8290cf3acbecf90be8415413 finishes the neighborhood function. This should mean that the base Boid behavior is more or less done, and we should work on the visualization bit.

We can then work on adding Fun Stuff once we can run some quick simulations and watch our flocking behavior.

[hawkw]

Pretty sure we can go ahead and close this.