<file_sep>//
// Created by adam on 2018-12-14.
//

#include <GL/gl.h>
#include <iostream>
#include "Game.h"
#include <algorithm>


Game::Game(int gridSizeX, int gridSizeY)
{
    m_grid = Grid(gridSizeX, gridSizeY);
    m_pathfinder = Pathfinder(&m_grid, getRandom(gridSizeX), getRandom(gridSizeY));
    createObstacles();
    m_playerX = getRandom(gridSizeX);
    m_playerY = getRandom(gridSizeY);
}




// draw a square in the grid
void Game::drawSquare(int x, int y)
{
    if(!m_grid.getNode(x, y)->isWalkable())
    {
        // non-walkable square
        glColor3f(0,0,1);
        glRectd(x, y, x+1, y+1);
    }
    // grid colour
    glColor3f(0.5,0.5,0.5);
    glLineWidth(1.0);
    glBegin(GL_LINE_LOOP);
        glVertex2f(x, y);
        glVertex2f(x+1, y);
        glVertex2f(x+1, y+1);
        glVertex2f(x, y+1);
    glEnd();


}

void Game::drawGrid()
{
    for(int x = 0; x < m_grid.getSizeX(); x++)
    {
        for(int y = 0; y < m_grid.getSizeY(); y++)
        {
            drawSquare(x, y);
        }
    }


}

void Game::drawSearched()
{
    for(Node* node : m_grid.getSearched())
    {
        glColor3f(0.5, 0, 0.25);
        glRectd(node->getX(), node->getY(), node->getX()+1, node->getY()+1);
    }

}


void Game::drawPlayer()
{
    glColor3f(0, 1, 0);
    glRectd(m_playerX, m_playerY, m_playerX+1, m_playerY+1);

}

void Game::move(Game::Direction direction)
{

    switch (direction)
    {
        case Direction::up:
        {
            if(m_playerY < m_grid.getSizeY()-1 )
                    m_playerY++;
            break;
        }
        case Direction::down:
        {
            if(m_playerY > 0)
                m_playerY--;
            break;
        }
        case Direction::left:
        {
            if(m_playerX > 0)
                m_playerX--;
            break;
        }
        case Direction::right:
        {
            if(m_playerX < m_grid.getSizeX()-1)
                m_playerX++;
            break;
        }
    }

}

void Game::setWalkable()
{
    m_grid.setWalkable(m_playerX, m_playerY);
}



void Game::drawPathfinder()
{
    glColor3f(1, 0, 0);
    glRectd(m_pathfinder.getX(), m_pathfinder.getY(), m_pathfinder.getX()+1, m_pathfinder.getY()+1);

}

void Game::findPath()
{
    m_pathfinder.findPath(m_playerX, m_playerY);
}

void Game::movePathfinder()
{
    while(!m_pathfinder.getPath().empty())
    {
        m_grid.addNodeToPath(m_grid.getNode(m_pathfinder.getX(), m_pathfinder.getY()));
        m_pathfinder.move();
    }

}

void Game::drawPath()
{

    for(Node *node : m_grid.getPath())
    {
        glColor3f(1, 0, 1);
        glRectd(node->getX(), node->getY(), node->getX()+1, node->getY()+1);
    }

}



void Game::reset()
{
    m_grid.reset();
    m_grid.clearSearched();
    m_playerX = getRandom(m_grid.getSizeX());
    m_playerY = getRandom(m_grid.getSizeY());
    createObstacles();
    m_pathfinder.setPosition(getRandom(m_grid.getSizeX()), getRandom(m_grid.getSizeY()));
    m_pathfinder.setTarget(-1, -1);



}

// see if target has moved and path needs to be recalculated
bool Game::targetHasMoved()
{
    return m_playerX != m_pathfinder.getTargetX() || m_playerY != m_pathfinder.getTargetY();
}


