Strangelights

About a week ago Rick Minerich made this blog post about an ant colony simulation in F#. I downloaded the code and played with it, I liked the simulation a lot but wasn’t too keen on the implementation – it used lots of thread and lots of mutable data. So I decided to dig around a tweak a little here and there, but before I knew it I’d rewritten the whole thing using immutable data structures. I also end up breaking the thing and having to mail Rick for help about why it was broken, anyway with a little help from him I managed to figure out the problem and finish the implementation.

The key to making it work with immutable data types was to use F# record types. These have a nice property that you can recreate them using a special “with” syntax, for example if we have a record type defined as:

/// represents an ant that moves within the territory

type Ant =

{ foodCarried: int

xloc: int

yloc: int

oldloc:list<int*int>

homeward: bool }

We can and we just want to changes its xloc and yloc we can do this by saying:

let ant = { ant with xloc = i; yloc = j; }

Because our structures are immutable we can no longer update a value at the top level, to get round this problem we end up passing all state into each function call. This is actually less incovient than it sounds; we defined an “environment” record to contain all the state we need so we have less identifiers to pass round:

type Env =

{ ants: seq<Ant>;

territory: Map<int*int, TerritoryNode> }

We also now rely heavily on the fact we can return more than one item from a function, as shown in this section taken from the “ANTHuntByPheromone” function:

let _,env,ant = ANTMoveRandomly env ant

So what’s the advantage in this approach? Now the algorithm no longer uses any shared mutable data we can run it in parallel very easily and have several ant simulations running at the same time:

So what’s the next step? I’ve been talking to Rick about an implementation use asynchronous workflows to move the ants and a number of “mailboxes” to represent the nodes that the ants live on. I think this could be very interesting stuff, so expect to see more in the future.

Here is a copy of the code of the current version:

#light

open Microsoft.FSharp.Control.CommonExtensions

open Microsoft.FSharp.Control.Mailboxes

open System

open System.Drawing

open System.Windows.Forms

open System.Collections.Generic

//Program constants

let antHome = 8;; //X by X in Size

let maxFoodPerSquare = 1000

let chanceFoodPerSquare = 80

let antMaxFoodCarried = 50

let antPheromoneDrop = 200

let antPheromoneDropNoFood = 0

let tickLength = 50

let antAdventurousness = 3 //Lower is more adventurous

let antWanderlust = 4 //Lower is lustier

let territoryHeight = 80

let territoryWidth = 80

let pixelWidth = 6

let pixelHeight = 6

let colonyTiles = 5

let _RandomGen = new System.Random();;

/// represents a single node in the ants territory

type TerritoryNode =

{ food: int;

pheromone: int;

isHome: bool

hasAnt: bool }

with

/// creates a new node with the default values

static member newNode home =

{ food = 0;

pheromone = 0;

isHome = home;

hasAnt = home }

/// creates a new node with food

static member newNodeFood f home =

{ food = f;

pheromone = 0;

isHome = home;

hasAnt = home; }

/// test if the node has food

member n.hasFood = n.food > 0

/// update where the pheromone value

member n.updatePheromone food =

if food then

{ n with pheromone = n.pheromone + antPheromoneDrop }

else

{ n with pheromone = n.pheromone + antPheromoneDropNoFood }

/// an ant arrives in the node

member n.antArrive () =

{ n with hasAnt = true }

/// an ant leaves the node

member n.antLeave () =

{ n with hasAnt = false }

/// represents an ant that moves within the territory

type Ant =

{ foodCarried: int

xloc: int

yloc: int

oldloc:list<int*int>

homeward: bool }

with

/// creates an new instance of an ant with the default values

static member newAnt x y =

{xloc = x; yloc = y; foodCarried = 0; oldloc = []; homeward = false; }

/// The environment - represents both the ants and the nodes they move within

type Env =

{ ants: seq<Ant>;

territory: Map<int*int, TerritoryNode> }

with

/// initalize the environment with the default values

static member initalize() =

//create a list of points to represent the grid

let points =

seq { for i in [0 .. territoryWidth - 1] do

for j in [0 .. territoryHeight - 1] do

yield i,j }

// randomly creat a node

let createNode i j =

let randomFoodDropValue = _RandomGen.Next( 0, chanceFoodPerSquare ) in

let home = i <= antHome && j <= antHome

if randomFoodDropValue = 5 then

TerritoryNode.newNodeFood ( _RandomGen.Next( 0, maxFoodPerSquare ) ) home

else

TerritoryNode.newNode home

// create a map of points to node values

let teritory = Seq.fold (fun acc (i,j) -> Map.add (i,j) (createNode i j) acc) Map.empty points

// create the list of ants

let antList =

seq { for i in [0 .. antHome] do

for j in [0 .. antHome] do

yield Ant.newAnt i j }

// return the environment

{ ants = antList;

territory = teritory }

/// replaces a node in the teritory with a new one

member x.replaceNode loc newNode =

if x.territory.ContainsKey(loc) then

let newTerr = x.territory.Remove(loc)

{ x with territory = newTerr.Add(loc, newNode) }

else

{ x with territory = x.territory.Add(loc, newNode) }

/// the direction that the ants travel in

type Direction = North | East | South | West

/// make an ant drop food some food

let TNDropFood node ant =

if (node.food = maxFoodPerSquare) then

false, node, ant

else

let space = maxFoodPerSquare - node.food in

if (space <= ant.foodCarried) then

true, { node with food = node.food + space }, { ant with foodCarried = ant.foodCarried - space}

else

true, { node with food = node.food + ant.foodCarried }, { ant with foodCarried = 0 }

/// remove the appropreate amount of food from a node

let TNGetFood (node:TerritoryNode) f =

if node.hasFood then

let food = node.food in

if food >= f then

{ node with food = food - f },

else

let retFood = node.food in

{ node with food = 0 },

retFood

else node, 0

/// test that a node is within the grid

let GTIsNodeReal i j =

0 < i && i < territoryWidth &&

0 < j && j < territoryHeight

/// attempt to move ant to a new node and return false if we can't

let ANTGoToNode env ant i j =

if GTIsNodeReal i j then

let node = env.territory.[(i,j)]

if not node.hasAnt then

let oldNode = env.territory.[(ant.xloc,ant.yloc)]

//printfn "i %i j %i xloc %i yloc %i " i j ant.xloc ant.yloc

//if not oldNode.hasAnt then

// System.Diagnostics.Debugger.Break()

let env = env.replaceNode ((ant.xloc,ant.yloc)) (oldNode.antLeave())

let env = env.replaceNode ((i,j)) (node.antArrive().updatePheromone(ant.foodCarried > 0))

true, env, { ant with xloc = i; yloc = j; oldloc = (ant.xloc,ant.yloc) :: ant.oldloc }

else

false, env, ant

else

false, env, ant

/// send an ant off in a given direction, trying the opersite direction if we can't

let ANTGoInDirection (env:Env) ant d =

let x1,y1, x2, y2 =

match d with

| North -> ant.xloc, ant.yloc - 1, ant.xloc, ant.yloc + 1

| South -> ant.xloc, ant.yloc + 1, ant.xloc, ant.yloc - 1

| East -> ant.xloc - 1, ant.yloc, ant.xloc + 1, ant.yloc

| West -> ant.xloc + 1, ant.yloc, ant.xloc - 1, ant.yloc

let moved,env,ant = ANTGoToNode env ant x1 y1

if not moved then

ANTGoToNode env ant x2 y2

else true, env, ant

/// move an ant in a random direction

let ANTMoveRandomly (env:Env) ant =

let dir =

match _RandomGen.Next( 0, 4 ) with

ANTGoInDirection env ant dir

/// make the ant hunt according to the pheromone surrounding it

let ANTHuntByPheromone (env:Env) ant =

let rnd = _RandomGen.Next( 0, antAdventurousness ) in

let env, ant =

if ( rnd = 0 ) then

let _,env,ant = ANTMoveRandomly env ant

env, ant

else env, ant

let southPheromone =

if GTIsNodeReal ant.xloc (ant.yloc + 1) then

env.territory.[(ant.xloc,ant.yloc + 1)].pheromone

else 0

let westPheromone =

if GTIsNodeReal (ant.xloc + 1) ant.yloc then

env.territory.[(ant.xloc + 1,ant.yloc)].pheromone

else 0

//printfn "%i %i" southPheromone westPheromone

if (southPheromone = westPheromone ) then

//printfn "random"

ANTMoveRandomly env ant

else

if (southPheromone > westPheromone ) then

//printfn "sout"

ANTGoInDirection env ant South

else

//printfn "west"

ANTGoInDirection env ant West

/// main encoding of ants behavior

