bool CanChange[MAP_WIDTH_MAX][MAP_HEIGHT_MAX];
short DOWNSTAIRCASEX = -1;
short DOWNSTAIRCASEY = -1;

bool isValid( short x, short y)
{
    return (x >= 0 && y >= 0 && x < MAP_WIDTH && y < MAP_HEIGHT && CanChange[x][y]);
}

void dig( short &x, short &y, short offx, short offy)
{
    short xx;
    short yy;
    xx = x + offx;
    yy = y + offy;
    if ( isValid( xx, yy))
    {
        if ( CanChange[xx][yy])
        {
            MAP[xx][yy] = TILE_FLOOR;
            x = xx;
            y = yy;
        }
    }
    PLAYER.x = x;
    PLAYER.y = y;
    return;
}

void makeRoom( short x, short y)
{
    short size, i, j;
    size = random( 2, 4);
    short xl, xr, yl, yr;
    xl = x - size/2;
    xr = x + size/2;
    yl = y - size/2;
    yr = y + size/2;
    for ( i = xl; i < xr; i++)
    {
        for ( j = yl; j < yr; j++)
        {
            if (isValid( i, j) == false)
            {
                return;
            }
        }
    }
    for ( i = xl; i < xr; i++)
    {
        for ( j = yl; j < yr; j++)
        {
            MAP[i][j] = TILE_FLOOR;
        }
    }
    if ( DOWNSTAIRCASEX == -1 && DOWNSTAIRCASEY == -1)
    {
        DOWNSTAIRCASEX  = x;
        DOWNSTAIRCASEY  = y;
        MAP[x][y]       = TILE_DOWNSTAIRCASE;
        CanChange[x][y] = false;
    }
    return;
}

void AngleToDelta( short &angle)
{
    if ( angle > 360)
    {
        angle -= 360;
    }
    if ( angle < 0)
    {
        angle += 360;
    }
    switch ( angle)
    {
        case 0:
        {
            deltaX = 1;
            deltaY = 0;
            break;
        }
        case 90:
        {
            deltaX = 0;
            deltaY = -1;
            break;
        }
        case 180:
        {
            deltaX = -1;
            deltaY = 0;
            break;
        }
        case 270:
        {
            deltaX = 0;
            deltaY = 1;
            break;
        }
        default:
        {
            deltaX = 0;
            deltaY = 0;
            break;
        }
    }
    return;
}

bool isPath( short x, short y, short tx, short ty)
{
    float best_dist     = 1000.0;
	int   best_x	    = x;
	int   best_y	    = y;
	int   tmpmax        = (MAP_WIDTH+MAP_HEIGHT)*20;
	for ( int temp = 0; temp < tmpmax; temp++)
	{
        for ( int i = x-1; i <= x+1; i++)
        {
            for ( int j = y-1; j <= y+1; j++)
            {
                if ( IsPassable( i, j) && (DistanceBetween( i, j, tx, ty) < best_dist) )
                {
                    best_dist = DistanceBetween( i, j, tx, ty);
                    best_x    = i;
                    best_y    = j;
                }
            }
        }
        x = best_x;
        y = best_y;
        if ( x == tx && y == ty)
        {
            return true;
        }
	}
    return false;
}

void GenerateMap( ushort width, ushort height, ushort level, short genstepsrate, short createroomchance, short changeangevery)
{
    short genx, geny, genang, genangnew;
    short genact;
    genx       = width/2;
    geny       = height/2;
    genang     = 0;
    MAP_WIDTH  = width;
    MAP_HEIGHT = height;

    DOWNSTAIRCASEX = -1;
    DOWNSTAIRCASEY = -1;
    MapClear();
    clear();
    uint i = 0;
    uint j = 0;
    for ( i = 0; i < width; i++)
    {
        for ( j = 0; j < height; j++)
        {
            MAP[i][j] = TILE_WALL;
            CanChange[i][j] = true;
            if ( i == 0 or j == 0 or i == (uint)(MAP_WIDTH-1) or j == (uint)(MAP_HEIGHT-1))
            {
                CanChange[i][j] = false;
            }
        }
    }
    genangnew = 0;
    uint mi = (width+height) * genstepsrate;
    for ( i = 0; i < mi; i++)
    {
        genact = random( 0, 100);
        if ( genact > 0 && genact <= (100-createroomchance))
        {
            genact = GEN_DIG;
        }else if ( genact > (100-createroomchance))
        {
            genact = GEN_ROOM;
        }
        switch ( genact)
        {
            case (GEN_DIG):
            {
                AngleToDelta( genang);
                dig( genx, geny, deltaX, deltaY);
                break;
            }
            case (GEN_ROOM):
            {
                makeRoom( genx, geny);
                break;
            }
        }
        if ( genangnew > changeangevery)
        {
            if ( random( 0, 2) == 1)
            {
                genang += 90;
            }
            else
            {
                genang -= 90;
            }
            genangnew = 0;
        }
        genangnew++;
    }
    return;
}