Simple grid-based pathing, without any heuristic. This means the path is generated from one point to everywhere

main.cpp

#include <stdarg.h>
#include <stdio.h>

#include <windows.h>

// ### Start helper stuff (This would normally be in differnt helper files)

// # I use these all the time for iterating over stuff
#define inc(variable, start, max_comp) for (int variable = (start); variable < (max_comp); ++variable)
#define inc0(variable, max_comp) for (int variable = 0; variable < (max_comp); ++variable)


// # Profiler stuff
unsigned __int64 profiler_startTime;
unsigned __int64 profiler_endTime;
double profiler_timerFrequency;

inline void PROFILER_INIT() {
    unsigned __int64 dummyFreq;
    QueryPerformanceFrequency((LARGE_INTEGER *)&dummyFreq);
    profiler_timerFrequency = (1.0 / dummyFreq);
}

#define PROFILER_START() QueryPerformanceCounter((LARGE_INTEGER *)&profiler_startTime);

inline double PROFILER_END() {
    QueryPerformanceCounter((LARGE_INTEGER *)&profiler_endTime);
    return ((profiler_endTime - profiler_startTime) * profiler_timerFrequency);
}

// # Asserts because why not

inline void Throw() {
    char* ptr = nullptr;
    *ptr = 'X';
}

#if NDEBUG
inline void Assert(bool condition, char* errorMsg, ...) { __assume(condition); }
#else
inline void Assert(bool condition, char* errorMsg, ...) {
    if (!condition) {
        va_list args;
        va_start(args, errorMsg);
        fprintf(stderr, "Wrong assertion error:\n\t");
        vfprintf(stderr, errorMsg, args);
        fprintf(stderr, "\n");
        va_end(args);
        Throw();
    }
}
#endif

// # Pseudo random generator

struct rand_data {
    unsigned int Seed;
};

void RandDataSeed(rand_data* rd, unsigned int seed) {
    rd->Seed = seed;
}

int RandDataNext(rand_data* rd) {
    rd->Seed = (214013 * rd->Seed + 2531011);
    return (rd->Seed & RAND_MAX) >> 16;
}

int RandRange(rand_data* rd, int min, int max) {
    Assert(max > min, "");
    int diff = max - min;
    int add = RandDataNext(rd) % diff;
    return min + add;
}

int RandRange0(rand_data* rd, int max) {
    Assert(max > 0, "");
    return RandDataNext(rd) % max;
}

float Rand01(rand_data* rd) {
    return RandDataNext(rd) / 32768.0f;
}

// # To store 2d coordinates

struct vec2i {
    int X;
    int Y;
};

inline vec2i operator+(vec2i vec1, vec2i vec2) {
    return vec2i{ vec1.X + vec2.X, vec1.Y + vec2.Y};
}

// # Accessing a 2d array with a vec2i

#define XY(thing) (thing).Y][(thing).X


    
    
// ### End Helper stuff

#define HEIGHT 100
#define WIDTH 100
#define RINGBUFFER_SIZE 16384 // 100 * 100 rounded up to the next power of 2 (this makes shifting it later cheaper)
#define OBSTACLE_DENSITY 0.25f
    
struct ringbuffer_vec2i {
    int Start;
    int End;

    vec2i Data[RINGBUFFER_SIZE]; // I don't know how big I should make that
    // There is a neat trick where one can make the memory size the multiple of a page table and can map the memory in a way where one doesn't really need to care about the fact that its a ring
};

