floodfill pathfinding

#include <iostream>
#include <vector>

#include <SFML/Graphics.hpp>

struct Cell
{
    int dist;
};

struct Position
{
    int x;
    int y;

    Position(int x, int y)
    : x(x), y(y)
    {}

    bool operator==(Position& b)
    {
        if(b.x != x)
            return false;
        if(b.y != y)
            return false;

        return true;
    }

    bool operator!=(Position& b)
    {
        if(b.x != x)
            return true;
        if(b.y != y)
            return true;

        return false;
    }
};

const unsigned int cellsHorizontal = 30,
                   cellsVertical   = 20;

Cell cells[cellsHorizontal][cellsVertical];
Cell startCells[cellsHorizontal][cellsVertical];

Position startpos(5, 10);
Position endpos(7, 17);

std::vector<Position> getNeighbours(Position pos, int width, int height)
{
    std::vector<Position> neighbours;

    if(pos.y+1 != height)
        if(cells[pos.x][pos.y+1].dist == 0)
            neighbours.push_back({pos.x, pos.y+1});

    if(pos.y-1 >= 0)
        if(cells[pos.x][pos.y-1].dist == 0)
            neighbours.push_back({pos.x, pos.y-1});

    if(pos.x+1 != width)
        if(cells[pos.x+1][pos.y].dist == 0)
            neighbours.push_back({pos.x+1, pos.y});

    if(pos.x-1 >= 0)
        if(cells[pos.x-1][pos.y].dist == 0)
            neighbours.push_back({pos.x-1, pos.y});

    return neighbours;
}

std::vector<Position> getPathNeighbours(Position pos, int width, int height)
{
    std::vector<Position> neighbours;

    if(pos.y+1 != height)
        if(cells[pos.x][pos.y+1].dist > 0)
            neighbours.push_back({pos.x, pos.y+1});

    if(pos.y-1 >= 0)
        if(cells[pos.x][pos.y-1].dist > 0)
            neighbours.push_back({pos.x, pos.y-1});

    if(pos.x+1 != width)
        if(cells[pos.x+1][pos.y].dist > 0)
            neighbours.push_back({pos.x+1, pos.y});

    if(pos.x-1 >= 0)
        if(cells[pos.x-1][pos.y].dist > 0)
            neighbours.push_back({pos.x-1, pos.y});

    return neighbours;
}

bool isPartOfPath(Position pos, std::vector<Position> path)
{
    for(Position& pathPos : path)
    {
        if(pathPos == pos)
            return true;
    }

    return false;
}

std::vector<Position> filterCells(std::vector<Position> vec)
{
    std::vector<Position> ret;

    for(int i=0; i<vec.size(); i++)
    {
        bool duplicate = false;

        for(int r=0; r<ret.size(); r++)
        {
            if(ret[r].x == vec[i].x)
            {
                if(ret[r].y == vec[i].y)
                {
                    duplicate = true;
                    break;
                }
            }
        }

        if(!duplicate)
        {
            int x = vec[i].x;
            int y = vec[i].y;
            if(cells[x][y].dist == 0)
                ret.push_back(vec[i]);
        }
    }

    return ret;
}

void calculateDistances(int width, int height)
{
    std::vector<Position> currCells, nextCells;
    currCells.push_back(endpos);
    int dist = 1;

    while(currCells.size())
    {
        for(int i=0; i<currCells.size(); i++)
        {
            int x = currCells[i].x;
            int y = currCells[i].y;
            cells[x][y].dist = dist;
            std::vector<Position> neighbours = getNeighbours(currCells[i], width, height);
            nextCells.insert(nextCells.end(), neighbours.begin(), neighbours.end());
        }

        dist++;

        currCells = filterCells(nextCells);
    }
}

std::vector<Position> findPath(int width, int height)
{
    std::vector<Position> path;

    Position currCell = startpos;
    while(currCell != endpos)
    {
        std::vector<Position> neighbours = getPathNeighbours(currCell, width, height);
        std::sort(neighbours.begin(), neighbours.end(), [](Position &a, Position &b){
            return cells[a.x][a.y].dist < cells[b.x][b.y].dist;
        });

        if(neighbours.size() == 0)
            return path;

        currCell = neighbours[0];
        path.push_back(currCell);
    }

    return path;
}

int main()
{
    for(int x = 0; x < cellsHorizontal; x++)
    {
        for(int y = 0; y < cellsVertical; y++)
        {
            // Initialise
            startCells[x][y].dist = 0;

            // Create walls
            if(!x || !y || x==cellsHorizontal-1 || y==cellsVertical-1)
                startCells[x][y].dist = -1;
        }
    }


    sf::RenderWindow window({800, 600}, "Floodfill example");

    while(window.isOpen())
    {
        // Events
        sf::Event event;
        while(window.pollEvent(event))
        {
            if(event.type == sf::Event::Closed)
                window.close();

            if(event.type == sf::Event::MouseButtonPressed)
            {
                if(sf::Mouse::isButtonPressed(sf::Mouse::Button::Left))
                {
                    sf::Vector2i cellClicked = sf::Mouse::getPosition(window) / 21;
                    int x = cellClicked.x;
                    int y = cellClicked.y;
                    if(x < cellsHorizontal && y < cellsVertical)
                    {
                        if(startCells[x][y].dist == 0)
                        {
                            startCells[x][y].dist = -1;
                        } else {
                            startCells[x][y].dist = 0;
                        }
                    }
                }
            }
        }

        // Rendering
        window.clear({35, 35, 35});

        sf::RectangleShape rect({20.f, 20.f});
        sf::Text txt;
        sf::Font fnt;
        fnt.loadFromFile("arial.ttf");
        txt.setFont(fnt);
        txt.setCharacterSize(12);
        txt.setColor(sf::Color::Black);

        for(int x = 0; x < cellsHorizontal; x++)
        {
            for(int y = 0; y < cellsVertical; y++)
            {
                cells[x][y].dist = startCells[x][y].dist;
            }
        }

        calculateDistances(cellsHorizontal, cellsVertical);
        std::vector<Position> path = findPath(cellsHorizontal, cellsVertical);

        for(int x = 0; x < cellsHorizontal; x++)
        {
            for(int y = 0; y < cellsVertical; y++)
            {
                rect.setPosition({21.f*x, 21.f*y});

                if(cells[x][y].dist < 0)
                {
                    rect.setFillColor({120,120,120});
                } else {
                    rect.setFillColor(sf::Color::White);
                }

                if(isPartOfPath(Position(x,y), path))
                    rect.setFillColor(sf::Color::Yellow);

                if(Position(x,y) == startpos)
                    rect.setFillColor(sf::Color::Green);

                if(Position(x,y) == endpos)
                    rect.setFillColor(sf::Color::Red);

                window.draw(rect);


                txt.setPosition({21.f*x, 21.f*y});
                txt.setString(std::to_string(cells[x][y].dist));
                window.draw(txt);
            }
        }

        window.setView(sf::View({0, 0, window.getSize().x, window.getSize().y}));

        window.display();
    }
}