This tutorial will walk you through creating a number of flies that will fallow a scent trail, that you draw on the screen using the mouse. It will be designed to show how easy it is to code AI to achieve simple path finding / fallowing "fly like" behavior. The full source code can be downloaded here FartSniffer.zip (23.81 kb)

What you will need

For this tutorial we will be using vb.net 2005 and the .NET framework 2.0. But if you do not have Visual Studio 2005 you can download it for free on Microsoft's website. This tutorial assumes that you are familiar with the visual studio IDE, as well as the graphics objects under the System.Drawing namespace.

Getting started

To begin you must first create a new windows application, under visual studio. Second you will need to add a new code file and insert the fallowing code into it.

 Public Module General
    Public Function RestrictValue(ByVal V As Single, ByVal Min As Single, ByVal Max As Single) As Single
        If V < Min Then V = Min
        If V > Max Then V = Max 

        Return V
    End Function 

    Public Function RestrictValue(ByVal V As Integer, ByVal Min As Integer, ByVal Max As Integer) As Integer
        If V < Min Then V = Min
        If V > Max Then V = Max
        Return V
    End Function

    Public Sub Displacement(ByVal X As Single, ByVal Y As Single, ByVal Distance As Single, ByVal AngleInRadians As Single, _
                                  ByRef NewX As Single, ByRef NewY As Single)
        NewX = CSng(X   (System.Math.Cos(AngleInRadians) * Distance))
        NewY = CSng(Y   (System.Math.Sin(AngleInRadians) * Distance))
    End Sub

    Public Function CircleCircle(ByVal Center1X As Single, ByVal Center1Y As Single, ByVal R1 As Single, _
                                ByVal Center2X As Single, ByVal Center2Y As Single, ByVal R2 As Single, _
                                Optional ByRef Distance As Single = 0) As Boolean
         Distance = CSng(Math.Sqrt((Math.Abs(Center1X - Center2X) ^ 2)   (Math.Abs(Center1Y - Center2Y) ^ 2)))
        Return Distance <= R1   R2
    End Function
End Module

The code provided above will be used by the application and provides simple helper functions. This code will not be covered in this tutorial as it is not relevant to the overall goal of this tutorial.

Part 1 - Base Types

First we will need to declare some class types to store the information we will need like Flies, Fly receptacles, and a Scent object.

Because the flies and the player we see on screen could be considered actors that share similar qualities we will declare an Actor class and then create a Fly class that inherits from the Actor class. We will not create a player class because the player will not possess any unique qualities other then what is already provided by the actor class.

Public Class Actor 
    Public Position As Point 
    Public Direction As Single = 0 
    Public Speed As Single = 1 
    Public Size As Single = 6 
End Class

Public Class Fly
    Inherits Actor
    Public Receptors As New Generic.List(Of Receptor)
    Private mlngLastDirectionChange As Long

    Public Sub Update()
        If Now.Ticks > Me.mlngLastDirectionChange   (TimeSpan.TicksPerSecond \ 2) Then
            Randomize(Now.Ticks)
            Me.Direction = CSng(Rnd() * (Math.PI * 2))
            Me.mlngLastDirectionChange = Now.Ticks
        End If
    End Sub

    Public Sub New(ByVal Position As Point)
        Me.Position = Position
        Me.Speed = 6
        mlngLastDirectionChange = CLng(Rnd() * TimeSpan.TicksPerSecond)
    End Sub

    Public Sub New(ByVal Position As Point, ByVal R As Generic.List(Of Receptor))
        Me.New(Position)
        Me.Receptors = R
    End Sub
End Class

You will notice that the Fly class contains a generic collection of Receptor objects. Receptors are like little antenna that we will use for detecting any scent that the Receptor may come in contact with. The flies we will be using for this tutorial will only be using 2 receptors.

Public Class Receptor 
    Public Distance As Single = 25 
    Public Direction As Single = 0 
    Public Size As Single = 2 

    Public Sub New(ByVal Distance As Single, ByVal Degree As Single, ByVal Size As Single) 
        Me.Distance = Distance
        Me.Direction = Degree 
        Me.Size = Size 
    End Sub 
End Class

Next we will define a Scent class that will represent a scent in our application. The scent class contains properties like Strength witch we will use to determine how large we should draw the scent on screen. It also contains two other properties DecayRate and DecaySpeed. DecayRate specifies how much the scent strength will be reduced. And DecaySpeed will be used to determine how fast to apply the DecayRate. The scent class also contains a field called Owner. Owner is not required in this tutorial, but it will be set to reference the player varible we will define later.

Public Class Scent
    Public Strength As Single = 25
    Public DecayRate As Single = 8
    Public DecaySpeed As Single = 1
    Public Position As Point
    Public Owner As Actor

    Public Sub New(ByVal Owner As Actor)
        Me.Owner = Owner
        Me.position = Me.Owner.Position
    End Sub

    Public Sub Decay()
        Static LastDecayTime As Long
        Dim TheTime As Long = Now.Ticks

        If TheTime > LastDecayTime   (TimeSpan.TicksPerSecond \ CLng(DecaySpeed)) Then
            Me.Strength = RestrictValue(Me.Strength - Me.DecayRate, 0, Single.MaxValue)
            LastDecayTime = TheTime
        End If
    End Sub    
End Class

Part 2 - Declaring Variables

Now that we have all of our classes defined we can proceed to declare some variables. Open up the Code View for Form1 and copy and paste the fallowing code.

Private Const NumberOfFlies As Integer = 25
Private Const SpawnStinkyInterval As Integer = 1000 \ 30 ' 1000 ms div 30 fps
Private Const UpdateFliesInterval As Integer = 1000 \ 60 ' 1000 ms div 60 fps
Private mobjPlayer As Actor
Private mobjFlies As Generic.List(Of Fly)
Private mobjScents As Generic.List(Of Scent)
Private WithEvents mobjTimer As Timers.Timer
Private WithEvents mobjFlyUpdater As Timers.Timer
Private WithEvents mobjStinkySpawner As Timers.Timer
Private mobjGraphics As BufferedGraphics

The first 3 constants are as fallows..

1. NumberOfFlies - Specifies how many flies our app will use.
2. SpawnStinkyInterval - Specifies how many times per second the app will update the scent objectss in the scene. The scent objects will be updated 30 times per second.
3. UpdateFliesInterval - Specifies how many timer per second the app will update the flies in the scene. Flies will be updated 60 times per second.

After the constants is the player object, which is just defined as an actor. The next two variables are collections to store the flies and scent objects.

The next three variables after that are timers that will be used to update the flies and scent objects as well as draw them on screen at specified intervals.

The last variable is a BufferedGraphics object that is new in .NET 2.0 and we will use it to draw our graphics on screen. The BufferedGraphics object will help prevent any flickering on the screen when we draw our flies and scent objects.

Part 3 - Draw Methods

In order to see what out flies and scents are doing we will need to draw them. Copy and paste the fallowing code into Form1

    Public Sub DrawFlies()
        For Each F As Fly In mobjFlies
            DrawActor(F)
        Next
    End Sub

    Public Sub DrawReceptors()
        For Each F As Fly In mobjFlies
            For Each R As Receptor In F.Receptors
                Dim NX, NY As Single
                Displacement(F.Position.X, F.Position.Y, R.Distance, R.Direction   F.Direction, NX, NY)
 
                Dim Half As Single
                Half = R.Size / 2.0F
                mobjGraphics.Graphics.DrawLine(Pens.Yellow, F.Position.X, F.Position.Y, NX, NY)
                mobjGraphics.Graphics.DrawEllipse(Pens.Yellow, NX - Half, NY - Half, R.Size, R.Size)
            Next
        Next
    End Sub

    Public Sub DrawScents()
        For Each s As Scent In mobjScents
            Dim Half As Single
            Half = s.Strength / 2.0F
            mobjGraphics.Graphics.DrawEllipse(Pens.Green, s.Position.X - Half, s.Position.Y - Half, s.Strength, s.Strength)
        Next
    End Sub

    Public Sub DrawActor(ByVal A As Actor)
        Dim Half As Single
        Half = A.Size / 2.0F
        mobjGraphics.Graphics.DrawEllipse(Pens.Red, A.Position.X - Half, A.Position.Y - Half, A.Size, A.Size)
    End Sub

The methods for drawing our flies and scents are pretty straight forward, and should be easy enough to understand by looking at the code.

Part 4 - Form Events

Next we will need to handle some form events. When the user clicks the mouse on the form or presses a key it will cause the application to quit so copy and paste the fallowing code into Form1

    Private Sub Form_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Click
        Me.Close()
    End Sub

    Private Sub Form_KeyDown(ByVal sender As Object, ByVal e As System.Windows.Forms.KeyEventArgs) Handles Me.KeyDown
        Me.Close()
    End Sub

We will want the ability to drag a scent trail on the scene by using the mouse. To do this, set the player position to the position of the mouse as it moves across the form. Copy and paste the code below into Form1

    Private Sub Form_MouseMove(ByVal sender As Object, ByVal e As MouseEventArgs) Handles Me.MouseMove
        mobjPlayer.Position = New Point(e.X, e.Y)
    End Sub

Next we will need to perform a check to see if the form is closing so we can dispose of the variables we have declared. We do this using the FormClosing event. If the form is not being canceled we can clean up our variables by calling the DoCleanUp method. Copy and paste the code below into Form1

    Private Sub Form1_FormClosing(ByVal sender As Object, _
                    ByVal e As System.Windows.Forms.FormClosingEventArgs) Handles Me.FormClosing
        If Not e.Cancel Then Me.DoCleanUp()
    End Sub

    Private Sub DoCleanUp()
        mobjTimer.Stop()
        mobjTimer = Nothing
        mobjStinkySpawner.Stop()
        mobjStinkySpawner = Nothing
        mobjFlyUpdater.Stop()
        mobjFlyUpdater = Nothing
        mobjScents.Clear()
        mobjScents = Nothing
        mobjPlayer = Nothing
        mobjFlies.Clear()
        mobjFlies = Nothing
        mobjGraphics.Dispose()
        mobjGraphics = Nothing
    End Sub

Finally we can add code to the forms Load event. Copy and paste the code below into Form1.

    Private Sub Form1_Load(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Load
        ' Resize form so that client size is 512x512
        Me.Size = New Size(512, 512)   (Me.Size - Me.ClientSize)
 
        ' create player object
        mobjPlayer = New Actor
        mobjPlayer.Position = New Point(Me.ClientSize.Width \ 2, Me.ClientSize.Height \ 2)
        mobjPlayer.Size = 10
 
        ' create flies and scent collections
        mobjFlies = New Generic.List(Of Fly)
        mobjScents = New Generic.List(Of Scent)
 
        ' add flies and receptors (Changing receptor values of one fly will change receptor of all flies)
        Dim R As New Generic.List(Of Receptor)
        R.Add(New Receptor(10, -(Math.PI / 4), 5))
        R.Add(New Receptor(10, Math.PI / 4, 5))
        Randomize(Now.Ticks)
        For idx As Integer = 0 To NumberOfFlies - 1
            Dim F As Fly
            F = New Fly(New Point(CInt(Rnd() * Me.ClientSize.Width), CInt(Rnd() * Me.ClientSize.Height)), R)
            F.Direction = CSng(Rnd() * (Math.PI * 2))
            mobjFlies.Add(F)
        Next
 
        ' Create graphics 
        Me.SetStyle(ControlStyles.AllPaintingInWmPaint Or ControlStyles.UserPaint, True)
        Drawing.BufferedGraphicsManager.Current.MaximumBuffer = New Size(1, 1)   Me.ClientSize
        mobjGraphics = Drawing.BufferedGraphicsManager.Current.Allocate(Me.CreateGraphics, Me.ClientRectangle)
 
        ' setup timers
        mobjTimer = New Timers.Timer
        mobjTimer.Interval = 1
        mobjTimer.AutoReset = False
        mobjTimer.Start()
 
        mobjStinkySpawner = New Timers.Timer
        mobjStinkySpawner.Interval = SpawnStinkyInterval
        mobjStinkySpawner.AutoReset = False
        mobjStinkySpawner.Start()
 
        mobjFlyUpdater = New Timers.Timer
        mobjFlyUpdater.Interval = UpdateFliesInterval
        mobjFlyUpdater.AutoReset = False
        mobjFlyUpdater.Start()
    End Sub 

The first thing we do is resize the form so the it's client area is 512 wide by 512 high. Second we create the player and position it in the center of the form, as well as set it's size to 10. The next thing is to create the flies and scent collections.

Next we create our flies. But before we do that we create a new collection that will contain the flies Receptor's. The Receptor collection will have two receptors added to it. The first receptor will be a distance of 10 from the position of the fly, and facing -45 degrees from the direction the fly is facing. We also specify that the receptor has a size value of 5. The second receptor is the same as the first except that it will be 45 Degrees to the right from the direction the fly is facing. Keep in mind that every fly in the scene will be referencing these same 2 receptors that were declared. Each fly does not hold it's own unique collection of receptors.

Now that we have a collection of receptors we can begin creating the flies. Each new fly we create will be randomly placed on the form and given a random starting direction.

After the flies have been created we specify that we want to control the painting on the form by calling the SetStyle method. Second we need to specify the maximum size of the buffer we will be drawing to. And third we allocate a new BufferedGraphics object by calling the allocate method and passing in a new graphics object that was created by the form, as well as the area on the form we will be drawing to.

The next thing to do is create the timer objects. Each timer has been setup to begin running, and after the interval of time has elapsed will raise it's Elapsed event once.

Part 5 - Timer events

Copy and paste the fallowing code into Form1.

    Private Sub mobjTimer_Elapsed(ByVal sender As Object, _
            ByVal e As System.Timers.ElapsedEventArgs) Handles mobjTimer.Elapsed
        If mobjGraphics Is Nothing Then Exit Sub
 
        Try
            mobjGraphics.Graphics.Clear(Color.Black)
 
            DrawFlies()
            DrawReceptors()
            DrawScents()
            DrawActor(mobjPlayer)
 
            KeepInBounds()
            DecayFarts()
 
            mobjGraphics.Graphics.DrawString("Click or press a key to exit...", _
                    Me.Font, Brushes.White, 50, 50)
            mobjGraphics.Render()
      
            mobjTimer.Start()
        Catch
        End Try
    End Sub 

The first thing we do is to check if the graphics variable has been set to nothing. If it has we can exit. We do this check because the timer objects we are using are running in the background and even if we were to close the form and set all variables to nothing the next Elapsed event will still be raised.

Next we call the Clear method on the graphics variable to clear the scene of what was drawn previously. Then it proceeds to draw the flies, receptors, player, and scent objects onto the buffered graphics variable we setup earlier.

The next two methods being called are KeepInBounds and DecayFarts. These methods will be covered later in the tutorial.

Next we draw a message on the screen for the user and then render out what we have drawn on out to the form.

The timer that is used to draw the graphics on screen has been setup to raise the Elapsed event only once. So we must call mobjTimer.Start again to receive another Elapsed event.

Copy and paste the fallowing code into Form1

    Private Sub mobjStinkySpawner_Elapsed(ByVal sender As Object, _
                         ByVal e As System.Timers.ElapsedEventArgs) Handles mobjStinkySpawner.Elapsed
        If mobjGraphics Is Nothing Then Exit Sub
 
        Try
            MakeStinky()
            mobjStinkySpawner.Start()
        Catch
        End Try
    End Sub
 
    Private Sub mobjFlyUpdater_Elapsed(ByVal sender As Object, _
                        ByVal e As System.Timers.ElapsedEventArgs) Handles mobjFlyUpdater.Elapsed
        If mobjGraphics Is Nothing Then Exit Sub
 
        Try
            MoveFlies()
            mobjFlyUpdater.Start()
        Catch
        End Try
    End Sub

The fly updater and stinky spawner timers are simply setup to call the MoveFiles and MakeStinky methods. After that they call there Start methods so that there Elapsed events will fire again.

Part 6 - Keeping things in view

Copy and paste the fallowing code into Form1

    Private Sub KeepInBounds()
        ' keep the player within the visible area of the form
        mobjPlayer.Position.X = RestrictValue(mobjPlayer.Position.X, 0, Me.ClientSize.Width - 1)
        mobjPlayer.Position.Y = RestrictValue(mobjPlayer.Position.Y, 0, Me.ClientSize.Height - 1)
 
        ' keep all flies within the visible area of the form
        For Each F As Fly In mobjFlies
            F.Position.X = RestrictValue(F.Position.X, 0, Me.ClientSize.Width - 1)
            F.Position.Y = RestrictValue(F.Position.Y, 0, Me.ClientSize.Height - 1)
        Next
    End Sub

The KeepInBounds method checks to see if the player is within the bounds of the forms client area and if not prevents it from moving outside that area. It then perform the same checking for each fly in the flies collection.

Part 7 - Fart Decay

Copy and paste the fallowing code into Form1

    Public Sub DecayFarts()
        Dim idx As Integer
        While idx <= mobjScents.Count - 1
            mobjScents(idx).Decay()
            If mobjScents(idx).Strength <= 0 Then
                mobjScents.RemoveAt(idx)
            Else
                idx  = 1
            End If
        End While
    End Sub

The DecayFarts method process each scent in the scene and call's it's Decay method. It then checks to see if the strength of the scent is less or equal to zero if it is then it removes it from the collection, otherwise it moves on to check the next scent in the collection.

The Decay method check to see if it is time for the scent to decay and if so reduces the scent strength by the DecayRate.

Part 8 - Methane production

Copy and paste the code below into Form1

    Private Sub MakeStinky()
        mobjScents.Add(New Scent(mobjPlayer))
    End Sub

The only thing the MakeStinky method does is add a new scent to the scents collection. Because the Stinky Spawner timer will raise it's event 30 times per second, 30 scent object will be created every second that passes. Scent objects that are created here are being removed by the DecayFarts method discussed earlier.

Part 9 - Incoming!

Finally after all that setup we can begin to code some AI. Copy and paste the code below into Form1

    Private Sub MoveFlies()
        Randomize(Now.Ticks)
        For Each F As Fly In mobjFlies
            Dim NX, NY As Single
 
            Displacement(F.Position.X, F.Position.Y, F.Speed, F.Direction, NX, NY)
            If NX > Me.ClientSize.Width - 1 Then F.Direction  = CSng(Rnd() * Math.PI)
            If NX < 0 Then F.Direction  = CSng(Rnd() * Math.PI)
            If NY > Me.ClientSize.Height - 1 Then F.Direction  = CSng(Rnd() * Math.PI)
            If NY < 0 Then F.Direction  = CSng(Rnd() * Math.PI)
 
            F.Position.X = CInt(NX)
            F.Position.Y = CInt(NY)
            Dim FoundScent As Boolean = False
            For Each R As Receptor In F.Receptors
                Displacement(F.Position.X, F.Position.Y, R.Distance, R.Direction   F.Direction, NX, NY)
                For Each S As Scent In mobjScents
                    If CircleCircle(S.Position.X, S.Position.Y, S.Strength, NX, NY, R.Distance) Then
                        F.Direction  = R.Direction 
                        ' Try using this line instead
                        'F.Direction  = ((R.Direction * 0.9F)   (Rnd() * (R.Direction * 0.2F)))
                        FoundScent = True
                        Exit For
                    End If
                Next
           Next
            If Not FoundScent Then F.Update()
        Next
    End Sub

The MoveFlies method is at the heart of this application. First it re-seeds the random number generator, and then begins to process each of the flies in the flies collection.

The NX and NY variables are used to store the next location that the fly will be moving to. A call to the Displacement method is made and stores the new fly position in the NX and NY variables. If the new position is outside of the bounds of the form then a new random direction is given to the fly so that it does not try to constantly escape from view.

The FoundScent variable will store weather or not a scent was detected by a receptor. It then proceeds to process each receptor. To determine the location of the receptor on screen a call is made to the Displacement method again. Now that the location of the receptor is known it begins to check each scent in an effort to determine if the receptor collides with it. To determine if a collision takes place a call to the CircleCircle method is made.

The next line of code is how the fly knows what direction to move to, and how it is able to fallow a trail of scent objects.

    F.Direction  = R.Direction

It takes the direction the fly is currently facing and adds the direction that the receptor is facing. Because the direction of the receptors are relative the fly will then be facing in the general direction of the scent.

Now that a scent has been detected we can set the FountScent variable to true and exit the scent checking loop.

After all receptors have been processed it checks if a scent was found and if so calls the flies update method. The Fly.Update method checks to see if the fly has changed direction within the last half second, and if so changes the flies direction to a new random direction.

Conclusion

You should now be able to run the application! Admittedly the name Fart Sniffer is meant to be somewhat amusing. But the technique used could be used for other kinds of AI path finding or fallowing such as a game where a scent trail is left behind by the player and a pack of wolves or demons use it to track down the players location.

As you can see from running the app the flies are not perfect, they sometimes travel backwards away from a stronger scent to a weaker scent, but with some minor tweaks you could direct the flies to always fallow a more stronger scent. One thing that could be done is to use the alternative way of setting the flies direction provided in the code in step 9.

    ' Try using this line instead
    ' F.Direction  = ((R.Direction * 0.9F)   (Rnd() * (R.Direction * 0.2F)))

What this code will do is instead of simply adding the direction of the receptor to the fly's direction it takes 90 percent of the receptors direction and adds a random of 0 to 20 percent of the receptors direction. For example if the fly was facing 0 degrees and the receptors direction is 45 degrees then the new fly direction would be set to anywhere from 40 degrees to 50 degrees. This would allow a little more detail to the fly's behavior instead of always making 45 degree turns all the time.

I hope you have found this tutorial to be useful. The full source code can be downloaded from the Created by X website here FartSniffer.zip (23.81 kb)