1
\$\begingroup\$

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:

screenshot of my map with green and blue points along the walls

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?

\$\endgroup\$
4
  • \$\begingroup\$ 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... \$\endgroup\$
    – q11
    Aug 21 at 8:45
  • \$\begingroup\$ 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... \$\endgroup\$
    – DMGregory
    Aug 21 at 14:44
  • \$\begingroup\$ you're right, i didn't realize! thanks so much! \$\endgroup\$
    – q11
    Aug 21 at 15:45
  • \$\begingroup\$ If you've solved your problem, try sharing your solution as an answer below. \$\endgroup\$
    – DMGregory
    Aug 21 at 16:20
0
\$\begingroup\$

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;
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Don't forget to click the checkmark to mark this answer as "Accepted" if it worked for you. \$\endgroup\$
    – DMGregory
    Aug 27 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.