Coding a snake AI in C

/*

At start up the program lets the user choose the grid size up to 100 by 100 as well as if they want to play or

the AI to play.

The game of snake works by having the snake stored in a queue. segments of the snake can then be dequeued and enqueued.

When the snake AI plays it uses a A* algorithm modified to take into account the tail moving as the game goes on, in order to find the move next move.

Before doing this move it will use The A* algorithm again but this time checking that move is safe ( leaves a complete loop to the tail).

If it is safe it plays that move. When this algorithm is in control the snake is green.

If the move is not safe it switches to an algorithm that finds the move that gets closet to the apple. When this algorithm starts the snake

goes purple or red.

It the executes the move that  gets the closest to the snake while also being a safe move.

I found the snake could still often get into loops with just these rules, So the order that the moves are checked in are sometimes reversed

as well as sometimes the second algorithm will try find the move that takes the snake the furthest away from the apple instead.

This works quite well but it still fails in some rare conditions and does sometimes get stuck in loops near the end game.

Author: Brick Bug

Date Written: 11/04/2026

*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

#include <windows.h>

#include <time.h>

#include <math.h>

struct game {

    char gamePixels[100][100][5]; //Because the game uses non ASCII, unicode  characters "■"  5 characters are needed to store

    int snakeQueue[10000][2]; //A circular queue that stores the coords of the snake.

    int numberOfRows;

    int numberOfColumns;

    int snakeQueueFront;

    int snakeQueueRear;

    int appleChance;

    int snakeSegmentNumber;

    char movementDirection;

    int appleRow;

    int appleColumn;

    int snakeLength;

    bool humanGame;//when true perfroms extra checks when addSnakeSegment is called

                    //to make sure that the game rules are not broken

};

//This is the structure of a node - used by the A* algorithm

struct node {

    int row; //The row the node is on

    int column; //The column the node is on

    int g; //Distance between the node and the start node

    int h; //Is the estimated distance from the node from the end

    int f; //Is the total cost of the node (g + h).

           //Including h means it priotizes nodes that are in the dirction of the end.

    struct node* parent; //Parent Node can be used to trace back the order of travel

    int depth;

};

// Fucntion prototypes

void printGame(struct game *gameToPrint);

void updateGame(struct game *gameToUpdate, char direction[]);

int addSnakeSegment(struct game *game, int row, int col);

void dequeueSnake(struct game *game);

void enqueueSnake(struct game *game, int row, int col);

bool isEmptySnakeQueue(struct game *game);

bool doesSnakeFillBaord(struct game *game);

void initializeSnakeQueue(struct game *game);

void getTheSnakeHead(struct game *game, int *row, int *col);

int checkIfPixelIsInSnake(struct game *game, int row, int col,  int stepIntoTheFuture);

int checkIfPixelIsOutOfBounds(struct game * game, int row, int col);

int getLenghtOfSnakeQueue(struct game * game);

void spawnApple(struct game * game);

void gameEnd();

void gameEnd();

bool doesSnakeFillBoard(struct game *game);                         //array of structs

bool AStarNextMove(struct game *game, bool findingTail, struct node path[10000], int *pathLen);

bool checkifNextMoveIsSafe(struct game*  game, int row, int column);

bool areBoardsEqualish(struct game *g1, struct game *g2);

bool runMachineSnakeGame( int numberOfRows, int  numberOfColumns);

bool runHumanSnakeGame( int numberOfRows, int numberOfColumns);

int main() {

    int playAgain = 1;

    while(playAgain ==1){

        system("chcp 65001 > nul"); // UTF-8 encoding, lets the terminal dispaly unicode character

        srand(time(NULL));

        //srand(10); // used  for testing

        system("cls");

        printf("\n");

        printf("Welcome to snake.  ");

        printf("\n");

        printf("\n");

        printf("Set your terminal, line height to 0.6 for best results. ");

        printf("\n");

        int HumanOrMachine;

        printf("\n");

        printf("Enter 1 if you want to play. Enter 0 if you want my algorithm to play: ");

        while (scanf("%d", &HumanOrMachine) != 1 || (HumanOrMachine != 0 && HumanOrMachine != 1)){

            printf("\n");

            printf("Invalid input. Please enter 1 or 0: ");

            while (getchar() != '\n');  //clears input buffer

        }

        int numberOfColumns;

        printf("\n");

        printf("Enter how many column you want snake to have (10-100): ");

        while (scanf("%d", &numberOfColumns) != 1 || numberOfColumns < 10 || numberOfColumns > 100) {

            printf("\n");

            printf("Invalid input. Please enter a number between 10 and 100: ");

            while (getchar() != '\n');

        }

        int numberOfRows;

        printf("\n");

        printf("Enter how many rows you want snake to have (10-100): ");

        while (scanf("%d", &numberOfRows) != 1 || numberOfRows < 10 || numberOfRows > 100) {

            printf("\n");

            printf("Invalid input. Please enter a numebr between 10 and 100: ");

            while (getchar() != '\n');

        }

        //Starts a human or AI game

        if (HumanOrMachine == 0){

            runMachineSnakeGame( numberOfRows, numberOfColumns);

        }

        else {

            runHumanSnakeGame(numberOfRows, numberOfColumns);;

        }

        //Asks if they want to play again?

        system("cls");

        printf("\n");

        printf("Would You like to play agian? (type 1 for yes or 0 for no): ");

        while (getchar() != '\n');

        while ((scanf("%d", &playAgain) !=1) || (playAgain !=1 && playAgain !=0))

        {

            printf("\n");

            printf("Invalid input. Please enter 1 or 0: ");

            while (getchar() != '\n');//clear the input buffer

        }

    }

    return 0;

}

/* This runs a new snake game with the you in control*/

bool runHumanSnakeGame(int numofRows, int numOfColumn){

    system("cls");

    printf("\n");

    printf("You use the arrow keys to move the snake. Game is won when the snake fills the grid.\n\n");

    printf("\n");

    printf("\n");

    struct game game;

    game.numberOfRows = numofRows;

    game.numberOfColumns = numOfColumn;

    game.movementDirection = 'r'; // start moving right

    game.humanGame = true;

    // make game board empty

    for (int row = 0; row < game.numberOfRows; row++) {

        for (int col = 0; col < game.numberOfColumns; col++) {

            strcpy(game.gamePixels[row][col], " ");

        }

    }

    initializeSnakeQueue(&game);

    spawnApple(&game);

    bool running = true;

    int gameFinished = 0; // If this set to 1 the game is done and the function returns

    while (running){

        int headRow, headColumn;

        getTheSnakeHead(&game, &headRow, &headColumn);

        // checks for any arrow keys being pressed

        if (GetKeyState(VK_UP) & 0x8000){

            if (game.movementDirection != 'd'){ //stops game enter if down is pressed while traveling up

                game.movementDirection = 'u';

            }

        } else if (GetKeyState(VK_DOWN) & 0x8000){

            if (game.movementDirection != 'u'){

                game.movementDirection = 'd';

            }

        } else if (GetKeyState(VK_LEFT) & 0x8000){

            if (game.movementDirection != 'r'){

                game.movementDirection = 'l';

            }

        } else if (GetKeyState(VK_RIGHT) & 0x8000){

            if (game.movementDirection != 'l'){

                game.movementDirection = 'r';

            }

        }

        // Enqueues a snake segment in that direction

        if (game.movementDirection == 'u') {

            gameFinished = addSnakeSegment(&game, headRow - 1, headColumn);

        } else if (game.movementDirection == 'd') {

            gameFinished = addSnakeSegment(&game, headRow + 1, headColumn);

        } else if (game.movementDirection == 'l') {

            gameFinished = addSnakeSegment(&game, headRow, headColumn - 1);

        } else if (game.movementDirection == 'r') {

            gameFinished = addSnakeSegment(&game, headRow, headColumn + 1);

        }

        // Draws the snake in the console

        system("cls");

        printGame(&game);

        Sleep(200); // controls snake speed

        if (gameFinished){

            return true; // the game ended so the function returns

        }

    }

    return false; // makes the compiler stop complain

}

/* Uses an snake AI algorithm to play the game, returns when it cant make a safe move*/

