I have a 2D grid of quadrilateral tiles, some of which are walls, some are floor; each tile has four vertices, which are shared with the tiles around it (so each rendered "wall" is at least two wall-tiles thick). In order to render this scene, I need to know, for each tile:

  • is it a wall?
  • if so, is it a straight wall, a convex corner (pointing outwards), or a concave (inwards) corner? (so that I can select an appropriate texture to use – for the sake of example, ignore tiles that are totally surrounded by walls)
  • which direction is the free space in? (so that I can rotate the texture correctly)

e.g. for tile @ with walls W and floor ., this would render a straight wall facing east:


whereas this would be a convex corner facing north-west:


Some more interesting arrangements: this would ideally be treated as a special case (with a valley down the middle of two walls):


and something like this would ideally be two convex corners at A and B, as if there were two independent 2x2 squares of walls:


I'm not worried about handling invalid patterns of walls (e.g. a cross-shape of 5 walls) for now.

It's easy to track whether each tile is a wall or not, but I don't see a clean way to determine the other two conditions from that data. Is there a nice algorithm to do this without enumerating every possible arrangement of neighbouring tiles?


It sounds like what you are attempting is the Marching Squares algorithm.

You define a M x N grid of points. For each point, you define whether it is 'inside' or 'outside' a wall.

With this, you can generate a world, sized M-1 x N-1, built with your tiles.

The marching squares algorithm will tell you which tile to use at each position based on its four corner values.

Writing a marching squares algorithm is pretty trivial, by the way. Here's my Python implementation.

  • \$\begingroup\$ Thanks. I'm trying a slightly different approach (using a LUT keyed on the eight neighbouring tiles rather than the four corners of the tile), just because it fits the datastructures I'm using a bit better, and it seems to work OK – it's a bit of a pain to manually define the texture & orientation to use for each combination of neighbouring walls, but at least I only have to do it once. Doing the "proper" approach with four corners seems like it would work better in most cases, but I think it would make some other functionality much harder to implement for me. \$\endgroup\$ – Ash Dec 6 '18 at 22:14

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.