main.cpp

#include <iostream>
#include <SDL2/SDL.h>
#include <SDL2/SDL_timer.h>
#include <SDL2/SDL_image.h>
#include <SDL2/SDL_events.h>
#include <SDL2/SDL_mouse.h>
#include <vector>
#include <climits>

#include "colours.h"            //Note: START,TARGET,DEFAULT etc defined here
#include "vector-operations.h"

std::vector<int> startCoords = {2,2};   //Todo: move these away from global scope
std::vector<int> targetCoords = {22,22};
std::vector< std::vector<std::vector<int>> > animationBuffer; //Awful way of doing this.
size_t frameNumber = 0;

std::vector<std::vector<int>> initialiseGrid(int columns, int rows, int defaultVal, const std::vector<int> &startCoords, const std::vector<int> &targetCoords){
    /**************************************************************************//**
    * Initialises the grid - a 2d int array that contains all the visual information about the scene - will be drawn to the screen.
    *
    * @param columns    n-columns in the 2d array
    * @param rows   n-rows in the 2d array
    * @param defaultVal initial value of the array elements
    * @param startCoords    Start coordinate for pathfinding [x,y]
    * @param targetCoords   Target coordinate for pathfinding [x,y]
    ******************************************************************************/
    std::vector<int> subArray(columns,defaultVal);
    std::vector<std::vector<int>> grid(rows,subArray);

    grid[startCoords[1]][startCoords[0]] = START;
    grid[targetCoords[1]][targetCoords[0]] = TARGET;

    return grid;
}

std::vector<std::vector<std::vector<int>>> initialisePathMemory(const std::vector<std::vector<int>> &grid){
    /**************************************************************************//**
    * Initialises pathmemory - a 2d array the same shape as 'grid'. Each element is a coordinate which denotes the previously visited coordinate in the path-finding algorithm. Initialised to {-1,-1} for clarity on which coords have already been visited.
    *
    * @param &grid    A 2d int array that contains all the visual information about the scene - will be drawn to the screen.
    ******************************************************************************/

    std::vector<int> coords(2,-1);
    std::vector<std::vector<int>> subArray(grid[0].size(),coords);
    std::vector<std::vector<std::vector<int>>> pathMemory(grid.size(),subArray);

    return pathMemory;
}

std::vector<std::vector<int>> getFinalPath(const std::vector<std::vector<std::vector<int>>>& pathMemory, const std::vector<int> &startCoords, const std::vector<int> &targetCoords){
    /**************************************************************************//**
    * When the target has been found- this function is called to traverse (in reverse) the path taken to the target.
    *
    * @param pathMemory    2D array containing the previous step in the path
    * @param startCoords    Start coordinate for pathfinding [x,y]
    * @param targetCoords   Target coordinate for pathfinding [x,y]
    ******************************************************************************/

    std::vector<std::vector<int>> finalPath;

    std::vector<int> currentCoord = pathMemory[targetCoords[1]][targetCoords[0]];

    size_t MAX_ITER = INT_MAX; //Set to a limit - otherwise causes a catastrophic memory leak if start coords cannot be count. Perhaps no longer necessary.
    size_t iter = 0;

    while (!(currentCoord == startCoords)){
        finalPath.push_back(currentCoord);
        currentCoord = pathMemory[currentCoord[1]][currentCoord[0]];
        iter ++;

        if(iter >= MAX_ITER){
            std::cout << "PATH NOT FOUND" << std::endl;
            return finalPath;
        }
    }

    return finalPath;
}

std::vector<std::vector<int>> breadthFirst(std::vector<std::vector<int>> grid, const std::vector<int> &startCoords, const std::vector<int> &targetCoords,int width, int height){
    /**************************************************************************//**
    * Performs a breadth-first pathfinding algorithm
    *
    * Starting from startCoords, adds the adjacent tiles to a queue and checks if they are the target.
    * Adjacent tiles are then taken from these adjacent tiles, and the path taken is recorded within pathMemory.
    * This process is repeated until the target is found, and the grid - the 2d grid to be drawn is returned.
    *
    * @param grid    n-columns in the 2d array
    * @param startCoords    Start coordinate for pathfinding [x,y]
    * @param targetCoords   Target coordinate for pathfinding [x,y]
    * @param width  Number of columns in the grid - used for finding adjacent tiles
    * @param height Number of rows in the grid - used for finding adjacent tiles
    ******************************************************************************/

    std::vector<std::vector<int>> visitedCoords;
    std::vector<std::vector<int>> queue{{startCoords[0],startCoords[1]}};
    std::vector<std::vector<int>> finalPath;
    bool targetFound = false;

    const int NUM_ITERATIONS = INT_MAX;
    int itCounter = 0;

    auto pathMemory = initialisePathMemory(grid); //Pick a better variable name for this

    while(!targetFound && (itCounter < NUM_ITERATIONS) ){
        std::vector<std::vector<int>> _toAddToQueue;
        for(int i = 0; i< queue.size();i++){
            auto coord = queue[i];

            if ( coordIn(coord,visitedCoords) ){
                continue;
            }

            auto adjacentTiles = getAdjacentCoords(coord[0],coord[1], width, height);
            for(auto adjCoord: adjacentTiles){

                //abstract this logic
                if(coordIn(adjCoord,_toAddToQueue) || pathMemory[adjCoord[1]][adjCoord[0]][0] != -1 || grid[adjCoord[1]][adjCoord[0]]==WALL){ //This probably needs to be here
                    continue;
                }

                pathMemory[adjCoord[1]][adjCoord[0]] = coord; //Sets adjacent coord's parent as coord.

                //If adjacent coord is a target, end.
                if(adjCoord == targetCoords){
                    targetFound == true;
                    std::cout << "Target Found" << std::endl;

                    auto finalPath = getFinalPath(pathMemory,startCoords,targetCoords);

                    drawCoords(grid, finalPath,PATH, startCoords, targetCoords);
                    return grid;
                }

                _toAddToQueue.push_back(adjCoord);
            }
        }
        visitedCoords.insert(visitedCoords.end(),queue.begin(),queue.end());

        if (_toAddToQueue.size() == 0){
            std::cout << "NO TARGET FOUND" << std::endl;
            return grid;
        }

        queue = _toAddToQueue;

        std::vector<std::vector<int>> animationFrame = grid;
        animationFrame = drawCoords(animationFrame,queue,PATH,startCoords,targetCoords);
        animationFrame = drawCoords(animationFrame,visitedCoords,SEEN,startCoords,targetCoords);
        animationBuffer.push_back(animationFrame);

        _toAddToQueue = {};
        itCounter ++ ;
    }

    std::cout << "Should not reach here" << std::endl;
    return {};
}

std::vector<std::vector<int>> recalculatePath(std::vector<std::vector<int>> grid, int rows, int columns){
    /**************************************************************************//**
    * Re-runs the pathfinding algorithm while retaining the wall information.
    *
    * @param grid    n-columns in the 2d array
    * @param columns    n-columns in the 2d array
    * @param rows   n-rows in the 2d array
    ******************************************************************************/
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < columns; j++){
            if(grid[i][j]== PATH){
                grid[i][j] = DEFAULT;
            }
        }
    }
    animationBuffer = {};
    return breadthFirst(grid,startCoords,targetCoords,columns,rows);
}

int main(){

    // returns zero on success else non-zero
    if (SDL_Init(SDL_INIT_EVERYTHING) != 0)
    {
        printf("error initializing SDL: %s\n", SDL_GetError());
        return 1;
    }

    int WINDOW_WIDTH = 800,
        WINDOW_HEIGHT = 800;

    SDL_Window *win = SDL_CreateWindow("PathFinder", // creates a window
                                       SDL_WINDOWPOS_CENTERED,
                                       SDL_WINDOWPOS_CENTERED,
                                       WINDOW_WIDTH, WINDOW_HEIGHT, 0);

    // triggers the program that controls
    // your graphics hardware and sets flags
    Uint32 render_flags = SDL_RENDERER_ACCELERATED;
    SDL_Renderer *rend = SDL_CreateRenderer(win, -1, render_flags);

    SDL_Event event;


    int columns=25,rows=25;
    std::vector<std::vector<int>> grid = initialiseGrid(columns,rows,DEFAULT,startCoords,targetCoords);

    int PIECE_SIZE=30;

    //Modifiers related to input events
    bool animationMode=false;
    bool ctrlModifier=false;
    bool movingStart=false;
    bool movingTarget=false;
    bool drawMode=false;
    bool eraseMode=false;
    bool exit = false;
    SDL_Point mousePos;

    grid = breadthFirst(grid,startCoords,targetCoords,columns,rows);

    Uint32 initialTime = SDL_GetTicks();
    Uint32 currentTime;
    Uint32 deltaTime;
    float FPS = 30;
    Uint32 frameCounter = 0;

    while(!exit){

        currentTime = SDL_GetTicks();
        deltaTime = currentTime - initialTime;

        if (deltaTime < 1000.0/FPS){
            continue;
        }   
        initialTime = currentTime;

        //Event handling starts
        while (SDL_PollEvent(&event))
        {
            switch(event.type){

                case SDL_QUIT:
                    exit = true;
                    break;

                case SDL_KEYDOWN:
                    if(event.key.keysym.sym == SDLK_r){
                        grid = initialiseGrid(columns,rows,DEFAULT,startCoords,targetCoords);
                        animationBuffer = {};
                    }

                    else if (event.key.keysym.sym == SDLK_LCTRL){
                        ctrlModifier = true;
                    }

                    else if(event.key.keysym.sym == SDLK_f){
                        animationMode = !animationMode; //Toggle animation mode
                        animationBuffer = {};
                        if(animationMode){
                            recalculatePath(grid,rows,columns);
                        }

                    }

                    else if(event.key.keysym.sym == SDLK_q){
                        exit = true;
                    }

                    break;

                case SDL_KEYUP:
                    if (event.key.keysym.sym == SDLK_LCTRL){
                        ctrlModifier = false;
                    }
                    break;


                case SDL_MOUSEBUTTONDOWN:

                    if(event.button.button == SDL_BUTTON_LEFT){
                        if(ctrlModifier){
                            movingStart = true;
                        }
                        else{
                        drawMode = true;
                        }
                    }

                    else if(event.button.button == SDL_BUTTON_RIGHT){
                        if(ctrlModifier){
                            movingTarget = true;
                        }
                        else{
                            eraseMode = true;
                        }
                    }

                    break;

                case SDL_MOUSEBUTTONUP:


                    grid = recalculatePath(grid,rows,columns);


                    if(event.button.button == SDL_BUTTON_LEFT){
                        movingStart = false;
                        drawMode = false;
                    }

                    else if(event.button.button == SDL_BUTTON_RIGHT){
                        movingTarget = false;
                        eraseMode = false;
                    }

                    break;

            }
            
        }
        //Event handling ends.

        // Fills screen with black
        SDL_SetRenderDrawColor(rend, 0, 0, 0, 1);
        SDL_RenderClear(rend);


        SDL_GetMouseState(&mousePos.x, &mousePos.y);

        //Loops through each cell in the grid and modifies the current cell based on current input event.
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){

                SDL_Rect rect{PIECE_SIZE*j + 1, PIECE_SIZE*i + 1, PIECE_SIZE, PIECE_SIZE};

                if( !SDL_PointInRect(&mousePos,&rect) ){}

                else if(drawMode){
                    if(grid[i][j] != TARGET && grid[i][j] != START){
                        grid[i][j] = WALL;
                        animationBuffer = {};
                    }
                }

                else if (eraseMode){
                    if(grid[i][j] != TARGET && grid[i][j] != START){
                        grid[i][j] = DEFAULT;
                        animationBuffer = {};
                    }
                }

                else if (movingStart){
                    if(grid[i][j] != TARGET){
                        grid[startCoords[1]][startCoords[0]] = DEFAULT;
                        startCoords = {j,i};
                        grid[i][j] = START;
                        animationBuffer = {};
                    }

                }

                else if (movingTarget){
                    if(SDL_PointInRect(&mousePos,&rect)&& grid[i][j] != START){
                        grid[targetCoords[1]][targetCoords[0]] = DEFAULT;
                        targetCoords = {j,i};
                        grid[i][j] = TARGET;
                        animationBuffer = {};
                    }
                }
                
                //Map the colour of the cell to the values defined in colours.h
                std::vector<int> rgb;
                if (animationBuffer.size() == 0 || !animationMode){
                    rgb = getCellColour(grid[i][j]);
                }
                else{
                    rgb = getCellColour(animationBuffer[0][i][j]);
                }
                SDL_SetRenderDrawColor(rend, rgb[0], rgb[1], rgb[2], 1);

                SDL_RenderDrawRect(rend, &rect);
                SDL_RenderFillRect(rend, &rect);
            }
        }

        //Remove the first element of the animation buffer every other frame.
        if(animationBuffer.size() != 0 && frameCounter%2==0 && animationMode){
            animationBuffer.erase(animationBuffer.begin());
        }

        frameCounter++;

        SDL_RenderPresent(rend); //Triggers double buffers - smoother rendering

    }

    return 0;
}