path: root/crawl-ref/source/ray.cc

/*
 *  File:       ray.cc
 *  Summary:    Diamond grid wrapper around geom::ray.
 *
 * The geom::grid diamonds is a checkerboard grid rotated
 * by 45 degrees such that the black cells ("diamonds") lie just
 * within the normal crawl map cells.
 *
 * ray_def provides for advancing and reflecting rays in
 * map coordinates, where a ray touches a given cell if it
 * meets the diamond.
 */

#include "AppHdr.h"

#include <cmath>

#include "los.h"
#include "ray.h"
#include "geom2d.h"

static geom::grid diamonds(geom::lineseq(1, 1, 0.5, 1),
                           geom::lineseq(1, -1, -0.5, 1));

static int _ifloor(double d)
{
    return static_cast<int>(floor(d));
}

static int iround(double d)
{
    return static_cast<int>(round(d));
}

static int ifloor(double d)
{
    int r = iround(d);
    if (double_is_zero(d - r))
        return (r);
    else
        return (_ifloor(d));
}

static bool double_is_integral(double d)
{
    return (double_is_zero(d - round(d)));
}

// Is v in the interiour of a diamond?
static bool in_diamond_int(const geom::vector &v)
{
    double d1 = diamonds.ls1.index(v);
    double d2 = diamonds.ls2.index(v);
    return (!double_is_integral(d1) && !double_is_integral(d2)
            && (ifloor(d1) + ifloor(d2)) % 2 == 0);
}

// Is v on a grid line?
static bool on_line(const geom::vector &v)
{
    double d1 = diamonds.ls1.index(v);
    double d2 = diamonds.ls2.index(v);
    return (double_is_integral(d1) || double_is_integral(d2));
}

// Is v an intersection of grid lines?
static bool is_corner(const geom::vector &v)
{
    double d1 = diamonds.ls1.index(v);
    double d2 = diamonds.ls2.index(v);
    return (double_is_integral(d1) && double_is_integral(d2));
}

// Is v in a diamond?
static bool in_diamond(const geom::vector &v)
{
    return (in_diamond_int(v) || is_corner(v));
}

// Is v in the interiour of a non-diamond?
static bool in_non_diamond_int(const geom::vector &v)
{
    // This could instead be done like in_diamond_int.
    return (!in_diamond(v) && !on_line(v));
}

static bool _to_grid(geom::ray *r, bool half);
// Is r on a corner and heading into a non-diamond?
static bool bad_corner(const geom::ray &r)
{
    if (!is_corner(r.start))
        return (false);
    geom::ray copy = r;
    _to_grid(&copy, true);
    return (in_non_diamond_int(copy.start));
}

static coord_def floor_vec(const geom::vector &v)
{
    int x = ifloor(v.x);
    int y = ifloor(v.y);
    return (coord_def(x, y));
}

coord_def ray_def::pos() const
{
    ASSERT(_valid());
    // XXX: pretty arbitrary if we're just on a corner.
    return (floor_vec(r.start));
}

void _round_to_corner(geom::ray *r)
{
    geom::vector v = 2.0 * r->start;
    v.x = round(v.x);
    v.y = round(v.y);
    ASSERT((iround(v.x) + iround(v.y)) % 2 == 1);
    r->start = 0.5 * v;
}

void _round_to_grid(geom::ray *r)
{
    // x + y or x - y is of the form 0.5+k
    geom::vector v = r->start;
    double sum = v.x + v.y - 0.5;
    double diff = v.x - v.y - 0.5;
    double deltas = round(sum) - sum;
    double deltad = round(diff) - diff;
    if (std::abs(deltas) <= std::abs(deltad))
    {
        v.x += 0.5 * deltas;
        v.y += 0.5 * deltas;
    }
    else
    {
        v.x += 0.5 * deltad;
        v.y -= 0.5 * deltad;
    }
    r->start = v;
}

static bool _to_next_cell(geom::ray *r)
{
    bool c = r->to_next_cell(diamonds);
    if (c)
        _round_to_corner(r);
    return (c);
}

static bool _to_grid(geom::ray *r, bool half)
{
    bool c = r->to_grid(diamonds, half);
    if (!half)
        _round_to_grid(r);
    c = c || is_corner(r->start);
    if (c)
        _round_to_corner(r);
    return (c);
}

static bool _advance_from_non_diamond(geom::ray *r)
{
    ASSERT(in_non_diamond_int(r->start));
    if (!_to_next_cell(r))
    {
        ASSERT(in_diamond_int(r->start));
        return (false);
    }
    else
    {
        // r is now on a corner, going from non-diamond to non-diamond.
        ASSERT(is_corner(r->start));
        return (true);
    }
}

// The ray is in a legal state to be passed around externally.
bool ray_def::_valid() const
{
    return (on_corner && is_corner(r.start) && bad_corner(r)
            || !on_corner && in_diamond_int(r.start));
}

geom::vector _normalize(const geom::vector &v)
{
    double n = sqrt(v.x*v.x + v.y*v.y);
    return ((1.0 / n) * v);
}

