# How can I remove unnecessary vertices from wall edges?

I've got a pretty simple tile based 2d top-down map with an array of walls. In order to figure where to cast light and shadows, I've generated an array of vertex coordinates along the walls like so: The blue points I'd like to keep while removing the green points. How can I check if a point should be kept or removed?

• just realized this is a similar problem to gamedev.stackexchange.com/questions/171591/… -- If I had one large connected wall, a wall-following algorithm might work, but I don't see it working with islands (that is, a wall that's disconnected from all other walls) so I'm stumped again...
– q11
Aug 21 at 8:45
• The wall-following algorithm still works with islands. You just put it in a loop: scan over all tiles in some order until you find a wall you haven't visited before. Then follow that wall, marking each segment visited. When you run out, resume your scan where you left off, skipping over subsequent hits to marked-visited walls, until you find the next island... Aug 21 at 14:44
• you're right, i didn't realize! thanks so much!
– q11
Aug 21 at 15:45
• If you've solved your problem, try sharing your solution as an answer below. Aug 21 at 16:20

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;

• Don't forget to click the checkmark to mark this answer as "Accepted" if it worked for you. Aug 27 at 17:09