back to lofibucket.com

The rays are casted towards corners marked in white.

The rays are casted towards corners marked in white.

The problem

Finding corners of a tile map can be handy if you need to do raycasted visibility checks for line of sight rendering like in the picture above. It is pretty straightforward if you don’t need any other information than the location of the corners.

The green markers are corners, and the red marker is an example of a non-corner point.

The green markers are corners, and the red marker is an example of a non-corner point.

Here’s a simple tile map and corners marked in green. If we take a hard look we can begin to classify these cases into corners and non-corners.

For example, the point marked in red inside square A is not a corner, but the one inside the green square B is. It’s now possible to see that the four tiles inside square A make two horizontal bars. Turns out this is enough to derive a simple rule to classify the points according to their four tile neighbourhoods, just like in the picture.

The rule

A point is not a corner if the four tiles connected to it are one of the two forms.

Otherwise it’s a corner.

The four cases

If the four tile neighbourhood is one of these, the point at the cross section is not a corner.

If the four tile neighbourhood is one of these, the point at the cross section is not a corner.

And that’s it.

Example code

Here’s an example implementation in pseudocode.1

dim neighbours(2, 2) // Temporary 2x2 array for neighbour collision information.

function find_map_corners()
    for ty=1 to MAP_HEIGHT
    for tx=1 to MAP_WIDTH

        // Assume that the 2D array map_collision contains boolean
        // values indicating if the tile is collidable or not.

        // Read the neighbourhood square around the point.
        neighbours(0,0) = map_collision(tx - 1, ty - 1)
        neighbours(1,0) = map_collision(tx    , ty - 1)
        neighbours(0,1) = map_collision(tx - 1, ty)
        neighbours(1,1) = map_collision(tx    , ty)
        
        is_corner = true
        
        // A A 
        // B B 
        if (neighbours(0,0) = neighbours(1,0)) and (neighbours(0,1) = neighbours(1,1)) then is_corner = false
        
        // A B 
        // A B 
        if neighbours(0,0) = neighbours(0,1) and neighbours(1,0) = neighbours(1,1) then is_corner = false      

        if is_corner then add_new_corner_at(tx - 1, ty - 1)
    next tx
    next ty
endFunction

  1. It’s actually CoolBasic code.


For feedback email to pekka.vaananen@iki.fi