// Return true if we didn't hit a corner, hence if this
// is a good ray so far.
bool ray_def::advance()
{
    ASSERT(_valid());
    r.dir = _normalize(r.dir);
    if (on_corner)
    {
        ASSERT (is_corner(r.start));
        on_corner = false;
        _to_grid(&r, true);
    }
    else
    {
        // Starting inside a diamond.
        bool c = _to_next_cell(&r);

        if (c)
        {
            // r is now on a corner, going from diamond to diamond.
            _to_grid(&r, true);
            ASSERT(_valid());
            return (true);
        }
    }

    // Now inside a non-diamond.
    ASSERT(in_non_diamond_int(r.start));

    on_corner = _advance_from_non_diamond(&r);
    ASSERT(_valid());
    return (!on_corner);
}

void ray_def::regress()
{
    ASSERT(_valid());
    r.dir = -r.dir;
    advance();
    r.dir = -r.dir;
    ASSERT(_valid());
}

static geom::vector _mirror_pt(const geom::vector &vorig, const coord_def &side)
{
    geom::vector v = vorig;
    if (side.x == -1)
        v.x = 1.0 - v.x;
    if (side.y == -1)
        v.y = 1.0 - v.y;
    return (v);
}

static geom::vector _mirror_dir(const geom::vector &vorig, const coord_def &side)
{
    geom::vector v = vorig;
    if (side.x == -1)
        v.x = -v.x;
    if (side.y == -1)
        v.y = -v.y;
    return (v);
}

static geom::ray _mirror(const geom::ray &rorig, const coord_def &side)
{
    geom::ray r;
    r.start = _mirror_pt(rorig.start, side);
    r.dir = _mirror_dir(rorig.dir, side);
    return (r);
}

static geom::line _choose_reflect_line(bool rx, bool ry, bool rxy)
{
    geom::line l;
    if (rxy)
    {
        if (rx && ry)
        {
            // x + y = 1.5
            l.f = geom::form(1, 1);
            l.val = 1.5;
        }
        else if (!rx && !ry)
        {
            // x + y = 2.5
            l.f = geom::form(1, 1);
            l.val = 2.5;
        }
        else if (rx)
        {
            // x = 1
            l.f = geom::form(1, 0);
            l.val = 1;
        }
        else if (ry)
        {
            // y = 1
            l.f = geom::form(0, 1);
            l.val = 1;
        }
    }
    else if (rx)
    {
        // Flattened corners: y = x - 0.5
        // l.f = geom::form(1, -1);
        // l.val = 0.5;
        // Instead like rxy && rx: x = 1
        l.f = geom::form(1, 0);
        l.val = 1;
    }
    else // ry
    {
        // y = x + 0.5
        // l.f = geom::form(1, -1);
        // l.val = -0.5;
        l.f = geom::form(0, 1);
        l.val = 1;
    }
    return (l);
}

geom::vector _fudge_corner(const geom::vector &w, const reflect_grid &rg)
{
    geom::vector v = w;
    if (double_is_integral(v.x))
    {
        // just try both sides
        v.x += 10 * EPSILON_VALUE;
        if (rg(floor_vec(v)))
            v.x -= 20 * EPSILON_VALUE;
        ASSERT(!rg(floor_vec(v)));
    }
    else
    {
        ASSERT(double_is_integral(v.y));
        v.y += 10 * EPSILON_VALUE;
        if (rg(floor_vec(v)))
            v.y -= 20 * EPSILON_VALUE;
        ASSERT(!rg(floor_vec(v)));
    }
    return (v);
}

// Bounce a ray leaving (0,0) through the positive side
// along a diagonal corridor between (0,1) and (1,0) until
// it's inside (1,1).
geom::ray _bounce_diag_corridor(const geom::ray &rorig)
{
    geom::ray r = rorig;
    geom::form wall(1, -1);
    // The actual walls: geom::line l1(1, -1, 0.5), l2(1, -1, -0.5);
    geom::line k(1, 1, 2.5);
    ASSERT(k.f(r.dir) > 0); // We're actually moving towards k.
    ASSERT(!geom::parallel(r.dir, geom::form(1, -1)));
    // Now bounce back and forth between l1 and l2 until we hit k.
    while (!double_is_zero(geom::intersect(r, k)))
    {
        _to_grid(&r, false);
        r.dir = reflect(r.dir, wall);
    }
    // Now pointing inside the destination cell (1,1) -- move inside.
    _to_grid(&r, true);
    return (r);
}

