collide.cpp

// include the header
#include "collide.h"

// usefull macros to improve readability
#define INDEX( Z, X, Y )    Z->data[ (X) + ((Y) * Z->width) ]
#define ISWALL( Z, X, Y ) ((Z->data[ (X) + ((Y) * Z->width) ] & cWall ) > 0 )

// preprocess the map to encode some gradients for each of the tiles
// to simplify the collision process
void collide_preprocess( sCollideMap *map )
{
    // clear all gradient data
    for ( uint32 i=0; i<map->width * map->height; i++ )
        // gradient data occupies lower four bits
        map->data[ i ] &= 0xF0;

    // horizontal process
    for ( uint32 x=0; x < map->width; x++ )
    {
        // check if first tile is wall
        int prev = ISWALL( map, x, 0 );
        // vertical process
        for ( uint32 y=1; y < map->height; y++ )
        {
            // sample the current tile
            int cur = ISWALL( map, x, y );
            // encode a wall gradient
            switch (cur - prev)
            {
            case ( -1 ): INDEX( map, x, y-1 ) |= cQLower; break;
            case (  1 ): INDEX( map, x, y   ) |= cQUpper; break;
            }
            //
            prev = cur;
        }
    }

    // vertical process
    for ( uint32 y=0; y < map->height; y++ )
    {
        // check if first tile is wall
        int prev = ISWALL( map, 0, y );
        // horozontal process
        for ( uint32 x=1; x < map->width; x++ )
        {
            // sample the current tile
            int cur = ISWALL( map, x, y );
            // encode a wall gradient
            switch (cur - prev)
            {
            case ( -1 ): INDEX( map, x-1, y ) |= cQRight; break;
            case (  1 ): INDEX( map, x  , y ) |= cQLeft ; break;
            }
            //
            prev = cur;
        }
    }
}

// clamp integer
static inline int clampi( int min, int cur, int max )
{
    if ( cur < min ) return min;
    if ( cur > max ) return max;
                     return cur;
}

// absolute value integer
static inline int absi( int a )
{
    if ( a < 0 ) return -a;
                 return  a;
}

//
static inline int select_from_absmin( int a, int b )
{
    int i = a, j = b;
    // compute abs
    if ( a < 0 ) a = -a;
    if ( b < 0 ) a = -b;
    // return closest to zero
    if ( a < b ) return i;
                 return j;
}

//
bool collide_test( sCollideMap *map, sCollideObject *info )
{
    // a little helper to simplify the look of the code
    const int ts = map->tileSize;

    // convert into map space and clamp
    int x1 = clampi( 0, info->x1 / ts, map->width -1 );
    int x2 = clampi( 0, info->x2 / ts, map->width -1 );
    int y1 = clampi( 0, info->y1 / ts, map->height-1 );
    int y2 = clampi( 0, info->y2 / ts, map->height-1 );

    // start with two 'invalid' resolution values
    int dp_x = 0xFFFF, dp_y = 0xFFFF;

    // traverse all tiles in the collision area
    for     ( int y=y1; y<=y2; y++ )
        for ( int x=x1; x<=x2; x++ )
        {
            // extract this tiles value
            uint8 tile = map->data[ x + y*map->width ];

            // skip if not a blocking tile
            if ( (tile & cWall) == 0 )
                continue;

            // four resolution values, one for each resolution direction
            int quad[4] = { 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF };

            // find all of the resolutions, one for each direction
            if ( (tile & cQUpper) != 0 ) quad[0] =  (y   *ts) - info->y2;
            if ( (tile & cQLower) != 0 ) quad[1] = ((y+1)*ts) - info->y1;
            if ( (tile & cQLeft ) != 0 ) quad[2] =  (x   *ts) - info->x2;
            if ( (tile & cQRight) != 0 ) quad[3] = ((x+1)*ts) - info->x1;

            // select smallest resolution for each axis by comparison of their abs min
            quad[0] = select_from_absmin( quad[0], quad[1] );
            quad[2] = select_from_absmin( quad[2], quad[3] );

            // select the smallest resolving axis for this tile
            if ( absi( quad[2] ) < absi( quad[0] ) )
            {
                // x - axis
                // save it if smaller then our current resolution
                if ( absi( quad[2] ) < absi( dp_x ) ) dp_x = quad[2];
            }
            else
            {
                // y - axis
                // save it if smaller then our current resolution
                if ( absi( quad[0] ) < absi( dp_y ) ) dp_y = quad[0];
            }

        }

    // resolve a overlap on each axis
    if ( dp_x != 0xFFFF ) info->r_x = dp_x;
    if ( dp_y != 0xFFFF ) info->r_y = dp_y;

    // return true if we had a resolution
    return (dp_x != 0xFFFF) || (dp_y != 0xFFFF);
}