#!/usr/bin/ruby

require 'libpng'

# a maze solver
# the maze has to be computer-generated (pixel-aligned, square)

# read the maze
maze = Png.read ARGV.first

grid = 2	# cell size
border = 0	# index in palette of border

w = maze.width/grid
h = maze.height/grid

# virtualize the maze: is cell X open left, right, up or down ?
pathopen = "\0" * (w*h)
h.times { |y|
	yy = (y<<1) | 1
	w.times { |x|
		xx = (x<<1) | 1
		i = y*w + x
		pathopen[i] |= 1 if xx > 0 and maze.lines[yy][xx-1] != border
		pathopen[i] |= 2 if xx < maze.width and maze.lines[yy][xx+1] != border
		pathopen[i] |= 4 if yy > 0 and maze.lines[yy-1][xx] != border
		pathopen[i] |= 8 if yy < maze.height and maze.lines[yy+1][xx] != border
	}
}
puts 'loaded'

# find the shortest path
# hash: target associated to source (neighbours)
pathr = {0 => -1}
#todo = [8/2*w+1514/2]	# new cells discovered
#target = 8/2*w+430/2
#pathopen[todo.first] &= ~4
#pathopen[target] &= ~4
todo = [0]
target = w*h-1
t = nil
step = proc { |tt| if not pathr[tt]: pathr[tt] = t ; todo << tt end }
while t = todo.shift
	step[t-1] if pathopen[t][0] > 0
	step[t+1] if pathopen[t][1] > 0
	step[t-w] if pathopen[t][2] > 0
	step[t+w] if pathopen[t][3] > 0
	if t == target
		puts 'found'
		break
	end
end

puts 'solved'

# draw solution in red
mazesolve = Png.read ARGV.first		# dup original
mazesolve.palette[2] = [255, 0, 0]
l = mazesolve.lines
tt = target
# from the target, walk up to the origin
done = {}
while t = pathr[tt] and t >= 0 and not done[t]
	done[t] = true
	x = ((t%w) << 1)
	y = ((t/w) << 1)
	case tt
	when t-1: l[y][x] = l[y][x-1] = 2
	when t+1: l[y][x] = l[y][x+1] = 2
	when t-w: l[y][x] = l[y-1][x] = 2
	when t+w: l[y][x] = l[y+1][x] = 2
	end
	tt = t
end

# save
mazesolve.write(ARGV[1] || ARGV[0].sub('.', '.solved.'), true)