Download source files - 115 Kb
The PathFinder application is a look into a number of different areas
which tend to run into each other; these are mostly the topics of
Memory, Artificial Life, Swarm Intelligence and Path Finding Algorithms,
which will be based on ideas in the literature in the bibliography below and
some of which I will make up on the spot. The main idea behind this program
not to prove any major scientific points but to in general have a look at
different areas and play around with them. It is meant to be a project that
can have fun with and develop occasionally. The program won't be developed
series of articles but as this single article being updated whenever I add a
algorithm or creature to the mix.
This being the case, the code will be in a state of perpetual flux and
probably never manage to be pretty or possibly even well written. A lot of
ideas thrown into the mix will be purely experimental and even by the first
release there is abandoned code lying around in places that contain ideas
would like to progress further but the current attempt(s) at implementing it
failed, miserably in some cases. This could be due to flaws in the ideas or
the implementation, so if you have a better implementation idea, feel free
add it on the message board at the bottom of the article and I'll take it
For the above reasons, I don't intend to put a lot of code in this
The code is freely available to anyone who wants to look at it, so cutting
pasting it into the article wont really serve much of a real purpose. The
article will deliberately maintain a higher level of discussion looking at
problems and rules of implementation using pseudo code where I feel
is necessary or proves a point.
The starting premise of the PathFinder program is writing the algorithms
get the creatures to move about on the given map. The idea is that each
algorithm used will be kept separate, identifiable and choose-able. This
serve two distinct purposes: one, it will show a kind of evolution of the
algorithms as they start out very basic and change over time with new ideas
altering the way they behave and then allowing a comparison between the
implementation and the new implementation to be run side by side, so that
differences in effect can be readily observed. One future planned aid to
will be a reporting system that will allow the user to stop the program and
generate a report of its current state. The second distinct purpose is that
later date, when certain modes are added, the different algorithms
be able to compete directly with each other to perform various tasks.
There isn't really a lot to say about the GUI at this moment in time. As
every aspect is due to be rewritten, it's pointless going into a lot of
here at the moment, so I'll briefly explain the available options and leave
at that for now.
The main page
The map that the ants move around is built up of separate squares that
defined routes or paths that the ants can move along. For this release, the
purple square represents the nest where the ants start out from and the
square represents the food source that they are, in theory, looking for.
The Critters options
These are the critters that you can have wandering around the map. At the
moment there is a choice between ants and the amoeba. You can choose only
critter at a time and once the start button is pressed the option is
For the initial release, there are two algorithms available. See below
discussion on the available algorithms. As with the critters, you can
choose one algorithm at a time and the option is disabled once the start
This timer controls the speed at which the update functions are called
therefore the speed at which the ants move.
Start and Stop buttons
These are pretty obvious although stop should probably be renamed pause
prevents the update timer from being called, effectively freezing the
until the Start button, which when the stop button is pressed is renamed the
Continue button, is pressed again.
General :- Number Of Ants
This is the number of ants that are currently running around on the map.
currently defaults to 5 and is adjustable while the program is running.
General :- Find Food
The option to find food or do something else will play a part later on,
the moment though all the ants do is, look for food.
General :- Try To Avoid Occupied Squares
This means that if a square is currently occupied, an ant will search for
alternative. This option has two interesting side effects, the first being
it appears to help the ants choose the directions to go in the first place
thus they might not find the food without it. The second effect, which is a
negative effect is that when an ant has found food and is returning home
(indicated by the green antennae), an ant searching for food will appear to
away from the ant with the food.
Behaviour :- Number Of Ants Affected
This is the number of ants affected by the check box option below. Note
at present this will be the first number of ants in the Critters array.
Behaviour :- Do Not Follow The Strongest Pheromone
This indicates to the ants that they should place no special emphasis on
pheromone levels of a square. Though it should be noted that once an ant has
discovered the food and returned home with it, the code will change this
as it attempts to find its way back to the food.
The Map Editor
PathFinder comes complete with a map editor that allows the user to
any of the five maps, provided this is so that the effectiveness of
can be tested against different types of maps and early on showed that some
the more basic algorithms weren't up to the task of dealing with the more
The way the map editing works is that you can enter the edit mode for the
by clicking on the "Enter Edit Mode" button or by using the menus. Once you
done this, you will be able to right click on any square in the map and a
context menu will give you the option of deleting that particular square.
though that the system is designed so that you can only edit one square at a
time as the system uses the surrounding squares to place the current square.
reason for this is because I didn't want the system to have a predefined
that later programs using the code can be of different sizes.
Once you have deleted a square, you can then right click on where the
used to be and a context menu will appear giving a selection of the
square types that can be placed at this point. In order to make life easier
blank map is provided which is just a collection of the standard square
(which means that the square has no paths and is just a background
When you are happy with the map you can save it with the "Save Current
option in the Save section of the menus. The default naming procedure
NameMap.xml although this is not enforced in any way.
Once you have finished editing a map, you must press the "Leave Edit
button or choose "Leave Edit Mode" from the edit menu.
It should be noted that the only restriction placed on the maps is that
should have one nest square. There is nothing to stop you adding more nest
squares but only the first one the code finds will be used.
The four maps are:
- DefaultMap which is the default map on loading and is pictured
- The TwoFoodsMap which is another simple map having two food
placed on it.
- The SnakesNLaddersMap resembles a snakes and ladders board and
- The OpenMap is comprised entirely of four way squares, meaning
the critters can move anywhere.
One of the problems I run across when writing programs that either
lots of data or run for long periods of time is the size of the log file.
problem when it came to this program is that you can generate enormous
of data most of which will tell you precisely nothing and could just contain
information about how the ant decided which square to move to next. The way
around this was to not only to be selective in the information that is
tracked in order to be written to the log but to work out a way in which the
file wasn't constantly being updated.
My solution to is to have an individual log for each object and a main
application log for the project. The size of the array is then limited or
the user of the program chooses. This is done through the logging panel in
application and allows the user to select the number of messages that each
object logs or to allow it to log all the messages that it receives.
The logs can then be written at any time by pressing the Log Data button
the main page. This will write out all the currently saved data to be
into the log. If a ant or object has no data to write then nothing about
ant will appear in the log. In order to allow multiple log files to be
during a single run each file for this program is named using the
DateTime.Now.Ticks value, with the log being written as a simple text
The common denominator in any of the literature of this type is Ant's,
such little creatures it's quite amazing how much gets written about what
get up to. Mostly they just go around breeding, eating, occasionally
and then dying which makes them the perfect starting point for this type of
program as they are about as simple as things can get when trying to look at
model of a living system. Well you could get simpler but then you start
with life forms that don't do what we as human beings would consider to be
basic requirements of life. That isn't to say that other life forms aren't
life forms, it's just that from a human perspective we prefer things that in
some ways have the same basic life requirements that we do.
Ants fulfil these requirements to a large extend by the fact that their
lives are based on a clearly defined social structure with each creature
a specific role to fill within the society. Although this role can change as
requirements of the society change the specific ant has a specific role at
Fear the amoeba.
The Basic Algorithms
There are a number of simple rules for the basic algorithm, these
- The ant must find the food and return it to the nest
- The ant has no detailed knowledge of its environment
- The ant can only remember where it previously came from. Up to four
- The ant's navigation is helped through the use of pheromones
How the Basic Algorithm works
The basic algorithms both follow the points given above with one major
difference between the two implementations. The first implementation which
the Basic Algorithm constantly updates the decision. That is at any point
through the process of deciding which way it is going to go, the ant has an
of which way it wants to go that may or may not end up as being the final
direction. The difference between this algorithm and the Basic 2 Algorithm
that the second algorithm uses the Fuzzy Decision class in the way that it
originally envisaged. This means that throughout the decision making
the algorithm increments or decrements its available options and decides
way to move on which available decision has the highest score once the end
the decision making process is reached.
Problems with the Basic Algorithms
The performance of the algorithm can fail suddenly with the ants becoming
stuck in certain locations, which tends to result in them shuffling
and forwards from one square to another. This occurs before the ants have
the food and even after they have found food. The reason for this is that
ant has very little knowledge about where it is going or even where it has
so its movements are mostly reactionary to its immediate surroundings. To
combat this, I've given the most basic ants a short term memory about where
have been. This means that they can remember the last four moves that they
and check to see if they are repeating the same moves over and over, at
point the code tries to force a different move. At this point though, the
is not based on any knowledge of direction or purpose.
Sequential reasoning has raised its head a couple of times in the
of the basic ant algorithm. The simplified code goes something like
if( APossibleDirection == "TOP" )
else if( APossibleDirection == "RIGHT" )
else if( APosibleDirection == "BOTTOM" )
Now picture this code from the ant's point of view. On most squares that
are moving from, you have at least two directions to move in. The problem
the above code is that if you can move either left or right, then in the
following code you are always going to move right; moving to the left will
even be considered and if you where to use straight
then the ant would always go left. It was this reasoning that inspired the
Decision class which at present is a simple mechanism for rating a decision
is based on the class having no knowledge of the decision that is being
One of the interesting things in coding the algorithms was changing the
of the sequential logic in the program and observing what effect it had on
way in which the ants moved around the map. There may be some options that
people to observe this for themselves at some point.
Over complicated maps
This is where Path Finding the basic algorithms break down due to the
that map structure is too complicated for it. Prime examples of this are the
basic algorithm in the SnakesNLadders map and that neither of the
algorithms have an easy time finding their way back to the base, once they
found the food.
The Pheromones Algorythm
The main change with this algorythm is
- A better implementation of the pheromone code so the ants will follow
The Pheromones Algorythm is based on the idea that the ants should follow
pheromones trails laid down by previous ants that have found the food and
the pheromone trail should point the way to the food or whatever the
trail is supposed to indicate. At this point only the food pheromone is
implemented and the ants can follow the trail back to the food.
Problems with the Pheromone Algorythm
On its own the Pheromone Algorythm isn't enough to get the ants working
properly. This is due to the fact that the Pheromone Algorythm is an
of the Basic 2 Algorythm and that it has all the same inherent problems.
are caused by the fact that once the ant has found the food there is no
improvement in it's ability to get home. This means that if an ant is trying
find it's way home and gets lost/confused then it can leave a pheromone
that leads away from the food instead of towards it.
The Memory Algorythm
The main change with this algorythm is,
- Ants now remember the path they took from the nest to the food
This is a simple modification to the basic algorythm in that the only
is that the ant remembers each step that it takes to get from the nest to
Problems with the Memory Algorythm
As with the pheromone algorythm the memory algorythm isn't enough to get
ants working properly on it's own. This is due to a couple of reasons the
being that if the ant takes the scenic route to the find the food then it is
going to take the scenic route back to the base as there is no optimisation
the way back but a reliance on blindly following each step backwards.
in this implementation the ant retains no memory of how to get back to the
so that once it does find it's way back to the nest with the food then it
over again searching for the food.
The Hill Climbing Algorythm
The main change with this algorythm is,
- The Ants now remember every square that they have crossed
The Hill Climbing algorythm is based on the idea that the ants follow a
to it's end and then return to the starting point and choose a different
This idea was too simplistic to implement as such and so the ants don't
religiously track back to where they started from but use the information a
more intelligently to explore different paths within the map.
Problems with the Hill Climbing Algorythm
Although the Hill Climbing algorythm functions better than some of the
algorythms at present this is due mainly to the fact that it explores the
map, so it's bound to get there eventually. Also the ants tend to hang
gangs there is no separation like there is with the other algorythms as it
doesn't implement the ant specific code such as trying to avoid squares that
other ants are occupying.
The Hill Climbing Algorythm Two
The Hill Climbing Two algorythm uses the standard Hill Climbing code from
previous algorythm but influences the decision with data provided by the
pheromone trails. Although this is only done during the search for the food
the algorythm uses the standard Hill Climbing code to try and find it's way
to the nest. It was this algorythm that inspired the Hill Climbing Three
algorythm that has a more natural result.
Problems with the Hill Climbing Two Algorythm
Despite it's relative simplicity this algorythm is surprisingly
although it does tend to have cases of wandering, where the ants just decide
that they want to go off an see what is in some other direction.
The Hill Climbing Algorythm Three
The main changes for the third Hill Climbing algorythm are that the ants
use the pheromone trails to find the food effectively and the code now
the pheromone values and not just if the square has a pheromone signature.
is done so that the ants will follow the most popular trail to the food and
use the memory algorythm to find their way back to the nest. This has the
that the ants now follow a more natural pattern in that once a popular trail
and from the food is established the ants will religiously follow it. The
that they follow will not necessarily be the fastest path too or from the
but the most popular.
This was done by rewriting the Hill Climbing algorythm and placing the
emphasis on moving forwards, away from any squares that have been previously
visited at any point by a specific ant rather than on the idea of was only
visited on the previous move.
Problems with the Hill Climbing Algorythm Three
At present there aren't any real problems that can be associated with the
algorythm itself at this stage. Although things have turned up such as the
not resetting the pheromone counts properly and confusing the ants but this
an implementation problem of mine and nothing to do with the actual
With the implementation of the Hill Climbing Three algorythm the question
how intelligent ants actually are in the real world is starting to come into
play any will of course require more research. One of the reasons for this
that I am currently using a simple memory system in which the ants find
way back to the nest by remembering exactly where they have been, yet from
admittedly limited reading on the subject ants in the real world are able to
take short cuts back to the nest once they have decided to return
The main question here will be one of implementation as I will need to do
this in a way that does not involve having an overview of the map other than
what the ant in question has seen.
Things to fix
Implement better algorithm management.
Things to implement
Implement new board control
- Tom Archer ( 2001 ) Inside C#, Microsoft Press
- Jeffery Richter ( 2002 ) Applied Microsoft .NET Framework Programming,
- Charles Peltzold ( 2002 ) Programming Microsoft Windows With C#,
- Robinson et al ( 2001 ) Professional C#, Wrox
- Bart Kosko ( 1994 ) Fuzzy Thinking, Flamingo
- Buckley & Eslami ( 2002 ) An Introduction To Fuzzy Logic And Fuzzy
- Earl Cox ( 1999 ) The Fuzzy Systems Handbook, AP Professional
- Steven Johnson ( 2001 ) Emergence, The Penguin Press
- John H. Holland ( 1998 ) Emergence From Chaos To Order, Oxford
- Mark Ward ( 1999 ) Virtual Organisms, Pan
- Bonabeau, Dorigo, Theraulaz ( 1999 ) Swarm Intelligence From Natural
Artificial Systems, Oxford University Press
- 21 September 2003 - Initial release with Ants, Amoeba and two basic
- 30 October 2003 - Added Map Editor and four maps
- 17 December 2003 - Added the Pheromones, Memory and Hill Climbing
- 29 April 2004 - Added Logging and Two more Hill Climbing