Determining which way a wall faces in a 2D grid with minimal boilerplate

Question

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:

WWW
W@.
WWW

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

...
.@W
.WW

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

WW.
W@W
.WW

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

WW..
WABW
..WW

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?

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.