Blarger

#include <iostream>
#include <string>
#include <assert.h>

// ANY OTHER HEADERS HERE

using namespace std;

#define IS_ANT_LABEL(ch) (((ch) >= '0' && (ch) <= '9') || (ch) == '+')
enum AntDirection { NORTH, EAST, SOUTH, WEST };
const int FIELD_WIDTH = 5;
const int FIELD_HEIGHT = 6;
const int MAX_MEMORY = 100; //for ant memory

const int MOUND_X = 1;
const int MOUND_Y = 3;

const int MAX_ANTS = 8;

int num_ants = 0;
AntDirection dir_assign = NORTH;

//holds x and y values. Useful for the PathHome variable of tracking memory for the Ant
struct Vector2
{
    int x, y;
    Vector2() {}
    Vector2(int X, int Y) : x(X), y(Y) {}
};

struct Ant {
    int x, y; // 0-based
    char label;
    AntDirection preferred_dir;
    bool have_food;

    //holds memory of visited positions on field. 0 for non visited, and 1 for have visited.
    bool MemField[FIELD_HEIGHT][FIELD_WIDTH];

    //holds a list of positions the ant has occupied thus far. Used to allow the ant to return home.
    Vector2 PathHome[MAX_MEMORY];
    int steps_thus_far; //how many steps the ant has taken since it was spawned


    Ant() {
        x = y = label = 0;
        preferred_dir = NORTH;
        have_food = false;
        steps_thus_far = 0;

        //initialize memory field with ant mound set to 1. Every other area is set to 0.
        for(int i=0; i<FIELD_HEIGHT; i++)
        {
            for(int k=0; k<FIELD_WIDTH; k++)
            {
                if(i == MOUND_Y && k == MOUND_X)
                {
                    MemField[i][k] = 1;
                }
                else
                {
                    MemField[i][k] = 0;
                }
            }
        }
    }
};
Ant ants[MAX_ANTS];

string AntField[FIELD_HEIGHT] = {
  "...X.",
  "XX.X.",
  "...X.",
  "._.X*",
  "...X.",
  ".....",
};


string fieldToString()
{
    string field_copy[FIELD_HEIGHT];
    copy(AntField, AntField+FIELD_HEIGHT, field_copy);
    for (int a = 0; a < num_ants; a++)
        if (IS_ANT_LABEL(field_copy[ants[a].y][ants[a].x]))
            field_copy[ants[a].y][ants[a].x] = '+';
        else
            field_copy[ants[a].y][ants[a].x] = ants[a].label;
    string result;
    for (int y = 0; y < FIELD_HEIGHT; y++)
    {
        result += field_copy[y];
        result += "\n";
    }
    return result;
}

void tickMound()
{
    //Check to see if mound can produce more ants. If so, assign a new ant onto the field and its preferred direction.
    if(num_ants < MAX_ANTS)
    {
        ants[num_ants].label = (char)(((int)'0')+num_ants); //assign its unique ID
        ants[num_ants].PathHome[0] = Vector2(MOUND_X, MOUND_Y);

        int prefDir = num_ants % 4; //since there's 4 cardinal directions, modulus by 4 to automatically assign

        switch(prefDir)
        {
        case 0:
            {
                ants[num_ants].preferred_dir = NORTH;
                break;
            }
        case 1:
            {
                ants[num_ants].preferred_dir = EAST;
                break;
            }
        case 2:
            {
                ants[num_ants].preferred_dir = SOUTH;
                break;
            }
        case 3:
            {
                ants[num_ants].preferred_dir = WEST;
                break;
            }
        }

        //now assign ant's x and y based on position of ant mound

        ants[num_ants].x = MOUND_X;
        ants[num_ants].y = MOUND_Y;
        ants[num_ants].MemField[MOUND_Y][MOUND_X] = 1;

        //finally increase the number of ants by 1
        num_ants++;
    }
}

/*
    Checks to see if ant can walk in chosen direction and returns true if successful. Called from tickAnts() normally.
*/
bool tryWalk(Ant& ant, AntDirection dir)
{
    //For each direction, check to see if the ant can move in that direction, assuming it's not a boundary,
    //obstacle, or a visited area. If it can, update its position and memory variables.
    switch(dir)
    {
        case NORTH:
            {
                if(ant.y - 1 < 0) //if the ant is at the edge, it can't move
                    return false;
                else if(ant.y > 0) //the ant is not against the edge
                {
                    //if there's an obstacle in the way or the ant has already went to the next location, don't move
                    if(AntField[ant.y-1][ant.x] == 'X' || ant.MemField[ant.y-1][ant.x] == 1)
                    {
                        return false;
                    }

                    else
                    {
                        if(ant.steps_thus_far < MAX_MEMORY)
                        {
                            ant.steps_thus_far++;
                            ant.y--;
                            ant.MemField[ant.y][ant.x] = 1;
                            ant.PathHome[ant.steps_thus_far] = Vector2(ant.x, ant.y);
                            return true;
                        }
                        else
                        {
                            cout << "Ant " << ant.label << " ran out of position memory.";
                            return false;
                        }
                    }

                }
                else
                { return false; }
                break;
            }
        case EAST:
            {
                if(ant.x + 1 > FIELD_WIDTH-1)
                    return false;
                else if(ant.x < FIELD_WIDTH-1)
                {
                    if(AntField[ant.y][ant.x + 1] == 'X' || ant.MemField[ant.y][ant.x+1] == 1)
                    {
                        return false;
                    }
                    else
                    {
                        if(ant.steps_thus_far < MAX_MEMORY)
                        {
                            ant.steps_thus_far++;
                            ant.x++;
                            ant.MemField[ant.y][ant.x] = 1;
                            ant.PathHome[ant.steps_thus_far] = Vector2(ant.x, ant.y);
                            return true;
                        }
                        else
                        {
                            cout << "Ant " << ant.label << " ran out of position memory.";
                            return false;
                        }
                    }
                }
                else
                { return false; }
                break;
            }

        case SOUTH:
            {
                if(ant.y + 1 > FIELD_HEIGHT-1)
                    return false;
                else if(ant.y < FIELD_HEIGHT-1)
                {
                    if(AntField[ant.y+1][ant.x] == 'X' || ant.MemField[ant.y+1][ant.x] == 1)
                    {
                        return false;
                    }
                    else
                    {
                        if(ant.steps_thus_far < MAX_MEMORY)
                        {
                            ant.steps_thus_far++;
                            ant.y++;
                            ant.MemField[ant.y][ant.x] = 1;
                            ant.PathHome[ant.steps_thus_far] = Vector2(ant.x, ant.y);
                            return true;
                        }
                        else
                        {
                            cout << "Ant " << ant.label << " ran out of position memory.";
                            return false;
                        }
                    }

                }
                else
                { return false;}
                break;

            }

        case WEST:
            {
                if(ant.x - 1 < 0)
                    return false;
                else if(ant.x > 0)
                {
                    if(AntField[ant.y][ant.x - 1] == 'X' || ant.MemField[ant.y][ant.x-1] == 1)
                        return false;
                    else
                    {
                        if(ant.steps_thus_far < MAX_MEMORY)
                        {
                            ant.steps_thus_far++;
                            ant.x--;
                            ant.MemField[ant.y][ant.x] = 1;
                            ant.PathHome[ant.steps_thus_far] = Vector2(ant.x, ant.y);
                            return true;
                        }
                        else
                        {
                            cout << "Ant " << ant.label << " ran out of position memory.";
                            return false;
                        }
                    }
                }
                else
                { return false; }
                break;
            }
    }
}

/*
    Iterate through each available ant, having them move in their preferred direction. Check to see if it has food or not.

    have_food = true:
        The ant follows its previous course back to the mound. If it reaches the mound, change have_food to false, reset
        the ant's memory, and have it resume looking for food.

    have_food = false:
        First check to see if the ant can move in its desired direction with tryWalk(). If false, the ant will
        attempt to move in the next cardinal direction. If tryWalk() becomes false for all directions, the ant will
        not move.

        If tryWalk() becomes true, the ant's position is updated to the new position. The new position is also assigned
        1 in the ant's MemField to have it remember where it has walked.

        If it lands on food, change its have_food status to true.
*/
void tickAnts()
{
    for(int i = 0; i < num_ants; i++)
    {
        int steps = ants[i].steps_thus_far;

        steps--;
        if (steps < 0)
            steps = 0;


        if(ants[i].have_food)
        {
            ants[i].x = ants[i].PathHome[steps].x;
            ants[i].y = ants[i].PathHome[steps].y;
            ants[i].steps_thus_far--;

            //Check to see if the ant has arrived back at the mound.
            if(ants[i].x == MOUND_X && ants[i].y == MOUND_Y)
            {
                ants[i].have_food = false;

                //clear its memory
                for(int j = 0; j < FIELD_HEIGHT; j++)
                {
                    for(int k = 0; k < FIELD_WIDTH; k++)
                    {
                        ants[i].MemField[j][k] = 0;
                    }
                }

                //Resetting steps_thus_far to zero. The PathHome values will be overwritten naturally.
                ants[i].steps_thus_far = 0;
            }
        }
        else
        {
            //have_food = false

            //Check to see if ant can move in its desired direction. If so, proceed and check for food.
            //Otherwise, try the other directions.
            bool moved = false;

            moved = tryWalk(ants[i], ants[i].preferred_dir);

            //try the other three directions based on the ant's preferred direction, going clockwise.
            //If neither of them come up true, the ant will not move.
            if(!moved)
            {
                if(ants[i].preferred_dir == NORTH)
                {
                    moved = tryWalk(ants[i], EAST);
                    if (!moved)
                    {
                        moved = tryWalk(ants[i], SOUTH);

                        if(!moved)
                            moved = tryWalk(ants[i], WEST);
                    }
                }

                else if(ants[i].preferred_dir == EAST)
                {
                    moved = tryWalk(ants[i], SOUTH);
                    if (!moved)
                    {
                        moved = tryWalk(ants[i], WEST);

                        if(!moved)
                            moved = tryWalk(ants[i], NORTH);
                    }
                }
                else if(ants[i].preferred_dir == SOUTH)
                {
                    moved = tryWalk(ants[i], WEST);
                    if (!moved)
                    {
                        moved = tryWalk(ants[i], NORTH);

                        if(!moved)
                            moved = tryWalk(ants[num_ants], EAST);
                    }
                }
                else if(ants[i].preferred_dir == WEST)
                {
                    moved = tryWalk(ants[i], NORTH);
                    if (!moved)
                    {
                        moved = tryWalk(ants[i], EAST);

                        if(!moved)
                            moved = tryWalk(ants[i], SOUTH);
                    }
                }
            }


            //check for food if the ant moved to a new location
            if(moved)
            {
                if(AntField[ants[i].y][ants[i].x] == '*')
                {
                    //have ant change its food status and remove the food from the field
                    ants[i].have_food = true;
                    AntField[ants[i].y][ants[i].x] = '.';
                }
            }
        }
    }
}

void timeStep(int numsteps)
{
    for (int i = 0; i < numsteps; i++)
    {
        tickMound();
        tickAnts();
        cout << fieldToString();
    }
}

int main()
{
    timeStep(5);

    assert(fieldToString() == ".0.X.\nXX.X.\n34.X.\n._.X*\n...X.\n2..1.\n");

    timeStep(5);
    assert(fieldToString() == "+3.X.\nXX.X.\n.72X.\n._.X*\n6..X.\n....+\n");

    timeStep(5);
    assert(fieldToString() == "+..X.\nXX.X.\n...X.\n.16X*\n...X.\n...52\n");

    timeStep(5);
    assert(fieldToString() == "+..X.\nXX.X.\n...X.\n._5X*\n...X6\n...21\n");

    timeStep(5);
    assert(fieldToString() == "+..X.\nXX.X.\n.2.X.\n._.X*\n...X5\n..61.\n");

    return 0;
}