Determining value based on adjacent cells in matrix

Input: a maze represented by an arbitrarily sized matrix of bools. (Out of bounds counts as 0)

00100
00100
01110
11111
01110
00100

Output: a nice looking representation of the maze (neighbourhood gets mapped to a wchar_t):

   ┌─┐
   │1│
  ┌┘1└┐
 ┌┘111└┐
 |11111|
 └┐111┌┘
  └┐1┌┘
   └─┘

Edit: Basically each 0 gets mapped to a 4 bit value representing the wall layout.

My approach and thoughts:

I thought it would be simplest to look at each cell at a time. Then look at it's neighbours to determine what kind of value to put there. Turns out I have 8 boolean inputs (all neighbours), this generates 2^8=256 different scenarios. I don't feel like hard coding them all.

Is there a more ele开发者_如何学Gogant way to map the values correctly?

I implemented this in my winning entry for the 2004 IOCCC. I'm sure you'll find the code well documented and easy to follow.

If you just want the answer, as I recall, the approach I took was to calculate a bitmap of occupied cells surrounding each cell, and use that as an index into an array of wall characters (or equivalently, glyphs). If, like my solution, you don't permit diagonal travel, the bitmap is 4 bits long, and thus the array has 2^4=16 elements. If you do permit diagonal travel, you need an 8 bit bitmap, and 256 entries.

Inspired by Doug T.'s solution I wrote the following myself. Basically I run through the matrix twice (poor performance :/). The first time I'll draw walls around every 1 in the matrix, I do this with bit-masks. The second time I clean up all the "inwards-pointing"-walls.

Example setup:

// Add padding to output-matrix
int owidth = width+2;
int oheight = height+2;
// 4-bit value: 0bWSEN
static char N = 0x1; // The dash that goes from the center to the north
static char E = 0x2; // The dash that goes from the center to the east
static char S = 0x4; // ...
static char W = 0x8;
// This is what I will draw around every tile
char box[] = 
    {S|E, E|W, W|S,
     N|S,  0 , N|S,
     N|E, E|W, W|N };

The walling loop:

for(unsigned int y = 0; y < height; y++)
    for(unsigned int x = 0; x < width; x++)
    {
        // We ignore walls
        if (! isOne(x, y)) // isOne takes care of out-of-bounds
            continue;
        // Go through neighbourhood
        for(int dy = -1; dy <= 1; dy++)
            for(int dx = -1; dx <= 1; dx++)
            {
                if (dy == 0 && dx == 0) // Ignore self
                    continue;

                if (! isOne(x+dx, y+dy))
                {
                    // Draw part of box
                    int ox = x+1, oy = y+1; // output-x and y
                    out[(oy+dy)*owidth+(ox+dx)] |= box[(dy+1)*3 + (dx+1)];
                }
            }
    }

The clean-up loop:

// Clean up "pointing edges"
for(unsigned int y = 0; y < height; y++)
    for(unsigned int x = 0; x < width; x++)
    {
        // We ignore zero's since we're only cleaning walls.
        if (isOne(x, y))
            continue;

        int ox = x+1, oy = y+1; // output-x and y
        // Remove edges that points to 'zero'-cells.
        if (! isOne(x  , y-1)) out[y*width+x] &= ~N;
        if (! isOne(x  , y+1)) out[y*width+x] &= ~S;
        if (! isOne(x-1, y  )) out[y*width+x] &= ~W;
        if (! isOne(x+1, y  )) out[y*width+x] &= ~E;
    }

I'll then have a 16 size (one for each symbol) look-up list with one entry for each character.

map<unsigned int, wchar_t> p;
p[0] = ' ';
p[N] = '.';
// ...
p[N|S] = L'\u2502'; // │
p[E|W] = L'\u2500'; // ─
// ...
p[N|E|S|W] = L'\u253C'; // ┼

This algorithm is not efficient by any means, O(2*width*height) ain't good... It can be improved by generating a 256 size loop-up table as others suggested, this would give us O(1) on execution.

You can winnow it down by looking at some cells before others, but, honestly, 256 is not that many. Write a program which generates them or do it by hand and use a lookup table, the extra 256 bytes (you can make the lookup map to another index to get the actual character) is plenty small enough to not worry about.

Instead of scanning each line for a 1 and drawing each cell, You could "walk" the walls.

while not at end of your bool array:

• Scan until you find a 1

define a function called "Draw" which will:

• Draw each adjacent 0 (or out-of-bounds) as a wall
• Change the current 1 to a 3 (this would require you to use something other than an array of bools)
• Switch the current cursor to an adjacent 1
  • Recurse into "Draw"
• If no such adjacent exists, return from Draw. of wall.

-upon return, resume scan until next 1 or end of input is found.

Maybe not the most efficient, but you said elegant. Recursion's always elegant! (until you get a stackoverflow that is).

Here is some hacked-out code (don't use magic numbers like I did :) ) to help you out:

int inputIdxToOutputIdx(int idx)
{
        return (idx + 1);
}


int draw(int x, int y, int arr[6][6], char outBuff[8][8])
{
        for (int deltaX = -1; deltaX < 2; ++deltaX)
        {       
                for (int deltaY = -1; deltaY < 2; ++deltaY)
                {       
                        int currX = (x + deltaX);
                        int currY = (y + deltaY);
                        int drawX = inputIdxToOutputIdx(x) + deltaX; 
                        int drawY = inputIdxToOutputIdx(y) + deltaY; 
                        // if any adjacent to 1 are 0 or off the map,
                        // draw a border
                        arr[x][y] = 3;
                        if (currX > 5 || currY > 5 || currX < 0 || currY < 0 || arr[currX][currY] == 0)
                        {       
                                printf("Drawing at %i, %i (%i,%i)\n", currX, currY,drawX,drawY);
                                outBuff[drawX][drawY] = '*';
                        }       
                        else if (arr[x][y] == 1) 
                        {       
                                draw(currX, currY, arr, outBuff);
                        }       
                }
        }
}


// make the output buffer size of input + 2
int printMaze(int arr[6][6], char outBuff[8][8])
{
        for (int x = 0; x < 6; ++x)
        {
                for (int y = 0; y < 6; ++y)
                {
                        // this might be able to be made more efficient.
                        if (arr[x][y] == 1)
                        {
                                draw(x, y, arr, outBuff);
                        }
                }
        }
}

In the above solution, I merely draw '*''s. However, if you wanted to draw a specific piece for a given situation, I would use a lookup table like walkytalky said in his comment. Map a given set of adjacent 1's and 0's to a give piece. IE:

Looking up:

0 1 0
0 1 1
0 1 0 

would give a "T" result for the center wall piece. Be sure to treat "off the map" as equivelant to 0.

When all is said and done just a straight scan with a a lookup table based on adjacent pieces (without recursion) might be your best bet unless you can make the above solution smarter about not rescanning what has already been scanned.

First run through the matrix adding the following kernel matrix, centering the 0 of the kernel on each 1 and adding the numbers to the adjacent squares (that is, make a binary representation of all the neighbors).

1   2   4 
8   16  32 
46  128 256  

Then just write the list of rules, one rule for every shape, not a rule for every possible sum. For example,

s = s_ij  # the sum at the location of interest
if not s & 16:  # never write a symbol over a 1
    if s & 8 and not (s & 128 or s & 2): 
        c = "|"
    elif s ==128:
        c = “┌─┐”
    # etc

or whatever you want.

If you first find which tiles are walls, then code a special case for each wall type that you have, like it being vertical if there's a one on the left and/or right, but none on the top or bottom.

That should narrow it down a bit, I hope. :) vertical, horizontal, and four different edges. That's 6 cases once you've detected which ones are edges at all.

Less than 256 at least. :)

Just a quick hack. Using a 3x3 array and some modulo arithmetic you could probably lower the number of memory accesses by a lot, but it might look ugly. Warning I didn't run it through a compiler so it may contain typos.

wchar_t maze_wall(int** input,int rows, int cols){

   wchar_t** output;
   int i,j;
   int N,E,S,W,NE,SE,NW,SW;

   output = (wchar_t**) malloc(sizeof(wchar_t*)*rows);
   for(i=0;i<cols;i++)
      output[i]= (wchar_t*) malloc(sizeof(wchar_t)*cols);
   for(i=0;i<rows;i++){
      for(j=0;j<cols;j++){
        if(input[i][j] ==1)
           {output[i][j] = '1'; continue;}
        N=E=S=W=NE=SE=NW=SW=0;
        if(i != 0) /*We are not at the top*/
           N = input[i-1][j];
        if(i != rows-1) /* We are not at the bottom*/
          S = input[i+1][j];
        if(j != rows-1) /* We are not at the right side*/
          E = input[i][j+1];
        if(j != 0) /* We are not at the left side*/
          W = input[i][j-1];
      /*Expand this for the corners*/

      if(N+E+S+W+NE+SE+SW+NE+NW == 0)
          {output[i][j] = ' '; continue;}

      /*Fill it in for the other six cases {'└', '┐', '┌', '┘', '-', '|'} */
      } 
   }
   return output; 
}