A Study on Artificial Intelligence

During the first Semester, the students on our course are given a simple graphic framework that displays a single ant on a little sand plane. They are then given the task of gradually adding functions to the program and intelligence to the ants. This way they get results quickly and are able to develop additional features into the program if they feel up to it. At the end of the Semester we were allowed to work in teams on a final version of the simulation. The best Version would be honoured with a certificate and a price of one cent :). I worked together with Clas Rurik, and we achieved first place. Click the pictures to enlarge.

So this little toy showcases our first project at university. It is not really interactive. After starting it just sit back, zoom around the screen and watch the ants do their work. The focus of the work was to develop an artificial intelligence for the little buggers. The original framework was developed by Simone Huber and Michael Schoell, This framework has been heavily expanded by Keno März and Clas Rurik and will be used for further educational purposes in future courses. I will elaborate on some of the algorithms used here, but do not expect fancy stuff. This is simple code programmed by first-semester students.

Download & Manual

 To start the simulation do either one of the following:

• Start the software directly using Java Webstart. Follow this link. Requires Java Webstart to be installed.
• Download the jar file and execute it locally. Follow this link. Requires Java to be installed.

Features

Here is a little list of what the simulation can do (Only lists the most important features implemented by Clas and I):

• Arbitrary playfield size
• Scrollable and zoomable playfield featuring a Minimap 
• Bucket System to manage ants and bugs.
• Simple Ant Intelligence
• Simple Eco System
• Ants imigrating into the playfield if other folks die out
• Bugs hunting the ants
• Ants hunting bugs and prey
• Name Generator. We like it close and personal.
• Struggle between capitalistic and communistic ants on the default map. We like it nonsensical.

Bucketing: Managing many entities on a 2d playfield.

One problem we encountered was to manage the abundance of ants on the playfield. The ants as well as the bugs check for nearby entities depending on their radius of sight. Obviously it would be very unefficient to check each versus each ant for sight-contact if the sight radius is just a fraction of he actual playfield. See the flash graphic below for details.

A naive implementation would be to simply place all ants in a List.  The Beetle (B) can see 4 ants (A) but has to iterate over the whole list, i.e. check for all ants on the playfield. For the Ants the situation is even more drastic: Each ant has to check every other ant for sight contact. This is equivalent to a complexity of n² and obviously suboptimal. So how could we improve this process? As mentioned before, the typical radii of sight are significantly smaller than the actual size of the playfield. The requirements to the algorithm are as follows:

• It should decrease the number of sight-checks to a number close to the actual ants in sight.
• The Ants move quickly. The underlying data structure should not require extensive restructuring due to ants moving.

An easily implementable solution for this problem is the so called bucketing. First, we divide the playfield into equally sized squares - our buckets - and put each ant into the bucket corresponding to the square it stands on.

B now first calculates the coordinates of the buckets that are touched or covered by field of vision. Then, he checks all ants in those buckets for sight contact. It is obvious that this method is more effective than the naive implementation. The actual reduction in complexity depends on the bucket size as well as the size of the playfield and the distribution of the ants.
Additionally, the simulation now has to keep track of ants changing buckets by walking. This operation is not terribly costly and can be furtherly reduced by making the calcuation fuzzy, for example recalculating the buckets only every fifth step. The parameters can also be tweaked according to the simulations needs. We made good results with choosing a bucket size equaling the ants' radius of sight.