// Bounce a ray leaving (0,0) properly through one of the sides
// of the diamond.
// r is positioned on the edge already, and side says which
// side this is.
geom::ray _bounce_noncorner(const geom::ray &r, const coord_def &side,
                            const reflect_grid &rg)
{
    // Mirror r to have it leave through the positive side.
    geom::ray rmirr = _mirror(r, side);

    // Determine which of the three relevant cells are bouncy.
    const coord_def dx = coord_def(side.x, 0);
    const coord_def dy = coord_def(0, side.y);
    bool rx  = rg(dx);
    bool ry  = rg(dy);
    bool rxy = rg(dx + dy);
    // One of the three neighbours on this side must be bouncy.
    ASSERT(rx || ry || rxy);

    // Now go through the cases separately.
    if (rx && ry && !rxy)
    {
        rmirr = _bounce_diag_corridor(rmirr);
    }
    else
    {
        // These all reduce to reflection at one line.
        geom::line l = _choose_reflect_line(rx, ry, rxy);

        double t = intersect(rmirr, l);
        ASSERT(double_is_zero(t) || t >= 0);
        rmirr.advance(t);
        rmirr.dir = geom::reflect(rmirr.dir, l.f);
        if (bad_corner(rmirr))
        {
            // Really want to stay and set on_corner.
            // But then pos() might be a solid cell.
            geom::vector v = _mirror_pt(rmirr.start, side);
            v = _fudge_corner(v, rg);
            rmirr.start = _mirror_pt(v, side);
        }
        else
        {
            // Depending on the case, we're on some diamond edge
            // or between diamonds. We'll just move safely into
            // the next one.
            _to_grid(&rmirr, true);
            if (in_non_diamond_int(rmirr.start))
                _advance_from_non_diamond(&rmirr);
        }
    }

    // Mirror back.
    return (_mirror(rmirr, side));
}

geom::form _corner_wall(const coord_def &side, const reflect_grid &rg)
{
    coord_def e;
    if (side.x == 0)
        e = coord_def(1, 0);
    else
        e = coord_def(0, 1);
    ASSERT(!rg(coord_def(0,0)) && rg(side));
    // Reflect back by an orthogonal wall...
    coord_def wall = e;
    // unless the wall is clearly diagonal:
    //  ##.
    //  #*.  (with side.y == -1)
    if (rg(e) && rg(side+e) && !rg(-e) && !rg(side-e))
    {
        // diagonal wall through side and e
        wall = side - e;
    }
    else if (rg(-e) && rg(side-e) && !rg(e) && !rg(side+e))
    {
        // diagonal wall through side and -e
        wall = side + e;
    }
    return (geom::form(wall.y, -wall.x));
}

// Bounce a ray that leaves cell (0,0) through a corner. We could
// just fudge it a little, but want to be consistent for rays
// shot in cardinal directions.
geom::ray _bounce_corner(const geom::ray &rorig, const coord_def &side,
                         const reflect_grid &rg)
{
    geom::ray r = rorig;
    geom::form f = _corner_wall(side, rg);

    if (r.dir.x == 0 || r.dir.y == 0)
    {
        // To keep cardinal rays nicely in the middle,
        // we reflect them earlier.
        r.start.x = r.start.y = 0.5;
        r.dir = geom::reflect(r.dir, f);
        ASSERT(r.dir.x == 0 || r.dir.y == 0);
    }
    else
    {
        // Others are reflected at the corner.
        r.dir = geom::reflect(r.dir, f);
        if (f.a != 0 && f.b != 0)
        {
            // Diagonal wall: to the next diamond, then inside.
            _to_grid(&r, false);
            _to_grid(&r, true);
        }
        else
        {
            // Back inside diamond (0,0).
            _to_grid(&r, true);
        }
    }
    return (r);
}

void ray_def::bounce(const reflect_grid &rg)
{
    ASSERT(_valid());
    ASSERT(!rg(coord_def(0,0))); // The cell we bounce from is not solid.
#ifdef DEBUG
    const coord_def old_pos = pos();
#endif

    // Translate to cell (0,0).
    geom::vector p(pos().x, pos().y);
    geom::ray rtrans;
    rtrans.start = r.start - p;
    rtrans.dir = r.dir;

    if (on_corner)
    {
        // Move a little bit towards cell center (0.5, 0.5).
       rtrans.start = 0.9 * rtrans.start + 0.1 * geom::vector(0.5, 0.5);
       on_corner = false;
       ASSERT(in_diamond_int(rtrans.start));
    }

    // Move to the diamond edge to determine the side.
    coord_def side;
    bool corner = _to_grid(&rtrans, false);
    double d1 = diamonds.ls1.index(rtrans.start);
    if (double_is_integral(d1))
        side += iround(d1) ? coord_def(1,1) : coord_def(-1,-1);
    double d2 = diamonds.ls2.index(rtrans.start);
    if (double_is_integral(d2))
        side += iround(d2) ? coord_def(1,-1) : coord_def(-1,1);
    ASSERT(corner == (side.x == 0 || side.y == 0));

    // In the corner case, we have side == (+-2, 0) or (0, +-2); reduce:
    if (corner)
    {
        side.x = side.x / 2;
        side.y = side.y / 2;
    }

    if (corner)
        rtrans = _bounce_corner(rtrans, side, rg);
    else
        rtrans = _bounce_noncorner(rtrans, side, rg);

    // Translate back.
    r.start = rtrans.start + p;
    r.dir = rtrans.dir;

    // Set on_corner if we happen to have ended up on a corner.
    on_corner = is_corner(r.start);

    ASSERT(_valid());
    ASSERT(!rg(pos() - old_pos));
}

double ray_def::get_degrees() const
{
    return (geom::degrees(r.dir));
}

void ray_def::set_degrees(double d)
{
    r.dir = geom::degree_to_vector(d);
}