An answer to this question on Stack Overflow.

Question

Considering a tiled based game, where each agents can move straight/diagonally (in 8-directions). Basically, a map like this can be represented as a regular 2D grid, where 0 would represent an walkable location and 1 unwalkable locations (I'm using Lua):

-- Example : 3x3 sized map
local map = {
 {0,0,0},
 {0,1,1},
 {0,0,0},
}

At this point, how can we represent tile walkability depending from the direction an agent comes from ? I.e. cell [2][2] above, which is statically unwalkable, would now be walkable if coming from [1][2] (above) or [2][1] (left), but not, for instance, from [3][2] (down).

I have given to this some thoughts, but I couldn't come up with something clean enough, to me.

Thanks in advance.

Answer

I'd overlay another 2D grid with of single bytes. Each bit of the byte corresponds to a possible entrance direction with a 1 meaning it can be walked on from that direction and a 0 meaning not. You can then check for enterability using binary masking.

If most of your cells can be entered from any direction, then you may consider using a [map][1] with the tile's absolute ID (X*MaxY+Y, for instance) as a key and the byte scheme described above indicating enterability. This is slower to access, but takes less space.

For instance, let the directions be laid out as so:

Bit #      X offset  Y offset
123        -1 0 1    -1 -1 -1
4 5        -1 0 1     0  0  0
678        -1 0 1     1  1  1

If I go in the northeast direction, this corresponds to bit #3. I can perform masking by translating the above values into bit masks:

1   2   4
8      16
32 64 128

I can enter from a direction if the following returns true

Enterability(CurrentX+Xoffset(Dir), CurrentY+Yoffset(Dir)) & BitMask(Dir)

(Sorry, I'm afraid I don't know Lua well enough to write this up in that language)

Edit

So, say my directions and such are as above and I want a square that can be entered only from the North. To do this, I set bit #2:

Enterability(X)=2

If I want a square that is enterable from both the north and the southwest, I would use:

Enterability(X)=2 | 64

where | is the bitwise OR operation.

If I want a square to be enterable from any direction but west I use:

Enterability(X)=(~8)

where ~ is the not operation.

If I need to close a door, say to the east, I could unset that bit:

Enterability(X)=Enterability(X) & (~16)

To open the door again, I use:

Enterability(X)=Enterability(X) | 16

or, more simply,

Enterability(X)|=16

The ~16 produces a bitfield which is all ones except for the bit referring to 16. Using this with the AND operator (&) leaves all the bits on, except the one referring to 16.

Also note that hexadecimal addressing can be more convenient:

 Decimal          Hexadecimal
1   2   4       0x1  0x2  0x4
8      16   =   0x8       0x10
32 64 128       0x20 0x40 0x80

[1]: https://en.wikipedia.org/wiki/Hash_table