// creates some randomised non-walkable squares on the grid
void Game::createObstacles()
{

    for(int i = 0; i < m_grid.getSizeX()*m_grid.getSizeY()/3; i++)
    {
        int y = getRandom(m_grid.getSizeY());
        int x = getRandom(m_grid.getSizeX());

        if(m_playerX != x && m_playerY != y)
        {
            m_grid.setWalkable(x, y);
        }


    }

}

int Game::getRandom(int max)
{
    return rand() % max;
}






<file_sep>cmake_minimum_required(VERSION 3.10)
project(Projekt)

set(CMAKE_CXX_STANDARD 14)

add_executable(Projekt main.cpp Game.cpp Game.h Node.cpp Node.h Grid.cpp Grid.h Pathfinder.cpp Pathfinder.h)

find_package(OpenGL REQUIRED)
find_package(GLUT REQUIRED)
include_directories( ${OPENGL_INCLUDE_DIRS}  ${GLUT_INCLUDE_DIRS} )

target_link_libraries(Projekt ${OPENGL_LIBRARIES} ${GLUT_LIBRARY} )
<file_sep>//
// Created by adam on 2018-12-16.
//

#include "Grid.h"
#include <cstdlib>
#include <iostream>


Grid::Grid(int sizeX, int sizeY)
{
    m_sizeX = sizeX;
    m_sizeY = sizeY;

    m_nodes.resize(sizeX);
    for(int i = 0; i < sizeX; i++)
    {
        m_nodes[i].resize(sizeY);
    }


    for(int x = 0; x < sizeX; x++)
    {
        for(int y = 0; y < sizeY; y++)
        {
            Node newNode = Node(x,y);
            m_nodes[x][y] = newNode;
        }
    }
}


int Grid::getSizeX() const
{
    return  m_sizeX;
}

int Grid::getSizeY() const
{
    return  m_sizeY;
}




Node* Grid::getNode(int x, int y)  {
    return &m_nodes[x][y];
}

// toggles walkable/unwalkable
void Grid::setWalkable(int x, int y)
{
    m_nodes[x][y].setWalkable(!m_nodes[x][y].isWalkable());

}


// find all of a nodes neighbours and return them in a vector
std::vector<Node*> Grid::getNodeNeighbours(Node *node)
{
    std::vector<Node*> neighbours;

    for(int x = -1; x <= 1; x++)
    {
        for(int y = -1; y <= 1; y++)
        {
            if(x == 0 && y == 0)
            {
                continue;
            }
            if(node->getX()+x >= 0 && node->getX()+x <= m_sizeX-1 &&
               node->getY()+y >= 0 && node->getY()+y <= m_sizeY-1)
            {
                neighbours.push_back(&m_nodes[node->getX()+x][node->getY()+y]);
            }
        }
    }

    return neighbours;
}

int Grid::getDistance(Node *from, Node *to)
{
    // Lowest number of x or y steps will give how many diagonal moves is needed to be in line with the target
    // the higher number minus the lower number will give the remaining steps needed to reach the target node



    // vertical/horizontal step is 10 units
    // diagonal step is 14 units.  (square root of two steps)
    // so the distance equation will be 14y + 10(x-y) or 14x + 10(y-x)

    int xDistance = abs(from->getX() - to->getX());
    int yDistance = abs(from->getY() - to->getY());

    if(xDistance > yDistance)
    {
        return 14*yDistance + 10 * (xDistance - yDistance);
    }
    return 14*xDistance + 10 * (yDistance - xDistance);
}

void Grid::addNodeToPath(Node * node)
{
    m_path.push_back(node);
}

std::vector<Node *> Grid::getPath()
{
    return m_path;
}

void Grid::resetPath()
{
    m_path.clear();

}

void Grid::reset()
{
    resetPath();
    for(auto& row : m_nodes)
    {
        for(auto& node : row)
        {
            node.setWalkable(true);
        }
    }

}

void Grid::setSearched(Node *node)
{
    m_searched.push_back(node);
}

std::vector<Node *> Grid::getSearched() const {
    return m_searched;
}

void Grid::clearSearched()
{
    m_searched.clear();
}





<file_sep>//
// Created by adam on 2018-12-16.
//

#ifndef PROJEKT_PATHFINDER_H
#define PROJEKT_PATHFINDER_H

#include <stack>
#include "Grid.h"



// Handles the pathfinding
class Pathfinder
{

    Grid *m_grid;
    int m_x, m_y, m_targetX, m_targetY;
    std::stack<Node*> m_path;

public:

    Pathfinder() = default;
    Pathfinder(Grid *grid, int x, int y);
    void findPath(int targetX, int targetY);
    void retrace(Node *start, Node *end);
    int getX() const {return m_x;}
    int getY() const {return m_y;}
    void setPosition(int x, int y);
    void setTarget(int x, int y);
    int getTargetX() const{return m_targetX;};
    int getTargetY() const{return m_targetY;};
    void move();
    std::stack<Node*> getPath() const;


};


#endif //PROJEKT_PATHFINDER_H
<file_sep>//
// Created by adam on 2018-12-16.
//

#include <iostream>
#include "Node.h"

// The node class represents a square in the grid
Node::Node(int x, int y)
{
    m_x = x;
    m_y = y;
    m_walkable = true;
    m_gCost = 0;
    m_hCost = 0;
    m_parent = nullptr;

}

void Node::setWalkable(bool walkable) {m_walkable = walkable;}

int Node::getX() const {return m_x;}

int Node::getY() const {return m_y;}

bool Node::isWalkable() const {return m_walkable;}

int Node::getFCost() const
{
    return m_gCost + m_hCost;
}

int Node::getGCost() const
{
    return m_gCost;
}

int Node::getHCost() const
{
    return m_hCost;
}

// compares nodes by coordinates
bool Node::operator==(const Node &n) const
{
    return (this->m_x == n.m_x && this->m_y == n.m_y);
}

void Node::setGCost(int cost)
{
    m_gCost = cost;
}

void Node::setHCost(int cost)
{
    m_hCost = cost;
}

void Node::setParent(Node *parent)
{
    m_parent = parent;
}

Node *Node::getParent() {
    return m_parent;
}


// Compares a node by f cost, if f costs are the same h costs are used
bool Node::operator<(const Node &n) const
{
    if(this->getFCost() < n.getFCost())
    {
        return true;
    }
    else if(this->getFCost() == n.getFCost() && this->m_hCost < n.m_hCost)
    {
        return true;
    }
    return false;
}







<file_sep>//
// Created by adam on 2018-12-16.
//

#ifndef PROJEKT_SQUARE_H
#define PROJEKT_SQUARE_H

// represents a square in the game grid
class Node
{

    int m_x;
    int m_y;
    Node *m_parent;
    bool m_walkable;
    int m_gCost;
    int m_hCost;


public:
    Node() = default;
    Node(int x, int y);
    int getX() const;;
    int getY() const;;
    bool isWalkable() const;
    void setWalkable(bool walkable);
    int getFCost() const;
    int getGCost() const;
    int getHCost() const;
    void setParent(Node *parent);
    void setGCost(int cost);
    void setHCost(int cost);
    bool operator==(const Node &n) const;
    bool operator< (const Node &n) const;

    Node *getParent();
};






#endif //PROJEKT_SQUARE_H
<file_sep>//
// Created by adam on 2018-12-16.
//

#ifndef PROJEKT_GRID_H
#define PROJEKT_GRID_H


#include <vector>
#include "Node.h"

class Grid
{

public:
    Grid(int sizeX, int sizeY);
    Grid() = default;

    int getSizeX() const;
    int getSizeY() const;
    Node* getNode(int x, int y) ;
    std::vector<Node*> getNodeNeighbours(Node *node);
    void setWalkable(int x, int y);
    int getDistance(Node *from, Node *to);
    void addNodeToPath(Node* node);
    std::vector<Node*> getPath();

    void resetPath();
    void clearSearched();
    void reset();
    // marks a square that has been searched by the pathfinder
    void setSearched(Node* node);
    std::vector<Node*> getSearched() const;

private:

    std::vector<std::vector<Node>> m_nodes;
    std::vector<Node*> m_path;
    // contains the nodes checked by the pathfinder before finding the best path
    std::vector<Node*> m_searched;
    int m_sizeX, m_sizeY;

};


#endif //PROJEKT_GRID_H
<file_sep>
#include <GL/glut.h>
#include <GL/gl.h>
#include "Game.h"


// Callback functions
void display();
void keyboardSpecial(int key, int, int);
void keyboard(unsigned char c, int x, int y);
void reshape(int w, int h);
void timer(int);



// Grid size
const int gridSizeX = 50;
const int gridSizeY = 50;

const int FPS = 60;

Game g =  Game(gridSizeX, gridSizeY);

int main(int argc, char **argv)
{


    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGBA);
    glutInitWindowPosition(300, 150);
    glutInitWindowSize(1280, 900);
    glutCreateWindow("A* Pathfinding");
    glutDisplayFunc(display);
    glutReshapeFunc(reshape);
    glutTimerFunc(0, timer, 0);
    glutKeyboardFunc(keyboard);
    glutSpecialFunc(keyboardSpecial);
    glutMainLoop();

    return 0;
}




void display()
{
    glClear(GL_COLOR_BUFFER_BIT);
    g.drawSearched();
    g.drawGrid();
    g.drawPath();
    g.drawPathfinder();
    g.drawPlayer();
    glutSwapBuffers();

}


void reshape(int w, int h)
{
    glViewport (0, 0, (GLsizei) w, (GLsizei) h);
    glMatrixMode (GL_PROJECTION);
    glLoadIdentity();
    glOrtho(-1, gridSizeX+1, -1, gridSizeY+1, -1, 1);
    glMatrixMode (GL_MODELVIEW);

}


void timer(int)
{
    glutPostRedisplay();
    glutTimerFunc(1000/FPS, timer, 0 );

}



void keyboard(unsigned char c, int x, int y)
{
    if (c == 27) // esc
    {
       exit(0);

    }
    else if(c == 32) // space
    {
        g.setWalkable();
    }
    else if(c == 70 || c == 102) // F
    {
        // calculate new path if needed
        if(g.targetHasMoved())
        {
            g.findPath();
        }
           g.movePathfinder();
    }

    else if(c == 82 || c == 114)  // R
    {
        g.reset();

    }
}



void keyboardSpecial(int key, int, int)
{
   switch(key)
   {
       case GLUT_KEY_UP:
       {
           g.move(Game::Direction::up);
           break;
       }
       case GLUT_KEY_DOWN:
       {
           g.move(Game::Direction::down);
           break;
       }
       case GLUT_KEY_LEFT:
       {
           g.move(Game::Direction::left);
           break;
       }
       case GLUT_KEY_RIGHT:
       {
           g.move(Game::Direction::right);
           break;
       }
   }

}

<file_sep>//
// Created by adam on 2018-12-14.
//

#ifndef PROJEKT_GAME_H
#define PROJEKT_GAME_H


#include "Grid.h"
#include "Pathfinder.h"

class Game
{


public:
    enum Direction{ up, down, left, right};

    Game(int gridSizeX, int gridSizeY);


    void drawGrid();
    void drawSquare(int x, int y);
    void drawPlayer();
    void move(Direction direction);

    void setWalkable();
    void findPath();
    void drawPathfinder();
    void drawPath();
    Grid *getGrid();
    void drawSearched();
    void movePathfinder();

    void reset();
    void createObstacles();
    bool targetHasMoved();
    int getRandom(int max);

private:

    int m_playerX, m_playerY;
    Pathfinder m_pathfinder;
    Grid m_grid;

};


#endif //PROJEKT_GAME_H
<file_sep>//
// Created by adam on 2018-12-16.
//

#include "Pathfinder.h"
#include <algorithm>
#include <unordered_set>
#include <iostream>


Pathfinder::Pathfinder(Grid *grid, int x, int y) : m_grid(grid), m_x(x), m_y(y)
{
    m_targetX = -1;
    m_targetY = -1;
}


// uses the a* algorithm to find the closest path between two nodes
void Pathfinder::findPath(int targetX, int targetY)
{

    m_targetX = targetX;
    m_targetY = targetY;
    Node *startNode = m_grid->getNode(m_x, m_y);
    Node *targetNode = m_grid->getNode(targetX, targetY);



    std::vector<Node*> openList;
    std::vector<Node*> closedList;

    // add start node to the open list
    openList.push_back(startNode);


    while(!openList.empty())
    {
        // find the node with the lowest f cost and make it the current node
        Node *currentNode;

        for(int i = 0; i < openList.size(); i++)
        {
            // sort vector by lowest first
            std::sort(openList.begin(), openList.end(), [ ]( const auto& lhs, const auto& rhs )
            {
                return lhs->getFCost() < rhs-> getFCost();
            });
            currentNode = openList.front();
            // remove the node with the lowest f cost from open and add to the closed list
            openList.erase(openList.begin());
            closedList.push_back(currentNode);

            // target found retrace the path
            if(currentNode == targetNode)
            {
                retrace(startNode, targetNode);
                return;
            }

            std::vector<Node*> neighbours = m_grid->getNodeNeighbours(currentNode);
            // check neighbours
            for(Node *neighbour : neighbours)
            {

                // skip if neighbour is not walkable or in the closed list
               if(!neighbour->isWalkable() ||
                    std::find(closedList.begin(), closedList.end(), neighbour) != closedList.end() )
                {
                    continue;
                }


                int newCost = currentNode->getGCost() + m_grid->getDistance(currentNode, neighbour);
                // if  neighbour not in open set
                if(std::find(openList.begin(), openList.end(), neighbour) == openList.end())
                {
                    // add to open list
                    openList.push_back(neighbour);
                    // mark as searched by the pathfinder
                    m_grid->setSearched(neighbour);
                    // set f cost
                    neighbour->setGCost(newCost);
                    // set h cost
                    neighbour->setHCost(m_grid->getDistance(neighbour, targetNode ));
                    // set parent of neighbour to current
                    neighbour->setParent(currentNode);


                }
                // if neighbour is in the open list
                else if(std::find(openList.begin(), openList.end(), neighbour) != openList.end())
                {
                    // check if the new path is better
                    if(newCost < neighbour->getGCost())
                    {
                        // set parent
                        neighbour->setParent(currentNode);
                        // set f cost
                        neighbour->setGCost(newCost);
                        // set h cost
                        neighbour->setHCost(m_grid->getDistance(neighbour, targetNode ));


                    }
                }
            }
        }
    }

}

// starting from the end node, retrace the path by going through each node's parent and adding them to a stack
void Pathfinder::retrace(Node *start, Node *end)
{
    while(!m_path.empty())
    {
        m_path.pop();
    }
    Node *currentNode = end;
    while(currentNode != start)
    {
        m_path.push(currentNode);
        currentNode = currentNode->getParent();
    }
}


void Pathfinder::move()
{

    if(!m_path.empty())
    {
        Node *node = m_path.top();
        m_x = node->getX();
        m_y = node->getY();
        m_path.pop();
    }
}

void Pathfinder::setPosition(int x, int y)
{
    m_x = x;
    m_y = y;
}

void Pathfinder::setTarget(int x, int y)
{
    m_targetX = x;
    m_targetY = y;

}

std::stack<Node *> Pathfinder::getPath() const
{
    return m_path;
}


bool sortByFCost(const Node &lhs, Node &rhs)
{
    if(lhs.getFCost() < rhs.getFCost())
    {
        return true;
    }
    else if(lhs.getFCost() == rhs.getFCost() && lhs.getHCost() < rhs.getHCost())
    {
        return true;
    }
    return false;
}









