Instead of guiding a wall-following algorithm along the wall tiles, which is a method that probably would have worked, I decided to solve this problem by finding the line segments that make up the edge of the walls instead.
Here is the code I ended up writing!
For reference, "colmap" refers to the array of walls. colmap[y][x] returns the tile value. My tiles are 8x8 pixels, which is why some vectors are being multiplied by 8.
// find wall vertices
// first, get the edges of walls in lines
let lines = [];
let overlaps = function(l) {
for (let i in lines) {
let line = lines[i];
if (
line.a.x == l.a.x &&
line.a.y == l.a.y &&
line.b.x == l.b.x &&
line.b.y == l.b.y
) {
return true
}
}
return false
};
let lineAngle = function(cx, cy, ex, ey) {
var dy = ey - cy;
var dx = ex - cx;
var theta = Math.atan2(dy, dx);
theta *= 180 / Math.PI;
return theta;
};
for (let y=0; y<this.colmap.length; y++) {
for (let x=0; x<this.colmap[y].length; x++) {
if (this.colmap[y][x] != "wall") continue;
let tx = x*8;
let ty = y*8;
let line;
// 4 lines for each wall tile
// top
if (y > 0 && this.colmap[y-1][x] != "wall") {
line = {
a: { x: tx, y: ty },
b: { x: tx+8, y: ty },
angle: lineAngle(tx, ty, tx+8, ty)
};
if (!overlaps(line)) lines.push(line);
}
// right
if (x+1 < this.colmap[y].length && this.colmap[y][x+1] != "wall") {
line = {
a: { x: tx+8, y: ty },
b: { x: tx+8, y: ty+8 },
angle: lineAngle(tx+8, ty, tx+8, ty+8)
};
if (!overlaps(line)) lines.push(line);
}
// bottom
if (
x+1 < this.colmap[y].length &&
y+1 < this.colmap.length &&
this.colmap[y+1][x] != "wall"
) {
line = {
a: { x: tx, y: ty+8 },
b: { x: tx+8, y: ty+8 },
angle: lineAngle(tx, ty+8, tx+8, ty+8)
};
if (!overlaps(line)) lines.push(line);
}
// left
if (x > 0 && this.colmap[y][x-1] != "wall") {
line = {
a: { x: tx, y: ty },
b: { x: tx, y: ty+8 },
angle: lineAngle(tx, ty, tx, ty+8)
};
if (!overlaps(line)) lines.push(line);
}
}
}
// second, consolidate lines that connect and have the same angle
for (let i=lines.length-1; i>0; i--) {
let l = lines[i];
for (let x in lines) {
let n = lines[x];
if (
l.a.x == n.b.x &&
l.a.y == n.b.y &&
l.angle == n.angle
) {
n.b = { x: l.b.x, y: l.b.y };
lines.splice(i, 1);
}
}
}
// lastly, generate vertices from the lines!
let verts = [];
overlaps = function(v) {
for (let i in verts) {
let n = verts[i];
if (v.x == n.x && v.y == n.y) {
return true
}
return false
}
};
for (let i in lines) {
let l = lines[i];
let v = { x: l.a.x, y: l.a.y };
if (!overlaps(v)) verts.push(v);
v = { x: l.b.x, y: l.b.y };
if (!overlaps(v)) verts.push(v);
}
this.vertices = verts;