Pre-game warm-up (Updated to include "Is this code I see before me?")

I have some bad news and I have some good news. Before I am hunted down by a ravenous horde of arts students, please note that:

1. I apologise for the cliché. 
2. I apologise for the cliché of starting a post with a cliché.
3. I apologise for the cliché of apologising for using a cliché. 

Now that I have finished cliché-ing my clichéd cliché's, let's move on to the news.

The bad news is that I have no pretty pictures (note the alliteration, I really am trying arts students) for you today as my computer has overheated. Or in other words my laptop has decided that what it would really really like to do instead of running my program is to raise the mean temperature of the local area by a couple degrees then take a half hour siesta. And by local area I mean Scotland. The good news is that I have written the program that should have produced said pictures, and I will be updating this post tomorrow assuming that the heat has dissipated sufficiently. I suggest you read "dissipated sufficiently" as melted the polar ice caps.

If you can read between the lines or italics, I have been a little antagonized by my laptop this evening. I think part of my problem is also that my code is extremely inefficient, mostly down to the constraints of using excel cells, something which I am going to need to deal with as this project progresses.

Here is a brief summary of the code my computer tried and failed to run:

Multiple ants are contained within a nxn square which has a boundary which the ants bounce off of. When one ant lands on another, the second ant "kills" the first. The game runs until only one ant is left alive.

It looks simple enough, but it quickly becomes clear that this is a game that will last a LONG time. Imagine you have only two ants on a 10x10 board. Suppose the ants are randomly placed each turn (uniformly for the probability nerds), then the probability of one ant killing the other on any one turn is 1/100. It is fair to say  that the odds are actually worse than this, as the position of the ant at every turn is determined once the ant is placed on the grid and these positions are likely to be fairly far away from the other ant on most turns. But suppose it is 1/100. Then if we scale to a 100x100 board (tiny on spreadsheet sizes) the odds are 1/10000. If we then introduce another ant being randomly distributed around the board the odds go up to 1/3333. Now suppose we use the entire spreadsheet and all 54 ants. Then we have odds of 1/6002750 that an ant will be killed on any one turn. And that is just the first ant. All in, the odds of there being a winner is approximately 1/10^426. For a sense of scale, excel returns that number as zero. 10^426 is 25 orders of magnitude larger than the age of the universe in seconds, or 5 orders of magnitude larger than the number of protons in the observable universe.

I have been extremely vague in my probabilities, but I think you get the picture. This game was an interesting diversion, but I will need to adapt it to actually make it completable. So far my best idea to correct this has been some form of area kills. However I am going to put this on hold for a new game. Ladies and gentleman I am going to issue myself with a challenge; to design and create a football game involving Langton's Ant by the full time whistle of the Euro 2012 Final.

781,

mathmo

Update:

I managed to run my code tonight, and it turns out that it wasn't so much my laptop overheating as that I had inadvertently included an infinite loop. "Sorry laptop, I will take you out for a byte to eat to make up for it."

The Game

I had to alter the game quite a lot to make it finish-able, but even then I had to limit it to running each ant 100,000 times then declare all surviving ants as winners. I have also managed to solve my previous issue of limited space by making the black border transport ants to the order side of the board. This can be most easily seen in the Cyan ant, where its expansion is divided by the border but is still continuous. You can also see that the Cyan ant has eliminated the Light Green ant fairly quickly. Other highlights include the epic battle between Maroon and Pink, and the swashbuckling adventures of Dark Blue, who seemed to be duelling 6 opposing ants at once. Pink wins the award for being the only ant to reach all four sides.

I think I can do more with this game, such as making it team battles and giving each ant lives and a special ability (for example extra speed or area attack), but I am putting it aside for now to focus on my challenge.

Interesting factoid: One of the errors that cropped up during coding was that I had forgotten to move the 'corpses' of the dead ants off the board. This resulted in ants claiming multiple kills for in essence what was them jumping up and down on a dead body. Who said programming wasn't gory?

The Execution (preferably of my code not of me)

Since the main audience for this will be people interested in programming, I think it is about time that I uploaded my code!


Sub antmenu()
'This is the code for the menu. It loops until a valid command is entered, in which case it runs that program then returns to the menu.
Dim mode, menucounter As String


menucounter = 0


Do While menucounter = 0


    mode = InputBox("Which program would you like to run?")


    Select Case mode
        Case Is = "demo"
            demo
        Case Is = "advanced"
            advanced
        Case Is = "clear"
            clear
        Case Is = "exit"
            menucounter = 1
        Case Else
            MsgBox ("Invalid option")
    End Select
Loop


End Sub


Sub demo()


Dim xa, xb, ya, yb, directiona, directionb, coloura, colourb, turn, offsetx, offsety As Long


xa = 8192
ya = 524288
turn = 1
offsetx = 100
offsety = 100
directiona = 4
directionb = 2
xb = xa + offsetx
yb = ya + offsety


Do Until turn = 50000
    
    coloura = Cells(ya, xa).Interior.ColorIndex
    If coloura = -4142 Then
        directiona = directiona + 1
        Cells(ya, xa).Interior.ColorIndex = 3
    ElseIf coloura = 1 Or 29 Or 5 Or 3 Or 12 Then
        directiona = directiona - 1
        Cells(ya, xa).Interior.ColorIndex = -4142
    End If
    
    If directiona = 0 Then directiona = 4
    If directiona = 5 Then directiona = 1
    
    Select Case directiona
        Case Is = 1
            ya = ya - 1
        Case Is = 2
            xa = xa + 1
        Case Is = 3
            ya = ya + 1
        Case Is = 4
            xa = xa - 1
    End Select


    colourb = Cells(yb, xb).Interior.ColorIndex
    If colourb = -4142 Then
        directionb = directionb + 1
        Cells(yb, xb).Interior.ColorIndex = 12
    ElseIf colourb = 1 Or 29 Or 5 Or 3 Or 12 Then
        directionb = directionb - 1
        Cells(yb, xb).Interior.ColorIndex = -4142
    End If
    
    If directionb = 0 Then directionb = 4
    If directionb = 5 Then directionb = 1
    
    Select Case directionb
        Case Is = 1
            yb = yb - 1
        Case Is = 2
            xb = xb + 1
        Case Is = 3
            yb = yb + 1
        Case Is = 4
            xb = xb - 1
    End Select


    turn = turn + 1


Loop


End Sub


Sub clear()
Range("A1:XFD1048576").Interior.ColorIndex = -4142
Range("A1:XFD1048576") = ""
End Sub




Sub advanced()


'Asks the user the number of ants they want.
Dim n As Integer
n = 55
Do Until n < 55
    n = InputBox("How many ants would you like?")
    n = n - 1
Loop


'Creates the arrays, x and y are the coordinates and currentcolour the colour of the cell the ant is in. Colour is the colour and direction is the direction of the ant, and turn is fairly obvious.
Dim x() As Long, y() As Long, direction() As Long, currentcolour() As Long, colour() As Long, turn As Long
ReDim x(0 To n) As Long
ReDim y(0 To n) As Long
ReDim direction(0 To n) As Long
ReDim currentcolour(0 To n) As Long
ReDim colour(0 To n) As Long


'Sets up the intial positions of the ants, randomly placing them around a 200 cell square.
x(0) = 8192
y(0) = 524288
direction(0) = 1
colour(0) = 3
turn = 1
Dim counterinitialpositions As Integer
counterinitialpositions = 1
Do Until counterinitialpositions = n + 1
    x(counterinitialpositions) = x(0) + Int((201) * Rnd - 100)
    y(counterinitialpositions) = y(0) + Int((201) * Rnd - 100)
    direction(counterinitialpositions) = Int((4 - 1) * Rnd - 1)
    colour(counterinitialpositions) = 3 + counterinitialpositions
    counterinitialpositions = counterinitialpositions + 1
Loop


Dim counterruntime As Integer


Do Until turn = 50000
    counterruntime = 0
    Do Until counterruntime = n + 1
        
        'Changes the colour of the cell and direction of the ant.
        currentcolour(counterruntime) = Cells(y(counterruntime), x(counterruntime)).Interior.ColorIndex
        If currentcolour(counterruntime) = -4142 Then
            direction(counterruntime) = direction(counterruntime) + 1
            Cells(y(counterruntime), x(counterruntime)).Interior.ColorIndex = colour(counterruntime)
        Else
            direction(counterruntime) = direction(counterruntime) - 1
            Cells(y(counterruntime), x(counterruntime)).Interior.ColorIndex = -4142
        End If
        
        'Keeps the direction modulus 4.
        If direction(counterruntime) = 0 Then direction(counterruntime) = 4
        If direction(counterruntime) = 5 Then direction(counterruntime) = 1
        
        'Moves the ant.
        Select Case direction(counterruntime)
            Case Is = 1
                y(counterruntime) = y(counterruntime) - 1
            Case Is = 2
                x(counterruntime) = x(counterruntime) + 1
            Case Is = 3
                y(counterruntime) = y(counterruntime) + 1
            Case Is = 4
                x(counterruntime) = x(counterruntime) - 1
        End Select
        
        counterruntime = counterruntime + 1
    Loop
    turn = turn + 1
Loop
End Sub

The code is in green and the comments are in red (comments are just notes that describe what the following section of code does). I decided not to waste time making the demo readable, if you read through the advanced code you should be able to see fairly easily what the demo is up to.

If you want to try this code out for yourself then you will need to do the following:

1. Open up Excel (hopefully you are using 2007/10, if not then just comment and I will give you help), go to the 'view' tab and click on 'macro' on the far right.
2. Click 'create' in the small window that opens, then copy and paste the code into the new window.
3. Close both new windows, then Ctrl+E will bring up the menu. 
4. The four commands are 
1. "basic" - Runs two Langton's Ants in the same starting pattern as in my first post.
2. "advanced" - Runs n ants, randomly distributing them around a 200 cell square.
3. "clear" - Returns every cell to its default white.
4. "exit" - Closes the menu.

No updates on the code today, but I am going out to the pub during the day tomorrow leaving all evening for some drunken antics (I apologise, I really couldn't help myself).

211,

mathmo

2 to 54, but is n possible?

After an hour's work I have amended my program so that it supports up to 54 ants running at once. Not quite n, but that is the largest number of colours I can easily use in excel cells. There is probably something I can knock together using hex but I will look at that tomorrow. Or perhaps some sort of alternating colours? I might try it even if I do figure out hex, because who can resist a wild spotted ant?

So my maiden use of my new 54-ant toy was with 3 ants, which turned out to be pretty unspectacular as the ants were so spread out they didn't even interact. So I reduced the size of the spawn area, cranked up the number of turns, and for good measure tried it with ten ants. Below is the result.

Ten ants running at once.

Just this one quick run has already thrown up a lot of interesting ideas. 

1. Cyan and Light Green collided at the very start of the run in such a way so that they followed the other ones path back to the starting position, ERASING the path as they went. Fortunately by the time they had regrown Blue had gotten in the way or we might have been stuck in an infinite loop.
2. It is possible for ants to hijack other ants highways, moving in an almost straight line along it. My first observation of this was Light Green climbing Red's, coming back down the other side and in the process forcing red to create a second highway back into the spawn area.  
3. Several times ants were in the right direction and cell such that they got caught following another ants path. This occurred with the Olive ant erasing most of Light Blue despite the fact that Light Blue's path was interleaved with Dark Blue.
4. Pink just sat back and watched the carnage. We can see the distinctive shape of an unmolested Langton's Ant, a clear indicator that despite the bizarre goings on that our code in fact runs correctly.

I think that tomorrow I will try to increase the number of ants I can have, find a way to highlight the position of each actual ant and to create an optional elastic barrier around the edge of the spawn zone.

31,

mathmo

Introductions

Okay, I am writing this first post at what I had originally planned to be the end of the project, but today I revised that decision. 

To get you up to speed: I have some basic functionality with a central menu that calls the demo as well as the clear option. The demo is two of Langton's Ants separated 100 cells each way and going in opposite directions. I have found that this set up was the simplest demonstration of the possibilities that multiple ants offer. (The clear option simply sets every cell on the spreadsheet to blank.)

Demo option produces this simple collision.

This afternoon I decided to see what would happen if I ran the demo multiple times without clearing the sheet. The result was beautiful.

The result of the demo being run 8 times in a row.

At first the two ants were in perfect symmetry, but eventually they moved into a square at the same time. The way I had written this code was that the red ant progressed on each turn before the green ant, hence when they 'collided' they were thrown out of symmetry as expected. But what happened next was most definitely unexpected. The two 'knots' formed where the highways intersect are perfectly symmetric, but occurred AFTER the break in symmetry at approximately the same time for both ants.

I think this is rather a case of

"Now this is not the end. It is not even the beginning of the end. But it is, perhaps, the end of the beginning." - Winston Churchill

I now plan to expand and improve my macro, on my wish list so far are:

• A border so that each ant terminates when it reaches the edge of the screen.
• An option for the user to have as many ants as they like.
• 'Passive' and 'Aggressive' modes, where ants annihilate any ants they 'land' on.
• Separate the macro into its own program. (Don't hold your breath on this one.)

I won't upload my code yet as there is always the risk that one of you might actually have access to a velociraptor.

1,

mathmo