bool runMachineSnakeGame(int numberOfRows, int numberOfColumns){

    int snakeDelay = 0; // slow it for debugging

    struct game game;

    game.numberOfRows = numberOfRows;

    game.numberOfColumns = numberOfColumns;

    game.movementDirection = ' '; // Reset direction for the new game

    game.humanGame = true;

    //makes the board blank

    for (int row = 0; row < game.numberOfRows; row++) {

        for (int column = 0; column < game.numberOfColumns; column++) {

            strcpy(game.gamePixels[row][column], " ");

        }

    }

    initializeSnakeQueue(&game);

    spawnApple(&game);

    struct game gameLast = game;

    bool reversedOffsets = false;

    int sortCounter = 0;

    bool running = true;

    while(running){ // loops unitl it returns when it cant make a safe move

        //Sees if there is a potential path to the Apple taking into acount the tail moving

        struct node pathToApple[10000];

        int pathLenToApple;

        bool isTherePathToApple = AStarNextMove(&game,false, pathToApple, &pathLenToApple);

        if (isTherePathToApple == true){

            //Only moves to the apple if there is a full path to its tail assuming the tail moves out the way

            if (checkifNextMoveIsSafe(&game, pathToApple[1].row, pathToApple[1].column) ){

                //moves one step to the apple

                system("color A"); //makes it green

                addSnakeSegment(&game, pathToApple[1].row, pathToApple[1].column);

                system("cls");

                printGame(&game);

                Sleep(snakeDelay);

            }

            else // If going towards the snake is not safe do the next thing...

            {

                printf("\n");

                printf("the next move would have been dangerous");

                printf("\n");

                //Sleep(5000);

                // Normally if going to straight to the apple it changes

                //  the algorithm switches algorithms one time to try do the legal move that gets closet to the apple

                int changeAlgorithmNTimes = 1;

                //However if the  board hasn't changed since last time, it is going in a loop

                //So it switches to the other algorithm for longer to shift the snake out the loop

                if (areBoardsEqualish(&gameLast, &game))

                {

                    printf("\n");

                    printf("THE GAME STATE IS THE SAME");

                    printf("\n");

                    //Sleep(5000);

                    //To shift the snake out of stubborn loop, the algorithm switches the order of the offsets it uses

                    if (reversedOffsets == false){

                        reversedOffsets = true;

                        system("color D"); //makes it purple

                    }else {

                        reversedOffsets = false;

                        system("color C"); //makes it purple

                    }

                    //To get the snake out of a loop, it switches the algorithm for the duration of the loop

                    // (the lenght of the snake)

                    changeAlgorithmNTimes = getLenghtOfSnakeQueue(&game)+1; // plus one means that it finishes at a different piont each  time

                }

                for (int i = changeAlgorithmNTimes; i >=1 ; i-- ){

                    gameLast = game;// So it can check above if in loop

                    printf("\n");

                    printf("the next move would have been dangerous");

                    printf("\n");

                    //Sleep(5000);

                    struct game nextMoveGame = game;

                    int snakeHeadRow;

                    int snakeHeadColumn;

                    getTheSnakeHead(&game, &snakeHeadRow, &snakeHeadColumn);

                    // priority list of direction to try

                    // DOWN - RIGHT - LEFT - UP

                    //or when flipped ..

                    //UP - LEFT - RIGHT - DOWN

                    int offsetRows[2][4] = {

                        {-1, 0, 0, 1},  // alternateOffsets = 0

                        {1, 0, 0, -1}   // alternateOffsets = 1 reversed

                    };

                    int offsetCols[2][4] = {

                        {0, 1, -1, 0},  // alternateOffsets = 0

                        {0, -1, 1, 0}   // alternateOffsets = 1 reversed

                    };

                    //offestRow and Column set to the right offsets

                    int *offsetRow = offsetRows[reversedOffsets];

                    int *offsetColumn = offsetCols[reversedOffsets];

                    //The distance to the apple from each offset

                    int distances[4];

                    for (int i = 0; i < 4; i++) {

                        int potentialRow = snakeHeadRow + offsetRow[i];

                        int potentialColumn = snakeHeadColumn + offsetColumn[i];

                        // Find the distance to the apple and store in distance

                        distances[i] = abs(potentialRow - game.appleRow) + abs(potentialColumn - game.appleColumn);

                    }

                     //A bubble sort is used to store indexs from distance and offset from closet to apple too furthest

                    int indexOrder[4] = {0, 1, 2, 3};

                    if (sortCounter == 3){

                        sortCounter =0;

                    }

                    sortCounter++; // Increase the counter every time we trigger the evasion sort

                    // use bubble sort to find the index

                    for (int i = 0; i < 3; i++) {

                        for (int j = 0; j < 3 - i; j++) {

                            bool shouldSwap = false;

                            // Every 3rd time it sorts it Biggest to smallest- to try get out of loops

                            if (sortCounter == 3) {

                                if (distances[indexOrder[j]] < distances[indexOrder[j + 1]]) {

                                    shouldSwap = true;

                                }

                            }

                            // Most the time it sorts smallest to biggest

                            else {

                                if (distances[indexOrder[j]] > distances[indexOrder[j + 1]]) {

                                    shouldSwap = true;

                                }

                            }

                            // Perform the swap if the condition was made

                            if (shouldSwap) {

                                int temp = indexOrder[j];

                                indexOrder[j] = indexOrder[j + 1];

                                indexOrder[j + 1] = temp;

                            }

                        }

                    }

                    //Next it goes through seeing if using the offests in there sorted order

                    //and it checks if the move would  be safe

                    bool foundMove = false;

                    int k = 0;

                    while (k < 4 && foundMove == false) {// k<4 to try up down left right

                        int index = indexOrder[k];

                        int potentialRow = snakeHeadRow + offsetRow[index];

                        int potentialColumn = snakeHeadColumn + offsetColumn[index];

                        //Sees if moving there is safe

                        if (checkifNextMoveIsSafe(&nextMoveGame, potentialRow, potentialColumn)){

                            //If it is safe that move made

                            addSnakeSegment(&game, potentialRow, potentialColumn);

                            system("cls");

                            printGame(&game);

                            Sleep(snakeDelay);

                            foundMove = true;

                        }

                        else

                        {

                            printf("\n");

                            printf("row %d column %d not an option", potentialRow, potentialColumn);

                            printf("\n");

                            //Sleep(1000);

                            //It k ==3 its tried all direction and cant find a safe move to do

                            if(k == 3 ){

                                printf("\n");

                                printf("No move can be found- giving up");

                                printf("\n");

                                gameEnd();

                                //it gives up and returns

                                return 1;

                            }

                        }

                        k++;

                    }

                }

            }

        }

        else

        {

            //Ive Not have a case where it could see a path to the apple so this shouldn't be triggered

            //taking acount for the tail moving, it always sees a way to the apple

            printf("\n");

            printf("no path to apple ");

            printf("\n");

            //Sleep(5000);

        }

    }

    return true;

}

/* Runs a check using A* algorithm to see if there is still a path from the snakes head to its tail,

if there is it returns true*/

bool checkifNextMoveIsSafe(struct game*  game, int row, int column){

    struct game tempGame = *game;

    struct node tempPathToApple[10000];

    int tempPathLenToApple;

    tempGame.humanGame = false; //So its doesn't trigger game end when testing moves

    //checks to see if the new segment is in the snake or out of bounds

    bool cannotBeAdded = addSnakeSegment(&tempGame,row, column);

    if (cannotBeAdded== false){

        bool isThereAPath  = AStarNextMove(&tempGame, true, tempPathToApple, &tempPathLenToApple);

        if (isThereAPath == true){

            //retruns true if that is a safe move- can still see its tail

            return true;

        }

    }

    return false;

}

/* Adds a apple to game.gamePixels. makes sure it doesn't spawn it on a snake segment

Updates applerow and apple column in game*/

void spawnApple(struct game * game)

{

    //If there is only one square left blank dont spawn the apple so that snake fills that space

    if (getLenghtOfSnakeQueue(game)== (game->numberOfColumns* game->numberOfRows) -1){

        return;

    }

    int randomRow, randomColumn;

    do {

        // Correct range: 0 to (nrows - 1)

        randomRow = rand() % game->numberOfRows;

        randomColumn = rand() % game->numberOfColumns;

        // Keep looping if the spot is has the snake in it

    } while (strcmp(game->gamePixels[randomRow][randomColumn], " ") != 0   );

    // Place the apple once an empty spot is found

    strcpy(game->gamePixels[randomRow][randomColumn], "ᾰ");

    game->appleRow = randomRow;

    game->appleColumn = randomColumn;

}

/* If findingTail is false it finds  the shortest path to the apple

If findingTail is true it find the shortest path its tail or sometimes the longest

It returns true if a path can be found and false if it can't

*/

bool AStarNextMove(struct game *game, bool findingTail, struct node path[10000], int *pathLen)

{

    //Make the start node

    struct node startNode;

    //The start node is the head of the snake.

    int headIdx = (game->snakeQueueRear - 1 + 10000) % 10000;

    startNode.row = game->snakeQueue[headIdx][0];

    startNode.column = game->snakeQueue[headIdx][1];

    startNode.g = 0;

    startNode.h = 0;

    startNode.f = 0;

    startNode.parent = NULL;//Has no parent

    struct node endNode;

    if (findingTail != true){

        //The end node is the apple

        endNode.row = game->appleRow;

        endNode.column = game->appleColumn;

    } else

    {

        endNode.row = game->snakeQueue[game->snakeQueueFront][0];

        endNode.column = game->snakeQueue[game->snakeQueueFront][1];

    }

    //The open list are the nodes that

    //it know about but haven't had all there children put on any list

    static struct node openList[10000];//max is 10*10

    int openLen = 0;

    //The closed list is the list of nodes that have had there node costs calculated

    //as well as all ther children put on the a list

    static struct node closedList[10000];

    int closedLen = 0;

    //start at the start node

    openList[openLen] = startNode;

    openLen++;

    //worst case every item in the open list has to be visted to find the end node.

    while (openLen > 0) {

        int indexOfLowestF = 0;

        struct node current = openList[0];

        //Each item in openList is looked at so that indexOfHighestF hold the

        //index of the node in openList with the lowest F. Current is that node

        for (int i = 1; i < openLen; i++) {

            if (openList[i].f < current.f) {

                current = openList[i];

                indexOfLowestF = i;

            }

        }

        //The node with the lowest F value is removed from openList

        openList[indexOfLowestF] = openList[openLen - 1];

        openLen--;

        //The node with the lowest F value is added to the closedList

        closedList[closedLen] = current;

        //CurrentNodePtr is saved to the pointer of the current node in closedList

        struct node* CurrentNodePtr = &closedList[closedLen];

        closedLen++;

        // Checks to see if the  Current Node is the EndNode

        if (current.row == endNode.row && current.column == endNode.column) {

            //tempPath will store the  list of nodes, backwards that need to be traveled

            //to get to the endNode

            static struct node tempPath[1000];

            int tempPathLen =0;

            //Temporary variable to store pointer of next node to go in Path

            struct node* PathNodePtr = CurrentNodePtr;

            //If its null it means the pionter pionts to startNode

            while (PathNodePtr != NULL) {

                tempPath[tempPathLen] = *PathNodePtr;

                tempPathLen++;

                //PathNodePtr pionts to the next node in the chain to look at

                PathNodePtr = PathNodePtr->parent;

            }

            //We need to reverse path to go from start to end

            for (int i = 0; i < tempPathLen; i++) {

                    path[i] = tempPath[(tempPathLen - 1) - i];

                }

                *pathLen = tempPathLen;

            return true; // A path could be found

        }

        //if the endNode was not found we need to generate the children from the current node

        int offsetRows[2][4] = {

            {-1, 0, 0, 1},  // normal

            {1, 0, 0, -1}   // reversed

        };

        int offsetCols[2][4] = {

            {0, 1, -1, 0},  // normal

            {0, -1, 1, 0}   // reversed

        };

        // Randomly pick the normal or reversed order ( resversed offset equals 1 or 0)

        int reversedOffsets = rand() % 2;

        // Set the pointers either reversed or normal

        int *offsetRow = offsetRows[reversedOffsets];

        int *offsetColumn = offsetCols[reversedOffsets];

        //there could be a potential child in each of the 4 directions

        for (int i = 0; i < 4; i++) {

            // Calculate the child coordinates using your new pointers

            int newRow = current.row + offsetRow[i];

            int newCol = current.column + offsetColumn[i];

            //check if the child would be out of bounds or inside the snake

            bool outOfBounds = checkIfPixelIsOutOfBounds(game, newRow, newCol);

            int stepsIntoTheFuture = current.g+1;// takes into acount the snakes tail moving away

            bool inSnake = checkIfPixelIsInSnake(game, newRow, newCol, stepsIntoTheFuture);

            //Allow stepping onto the tail when finding tail other wise it wont find get to the endNode(the tail)

            if (findingTail) {

                int tailRow = game->snakeQueue[game->snakeQueueFront][0];

                int tailCol = game->snakeQueue[game->snakeQueueFront][1];

                if (newRow == tailRow && newCol == tailCol) {

                    inSnake = false;

                }

            }

            // continue if its a emtpy square

            if (outOfBounds==false && inSnake== false) {

                // Check if child is in closedList

                bool inClosed = false;

                for (int j = 0; j < closedLen; j++) {

                    if (closedList[j].row == newRow && closedList[j].column == newCol) {

                        inClosed = true;

                    }

                }

                //If nod it ClosedList the child is made and added to openList

                if (inClosed== false) {

                    struct node child;

                    child.row = newRow;

                    child.column = newCol;

                    child.parent = CurrentNodePtr;

                    //It is one further away from start than parent (current)

                    child.g = current.g + 1;

                    // H is a estimate of the distance to the EndNode

                    //Means that node with a smaller estimate are priotised

                    child.h = abs(newRow - endNode.row) + abs(newCol - endNode.column);

                    child.f = child.g + child.h;

                    // Check if already in open list

                    bool inOpen = false;

                    for (int j = 0; j < openLen; j++) {

                        if (openList[j].row == child.row && openList[j].column == child.column) {

                            inOpen = true;

                        }

                    }

                    //The child of the current node is added to open list

                    //If its not already there

                    if (!inOpen) {

                        openList[openLen] = child;

                        openLen++;

                    }

                }

            }

        }

    }

    printf("\n");

    printf("Couldn't find a path\n");

    printf("\n");

    //Sleep(2000);

    return false; //path could not be found

}

/*You pass in the game state as well as row and column you want to see if its within the game*/

int checkIfPixelIsOutOfBounds(struct game * game, int row, int col)

{

    if (row <0 || row > (game->numberOfRows-1) ||col  <0 || col > (game->numberOfColumns-1)){

        return 1;

    }

    return 0;

}

/*You pass in the game state and it get the snake head coords

its the same as peaking the rear of the snake queue*/

void getTheSnakeHead(struct game *game, int *row, int *col) {

    int headIdx = (game->snakeQueueRear - 1 + 10000) % 10000;//use mod becuase its a ciruclar queue

    *row = game->snakeQueue[headIdx][0];

    *col = game->snakeQueue[headIdx][1];

}

/* This sets up the snake queue as well as addin the first snake segment to the center of the board */

void initializeSnakeQueue(struct game *game) {

    game->snakeQueueFront = 0;

    game->snakeQueueRear = 0;

    game->snakeLength = 0;

    addSnakeSegment(game, game->numberOfRows / 2, game->numberOfColumns / 2);

}

//* This takes the current game state and prints it to the console

void printGame(struct game *gameToPrint) {

    //Adds the top boarder ▨▨▨ ect..

    for (int column = 0; column < gameToPrint->numberOfColumns + 2; column++) printf("▨");

    printf("\n");

    //pinters the game state with ▨ to the left and right

    for (int row = 0; row < gameToPrint->numberOfRows; row++) {

        printf("▨");

        for (int column = 0; column < gameToPrint->numberOfColumns; column++) {

            printf("%s", gameToPrint->gamePixels[row][column]);

        }

        printf("▨\n");

    }

    //Adds the bottom boarder ▨▨▨ ect..

    for (int column = 0; column < gameToPrint->numberOfColumns + 2; column++) printf("▨");

    printf("\n");

}

bool isEmptySnakeQueue(struct game *game) {

    return (game->snakeLength == 0);

}

//This checks to see if the snake lenght is the number of squares on the board

bool doesSnakeFillBoard(struct game *game) {

    int currentLength = getLenghtOfSnakeQueue(game);

    int totalBoardPixels = game->numberOfColumns * game->numberOfRows;

    return (currentLength == totalBoardPixels);

}

int getLenghtOfSnakeQueue(struct game *game) {

    return game->snakeLength;

}

/* This places the next segment on the board as well as checks if the game is won or lost

it removes the last segment of the snake if no apple is eaten

It reurns true if game was lost or won*/

int addSnakeSegment(struct game *game, int newHeadRow, int newHeadColumn) {

    bool StartNewGame = 0;

    //game lost if it hits the wall

    if (checkIfPixelIsOutOfBounds(game, newHeadRow, newHeadColumn)){

        if (game->humanGame==true){ //We use this for chekcing if moves are valid when the AI plays

            gameEnd();              //so we only want gameEnd when a person plays

        }

        StartNewGame = 1;

        return StartNewGame;

    }

    int willEatApple;

    int stepsIntoFuture;

    if (strcmp(game->gamePixels[newHeadRow][newHeadColumn], "ᾰ") ==0){

        willEatApple = 1; //if adding it causes it to eat apple the tail doesn't move so stepsIntoFuture is zero

        stepsIntoFuture = 0;

    }

    else {

        willEatApple = 0;

        stepsIntoFuture = 1; //The tail moves so stepsIntoTheFuture is one

    }

    //game is won is the baird is filled

    if (doesSnakeFillBoard(game)) {

        if (game->humanGame){

            gameEnd();

        }

        StartNewGame = 1;

        return StartNewGame;

    }

    //game lost if hits itself

    if (checkIfPixelIsInSnake(game, newHeadRow, newHeadColumn, stepsIntoFuture)){

        if (game->humanGame){

            gameEnd();

        }

        StartNewGame = 1;

        return StartNewGame;

    }

    if (willEatApple)

    {

        spawnApple(game);

    }

    else

    {

        // Only dequeue the  tail if not eating

        if (getLenghtOfSnakeQueue(game) > 2) {//We want the tail to grow to 2 long at the start of the game anyway

            //gets the snakes tail

            int dequeueRow = game->snakeQueue[game->snakeQueueFront][0];

            int dequeueColumn = game->snakeQueue[game->snakeQueueFront][1];

            strcpy(game->gamePixels[dequeueRow][dequeueColumn], " ");//puts blank were the tail was

            dequeueSnake(game);

        }

    }

    //If there are already 2 ssegments you can use this to work out what bends to show at the current head,

    // ╗ ╔ not just direction

    if (getLenghtOfSnakeQueue(game) > 1) {

        int currentSnakeHeadRow, currentsSnakeHeadColumn;

        getTheSnakeHead(game, &currentSnakeHeadRow, &currentsSnakeHeadColumn);

        // Get the previous head coords, the one before the current head that ois about to be replaces

        int lastSnakeHeadIndex = (game->snakeQueueRear - 2 + 10000) % 10000;

        int lastSnakeHeadRow = game->snakeQueue[lastSnakeHeadIndex][0];

        int lastSnakeHeadColumn = game->snakeQueue[lastSnakeHeadIndex][1];

        //We need to find the character to put on the current head basted on the previous head head and the current head

        // Horizontal segment

        if (lastSnakeHeadRow == newHeadRow) {

            strcpy(game->gamePixels[currentSnakeHeadRow][currentsSnakeHeadColumn], "═");

        }

        // Vertical segment

        else if (lastSnakeHeadColumn == newHeadColumn) {

            strcpy(game->gamePixels[currentSnakeHeadRow][currentsSnakeHeadColumn], "║");

        }

        // Corner: Bottom-Right turn

        else if ((lastSnakeHeadColumn < currentsSnakeHeadColumn && newHeadRow > currentSnakeHeadRow) ||

                (lastSnakeHeadRow > currentSnakeHeadRow && newHeadColumn < currentsSnakeHeadColumn)) {

            strcpy(game->gamePixels[currentSnakeHeadRow][currentsSnakeHeadColumn], "╗");

        }

        // Corner: Bottom-Left turn

        else if ((lastSnakeHeadColumn > currentsSnakeHeadColumn && newHeadRow > currentSnakeHeadRow) ||

                  (lastSnakeHeadRow > currentSnakeHeadRow && newHeadColumn > currentsSnakeHeadColumn)) {

            strcpy(game->gamePixels[currentSnakeHeadRow][currentsSnakeHeadColumn], "╔");

        }

        // Corner: Top-Right turn

        else if ((lastSnakeHeadColumn < currentsSnakeHeadColumn && newHeadRow < currentSnakeHeadRow) ||

                (lastSnakeHeadRow < currentSnakeHeadRow &&  newHeadColumn < currentsSnakeHeadColumn)) {

            strcpy(game->gamePixels[currentSnakeHeadRow][currentsSnakeHeadColumn], "╝");

        }

        // Corner: Top-Left turn

        else if ((lastSnakeHeadColumn > currentsSnakeHeadColumn && newHeadRow  < currentSnakeHeadRow) ||

                (lastSnakeHeadRow  < currentSnakeHeadRow && newHeadColumn >  currentsSnakeHeadColumn)) {

            strcpy(game->gamePixels[currentSnakeHeadRow][currentsSnakeHeadColumn], "╚");

        }

    // it this is the second segment of the snake being added last Snake head doesnt exist

    //So the charters are only straight

    } else if (getLenghtOfSnakeQueue(game) == 1) {

        int currenHeadRow, currentHeadColumn;

        getTheSnakeHead(game, &currenHeadRow, &currentHeadColumn);

        if (currenHeadRow > newHeadRow) strcpy(game->gamePixels[currenHeadRow][currentHeadColumn], "║");

        else if (currenHeadRow < newHeadRow) strcpy(game->gamePixels[currenHeadRow][currentHeadColumn], "║");

        else if (currentHeadColumn > newHeadColumn) strcpy(game->gamePixels[currenHeadRow][currentHeadColumn], "═");

        else strcpy(game->gamePixels[currenHeadRow][currentHeadColumn], "═");

    }

    //Adds the new snake head segment to the queue

    enqueueSnake(game, newHeadRow, newHeadColumn);

    // Mark the new segment as The headOfTheSnake

    strcpy(game->gamePixels[newHeadRow][newHeadColumn], "■");

    return StartNewGame;

}

/* the new snake segement is added to the queue*/

void enqueueSnake(struct game *game, int row, int col){

    game->snakeQueue[game->snakeQueueRear][0] = row;

    game->snakeQueue[game->snakeQueueRear][1] = col;

    game->snakeQueueRear = (game->snakeQueueRear + 1) % 10000; // Wrap around because circular queue

    game->snakeLength++;

}

/*

Checks if pixel is in snake. stepsIntoTheFuture simulates the tail predicted to move away

it doesnt acount for the snake gorwing form the head*/

int checkIfPixelIsInSnake(struct game *game, int row, int column, int stepsIntoTheFuture) {

    //if its trying to look into the future more then the length of the snake

    //it is set to zero to avoid negative indices

    if (stepsIntoTheFuture > game->snakeLength) {

        stepsIntoTheFuture = game->snakeLength;

    }

    int index = (game->snakeQueueFront + stepsIntoTheFuture) % 10000;

    int numberOfElementsToCheck = game->snakeLength - stepsIntoTheFuture;

    //Goes through each segment of the snake and checks if the pixel is in the snake

    for (int i = 0; i < numberOfElementsToCheck; i++) {

        if ((game->snakeQueue[index][0] == row) && (game->snakeQueue[index][1] == column)) {

            return 1; //if it is in snake returns true

        }

        index = (index + 1) % 10000;

    }

    return 0; //if not in snake

}

/*This is used to check if the snake is stuck in a loop. It only returns false ios there are more than 2 differnces becuase

the snake can be in a loop were the is a one square gap between its head and tail meaning the boards wont be exactly equal*/

bool areBoardsEqualish(struct game *game1, struct game *game2) {

    int differenceCounter=0;

    //iterates through each pixel

    for (int r = 0; r < game1->numberOfRows; r++) {

        for (int c = 0; c < game1->numberOfColumns; c++) {

            bool isGame1Space = (strcmp(game1->gamePixels[r][c], " ") == 0);

            bool isGame2Space = (strcmp(game2->gamePixels[r][c], " ") == 0);

            // If both are spaces, Thats good

            if (isGame1Space && isGame2Space) {

                ;

            }else if (isGame1Space || isGame2Space){ //If only one has a space, the game boards are different

                differenceCounter++;

            }

        }

    }

    if (differenceCounter > 2){

        return false;

    }

    return true;

}

/* removes the last tial segment from the snake queue*/

void dequeueSnake(struct game *game) {

    if (game->snakeLength == 0){

        return;

    }

    game->snakeQueueFront = (game->snakeQueueFront + 1) % 10000; // Wrap around beccause circular queue

    game->snakeLength--;

}

/* Called if the game is won or lost*/

void gameEnd(){

    system("color 0F");

    printf("\n");

    printf("\n");

    printf("GAME END");

    printf("\n");

    printf("\n");

    system("pause");

}