https://old.reddit.com/r/proceduralgeneration/comments/1niaw09/this_is_not_a_maze/

main.c

// Assumes input is a 1080x1527 PPM with minimal header named maze.ppm.
// Outputs output.ppm with the solution drawn on top, and maze.txt with
// the raw maze structure.
//
// This is free and unencumbered software released into the public domain.
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

enum {
    header = 17,
    width  = 1080,
    height = 1527,
    mazew  = 40,
    mazeh  = 56,
    xbeg   = 81,
    ybeg   = 135,
    xend   = 998,
    yend   = 1434,
    thresh = 200,
};

typedef struct {
    uint8_t hdr[header];
    uint8_t image[width*height*3];
    bool    mark[height][width];
    bool    ewall[mazeh][mazew];
    bool    swall[mazeh][mazew];
} Maze;

static void drawvline(Maze *m, int32_t x, int32_t y, int32_t c)
{
    float   cy = (float)(yend - ybeg) / (float)(mazeh - 1);
    float   cx = (float)(xend - xbeg) / (float)(mazew - 1);
    int32_t py = ybeg + (int32_t)round((float)y*cy);
    int32_t px = xbeg + (int32_t)round((float)x*cx);
    for (int32_t dy = 0; dy < cy; dy++) {
        for (int32_t dx = -1; dx <= 1; dx++) {
            m->image[(py+dy)*3*width + (px+dx)*3 + 0] = (uint8_t)(c >> 16);
            m->image[(py+dy)*3*width + (px+dx)*3 + 1] = (uint8_t)(c >>  8);
            m->image[(py+dy)*3*width + (px+dx)*3 + 2] = (uint8_t)(c >>  0);
        }
    }
}

static void drawhline(Maze *m, int32_t x, int32_t y, int32_t c)
{
    float   cy = (float)(yend - ybeg) / (float)(mazeh - 1);
    float   cx = (float)(xend - xbeg) / (float)(mazew - 1);
    int32_t py = ybeg + (int32_t)round((float)y*cy);
    int32_t px = xbeg + (int32_t)round((float)x*cx);
    for (int32_t dx = 0; dx < cx; dx++) {
        for (int32_t dy = -1; dy <= 1; dy++) {
            m->image[(py+dy)*3*width + (px+dx)*3 + 0] = (uint8_t)(c >> 16);
            m->image[(py+dy)*3*width + (px+dx)*3 + 1] = (uint8_t)(c >>  8);
            m->image[(py+dy)*3*width + (px+dx)*3 + 2] = (uint8_t)(c >>  0);
        }
    }
}

static bool solve(Maze *m, int32_t x, int32_t y, int32_t tx, int32_t ty)
{
    if (m->mark[y][x]) {
        return false;
    }
    m->mark[y][x] = true;

    if (x == tx && y==ty) {
        return true;
    } else if (x+1<mazew && !m->ewall[y  ][x  ] && solve(m, x+1, y, tx, ty)) {
        drawhline(m, x, y, 0xff0000);
        return true;
    } else if (y+1<mazeh && !m->swall[y  ][x  ] && solve(m, x, y+1, tx, ty)) {
        drawvline(m, x, y, 0xff0000);
        return true;
    } else if (x-1>=0    && !m->ewall[y  ][x-1] && solve(m, x-1, y, tx, ty)) {
        drawhline(m, x-1, y, 0xff0000);
        return true;
    } else if (y-1>=0    && !m->swall[y-1][x  ] && solve(m, x, y-1, tx, ty)) {
        drawvline(m, x, y-1, 0xff0000);
        return true;
    }
    return false;
}

int main()
{
    static Maze m;
    fread(&m, 1, sizeof(m), fopen("maze.ppm", "rb"));

    float cx = (float)(xend - xbeg) / (float)(mazew - 1);
    float cy = (float)(yend - ybeg) / (float)(mazeh - 1);
    for (int32_t y = 0; y < mazeh; y++) {
        int32_t py = ybeg + (int32_t)round((float)y*cy);
        for (int32_t x = 0; x < mazew; x++) {
            int32_t px = xbeg + (int32_t)round((float)x*cx);

            bool ewall = false;
            for (int32_t dx = 0; dx < cx; dx++) {
                uint8_t r = m.image[py*3*width + (px+dx)*3 + 0];
                uint8_t g = m.image[py*3*width + (px+dx)*3 + 1];
                uint8_t b = m.image[py*3*width + (px+dx)*3 + 2];
                if (r < thresh && g < thresh && b < thresh) {
                    ewall = true;
                }
            }

            bool swall = false;
            for (int32_t dy = 0; dy < cy; dy++) {
                uint8_t r = m.image[(py+dy)*3*width + px*3 + 0];
                uint8_t g = m.image[(py+dy)*3*width + px*3 + 1];
                uint8_t b = m.image[(py+dy)*3*width + px*3 + 2];
                if (r < thresh && g < thresh && b < thresh) {
                    swall = true;
                }
            }

            #if 0
            // check alignment/connectivity to adjust threshold/position
            if (!ewall) {
                drawhline(&m, x, y, 0x00ff00);
            }
            if (!swall) {
                drawvline(&m, x, y, 0x00ff00);
            }
            for (int32_t dy = -1; dy <= 1; dy++) {
                for (int32_t dx = -1; dx <= 1; dx++) {
                    m.image[(py+dy)*3*width + (px+dx)*3 + 0] = 0;
                    m.image[(py+dy)*3*width + (px+dx)*3 + 1] = 0;
                    m.image[(py+dy)*3*width + (px+dx)*3 + 2] = 255;
                }
            }
            #endif

            m.ewall[y][x] = ewall;
            m.swall[y][x] = swall;
        }
    }

    static uint8_t txt[1+2*mazeh][1+2*mazew+1];
    memset(txt, '#', sizeof(txt));
    txt[0][1+2*mazew] = '\n';
    for (int32_t y = 0; y < mazeh; y++) {
        for (int32_t x = 0; x < mazew; x++) {
            txt[1+2*y+0][1+2*x+0] = ' ';
            txt[1+2*y+0][1+2*x+1] = m.ewall[y][x] ? '#' : ' ';
            txt[1+2*y+1][1+2*x+0] = m.swall[y][x] ? '#' : ' ';
        }
        txt[1+2*y+0][1+2*mazew] = '\n';
        txt[1+2*y+1][1+2*mazew] = '\n';
    }
    fwrite(txt, 1, sizeof(txt), fopen("maze.txt", "wb"));

    bool r = false;
    #if 0
    r = solve(&m, 0, 0, mazew-1, mazeh-1);
    #else
    r = solve(&m, 0, mazeh-1, mazew-1, 0);
    #endif
    fwrite(&m, 1, sizeof(m.hdr)+sizeof(m.image), fopen("output.ppm", "wb"));
    return !r;
}

maze.webp