maze-solver.shadron

#include <math_constants>

image Input = file("maze.png");

glsl vec4 initialState(vec2 pos) {
    vec4 input = texture(Input, pos);
    vec4 color = vec4(0.0, 0.0, 0.0, 1.0);
    // Detect starting point
    if (input.g > 0.5 && input.r + input.b < 1.0)
        color.g = 1.0;
    // Detect end point
    if (input.r > 0.5 && input.g + input.b < 1.0)
        color.r = 1.0;
    // Detect boundary
    if (input.r < 0.5 && input.g < 0.5 && input.b < 0.5)
        color.a = 0.0;
    return color;
}

param int DIRECTIONS = 16 : logrange(4, 32);

glsl vec4 solver(sampler2D self, vec2 pos, float timeDelta) {
    vec4 local = texture(self, pos);
    // Update shortest path length
    local.b = max(local.b, local.r*local.g);
    // Evaluate neighboring maxima
    vec4 neighborMax = vec4(0.0);
    for (int i = 0; i < DIRECTIONS; ++i) {
        float a = TAU*float(i)/float(DIRECTIONS);
        vec2 neighborPos = pos + shadron_PixelSize*vec2(sin(a), cos(a));
        vec4 neighbor = texture(self, neighborPos);
        neighbor.rgb *= neighbor.a;
        neighborMax = max(neighborMax, neighbor);
    }
    // Attenuate wave
    neighborMax.rg *= 4095.0/4096.0;
    // Update local values
    local.rgb = max(local.rgb, neighborMax.rgb*local.a);
    return local;
}

feedback Solver = glsl(solver, sizeof(Input)) :
    initialize(initialState),
    full_range(true),
    update_rate(1024);

param float tolerance = 0.0001 : logrange(0.000001, 0.01);
param float smoothness = 0.00001 : logrange(0.000001, 0.01);
param vec4 pathColor = vec4(1.0, 0.0, 0.0, 1.0) : color();

glsl vec4 visualize(vec2 pos) {
    vec4 background = texture(Input, pos);
    vec4 solution = texture(Solver, pos);
    float pathOpacity = 0.0;
    if (solution.b > 0.0) {
        // Evaluate difference from shortest path length
        float pathDistance = solution.b - solution.r*solution.g;
        pathOpacity = smoothstep(tolerance+smoothness, tolerance-smoothness, pathDistance);
    }
    return mix(background, pathColor, pathOpacity);
}

animation Solution = glsl(visualize, sizeof(Solver));