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 },

            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

       | 0 -> North | 1 -> East | 2 -> South | 3 -> West | _ -> assert false

    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