int main (int, char**) {
    PROFILER_INIT();

    bool obstacles[HEIGHT][WIDTH];

    rand_data rand;
    RandDataSeed(&rand, 1337);

    /// Setup obstacles
    {
        /// Left/Right walls
        inc (y_i,   1,    HEIGHT - 1) {
            obstacles[y_i][        0] = true;
            obstacles[y_i][WIDTH - 1] = true;
        }

        /// Top/Bottom walls
        inc0 (x_i,   WIDTH) {
            obstacles[         0][x_i] = true;
            obstacles[HEIGHT - 1][x_i] = true;
        }

        /// Random obstacles
        inc (y_i,   1,    HEIGHT - 1) {
            inc (x_i,   1,    WIDTH - 1) {
                obstacles[y_i][x_i] = Rand01(&rand) < OBSTACLE_DENSITY;
            }
        }
    }

    // Printing the level; very slow due to sending each char to printf on its own
    inc0 (y_i,   HEIGHT) {
        inc0 (x_i,   WIDTH) {
            printf("%c", obstacles[y_i][x_i] ? 'X' : ' ');
        }
        printf("\n");
    }

    // Stupidly simple that doesn't use any heuristic
    PROFILER_START();
    int longestPathsCombined = 0;
    inc0 (run_i,   1000) {
        vec2i deltas[4] = {
            vec2i { -1, 0 },
            vec2i { +1, 0 },
            vec2i { 0, -1 },
            vec2i { 0, +1 },
        };

        vec2i start   = vec2i { RandRange(&rand, 1, WIDTH - 1), RandRange(&rand, 1, HEIGHT - 1) };
        obstacles[XY(start)] = false;

        int distFromStart[HEIGHT][WIDTH] = {};
        
        ringbuffer_vec2i ringbuffer;
        ringbuffer.Start = 0;
        ringbuffer.End = 1;

        ringbuffer.Data[0] = start;

        distFromStart[XY(start)] = 1;

        while (ringbuffer.End != ringbuffer.Start) {
            vec2i here = ringbuffer.Data[ringbuffer.Start];
            int valueHere = distFromStart[XY(here)];
            ringbuffer.Start = (ringbuffer.Start + 1) % RINGBUFFER_SIZE;

            // Given that I have a border of obstacles around the world, I don't have to check if the neighbours are actually on the map

            inc0 (neighbour_i,   4) {
                vec2i neighbour = here + deltas[neighbour_i];
                if (obstacles[XY(neighbour)]) { continue; }

                // Given that I don't use a heuristic and I am working on the things from low value to high value, my number has to be the lowest one
                if (!distFromStart[XY(neighbour)]) {
                    distFromStart[XY(neighbour)] = valueHere + 1;
                    ringbuffer.Data[ringbuffer.End] = neighbour;
                    ringbuffer.End = (ringbuffer.End + 1) % RINGBUFFER_SIZE;
                }
            }
        }

        int longestPath = 0;
        vec2i longestPathGoal = {};
        inc0 (y_i,   HEIGHT) {
            inc0 (x_i,   WIDTH) {
                int dist = distFromStart[y_i][x_i];
                if (dist > longestPath) {
                    longestPath = dist;
                    longestPathGoal = vec2i { x_i, y_i };
                }
            }
        }

        longestPathsCombined += longestPath;


        // I commented out generating and printing the final path
        // While generating the path should be part of the test; I wasn't sure if it would be optimised away
        // However, I kept searching for the longest path, which probably actually takes longre (and normally you wouldn't do that)

        #if 0
        vec2i path[1000]; // Again, idk how long that should be
        vec2i workingPos = longestPathGoal;
        for (int pos_i = longestPath - 1; pos_i >= 0; --pos_i) {
            path[pos_i] = workingPos;
            inc0 (neighbour_i,   4) {
                vec2i neighbour = workingPos + deltas[neighbour_i];
                if (distFromStart[XY(neighbour)] == pos_i) {
                    workingPos = neighbour;
                    break;
                }
            }
        }

        // The printing code here is obviously really bad
        inc0 (y_i,   HEIGHT) {
            inc0 (x_i,   WIDTH) {

                bool isOnPath = false;
                inc0 (i,   longestPath) {
                    if (
                        path[i].X == x_i &&
                        path[i].Y == y_i
                    ) {
                        isOnPath = true;
                        break;
                    }
                }

                if (isOnPath) {
                    printf(".");
                } else {
                    printf("%c", obstacles[y_i][x_i] ? 'X' : ' ');
                }
            }
            printf("\n");
        }
        #endif
    }
    double time = PROFILER_END();

    printf("1000 runs needed %fs (Longest paths combined: %d)", time, longestPathsCombined);
    // With -O2 -DNDEBUG runs in less than 0.2s on my machine

    return 0;
}

In hindsight, if I make the ringbuffer bigger than the map, it will never wrap-around, so I could have just made it an array.