let ANTBehave (env:Env) (ant: Ant) =

let x, y = ant.xloc, ant.yloc

let curNode = env.territory.[(x,y)] in

if ant.foodCarried > 0 then

if curNode.isHome then

let isDropped, curNode, ant = TNDropFood curNode ant in

let env = env.replaceNode ((x, y)) curNode

let _, env, ant =

if not isDropped then

ANTMoveRandomly env ant

else

false, env, ant

env, ant

else

let rnd = _RandomGen.Next( 0, antWanderlust ) in

let _,env,ant =

if rnd = 0 then

ANTGoInDirection env ant North

else if rnd = 1 then

ANTGoInDirection env ant East

else

if ant.xloc > ant.yloc then

ANTGoInDirection env ant East

else

ANTGoInDirection env ant North

env, ant

else

let _, env, ant =

if curNode.hasFood then

if curNode.isHome then

ANTMoveRandomly env ant

else

let tillMaxFood = antMaxFoodCarried - ant.foodCarried in

let curNode,foodGot = (TNGetFood curNode tillMaxFood) in

true,

env.replaceNode ((x,y)) curNode,

{ ant with foodCarried = ant.foodCarried + foodGot }

else

//printfn "hunt by pheromone"

ANTHuntByPheromone env ant

env, ant

/// loop though all the ants trying to move them

let ANTLoopBehave env =

let doAnts (env, acc) ant =

let envNew, antNew= ANTBehave env ant

envNew, antNew:: acc

let env, newAnts = Seq.fold (fun env ant -> doAnts env ant) (env, []) env.ants

{ env with ants = Seq.of_list newAnts }

// start of the worker mailbox statemachine ala game of life sample

type msg =

| Run

| Exit

| Pause

| Step

/// A worker automaton is a reactive automaton running on a dedicated thread of its

/// own.

type Worker() =

// Capture the synchronization context of the thread that creates this object. This

// allows us to send messages back to the GUI thread painlessly.

let callerCtxt =

match System.Threading.SynchronizationContext.Current with

| null -> null // System.ComponentModel.AsyncOperationManager.SynchronizationContext

| x -> x

//do if callerCtxt = null then failwith "Couldn't detect the synchronization context of the calling thread"

let runInGuiCtxt f =

match callerCtxt with

| null ->

// callerCtxt is null on Mono. This is a bug. System.Threading.SynchronizationContext.Current doesn't return a useful

// result. This is a little unfortunate. System.ComponentModel.AsyncOperationManager.SynchronizationContext returns

// an inconsistent result.

// So here we works around, where we finds the open form and sends to it.

if System.Windows.Forms.Application.OpenForms.Count > 0 then

System.Windows.Forms.Application.OpenForms.Item(0).BeginInvoke(new System.Windows.Forms.MethodInvoker(fun _ -> f())) |> ignore

| _ -> callerCtxt.Post((fun _ -> f()),null)

// This events are fired in the synchronization context of the GUI (i.e. the thread

// that created this object)

let fireUpdates,onUpdates = IEvent.create()

// Updates are generated very, very quickly. So we keep a queue, and every time we push

// into an empty queue we trigger an event in the GUI context that empties the queue and invokes

// the update event in the GUI context.

let updateQueue = new Queue<_>()

let enqueueUpdates(update) =

let first =

lock (updateQueue) (fun () ->

let first = (updateQueue.Count = 0)

updateQueue.Enqueue(update);

first)

if first then

runInGuiCtxt(fun _ ->

let updates =

lock (updateQueue) (fun () ->

[ while updateQueue.Count > 0 do

yield updateQueue.Dequeue() ])

fireUpdates(updates))

/// Compute one step of the game and call the

/// NotifyUpdates callback. That is, this function provides

/// glue between the core computation and the computation of that algorithm

let oneStep(env) =

let env = ANTLoopBehave env

let current = Seq.map (fun ant -> ant.xloc,ant.yloc) env.ants

let old = env.ants |> Seq.map (fun ant -> ant.oldloc) |> Seq.concat

let foodAnt =

env.territory.ToList()

|> Seq.of_list

|> Seq.map (fun (loc, node) -> loc, node.food)

|> Seq.filter (fun (_, food) -> food > 0)

//enqueueUpdates(old, current, foodAnt)

runInGuiCtxt(fun _ -> fireUpdates([ old, current, foodAnt]))

// clean out oldloc

let ants = Seq.map (fun ant -> {ant with oldloc = [] } ) env.ants

{ env with ants = ants }

// The control logic is written using the 'async' non-blocking style. We could also write this

// using a set of synchronous recursive functions, or using a synchronous workflow,

// but it's more fun to use the asynchronous version, partly because the MailboxProcessor type gives us a

// free message queue.

// Wherever you see 'return!' in the code below you should interpret

/// that as 'go to the specified state'.

let mailboxProcessor =

Mailboxes.MailboxProcessor.Create(fun inbox ->

/// This is the States of the worker's automata using a set of

/// tail-calling recursive functions.

let rec Running(s) =

async { let! msgOption = inbox.TryReceive(timeout=0)

match msgOption with

| None -> return! StepThen (SleepThen Running) s

| Some(msg) ->

match msg with

| Pause -> return! Paused s

| Step -> return! Running s

| Run -> return! Running s

| Exit -> return! Finish s }

and StepThen f s =

async { let s = oneStep(s)

return! f s }

and SleepThen f s =

async { // yield to give the GUI time to update

do! System.Threading.Timer.SleepAsync(20);

// Requeue in thread pool - strictly speaking we dont have to

// do this, but it ensures we reclaim stack on Mono and other

// platforms that do not take tailcalls on all architectures.

do! Async.SwitchToThreadPool()

return! f(s) }

and Paused(s) =

async { let! msg = inbox.Receive()

match msg with

| Pause -> return! Paused s

| Step -> return! StepThen Paused s

| Run -> return! Running s

| Exit -> return! Finish s }

and Finish(s) =

async { return () }

// Enter the initial state

Running (Env.initalize()))

/// Here is the public API to the worker

member w.RunAsync () = mailboxProcessor.Post(Run)

member w.StopAsync() = mailboxProcessor.Post(Pause)

member w.ExitAsync() = mailboxProcessor.Post(Exit)

member w.StepAsync() = mailboxProcessor.Post(Step)

member w.Updates = onUpdates

member w.Start() = mailboxProcessor.Start()

/// make and show the form

let main() =

let form = new Form(Visible=true,Text="Ant Colony",Width=800, Height=600)

form.Visible <- true

for x in [ 0 .. 1 ] do

for y in [ 0 .. 1 ] do

let bitmap = new Bitmap(territoryWidth, territoryHeight, System.Drawing.Imaging.PixelFormat.Format24bppRgb)

let pb = new PictureBox(SizeMode=PictureBoxSizeMode.Zoom)

pb.Size <- new Size(300, 300)

pb.Location <- new Point( x * 310, y * 310)

pb.Image <- bitmap

form.Controls.Add( pb )

let worker = new Worker()

worker.Updates.Add(fun updates ->

for (old, current, foodAnt) in updates do

old |> Seq.iter (fun (x,y) -> bitmap.SetPixel(x,y, Color.Black) )

current |> Seq.iter (fun (x,y) -> bitmap.SetPixel(x,y, Color.Red))

foodAnt |> Seq.iter (fun ((x,y), food) ->

let c = Color.FromArgb( food / maxFoodPerSquare * 255, Color.Green)

bitmap.SetPixel(x,y, c))

pb.Invalidate() )

worker.Start()

form.Activate()

Application.Run(form)

[<STAThread>]

do main()

Feedback:

Feedback was imported from my only blog engine, it's no longer possible to post feedback here.

re: Ants everywhere! An ant colony simulation in F# - Derek

I'm working on a simulation in F# and have been struggling to come to grips with immutability vs my old oop way of thinking.

I originally started out with mutable Lists and Dictionaries, but then stopped and tried to figure out how to do this with immutability in mind. I couldn't come up with anything I thought was reasonable, and arrived at a similar solution to what you've done here. A big global structure that gets recreated every time something changes.

But isn't this pretty inefficient, aren't we making a copy of the whole environment every time an ant moves or does something? Is there some optimization of using 'with' that reduces all the copying of everything that didn't change?

I'm still pretty new to F# and the functional way of thinking.

Email directly if you feel like it.

thanks, Derek

updated version - ray glover

Hi there! I'm learning F# too. I updated your simulation for F# 2.0, with some small additions. Keep on coding!

re: Ants everywhere! An ant colony simulation in F# - Robert Pickering

You can find the latest version here: https://github.com/Rickasaurus/F--Ant-Colony

Strangelights

Another tech blog.

Feedback: