Breadth-first search implementation for finding edge of grid c++

Question

I have implemented a breadth-first search algorithm to find the distance from a point to an edge of a grid. The grid consists of spaces that may have walls between them, effectively blocking certain paths. Currently, I have a solution that performs well, but I am looking for ways to optimize it further. If you have expertise in C++ and are interested in improving the speed of my implementation, I would greatly appreciate your assistance. Thank you in advance for any help you can provide!

Here is my code so far:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <chrono>

#define UNREACHABLE -1
#define UNVISITED -1

using namespace std;

struct Vector2
{
    int x;
    int y;

    Vector2() : Vector2(0, 0) {}
    Vector2(int x, int y)
    {
        this->x = x;
        this->y = y;
    }

    Vector2 operator+(const Vector2 &other) const
    {
        return Vector2(x + other.x, y + other.y);
    }
};

enum class Direction
{
    UP,
    DOWN,
    LEFT,
    RIGHT
};

class Grid
{
public:
    Grid(int width, int height)
    {
        this->width = width;
        this->height = height;
        this->blocked_paths = new bool[width * height * width * height]{false};
        this->visited = new int[width * height];
        this->queue = new Vector2[width * height];
    }
    ~Grid()
    {
        delete[] blocked_paths;
        delete[] visited;
        delete[] queue;
    }

    bool is_inside(Vector2 pos)
    {
        return pos.x >= 0 && pos.x < width && pos.y >= 0 && pos.y < height;
    }

    int get_index(Vector2 pos)
    {
        return pos.x + pos.y * width;
    }

    bool is_blocked(Vector2 pos1, Vector2 pos2)
    {
        // will crash if pos1 or pos2 are outside the grid
        return blocked_paths[pos1.x + pos1.y * width + pos2.x * width * height + pos2.y * width * width * height];
    }

    void set_blocked(Vector2 pos1, Vector2 pos2, bool blocked)
    {
        // Exploit symmetry
        blocked_paths[pos1.x + pos1.y * width + pos2.x * width * height + pos2.y * width * width * height] = blocked;
        blocked_paths[pos2.x + pos2.y * width + pos1.x * width * height + pos1.y * width * width * height] = blocked;
    }

    int get_distance(Vector2 pos, Direction dir)
    {
        if (!is_inside(pos))
            return UNREACHABLE;

        write_index = 0;
        read_index = 0;

        fill_n(visited, width * height, UNVISITED);

        visited[get_index(pos)] = 0;

        // queue
        queue[write_index++] = pos;

        while (write_index > read_index)
        {
            Vector2 current = queue[read_index++];

            switch (dir)
            {
            case Direction::UP:
                if (current.y == 0)
                    return visited[get_index(current)];
                break;
            case Direction::DOWN:
                if (current.y == height - 1)
                    return visited[get_index(current)];
                break;
            case Direction::LEFT:
                if (current.x == 0)
                    return visited[get_index(current)];
                break;
            case Direction::RIGHT:
                if (current.x == width - 1)
                    return visited[get_index(current)];
                break;
            }

            int next_distance = visited[get_index(current)] + 1;

            Vector2 next = Vector2(current.x, current.y - 1);
            int next_index = get_index(next);
            if (is_inside(next) && visited[next_index] == UNVISITED && !is_blocked(current, next))
            {
                visited[next_index] = next_distance;
                queue[write_index++] = next;
            }

            next = Vector2(current.x, current.y + 1);
            next_index = get_index(next);
            if (is_inside(next) && visited[next_index] == UNVISITED && !is_blocked(current, next))
            {
                visited[next_index] = next_distance;
                queue[write_index++] = next;
            }

            next = Vector2(current.x - 1, current.y);
            next_index = get_index(next);
            if (is_inside(next) && visited[next_index] == UNVISITED && !is_blocked(current, next))
            {
                visited[next_index] = next_distance;
                queue[write_index++] = next;
            }

            next = Vector2(current.x + 1, current.y);
            next_index = get_index(next);
            if (is_inside(next) && visited[next_index] == UNVISITED && !is_blocked(current, next))
            {
                visited[next_index] = next_distance;
                queue[write_index++] = next;
            }
        }

        return UNREACHABLE;
    }

private:
    int width;
    int height;
    bool *blocked_paths;
    int *visited;
    Vector2 *queue;
    int write_index;
    int read_index;
};

int main()
{
    // start message
    cout << "start" << endl;
    // make a grid speed test
    Grid grid(9, 9);

    grid.set_blocked(Vector2(3, 0), Vector2(4, 0), true);
    grid.set_blocked(Vector2(3, 1), Vector2(4, 1), true);
    grid.set_blocked(Vector2(3, 2), Vector2(4, 2), true);

    // time test
    // take time
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000000; i++)
    {
        grid.get_distance(Vector2(0, 0), Direction::RIGHT);
    }
    // take time
    auto end = chrono::high_resolution_clock::now();
    // print time
    cout << "Time taken by function: "
         << chrono::duration_cast<chrono::nanoseconds>(end - start).count() / 1000000
         << " milliseconds" << endl;
    // and in seconds
    cout << "Time taken by function: " << chrono::duration_cast<chrono::seconds>(end - start).count() << " seconds" << endl;

    // distance test
    cout << grid.get_distance(Vector2(0, 0), Direction::RIGHT) << endl;

    cout << "end" << endl;
}

Answer 1

Tests

Some automated testing lets people have confidence in changing the code. Tests are also definition of correctness - without tests it is hard to understand what is the intended behavior of the code.

Benchmarking

Benchmarks ideally produce some side effect. The side effect doesn't have to happen inside the benchmarked section.

    constexpr int iteration_count = 1'000'000;
    std::vector<int> distances(iteration_count);
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < iteration_count; i++)
    {
        distances[i] = grid.get_distance(Vector2(0, 0), Direction::RIGHT);
    }
    auto end = chrono::high_resolution_clock::now();
    for (const auto distance: distances) {
        std::cout << distance << '\n'; // can also be into a stream pointing to /dev/null
    }
    

This way the compiler is not allowed to pull off tricks like optimizing away the code, as the effects of it will affect the outside of the program. Note that C++ compiler produces binaries that behave "as-if" the written code is executed. If there are no side effects, it is as if the program doesn't exist!

Avoid macros if you can

Plain text replacements, which macros do, can lead to surprising results and hinder the ability of tooling like IDE to warn you of erroneous actions. In this case, constexpr int would not only do the job, but would convey the meaning a lot more effectively.

Internals are best kept internal

The interface overall could flow a bit smoother, but there are some functions like is_inside, get_index that could be made private, thus reducing the public interface which needs to be maintained. Ideally there is concise interface that efficiently solves the problems the library is intended to solve.

(Unnecessary) Manual memory management

Copy constructor for the class hasn't been deleted. This will likely cause segfault on copying, even though the destructor correct. std::vector would do the job and do it well.

Standard library usage

There is std::mdspan if the standard library you use already implements it. Paired with above point (i.e. creating a vector and then making mdspan of it) it would simplify some of the code. Watch out for the copy and move constructors though, as with any pointers pointing inside the object, they need to be updated on copy/move construction.

std::optional could be used instead of unreachable.

Algorithmic Performance

I am not good at graph algorithms, but in sparsely blocked grid, depth first search is likely to perform less iterations. If paired with prioritizing the direction of the next iteration, this might yield significant performance gain.