fiddlerwoaroof/crawl - Change BLJ6YULKT57MKKU3KUKMS7HITS2CDUFPZ4U6EQHBGLGQ7O7GUSLAC

Rewrite cellray comparison; parametrize precomputations.

There are now defines LOS_MAX_ANGLE and LOS_INTERCEPT_MULT that determine what rays are cast in the precomputation. Current values should be the minimal correct ones.

Also check subray relationship both directions at once.

Created by Robert Vollmert on October 13, 2009

BLJ6YULKT57MKKU3KUKMS7HITS2CDUFPZ4U6EQHBGLGQ7O7GUSLAC

Dependencies

In channels

main

Change contents

Insertion in crawl-ref/source/los.cc at line 63 [3.26450]

[3.26922]


// These determine what rays are cast in the precomputation,
// and affect start-up time significantly.
// XXX: Argue that these values are sufficient.
#define LOS_MAX_ANGLE (2*LOS_MAX_RANGE-2)
#define LOS_INTERCEPT_MULT (2)

Deletion in crawl-ref/source/los.cc at line 75 [3.26450]
B:BD[3.27239] → [3.27239:27240]
Deletion in crawl-ref/source/los.cc at line 196 [3.26450]
B:BD[3.29247] → [2.3036:3037]
∅:D[2.3037] → [3.29247:29301]
B:BD[3.29247] → [3.29247:29301]
B:BD[3.29301] → [4.4748:4821]
∅:D[4.4821] → [3.29376:29520]
B:BD[3.29376] → [3.29376:29520]
B:BD[3.29520] → [4.4822:4875]
∅:D[5.3592] → [3.29571:29599]
∅:D[4.4875] → [3.29571:29599]
B:BD[3.29571] → [3.29571:29599]
B:BD[3.29599] → [4.4876:4929]
∅:D[5.3644] → [3.29650:29678]
∅:D[4.4929] → [3.29650:29678]
B:BD[3.29650] → [3.29650:29678]
```
// Is starta...lengtha a subset of startb...lengthb?
static bool _is_subset(int starta, int startb, int lengtha, int lengthb)
{
    int cura = starta, curb = startb;
    int enda = starta + lengtha, endb = startb + lengthb;
    while (cura < enda && curb < endb)
    {
        if (ray_coords[curb].x > ray_coords[cura].x)
            return (false);
        if (ray_coords[curb].y > ray_coords[cura].y)
            return (false);
```
Deletion in crawl-ref/source/los.cc at line 197 [3.26450]
B:BD[3.29679] → [4.4930:5001]
∅:D[4.5001] → [3.29825:29826]
B:BD[3.29825] → [3.29825:29826]
B:BD[3.29826] → [4.5002:5019]
∅:D[4.5019] → [3.29842:29879]
B:BD[3.29842] → [3.29842:29879]
```
        if (ray_coords[cura] == ray_coords[curb])
             ++cura;
         ++curb;
    }
    return (cura == enda);
}
```

Replacement in crawl-ref/source/los.cc at line 203 [3.26450]

B:BD[2.3130] → [2.3130:3207]

    cellray(const los_ray& r, int l)
        : ray(r), length(l)
    {
    }

[2.3130]

[2.3207]

    cellray(const los_ray& r, int l) : ray(r), length(l) {}

Replacement in crawl-ref/source/los.cc at line 205 [3.26450]

B:BD[2.3208] → [2.3208:3352]

    int index() const
    {
        return ray.start + length;
    }
    coord_def end() const
    {
        return ray_coords[index()];
    }

[2.3208]

[2.3352]

    int index() const { return ray.start + length; }
    coord_def end() const { return ray_coords[index()]; }

Insertion in crawl-ref/source/los.cc at line 216 [3.26450]

[2.3424]

// Check whether one of the passed cellrays is a subray of the
// other in terms of footprint.

Replacement in crawl-ref/source/los.cc at line 222 [3.26450]

B:BD[2.3547] → [2.3547:3704]

    if (_is_subset(a.ray.start, b.ray.start, a.length, b.length))
        return C_SUBRAY;
    if (_is_subset(b.ray.start, a.ray.start, b.length, a.length))

[2.3547]

[2.3704]


    int cura = a.ray.start;
    int curb = b.ray.start;
    int enda = cura + a.length;
    int endb = curb + b.length;
    bool maybe_sub = true;
    bool maybe_super = true;
    while (cura < enda && curb < endb && (maybe_sub || maybe_super))
    {
        coord_def pa = ray_coords[cura];
        coord_def pb = ray_coords[curb];
        if (pa.x > pb.x || pa.y > pb.y)
        {
            maybe_super = false;
            curb++;
        }
        if (pa.x < pb.x || pa.y < pb.y)
        {
            maybe_sub = false;
            cura++;
        }
        if (pa == pb)
        {
            cura++;
            curb++;
        }
    }
    maybe_sub = maybe_sub && (cura == enda);
    maybe_super = maybe_super && (curb == endb);
    if (maybe_sub)
        return C_SUBRAY;    // includes equality
    else if (maybe_super)

Replacement in crawl-ref/source/los.cc at line 421 [3.26450]

B:BD[3.37044] → [6.3179:3307]

    for (int xangle = 1; xangle <= 2*LOS_MAX_RANGE; ++xangle)
        for (int yangle = 1; yangle <= 2*LOS_MAX_RANGE; ++yangle)

[3.37044]

[3.37176]

    for (int xangle = 1; xangle <= LOS_MAX_ANGLE; ++xangle)
        for (int yangle = 1; yangle <= LOS_MAX_ANGLE; ++yangle)

Replacement in crawl-ref/source/los.cc at line 436 [3.26450]

B:BD[3.37654] → [7.4978:5047]

        for (int intercept = 1; intercept <= 2*yangle; ++intercept )

[3.37654]

[3.37724]

        for (int intercept = 1; intercept <= LOS_INTERCEPT_MULT*yangle; ++intercept )

Replacement in crawl-ref/source/los.cc at line 438 [3.26450]

B:BD[3.37734] → [8.5050:5112]

            double xstart = ((double)intercept) / (2*yangle);

[3.37734]

[3.37798]

            double xstart = ((double)intercept) / (LOS_INTERCEPT_MULT*yangle);