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?


1 Answer 1


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
    Commented Dec 6, 2018 at 22:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .