fiddlerwoaroof/crawl - Change ACZYEIX7WMPIIODKCATBCUE626AJ4ZGGBOMVC6BGXM27EQU2RECAC

Split LOS code from view.cc.

los.cc: basic raycasting algorithm; losight(), see_grid() etc. ray.cc: ray_def implementation. mon-los.cc: monster_los

This includes adding a bunch of #includes; there's probably some obsolete includes of view.h now.

Created by Robert Vollmert on October 8, 2009

ACZYEIX7WMPIIODKCATBCUE626AJ4ZGGBOMVC6BGXM27EQU2RECAC

Dependencies

In channels

main

Change contents

Insertion in crawl-ref/source/xom.cc at line 21 [13.3]
[11.23]
[13.287]
```
#include "los.h"
```
Deletion in crawl-ref/source/view.h at line 71 [15.13254]
∅:D[14.67] → [15.14492:14493]
∅:D[16.432] → [15.14492:14493]
B:BD[15.14492] → [15.14492:14493]
B:BD[15.14493] → [17.5:32]
∅:D[17.32] → [18.6:56]
B:BD[15.14720] → [18.6:56]
B:BD[18.56] → [19.6:76]
B:BD[19.76] → [5.6:48]
∅:D[5.48] → [15.14829:14830]
∅:D[20.69] → [15.14829:14830]
∅:D[21.70] → [15.14829:14830]
∅:D[19.118] → [15.14829:14830]
∅:D[22.128] → [15.14829:14830]
∅:D[23.179] → [15.14829:14830]
B:BD[15.14829] → [15.14829:14830]
```
void clear_rays_on_exit();
void losight(env_show_grid &sh, feature_grid &gr,
             const coord_def& center, bool clear_walls_block = false,
             bool ignore_clouds = false);
```

Deletion in crawl-ref/source/view.h at line 176 [15.13254]

B:BD[24.940] → [18.57:302]

B:BD[18.302] → [22.449:510]

∅:D[22.510] → [25.73:137]

B:BD[25.73] → [25.73:137]

bool see_grid( const env_show_grid &show,
               const coord_def &c,
               const coord_def &pos );
bool see_grid(const coord_def &p);
bool see_grid_no_trans( const coord_def &p );
bool trans_wall_blocking( const coord_def &p );
bool grid_see_grid(const coord_def& p1, const coord_def& p2,
                   dungeon_feature_type allowed = DNGN_UNSEEN);

Deletion in crawl-ref/source/view.h at line 177 [15.13254]
∅:D[26.54] → [24.975:976]
∅:D[27.77] → [24.975:976]
∅:D[25.137] → [24.975:976]
∅:D[18.302] → [24.975:976]
B:BD[24.975] → [24.975:976]
B:BD[24.976] → [18.303:344]
∅:D[18.344] → [20.164:166]
B:BD[20.164] → [20.164:166]
B:BD[20.166] → [18.345:483]
∅:D[18.483] → [20.206:209]
B:BD[20.206] → [20.206:209]
B:BD[20.209] → [18.484:583]
```
inline bool see_grid( int grx, int gry )
{
    return see_grid(coord_def(grx, gry));
}
inline bool see_grid_no_trans(int x, int y)
{
    return see_grid_no_trans(coord_def(x, y));
}
inline bool trans_wall_blocking(int x, int y)
{
    return trans_wall_blocking(coord_def(x, y));
}
```
Deletion in crawl-ref/source/view.h at line 191 [15.13254]
B:BD[28.145] → [4.6:28]
```
void calc_show_los();
```

Deletion in crawl-ref/source/view.h at line 195 [15.13254]

∅:D[29.32] → [24.1167:1168]

∅:D[30.36] → [24.1167:1168]

∅:D[31.38] → [24.1167:1168]

∅:D[32.51] → [24.1167:1168]

B:BD[24.1167] → [24.1167:1168]

B:BD[24.1168] → [33.2016:2032]

B:BD[33.2032] → [22.511:576]

∅:D[22.576] → [34.5:74]

B:BD[24.1235] → [34.5:74]

B:BD[34.74] → [20.257:330]

B:BD[20.330] → [22.577:649]

∅:D[22.649] → [20.404:510]

B:BD[20.404] → [20.404:510]

B:BD[20.510] → [35.6:107]


struct ray_def;
bool find_ray( const coord_def& source, const coord_def& target,
               bool allow_fallback, ray_def& ray, int cycle_dir = 0,
               bool find_shortest = false, bool ignore_solid = false );
int num_feats_between(const coord_def& source, const coord_def& target,
                      dungeon_feature_type min_feat,
                      dungeon_feature_type max_feat,
                      bool exclude_endpoints = true,
                      bool just_check = false);

Deletion in crawl-ref/source/view.h at line 204 [15.13254]

B:BD[15.16784] → [36.6:55]

∅:D[36.55] → [37.6:378]

B:BD[15.16784] → [37.6:378]

B:BD[37.378] → [38.6:86]

∅:D[38.86] → [39.6:37]

B:BD[37.378] → [39.6:37]

∅:D[39.37] → [37.378:442]

B:BD[37.378] → [37.378:442]

B:BD[37.442] → [38.87:162]

∅:D[38.162] → [37.442:563]

B:BD[37.442] → [37.442:563]

∅:D[37.563] → [24.1440:1441]

B:BD[15.16784] → [24.1440:1441]

B:BD[24.1441] → [37.564:827]

B:BD[37.827] → [36.56:84]

∅:D[36.84] → [37.876:877]

B:BD[37.876] → [37.876:877]

B:BD[37.877] → [36.85:181]

∅:D[36.181] → [37.988:1307]

B:BD[37.988] → [37.988:1307]

B:BD[37.1307] → [39.38:105]

∅:D[39.105] → [37.1307:1350]

B:BD[37.1307] → [37.1307:1350]

B:BD[37.1350] → [36.182:241]

∅:D[36.241] → [37.1383:1386]

B:BD[37.1383] → [37.1383:1386]


#define _monster_los_LSIZE (2 * LOS_RADIUS + 1)
// This class can be used to fill the entire surroundings (los_range)
// of a monster or other position with seen/unseen values, so as to be able
// to compare several positions within this range.
class monster_los
{
public:
    monster_los();
    virtual ~monster_los();
    // public methods
    void set_monster(monsters *mon);
    void set_los_centre(int x, int y);
    void set_los_centre(const coord_def& p) { this->set_los_centre(p.x, p.y); }
    void set_los_range(int r);
    void fill_los_field(void);
    bool in_sight(int x, int y);
    bool in_sight(const coord_def& p) { return this->in_sight(p.x, p.y); }
protected:
    // protected methods
    coord_def pos_to_index(coord_def &p);
    coord_def index_to_pos(coord_def &i);
    void set_los_value(int x, int y, bool blocked, bool override = false);
    int get_los_value(int x, int y);
    bool is_blocked(int x, int y);
    bool is_unknown(int x, int y);
    void check_los_beam(int dx, int dy);
    // The (fixed) size of the array.
    static const int LSIZE;
    static const int L_VISIBLE;
    static const int L_UNKNOWN;
    static const int L_BLOCKED;
    // The centre of our los field.
    int gridx, gridy;
    // Habitat checks etc. should be done for this monster.
    // Usually the monster whose LOS we're trying to calculate
    // (if mon->x == gridx, mon->y == gridy).
    // Else, any monster trying to move around within this los field.
    monsters *mons;
    // Range may never be greater than LOS_RADIUS!
    int range;
    // The array to store the LOS values.
    int los_field[_monster_los_LSIZE][_monster_los_LSIZE];
};

Insertion in crawl-ref/source/view.cc at line 38 [15.16817]
[24.1556]
[40.6]
```
#include "los.h"
```

Deletion in crawl-ref/source/view.cc at line 82 [15.16817]

B:BD[24.2576] → [9.50:200]

∅:D[9.200] → [36.390:564]

B:BD[36.390] → [36.390:564]

// Static class members must be initialised outside of the class
// declaration, or gcc won't define them in view.o and we'll get a
// linking error.
const int monster_los::LSIZE     =  _monster_los_LSIZE;
const int monster_los::L_VISIBLE =  1;
const int monster_los::L_UNKNOWN =  0;
const int monster_los::L_BLOCKED = -1;

Deletion in crawl-ref/source/view.cc at line 1924 [15.16817]

B:BD[41.1390] → [41.1390:1444]

∅:D[41.1444] → [42.3291:3307]

∅:D[22.2046] → [42.3291:3307]

B:BD[42.3291] → [42.3291:3307]

B:BD[42.3307] → [22.2047:2049]

∅:D[22.2049] → [42.3335:3336]

B:BD[42.3335] → [42.3335:3336]

B:BD[42.3336] → [2.7:53]

∅:D[2.53] → [15.59042:59043]

∅:D[24.14031] → [15.59042:59043]

B:BD[15.59042] → [15.59042:59043]

B:BD[15.59043] → [24.14032:14151]

∅:D[24.14151] → [15.59142:59214]

B:BD[15.59142] → [15.59142:59214]

B:BD[15.59214] → [24.14152:14222]

∅:D[24.14222] → [15.59285:59550]

B:BD[15.59285] → [15.59285:59550]

B:BD[15.59625] → [15.59625:59626]

B:BD[15.59626] → [24.14223:14292]

∅:D[24.14292] → [15.59858:59859]

B:BD[15.59858] → [15.59858:59859]

B:BD[15.59859] → [24.14293:14330]

B:BD[24.14330] → [17.34:108]

∅:D[43.39] → [24.14363:14561]

∅:D[17.108] → [24.14363:14561]

B:BD[24.14363] → [24.14363:14561]

B:BD[24.14561] → [17.109:217]

∅:D[17.217] → [15.59902:59903]

∅:D[24.14561] → [15.59902:59903]

B:BD[15.59902] → [15.59902:59903]

B:BD[15.59903] → [24.14562:14591]

∅:D[24.14591] → [15.59921:59923]

B:BD[15.59921] → [15.59921:59923]

B:BD[15.59923] → [24.14592:14638]

∅:D[24.14638] → [15.60052:60055]

B:BD[15.60052] → [15.60052:60055]

B:BD[15.60055] → [24.14639:14706]

∅:D[24.14706] → [15.60081:60083]

B:BD[15.60081] → [15.60081:60083]

B:BD[15.60083] → [24.14707:14834]

B:BD[24.14834] → [44.3509:3578]

∅:D[44.3578] → [45.136:138]

B:BD[45.136] → [45.136:138]

∅:D[45.138] → [24.14904:15015]

B:BD[24.14904] → [24.14904:15015]

∅:D[24.15015] → [15.60357:60358]

B:BD[15.60357] → [15.60357:60358]

B:BD[15.60358] → [24.15016:15142]

∅:D[24.15142] → [15.60376:60379]

B:BD[15.60376] → [15.60376:60379]

B:BD[15.60379] → [24.15143:15267]

B:BD[24.15267] → [44.3579:3659]

∅:D[44.3659] → [15.60405:60407]

∅:D[24.15346] → [15.60405:60407]

B:BD[15.60405] → [15.60405:60407]

B:BD[15.60628] → [15.60628:60629]

B:BD[15.60629] → [24.15347:15538]

∅:D[24.15538] → [15.60649:60650]

B:BD[15.60649] → [15.60649:60650]

B:BD[15.60650] → [46.5:121]

∅:D[46.121] → [24.15649:15741]

B:BD[24.15649] → [24.15649:15741]

B:BD[24.15741] → [47.6:61]

∅:D[47.61] → [24.15802:15823]

B:BD[24.15802] → [24.15802:15823]

B:BD[24.15823] → [45.139:183]

∅:D[45.183] → [24.15863:15909]

B:BD[24.15863] → [24.15863:15909]

B:BD[24.15909] → [45.184:221]

∅:D[45.221] → [24.15938:16054]

B:BD[24.15938] → [24.15938:16054]

B:BD[24.16054] → [45.222:245]

∅:D[45.245] → [24.16069:16209]

B:BD[24.16069] → [24.16069:16209]

∅:D[24.16209] → [15.60725:60726]

B:BD[15.60725] → [15.60725:60726]

B:BD[15.60726] → [47.62:90]

∅:D[47.90] → [24.16210:16250]

B:BD[15.60726] → [24.16210:16250]

B:BD[24.16250] → [45.246:278]

∅:D[45.278] → [24.16278:16340]

B:BD[24.16278] → [24.16278:16340]

B:BD[24.16340] → [45.279:294]

∅:D[45.294] → [24.16351:16405]

B:BD[24.16351] → [24.16351:16405]

∅:D[24.16405] → [15.60874:60875]

B:BD[15.60874] → [15.60874:60875]

B:BD[15.60875] → [47.91:298]

∅:D[47.298] → [15.60918:60919]

∅:D[24.16446] → [15.60918:60919]

B:BD[15.60918] → [15.60918:60919]

B:BD[15.60919] → [24.16447:16520]

B:BD[24.16520] → [34.139:142]

B:BD[34.142] → [48.6:115]

∅:D[48.115] → [34.142:288]

B:BD[34.142] → [34.142:288]

B:BD[34.288] → [49.6:57]

∅:D[49.57] → [34.337:389]

B:BD[34.337] → [34.337:389]

B:BD[34.389] → [49.58:134]

∅:D[49.134] → [34.445:1192]

B:BD[34.445] → [34.445:1192]

∅:D[34.1192] → [24.16520:16522]

B:BD[24.16520] → [24.16520:16522]

∅:D[24.16522] → [15.60999:61000]

B:BD[15.60999] → [15.60999:61000]

B:BD[15.61000] → [24.16523:16558]

∅:D[24.16558] → [15.61084:61086]

B:BD[15.61084] → [15.61084:61086]

B:BD[15.61086] → [24.16559:16623]

B:BD[24.16623] → [45.295:328]

∅:D[45.328] → [24.16652:16750]

B:BD[24.16652] → [24.16652:16750]

B:BD[24.16750] → [34.1193:1242]

B:BD[34.1242] → [50.6:35]

∅:D[50.35] → [24.16774:16852]

∅:D[34.1270] → [24.16774:16852]

B:BD[24.16774] → [24.16774:16852]

B:BD[24.16852] → [34.1271:1390]

B:BD[34.1390] → [51.227:228]

∅:D[51.228] → [24.16852:17082]

∅:D[34.1395] → [24.16852:17082]

B:BD[24.16852] → [24.16852:17082]

B:BD[24.17196] → [24.17196:17428]

B:BD[24.17428] → [34.1396:1474]

B:BD[34.1474] → [52.7:1402]

∅:D[52.1402] → [24.17443:17445]

∅:D[34.1474] → [24.17443:17445]

B:BD[24.17443] → [24.17443:17445]

∅:D[24.17445] → [15.61100:61101]

B:BD[15.61100] → [15.61100:61101]

B:BD[15.61101] → [53.6:30]

∅:D[53.30] → [24.17470:17553]

∅:D[34.1521] → [24.17470:17553]

B:BD[24.17470] → [24.17470:17553]

B:BD[24.17553] → [53.31:51]

∅:D[53.51] → [24.17568:17609]

∅:D[34.1549] → [24.17568:17609]

B:BD[24.17568] → [24.17568:17609]

∅:D[24.17609] → [15.61210:61211]

B:BD[15.61210] → [15.61210:61211]

B:BD[15.61211] → [34.1550:1778]

B:BD[34.1778] → [51.229:230]

B:BD[51.230] → [9.201:272]

∅:D[9.272] → [34.1854:1906]

B:BD[34.1854] → [34.1854:1906]

B:BD[34.1906] → [51.231:232]

∅:D[51.232] → [49.135:208]

B:BD[34.1911] → [49.135:208]

∅:D[49.208] → [34.1948:2056]

B:BD[34.1948] → [34.1948:2056]

B:BD[34.2056] → [51.233:234]

∅:D[51.234] → [34.2061:2140]

B:BD[34.2061] → [34.2061:2140]

B:BD[34.2140] → [49.209:289]

∅:D[49.289] → [34.2184:2424]

B:BD[34.2184] → [34.2184:2424]

∅:D[34.2424] → [24.17633:17717]

B:BD[24.17633] → [24.17633:17717]

B:BD[24.17717] → [44.3660:3718]

∅:D[44.3718] → [24.17774:17882]

B:BD[24.17774] → [24.17774:17882]

B:BD[24.17882] → [44.3719:3779]

∅:D[44.3779] → [24.17939:18145]

B:BD[24.17939] → [24.17939:18145]

B:BD[24.18145] → [44.3780:3840]

∅:D[44.3840] → [24.18202:18252]

B:BD[24.18202] → [24.18202:18252]

B:BD[24.18252] → [51.235:285]

∅:D[51.285] → [24.18310:18417]

B:BD[24.18310] → [24.18310:18417]

B:BD[24.18417] → [44.3841:3901]

B:BD[44.3901] → [51.286:336]

∅:D[51.336] → [24.18532:18591]

B:BD[24.18532] → [24.18532:18591]

∅:D[24.18591] → [15.61296:61297]

B:BD[15.61296] → [15.61296:61297]

B:BD[15.61297] → [24.18592:18831]

B:BD[24.18831] → [44.3902:4033]

∅:D[44.4033] → [24.18960:18999]

B:BD[24.18960] → [24.18960:18999]

B:BD[24.18999] → [54.244:283]

∅:D[54.283] → [24.19040:19046]

B:BD[24.19040] → [24.19040:19046]

B:BD[24.19046] → [44.4034:4087]

∅:D[44.4087] → [46.122:200]

B:BD[24.19098] → [46.122:200]

B:BD[46.200] → [10.6:62]

∅:D[10.62] → [24.19204:19223]

∅:D[54.332] → [24.19204:19223]

B:BD[24.19204] → [24.19204:19223]

∅:D[24.19223] → [15.61393:61394]

B:BD[15.61393] → [15.61393:61394]

B:BD[15.61394] → [54.333:370]

∅:D[54.370] → [24.19260:19349]

B:BD[24.19260] → [24.19260:19349]

B:BD[24.19349] → [54.371:424]

∅:D[54.424] → [44.4088:4153]

B:BD[24.19401] → [44.4088:4153]

∅:D[44.4153] → [24.19465:19491]

B:BD[24.19465] → [24.19465:19491]

B:BD[24.19491] → [54.425:482]

∅:D[54.482] → [15.61494:61500]

∅:D[24.19550] → [15.61494:61500]

B:BD[15.61494] → [15.61494:61500]

B:BD[15.61500] → [54.483:560]

∅:D[54.560] → [15.61555:61565]

∅:D[24.19629] → [15.61555:61565]

B:BD[15.61555] → [15.61555:61565]

B:BD[15.61565] → [24.19630:19671]

∅:D[24.19671] → [15.61599:61632]

B:BD[15.61599] → [15.61599:61632]

B:BD[15.61632] → [24.19672:19687]

B:BD[24.19687] → [54.561:595]

∅:D[54.595] → [15.61669:61679]

∅:D[24.19723] → [15.61669:61679]

B:BD[15.61669] → [15.61669:61679]

B:BD[15.61679] → [44.4154:4282]

∅:D[44.4282] → [15.61915:61938]

∅:D[24.19841] → [15.61915:61938]

B:BD[15.61915] → [15.61915:61938]

B:BD[15.61938] → [44.4283:4297]

∅:D[44.4297] → [15.61952:61962]

B:BD[15.61952] → [15.61952:61962]

B:BD[15.61962] → [24.19842:19843]

B:BD[24.19843] → [54.596:673]

∅:D[54.673] → [24.19920:19921]

B:BD[24.19920] → [24.19920:19921]

B:BD[24.19921] → [54.674:716]

∅:D[54.716] → [24.19962:19999]

B:BD[24.19962] → [24.19962:19999]

∅:D[24.19999] → [15.61962:61968]

B:BD[15.61962] → [15.61962:61968]

B:BD[15.61968] → [54.717:737]

∅:D[54.737] → [15.61968:61971]

∅:D[24.20018] → [15.61968:61971]

B:BD[15.61968] → [15.61968:61971]

B:BD[15.61971] → [54.738:791]

∅:D[54.791] → [44.4298:4373]

B:BD[24.20072] → [44.4298:4373]

∅:D[44.4373] → [15.62008:62010]

∅:D[24.20146] → [15.62008:62010]

B:BD[15.62008] → [15.62008:62010]

B:BD[15.62010] → [24.20147:20243]

B:BD[24.20243] → [54.792:832]

∅:D[54.832] → [24.20284:20290]

B:BD[24.20284] → [24.20284:20290]

B:BD[24.20290] → [54.833:1108]

∅:D[54.1108] → [24.20557:20577]

B:BD[24.20557] → [24.20557:20577]

B:BD[24.20577] → [54.1109:1119]

∅:D[54.1119] → [15.62139:62140]

∅:D[24.20577] → [15.62139:62140]

B:BD[15.62139] → [15.62139:62140]

B:BD[15.62140] → [24.20578:20600]

B:BD[24.20600] → [54.1120:1148]

∅:D[54.1148] → [24.20629:20631]

B:BD[24.20629] → [24.20629:20631]

∅:D[24.20631] → [15.62287:62288]

B:BD[15.62287] → [15.62287:62288]

B:BD[15.62288] → [54.1149:1219]

∅:D[54.1219] → [44.4374:4424]

B:BD[24.20700] → [44.4374:4424]

∅:D[44.4424] → [24.20749:20751]

B:BD[24.20749] → [24.20749:20751]

B:BD[24.20751] → [54.1220:1349]

∅:D[54.1349] → [24.20879:20993]

B:BD[24.20879] → [24.20879:20993]

B:BD[24.20993] → [44.4425:4458]

∅:D[44.4458] → [46.201:256]

B:BD[24.21022] → [46.201:256]

∅:D[46.256] → [24.21064:21188]

B:BD[24.21064] → [24.21064:21188]

B:BD[24.21188] → [54.1350:1408]

∅:D[54.1408] → [24.21246:21280]

B:BD[24.21246] → [24.21246:21280]

B:BD[24.21280] → [54.1409:1473]

∅:D[54.1473] → [24.21343:21686]

B:BD[24.21343] → [24.21343:21686]

B:BD[24.21686] → [54.1474:1614]

∅:D[54.1614] → [24.21827:21987]

B:BD[24.21827] → [24.21827:21987]

B:BD[24.21987] → [54.1615:1724]

∅:D[54.1724] → [24.22097:22128]

B:BD[24.22097] → [24.22097:22128]

B:BD[24.22128] → [54.1725:1812]

∅:D[54.1812] → [24.22216:22238]

B:BD[24.22216] → [24.22216:22238]

B:BD[24.22238] → [44.4459:4596]

∅:D[44.4596] → [24.22373:22444]

B:BD[24.22373] → [24.22373:22444]

B:BD[24.22444] → [54.1813:1917]

∅:D[54.1917] → [24.22549:22563]

B:BD[24.22549] → [24.22549:22563]

B:BD[24.22563] → [54.1918:1949]

∅:D[54.1949] → [24.22596:22683]

B:BD[24.22596] → [24.22596:22683]

∅:D[24.22683] → [15.62306:62309]

B:BD[15.62306] → [15.62306:62309]

B:BD[15.62309] → [24.22684:22816]

B:BD[24.22816] → [44.4597:4665]

∅:D[44.4665] → [15.62346:62348]

∅:D[24.22883] → [15.62346:62348]

B:BD[15.62346] → [15.62346:62348]

B:BD[15.62348] → [24.22884:22950]

B:BD[24.22950] → [44.4666:4743]

∅:D[44.4743] → [15.62462:62463]

∅:D[24.23026] → [15.62462:62463]

B:BD[15.62462] → [15.62462:62463]

B:BD[15.62463] → [54.1950:2061]

∅:D[54.2061] → [15.62507:62508]

∅:D[24.23136] → [15.62507:62508]

B:BD[15.62507] → [15.62507:62508]

B:BD[15.62508] → [54.2062:2131]

∅:D[54.2131] → [24.23207:23213]

B:BD[24.23207] → [24.23207:23213]

B:BD[24.23213] → [54.2132:2164]

∅:D[54.2164] → [24.23244:23331]

B:BD[24.23244] → [24.23244:23331]

B:BD[24.23331] → [54.2165:2194]

∅:D[54.2194] → [24.23359:23527]

B:BD[24.23359] → [24.23359:23527]

B:BD[24.23527] → [54.2195:2214]

∅:D[54.2214] → [15.62563:62566]

∅:D[24.23544] → [15.62563:62566]

B:BD[15.62563] → [15.62563:62566]

B:BD[15.62566] → [44.4794:4826]

∅:D[44.4826] → [15.62991:62993]

∅:D[24.23576] → [15.62991:62993]

B:BD[15.62991] → [15.62991:62993]

B:BD[15.62993] → [24.23577:23613]

B:BD[24.23613] → [44.4827:4965]

∅:D[44.4965] → [24.23746:23978]

B:BD[24.23746] → [24.23746:23978]

∅:D[24.23978] → [15.63228:63229]

B:BD[15.63228] → [15.63228:63229]

B:BD[15.63229] → [24.23979:24366]

∅:D[24.24366] → [15.63291:63292]

B:BD[15.63291] → [15.63291:63292]

B:BD[15.63292] → [24.24367:24391]

∅:D[24.24391] → [15.63423:63424]

B:BD[15.63423] → [15.63423:63424]

B:BD[15.63424] → [17.218:281]

∅:D[17.281] → [15.63489:63495]

∅:D[24.24457] → [15.63489:63495]

B:BD[15.63489] → [15.63489:63495]

B:BD[15.63495] → [17.282:332]

∅:D[17.332] → [24.24510:24748]

B:BD[24.24510] → [24.24510:24748]

∅:D[24.24748] → [15.63520:63521]

B:BD[15.63520] → [15.63520:63521]

B:BD[15.63521] → [24.24749:24790]

B:BD[24.24790] → [17.333:389]

∅:D[17.389] → [44.4966:5031]

B:BD[24.24848] → [44.4966:5031]

∅:D[44.5031] → [15.63664:63665]

∅:D[24.24912] → [15.63664:63665]

B:BD[15.63664] → [15.63664:63665]

B:BD[15.63665] → [24.24913:25511]

B:BD[24.25511] → [17.390:446]

∅:D[17.446] → [24.25569:25800]

B:BD[24.25569] → [24.25569:25800]

B:BD[24.25800] → [17.447:545]

∅:D[17.545] → [15.63709:63719]

∅:D[24.25908] → [15.63709:63719]

B:BD[15.63709] → [15.63709:63719]

B:BD[15.63719] → [17.546:682]

∅:D[17.682] → [44.5032:5087]

B:BD[24.26049] → [44.5032:5087]

B:BD[44.5087] → [51.337:338]

∅:D[51.338] → [24.26103:26187]

∅:D[44.5108] → [24.26103:26187]

B:BD[24.26103] → [24.26103:26187]

B:BD[24.26193] → [24.26193:26242]

B:BD[24.26242] → [17.683:716]

∅:D[17.716] → [24.26276:26277]

B:BD[24.26276] → [24.26276:26277]

B:BD[24.26277] → [17.717:772]

∅:D[17.772] → [43.40:95]

B:BD[24.26331] → [43.40:95]

B:BD[43.95] → [51.339:340]

∅:D[51.340] → [24.26336:26507]

B:BD[24.26336] → [24.26336:26507]

B:BD[24.26507] → [44.5109:5141]

∅:D[44.5141] → [24.26538:26553]

B:BD[24.26538] → [24.26538:26553]

B:BD[24.26553] → [17.773:792]

∅:D[17.792] → [24.26574:26667]

B:BD[24.26574] → [24.26574:26667]

∅:D[24.26667] → [15.63876:63877]

B:BD[15.63876] → [15.63876:63877]

B:BD[15.63877] → [55.5:173]

∅:D[55.173] → [24.26668:26740]

B:BD[15.63877] → [24.26668:26740]

B:BD[24.26740] → [17.793:815]

∅:D[17.815] → [24.26764:26780]

B:BD[24.26764] → [24.26764:26780]

B:BD[24.26780] → [51.341:342]

∅:D[51.342] → [24.26785:26829]

B:BD[24.26785] → [24.26785:26829]

B:BD[24.26829] → [51.343:393]

∅:D[51.393] → [24.26882:26907]

B:BD[24.26882] → [24.26882:26907]

B:BD[24.26932] → [24.26932:27023]

B:BD[24.27023] → [44.5142:5217]

∅:D[44.5217] → [15.64256:64257]

∅:D[24.27096] → [15.64256:64257]

B:BD[15.64256] → [15.64256:64257]

B:BD[15.64257] → [24.27097:27418]

B:BD[24.27418] → [55.174:341]

B:BD[55.341] → [10.63:195]

∅:D[10.195] → [44.5218:5273]

B:BD[55.469] → [44.5218:5273]

∅:D[44.5273] → [55.513:585]

B:BD[55.513] → [55.513:585]

B:BD[55.585] → [44.5274:5284]

∅:D[44.5284] → [55.585:709]

B:BD[55.585] → [55.585:709]

∅:D[55.709] → [45.387:393]

B:BD[45.387] → [45.387:393]

B:BD[45.393] → [55.710:921]

B:BD[55.921] → [10.196:266]

∅:D[10.266] → [45.455:465]

∅:D[47.367] → [45.455:465]

∅:D[55.989] → [45.455:465]

B:BD[45.455] → [45.455:465]

B:BD[45.465] → [10.267:331]

∅:D[10.331] → [47.368:399]

B:BD[55.1050] → [47.368:399]

∅:D[47.399] → [51.394:395]

B:BD[55.1219] → [51.394:395]

B:BD[51.395] → [47.400:450]

∅:D[47.450] → [51.395:440]

B:BD[51.395] → [51.395:440]

B:BD[51.440] → [47.451:596]

∅:D[47.596] → [55.1347:1402]

∅:D[44.5375] → [55.1347:1402]

B:BD[55.1347] → [55.1347:1402]

B:BD[55.1402] → [47.597:650]

∅:D[47.650] → [24.28334:28350]

∅:D[55.1474] → [24.28334:28350]

∅:D[44.5449] → [24.28334:28350]

B:BD[15.65828] → [24.28334:28350]

∅:D[24.28350] → [15.65828:65829]

B:BD[15.65828] → [15.65828:65829]

B:BD[15.65829] → [24.28351:28401]

B:BD[24.28401] → [44.5450:5475]

∅:D[44.5475] → [24.28428:28431]

B:BD[24.28428] → [24.28428:28431]

B:BD[24.28431] → [44.5476:5554]

∅:D[44.5554] → [24.28508:28817]

B:BD[24.28508] → [24.28508:28817]

∅:D[24.28817] → [15.66199:66200]

B:BD[15.66199] → [15.66199:66200]

B:BD[15.66200] → [44.5555:5672]

∅:D[44.5672] → [56.192:477]

B:BD[56.192] → [56.192:477]

B:BD[56.477] → [57.6:55]

B:BD[57.55] → [44.5673:5719]

∅:D[44.5719] → [57.100:259]

B:BD[57.100] → [57.100:259]

B:BD[57.259] → [44.5720:5768]

∅:D[44.5768] → [57.306:462]

B:BD[57.306] → [57.306:462]

B:BD[57.462] → [51.441:442]

∅:D[51.442] → [44.5778:5830]

B:BD[44.5778] → [44.5778:5830]

∅:D[44.5830] → [57.513:551]

B:BD[57.513] → [57.513:551]

∅:D[57.551] → [56.477:479]

B:BD[56.477] → [56.477:479]

∅:D[56.479] → [15.66293:66294]

B:BD[15.66293] → [15.66293:66294]

B:BD[15.66294] → [44.5831:6010]

∅:D[44.6010] → [57.728:919]

B:BD[57.728] → [57.728:919]

B:BD[57.919] → [22.2050:2117]

∅:D[22.2117] → [24.28885:29082]

B:BD[24.28885] → [24.28885:29082]

B:BD[24.29082] → [56.480:649]

B:BD[56.649] → [34.2425:2547]

∅:D[34.2547] → [58.68:69]

B:BD[56.649] → [58.68:69]

B:BD[58.69] → [22.2118:2183]

∅:D[22.2183] → [34.2548:2613]

B:BD[24.29149] → [34.2548:2613]

B:BD[34.2613] → [20.566:621]

∅:D[20.621] → [24.29200:29202]

∅:D[56.716] → [24.29200:29202]

∅:D[34.2649] → [24.29200:29202]

B:BD[24.29200] → [24.29200:29202]

B:BD[24.29207] → [24.29207:29231]

B:BD[24.29231] → [22.2184:2322]

∅:D[22.2322] → [24.29231:29349]

B:BD[24.29231] → [24.29231:29349]

B:BD[24.29349] → [44.6011:6113]

B:BD[44.6113] → [22.2323:2324]

∅:D[22.2324] → [44.6113:6328]

B:BD[44.6113] → [44.6113:6328]

∅:D[57.1022] → [34.2727:2769]

∅:D[44.6328] → [34.2727:2769]

B:BD[34.2727] → [34.2727:2769]

B:BD[34.2769] → [51.443:444]

∅:D[51.444] → [56.717:789]

∅:D[34.2774] → [56.717:789]

B:BD[24.29473] → [56.717:789]

B:BD[56.789] → [44.6329:6470]

B:BD[44.6470] → [59.210:257]

∅:D[59.257] → [56.975:999]

B:BD[56.975] → [56.975:999]

B:BD[56.999] → [59.258:300]

∅:D[59.300] → [56.1043:1084]

B:BD[56.1043] → [56.1043:1084]

∅:D[56.1084] → [15.66402:66403]

∅:D[24.29586] → [15.66402:66403]

B:BD[15.66402] → [15.66402:66403]

B:BD[15.66403] → [59.301:369]

∅:D[59.369] → [24.29657:29667]

B:BD[24.29657] → [24.29657:29667]

B:BD[24.29667] → [59.370:490]

∅:D[59.490] → [56.1146:1160]

B:BD[56.1146] → [56.1146:1160]

B:BD[56.1160] → [34.2775:2951]

∅:D[56.1160] → [15.66708:66709]

∅:D[34.2951] → [15.66708:66709]

∅:D[24.29792] → [15.66708:66709]

B:BD[15.66708] → [15.66708:66709]

B:BD[15.66709] → [59.491:541]

∅:D[59.541] → [24.29842:29880]

B:BD[24.29842] → [24.29842:29880]

B:BD[24.29880] → [34.2952:3023]

B:BD[34.3023] → [59.542:601]

∅:D[60.372] → [56.1221:1239]

∅:D[59.601] → [56.1221:1239]

B:BD[56.1221] → [56.1221:1239]

B:BD[56.1239] → [34.3024:3176]

B:BD[34.3176] → [20.622:679]

∅:D[20.679] → [60.413:488]

B:BD[60.413] → [60.413:488]

∅:D[58.341] → [15.66790:66812]

∅:D[60.488] → [15.66790:66812]

∅:D[34.3248] → [15.66790:66812]

∅:D[24.30088] → [15.66790:66812]

B:BD[15.66790] → [15.66790:66812]

B:BD[15.66812] → [34.3249:3289]

∅:D[34.3289] → [24.30148:30179]

B:BD[24.30148] → [24.30148:30179]

B:BD[24.30179] → [34.3290:4111]

B:BD[34.4111] → [51.445:446]

∅:D[51.446] → [34.4136:4250]

B:BD[34.4136] → [34.4136:4250]

∅:D[34.4250] → [15.67200:67240]

∅:D[24.30179] → [15.67200:67240]

B:BD[15.67200] → [15.67200:67240]

∅:D[34.4396] → [24.30180:30181]

B:BD[15.67240] → [24.30180:30181]

B:BD[24.30181] → [34.4397:4961]

B:BD[34.4961] → [44.6471:6551]

∅:D[44.6551] → [34.5066:5206]

B:BD[34.5066] → [34.5066:5206]

B:BD[34.5206] → [51.447:448]

∅:D[51.448] → [34.5206:5721]

∅:D[44.6581] → [34.5206:5721]

B:BD[34.5206] → [34.5206:5721]

B:BD[34.5721] → [44.6582:6723]

∅:D[44.6723] → [57.1220:1221]

B:BD[57.1220] → [57.1220:1221]

B:BD[57.1221] → [59.602:873]

∅:D[59.873] → [15.67261:67279]

∅:D[57.1465] → [15.67261:67279]

∅:D[34.5954] → [15.67261:67279]

∅:D[44.6929] → [15.67261:67279]

∅:D[24.30213] → [15.67261:67279]

B:BD[15.67261] → [15.67261:67279]

B:BD[15.67279] → [59.874:906]

B:BD[59.906] → [19.586:643]

∅:D[19.643] → [56.1240:1287]

∅:D[57.1518] → [56.1240:1287]

B:BD[24.30291] → [56.1240:1287]

B:BD[56.1287] → [57.1519:1661]

B:BD[57.1661] → [19.644:687]

∅:D[19.687] → [24.30336:30387]

B:BD[24.30336] → [24.30336:30387]

B:BD[24.30387] → [19.688:731]

∅:D[19.731] → [24.30432:30483]

B:BD[24.30432] → [24.30432:30483]

B:BD[24.30483] → [59.907:908]

∅:D[59.908] → [24.30483:30565]

B:BD[24.30483] → [24.30483:30565]

B:BD[24.30565] → [59.909:910]

∅:D[59.910] → [44.6930:7010]

B:BD[24.30565] → [44.6930:7010]

∅:D[44.7010] → [34.6045:6085]

B:BD[24.30644] → [34.6045:6085]

B:BD[34.6085] → [59.911:950]

∅:D[59.950] → [15.67328:67360]

∅:D[34.6122] → [15.67328:67360]

∅:D[24.30677] → [15.67328:67360]

B:BD[15.67328] → [15.67328:67360]

B:BD[15.67360] → [24.30678:30694]

B:BD[24.30694] → [34.6123:6203]

B:BD[34.6203] → [51.449:450]

B:BD[51.450] → [59.951:975]

∅:D[59.975] → [45.579:585]

B:BD[45.579] → [45.579:585]

∅:D[45.585] → [24.30722:30790]

B:BD[24.30722] → [24.30722:30790]

B:BD[24.30790] → [59.976:1008]

∅:D[59.1008] → [57.1662:1702]

B:BD[24.30824] → [57.1662:1702]

∅:D[57.1702] → [45.586:609]

B:BD[24.30857] → [45.586:609]

B:BD[45.609] → [59.1009:1053]

∅:D[59.1053] → [24.30915:30959]

B:BD[24.30915] → [24.30915:30959]

B:BD[24.30959] → [59.1054:1085]

∅:D[59.1085] → [24.30992:31042]

B:BD[24.30992] → [24.30992:31042]

B:BD[24.31042] → [44.7011:7079]

∅:D[44.7079] → [56.1288:1318]

B:BD[24.31109] → [56.1288:1318]

B:BD[56.1318] → [59.1086:1109]

∅:D[59.1109] → [24.31130:31136]

B:BD[24.31130] → [24.31130:31136]

B:BD[24.31136] → [59.1110:1130]

∅:D[59.1130] → [20.680:813]

B:BD[24.31154] → [20.680:813]

B:BD[20.813] → [25.139:193]

B:BD[25.193] → [35.109:207]

B:BD[35.207] → [22.2325:2397]

∅:D[22.2397] → [20.938:1044]

B:BD[20.938] → [20.938:1044]

B:BD[20.1044] → [35.208:271]

∅:D[35.271] → [20.1090:1135]

B:BD[20.1090] → [20.1090:1135]

B:BD[20.1135] → [22.2398:2452]

∅:D[22.2452] → [20.1209:1257]

B:BD[20.1209] → [20.1209:1257]

B:BD[20.1335] → [20.1335:1336]

B:BD[20.1336] → [59.1131:1202]

B:BD[59.1202] → [22.2453:2512]

∅:D[22.2512] → [59.1281:1282]

B:BD[59.1281] → [59.1281:1282]

B:BD[59.1282] → [22.2513:2563]

∅:D[22.2563] → [20.1407:1485]

B:BD[20.1407] → [20.1407:1485]

B:BD[20.1485] → [35.272:305]

∅:D[35.305] → [20.1485:1522]

B:BD[20.1485] → [20.1485:1522]

B:BD[20.1522] → [22.2564:2622]

∅:D[22.2622] → [20.1581:1582]

B:BD[20.1581] → [20.1581:1582]

B:BD[20.1582] → [22.2623:2656]

∅:D[22.2656] → [35.360:395]

B:BD[35.360] → [35.360:395]

∅:D[35.395] → [20.1653:1654]

B:BD[20.1653] → [20.1653:1654]

B:BD[20.1654] → [35.396:501]

∅:D[35.501] → [20.1708:1718]

B:BD[20.1708] → [20.1708:1718]

B:BD[20.1718] → [35.502:523]

∅:D[35.523] → [20.1818:1819]

B:BD[20.1818] → [20.1818:1819]

B:BD[20.1819] → [35.524:609]

∅:D[35.609] → [20.1838:1848]

B:BD[20.1838] → [20.1838:1848]

B:BD[20.1848] → [35.610:659]

∅:D[35.659] → [20.1848:1882]

B:BD[20.1848] → [20.1848:1882]

B:BD[20.1882] → [35.660:680]

∅:D[35.680] → [24.31154:31156]

∅:D[20.1900] → [24.31154:31156]

B:BD[24.31154] → [24.31154:31156]

∅:D[24.31156] → [15.67636:67637]

B:BD[15.67636] → [15.67636:67637]

B:BD[15.67637] → [24.31157:32863]

B:BD[24.32863] → [43.96:221]

B:BD[43.221] → [18.585:617]

B:BD[18.617] → [22.2657:2713]

B:BD[22.2713] → [5.50:107]

∅:D[5.107] → [24.32990:33007]

∅:D[21.143] → [24.32990:33007]

∅:D[23.476] → [24.32990:33007]

∅:D[19.789] → [24.32990:33007]

∅:D[20.2018] → [24.32990:33007]

B:BD[24.32990] → [24.32990:33007]

B:BD[24.33007] → [22.2714:2774]

∅:D[22.2774] → [24.33007:33038]

B:BD[24.33007] → [24.33007:33038]

B:BD[24.33038] → [43.222:322]

∅:D[43.322] → [15.68207:68208]

∅:D[24.33126] → [15.68207:68208]

B:BD[15.68207] → [15.68207:68208]

B:BD[15.68208] → [24.33127:33147]

B:BD[24.33147] → [43.323:339]

∅:D[43.339] → [15.68655:68656]

∅:D[24.33247] → [15.68655:68656]

B:BD[15.68655] → [15.68655:68656]

B:BD[15.68656] → [61.7:65]

∅:D[61.65] → [62.438:788]

B:BD[62.438] → [62.438:788]

∅:D[62.788] → [24.33248:33388]

B:BD[15.68656] → [24.33248:33388]

∅:D[24.33388] → [15.68927:68928]

B:BD[15.68927] → [15.68927:68928]

B:BD[15.68928] → [19.790:843]

∅:D[19.843] → [45.665:671]

B:BD[45.665] → [45.665:671]

∅:D[45.671] → [24.33446:33542]

B:BD[24.33446] → [24.33446:33542]

∅:D[24.33542] → [15.69082:69083]

B:BD[15.69082] → [15.69082:69083]

B:BD[15.69083] → [24.33543:33584]

B:BD[24.33584] → [43.340:488]

∅:D[43.488] → [15.69383:69384]

∅:D[24.33657] → [15.69383:69384]

B:BD[15.69383] → [15.69383:69384]

B:BD[15.69384] → [24.33658:33743]

B:BD[24.33743] → [21.144:145]

∅:D[21.145] → [19.844:907]

B:BD[24.33743] → [19.844:907]

∅:D[45.747] → [24.33810:33868]

∅:D[19.907] → [24.33810:33868]

B:BD[24.33810] → [24.33810:33868]

B:BD[24.33868] → [19.908:954]

∅:D[19.954] → [45.795:809]

B:BD[45.795] → [45.795:809]

B:BD[45.809] → [51.451:452]

∅:D[51.452] → [24.33934:34044]

B:BD[24.33934] → [24.33934:34044]

∅:D[24.34044] → [15.69510:69511]

B:BD[15.69510] → [15.69510:69511]

B:BD[15.69511] → [63.7:54]

∅:D[63.54] → [24.34117:34147]

B:BD[24.34117] → [24.34117:34147]

∅:D[24.34147] → [15.69690:69691]

B:BD[15.69690] → [15.69690:69691]

B:BD[15.69691] → [64.7:53]

B:BD[64.53] → [19.955:1027]

∅:D[64.121] → [51.453:454]

∅:D[19.1027] → [51.453:454]

∅:D[22.2857] → [51.453:454]

B:BD[65.188] → [51.453:454]

∅:D[65.188] → [24.34148:34193]

∅:D[51.454] → [24.34148:34193]

∅:D[44.7101] → [24.34148:34193]

B:BD[15.69691] → [24.34148:34193]

B:BD[24.34193] → [6.6:79]

∅:D[6.79] → [19.1028:1070]

B:BD[24.34193] → [19.1028:1070]

B:BD[19.1070] → [6.80:146]

∅:D[66.146] → [45.865:883]

∅:D[6.146] → [45.865:883]

∅:D[65.300] → [45.865:883]

∅:D[43.545] → [45.865:883]

∅:D[19.1135] → [45.865:883]

∅:D[20.2152] → [45.865:883]

B:BD[45.865] → [45.865:883]

∅:D[45.883] → [24.34250:34305]

B:BD[24.34250] → [24.34250:34305]

B:BD[24.34305] → [19.1136:1201]

∅:D[19.1201] → [24.34372:34422]

B:BD[24.34372] → [24.34372:34422]

B:BD[24.34422] → [43.546:564]

B:BD[43.564] → [19.1202:1312]

∅:D[19.1312] → [43.633:717]

B:BD[43.633] → [43.633:717]

B:BD[43.717] → [19.1313:1378]

∅:D[19.1378] → [43.784:806]

B:BD[43.784] → [43.784:806]

B:BD[43.806] → [17.816:885]

∅:D[17.885] → [43.874:947]

B:BD[43.874] → [43.874:947]

∅:D[43.947] → [24.34422:34454]

B:BD[24.34422] → [24.34422:34454]

∅:D[24.34464] → [15.69831:69832]

B:BD[15.69831] → [15.69831:69832]

B:BD[15.69832] → [24.34465:34596]

B:BD[24.34596] → [19.1379:1450]

∅:D[19.1450] → [45.957:967]

B:BD[45.957] → [45.957:967]

∅:D[45.967] → [24.34671:34786]

B:BD[24.34671] → [24.34671:34786]

B:BD[24.34786] → [19.1451:1522]

∅:D[19.1522] → [45.1040:1054]

B:BD[45.1040] → [45.1040:1054]

∅:D[45.1054] → [24.34860:34933]

B:BD[24.34860] → [24.34860:34933]

B:BD[24.34933] → [45.1055:1129]

∅:D[45.1129] → [24.34991:35218]

B:BD[24.34991] → [24.34991:35218]

B:BD[24.35218] → [3.7:134]

∅:D[3.134] → [19.1523:1603]

B:BD[44.7227] → [19.1523:1603]

∅:D[19.1603] → [44.7308:7411]

B:BD[44.7308] → [44.7308:7411]

                    }
                }
            }
        }
    }
}
// The LOS code now uses raycasting -- haranp
#define LONGSIZE (sizeof(unsigned long)*8)
#define LOS_MAX_RANGE_X 9
#define LOS_MAX_RANGE_Y 9
#define LOS_MAX_RANGE 9
// the following two constants represent the 'middle' of the sh array.
// since the current shown area is 19x19, centering the view at (9,9)
// means it will be exactly centered.
// This is done to accomodate possible future changes in viewable screen
// area - simply change sh_xo and sh_yo to the new view center.
const int sh_xo = 9;            // X and Y origins for the sh array
const int sh_yo = 9;
// Data used for the LOS algorithm
int los_radius_squared = 8*8 + 1;
unsigned long* los_blockrays = NULL;
unsigned long* dead_rays     = NULL;
unsigned long* smoke_rays    = NULL;
std::vector<short> ray_coord_x;
std::vector<short> ray_coord_y;
std::vector<short> compressed_ray_x;
std::vector<short> compressed_ray_y;
std::vector<int> raylengths;
std::vector<ray_def> fullrays;
void clear_rays_on_exit()
{
    delete[] dead_rays;
    delete[] smoke_rays;
    delete[] los_blockrays;
}
void setLOSRadius(int newLR)
{
    los_radius_squared = newLR * newLR + 1*1;
}
bool get_bit_in_long_array( const unsigned long* data, int where )
{
    int wordloc = where / LONGSIZE;
    int bitloc = where % LONGSIZE;
    return ((data[wordloc] & (1UL << bitloc)) != 0);
}
static void _set_bit_in_long_array( unsigned long* data, int where )
{
    int wordloc = where / LONGSIZE;
    int bitloc = where % LONGSIZE;
    data[wordloc] |= (1UL << bitloc);
}
#define EPSILON_VALUE 0.00001
bool double_is_zero( const double x )
{
    return (x > -EPSILON_VALUE) && (x < EPSILON_VALUE);
}
// note that slope must be nonnegative!
// returns 0 if the advance was in x, 1 if it was in y, 2 if it was
// the diagonal
static int _find_next_intercept(double* accx, double* accy, const double slope)
{
    // handle perpendiculars
    if ( double_is_zero(slope) )
    {
        *accx += 1.0;
        return 0;
    }
    if ( slope > 100.0 )
    {
        *accy += 1.0;
        return 1;
    }
    const double xtarget = (static_cast<int>(*accx) + 1);
    const double ytarget = (static_cast<int>(*accy) + 1);
    const double xdistance = xtarget - *accx;
    const double ydistance = ytarget - *accy;
    double distdiff = (xdistance * slope - ydistance);
    // exact corner
    if ( double_is_zero( distdiff ) )
    {
        // move somewhat away from the corner
        if ( slope > 1.0 )
        {
            *accx = xtarget + EPSILON_VALUE * 2;
            *accy = ytarget + EPSILON_VALUE * 2 * slope;
        }
        else
        {
            *accx = xtarget + EPSILON_VALUE * 2 / slope;
            *accy = ytarget + EPSILON_VALUE * 2;
        }
        return 2;
    }
    // move to the boundary
    double traveldist;
    int rc = -1;
    if ( distdiff > 0.0 )
    {
        traveldist = ydistance / slope;
        rc = 1;
    }
    else
    {
        traveldist = xdistance;
        rc = 0;
    }
    // and a little into the next cell, taking care
    // not to go too far
    if ( distdiff < 0.0 )
        distdiff = -distdiff;
    traveldist += std::min(EPSILON_VALUE * 10.0, 0.5 * distdiff / slope);
    *accx += traveldist;
    *accy += traveldist * slope;
    return rc;
}
ray_def::ray_def() : accx(0.0), accy(0.0), slope(0.0), quadrant(0),
                     fullray_idx(0)
{
}
double ray_def::reflect(double p, double c) const
{
    return (c + c - p);
}
double ray_def::reflect(bool rx, double oldx, double newx) const
{
    if (rx? fabs(slope) > 1.0 : fabs(slope) < 1.0)
        return (reflect(oldx, floor(oldx) + 0.5));
    const double flnew = floor(newx);
    const double flold = floor(oldx);
    return (reflect(oldx,
                    flnew > flold? flnew :
                    flold > flnew? flold :
                    (newx + oldx) / 2));
}
void ray_def::set_reflect_point(const double oldx, const double oldy,
                                double *newx, double *newy,
                                bool blocked_x, bool blocked_y)
{
    if (blocked_x == blocked_y)
    {
        // What to do?
        *newx = oldx;
        *newy = oldy;
        return;
    }
    if (blocked_x)
    {
        ASSERT(int(oldy) != int(*newy));
        *newy = oldy;
        *newx = reflect(true, oldx, *newx);
    }
    else
    {
        ASSERT(int(oldx) != int(*newx));
        *newx = oldx;
        *newy = reflect(false, oldy, *newy);
    }
}
void ray_def::advance_and_bounce()
{
    // 0 = down-right, 1 = down-left, 2 = up-left, 3 = up-right
    int bouncequad[4][3] =
    {
        { 1, 3, 2 }, { 0, 2, 3 }, { 3, 1, 0 }, { 2, 0, 1 }
    };
    int oldx = x(), oldy = y();
    const double oldaccx = accx, oldaccy = accy;
    int rc = advance(false);
    int newx = x(), newy = y();
    ASSERT( grid_is_solid(grd[newx][newy]) );
    const bool blocked_x = grid_is_solid(grd[oldx][newy]);
    const bool blocked_y = grid_is_solid(grd[newx][oldy]);
    if ( double_is_zero(slope) || slope > 100.0 )
        quadrant = bouncequad[quadrant][2];
    else if ( rc != 2 )
        quadrant = bouncequad[quadrant][rc];
    else
    {
        ASSERT( (oldx != newx) && (oldy != newy) );
        if ( blocked_x && blocked_y )
            quadrant = bouncequad[quadrant][rc];
        else if ( blocked_x )
            quadrant = bouncequad[quadrant][1];
        else
            quadrant = bouncequad[quadrant][0];
    }
    set_reflect_point(oldaccx, oldaccy, &accx, &accy, blocked_x, blocked_y);
}
double ray_def::get_degrees() const
{
    if (slope > 100.0)
    {
        if (quadrant == 3 || quadrant == 2)
            return (90.0);
        else
            return (270.0);
    }
    else if (double_is_zero(slope))
    {
        if (quadrant == 0 || quadrant == 3)
            return (0.0);
        else
            return (180.0);
    }
    double deg = atan(slope) * 180.0 / M_PI;
    switch (quadrant)
    {
    case 0:
        return (360.0 - deg);
    case 1:
        return (180.0 + deg);
    case 2:
        return (180.0 - deg);
    case 3:
        return (deg);
    }
    ASSERT(!"ray has illegal quadrant");
    return (0.0);
}
void ray_def::set_degrees(double deg)
{
    while (deg < 0.0)
        deg += 360.0;
    while (deg >= 360.0)
        deg -= 360.0;
    double _slope = tan(deg / 180.0 * M_PI);
    if (double_is_zero(_slope))
    {
        slope = 0.0;
        if (deg < 90.0 || deg > 270.0)
            quadrant = 0; // right/east
        else
            quadrant = 1; // left/west
    }
    else if (_slope > 0)
    {
        slope = _slope;
        if (deg >= 180.0 && deg <= 270.0)
            quadrant = 1;
        else
            quadrant = 3;
    }
    else
    {
        slope = -_slope;
        if (deg >= 90 && deg <= 180)
            quadrant = 2;
        else
            quadrant = 0;
    }
    if (slope > 1000.0)
        slope = 1000.0;
}
void ray_def::regress()
{
    int opp_quadrant[4] = { 2, 3, 0, 1 };
    quadrant = opp_quadrant[quadrant];
    advance(false);
    quadrant = opp_quadrant[quadrant];
}
int ray_def::advance_through(const coord_def &target)
{
    return (advance(true, &target));
}
int ray_def::advance(bool shortest_possible, const coord_def *target)
{
    if (!shortest_possible)
        return (raw_advance());
    // If we want to minimise the number of moves on the ray, look one
    // step ahead and see if we can get a diagonal.
    const coord_def old(static_cast<int>(accx), static_cast<int>(accy));
    const int ret = raw_advance();
    if (ret == 2 || (target && pos() == *target))
        return (ret);
    const double maccx = accx, maccy = accy;
    if (raw_advance() != 2)
    {
        const coord_def second(static_cast<int>(accx), static_cast<int>(accy));
        // If we can convert to a diagonal, do so.
        if ((second - old).abs() == 2)
            return (2);
    }
    // No diagonal, so roll back.
    accx = maccx;
    accy = maccy;
    return (ret);
}
int ray_def::raw_advance()
{
    int rc;
    switch ( quadrant )
    {
    case 0:
        // going down-right
        rc = _find_next_intercept( &accx, &accy, slope );
        return rc;
    case 1:
        // going down-left
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        rc   = _find_next_intercept( &accx, &accy, slope );
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        return rc;
    case 2:
        // going up-left
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        rc   = _find_next_intercept( &accx, &accy, slope );
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        return rc;
    case 3:
        // going up-right
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        rc   = _find_next_intercept( &accx, &accy, slope );
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        return rc;
    default:
        return -1;
    }
}
// Shoot a ray from the given start point (accx, accy) with the given
// slope, with a maximum distance (in either x or y coordinate) of
// maxrange. Store the visited cells in xpos[] and ypos[], and
// return the number of cells visited.
static int _shoot_ray( double accx, double accy, const double slope,
                       int maxrange, int xpos[], int ypos[] )
{
    int curx, cury;
    int cellnum;
    for (cellnum = 0; true; ++cellnum)
    {
        _find_next_intercept( &accx, &accy, slope );
        curx = static_cast<int>(accx);
        cury = static_cast<int>(accy);
        if (curx*curx + cury*cury > los_radius_squared)
            break;
        // Work with the new square.
        xpos[cellnum] = curx;
        ypos[cellnum] = cury;
    }
    return cellnum;
}
// Check if the passed ray has already been created.
static bool _is_duplicate_ray( int len, int xpos[], int ypos[] )
{
    int cur_offset = 0;
    for (unsigned int i = 0; i < raylengths.size(); ++i)
    {
        // Only compare equal-length rays.
        if (raylengths[i] != len)
        {
            cur_offset += raylengths[i];
            continue;
        }
        int j;
        for (j = 0; j < len; ++j)
        {
            if (ray_coord_x[j + cur_offset] != xpos[j]
                || ray_coord_y[j + cur_offset] != ypos[j])
            {
                break;
            }
        }
        // Exact duplicate?
        if (j == len)
            return (true);
        // Move to beginning of next ray.
        cur_offset += raylengths[i];
    }
    return (false);
}
// 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_coord_x[curb] > ray_coord_x[cura])
            return (false);
        if (ray_coord_y[curb] > ray_coord_y[cura])
            return (false);
        if (ray_coord_x[cura] == ray_coord_x[curb]
            && ray_coord_y[cura] == ray_coord_y[curb])
        {
            ++cura;
        }
        ++curb;
    }
    return (cura == enda);
}
// Returns a vector which lists all the nonduped cellrays (by index).
static std::vector<int> _find_nonduped_cellrays()
{
    // A cellray c in a fullray f is duped if there is a fullray g
    // such that g contains c and g[:c] is a subset of f[:c].
    int raynum, cellnum, curidx, testidx, testray, testcell;
    bool is_duplicate;
    std::vector<int> result;
    for (curidx = 0, raynum = 0;
         raynum < static_cast<int>(raylengths.size());
         curidx += raylengths[raynum++])
    {
        for (cellnum = 0; cellnum < raylengths[raynum]; ++cellnum)
        {
            // Is the cellray raynum[cellnum] duplicated?
            is_duplicate = false;
            // XXX: We should really check everything up to now
            // completely, and all further rays to see if they're
            // proper subsets.
            const int curx = ray_coord_x[curidx + cellnum];
            const int cury = ray_coord_y[curidx + cellnum];
            for (testidx = 0, testray = 0; testray < raynum;
                 testidx += raylengths[testray++])
            {
                // Scan ahead to see if there's an intersect.
                for (testcell = 0; testcell < raylengths[raynum]; ++testcell)
                {
                    const int testx = ray_coord_x[testidx + testcell];
                    const int testy = ray_coord_y[testidx + testcell];
                    // We can short-circuit sometimes.
                    if (testx > curx || testy > cury)
                        break;
                    // Bingo!
                    if (testx == curx && testy == cury)
                    {
                        is_duplicate = _is_subset(testidx, curidx,
                                                  testcell, cellnum);
                        break;
                    }
                }
                if (is_duplicate)
                    break;      // No point in checking further rays.
            }
            if (!is_duplicate)
                result.push_back(curidx + cellnum);
        }
    }
    return result;
}
// Create and register the ray defined by the arguments.
// Return true if the ray was actually registered (i.e., not a duplicate.)
static bool _register_ray( double accx, double accy, double slope )
{
    int xpos[LOS_MAX_RANGE * 2 + 1], ypos[LOS_MAX_RANGE * 2 + 1];
    int raylen = _shoot_ray( accx, accy, slope, LOS_MAX_RANGE, xpos, ypos );
    // Early out if ray already exists.
    if (_is_duplicate_ray(raylen, xpos, ypos))
        return (false);
    // Not duplicate, register.
    for (int i = 0; i < raylen; ++i)
    {
        // Create the cellrays.
        ray_coord_x.push_back(xpos[i]);
        ray_coord_y.push_back(ypos[i]);
    }
    // Register the fullray.
    raylengths.push_back(raylen);
    ray_def ray;
    ray.accx = accx;
    ray.accy = accy;
    ray.slope = slope;
    ray.quadrant = 0;
    fullrays.push_back(ray);
    return (true);
}
static void _create_blockrays()
{
    // determine nonduplicated rays
    std::vector<int> nondupe_cellrays    = _find_nonduped_cellrays();
    const unsigned int num_nondupe_rays  = nondupe_cellrays.size();
    const unsigned int num_nondupe_words =
        (num_nondupe_rays + LONGSIZE - 1) / LONGSIZE;
    const unsigned int num_cellrays = ray_coord_x.size();
    const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE;
    // first build all the rays: easier to do blocking calculations there
    unsigned long* full_los_blockrays;
    full_los_blockrays = new unsigned long[num_words * (LOS_MAX_RANGE_X+1) *
                                           (LOS_MAX_RANGE_Y+1)];
    memset((void*)full_los_blockrays, 0, sizeof(unsigned long) * num_words *
           (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1));
    int cur_offset = 0;
    for (unsigned int ray = 0; ray < raylengths.size(); ++ray)
    {
        for (int i = 0; i < raylengths[ray]; ++i)
        {
            // every cell blocks...
            unsigned long* const inptr = full_los_blockrays +
                (ray_coord_x[i + cur_offset] * (LOS_MAX_RANGE_Y + 1) +
                 ray_coord_y[i + cur_offset]) * num_words;
            // ...all following cellrays
            for (int j = i+1; j < raylengths[ray]; ++j)
                _set_bit_in_long_array( inptr, j + cur_offset );
        }
        cur_offset += raylengths[ray];
    }
    // we've built the basic blockray array; now compress it, keeping
    // only the nonduplicated cellrays.
    // allocate and clear memory
    los_blockrays = new unsigned long[num_nondupe_words * (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y + 1)];
    memset((void*)los_blockrays, 0, sizeof(unsigned long) * num_nondupe_words *
           (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1));
    // we want to only keep the cellrays from nondupe_cellrays.
    compressed_ray_x.resize(num_nondupe_rays);
    compressed_ray_y.resize(num_nondupe_rays);
    for (unsigned int i = 0; i < num_nondupe_rays; ++i)
    {
        compressed_ray_x[i] = ray_coord_x[nondupe_cellrays[i]];
        compressed_ray_y[i] = ray_coord_y[nondupe_cellrays[i]];
    }
    unsigned long* oldptr = full_los_blockrays;
    unsigned long* newptr = los_blockrays;
    for (int x = 0; x <= LOS_MAX_RANGE_X; ++x)
        for (int y = 0; y <= LOS_MAX_RANGE_Y; ++y)
        {
            for (unsigned int i = 0; i < num_nondupe_rays; ++i)
                if (get_bit_in_long_array(oldptr, nondupe_cellrays[i]))
                    _set_bit_in_long_array(newptr, i);
            oldptr += num_words;
            newptr += num_nondupe_words;
        }
    // we can throw away full_los_blockrays now
    delete[] full_los_blockrays;
    dead_rays  = new unsigned long[num_nondupe_words];
    smoke_rays = new unsigned long[num_nondupe_words];
#ifdef DEBUG_DIAGNOSTICS
    mprf( MSGCH_DIAGNOSTICS, "Cellrays: %d Fullrays: %u Compressed: %u",
          num_cellrays, raylengths.size(), num_nondupe_rays );
#endif
}
static int _gcd( int x, int y )
{
    int tmp;
    while (y != 0)
    {
        x %= y;
        tmp = x;
        x = y;
        y = tmp;
    }
    return x;
}
bool complexity_lt( const std::pair<int,int>& lhs,
                    const std::pair<int,int>& rhs )
{
    return lhs.first * lhs.second < rhs.first * rhs.second;
}
// Cast all rays
void raycast()
{
    static bool done_raycast = false;
    if (done_raycast)
        return;
    // Creating all rays for first quadrant
    // We have a considerable amount of overkill.
    done_raycast = true;
    // register perpendiculars FIRST, to make them top choice
    // when selecting beams
    _register_ray( 0.5, 0.5, 1000.0 );
    _register_ray( 0.5, 0.5, 0.0 );
    // For a slope of M = y/x, every x we move on the X axis means
    // that we move y on the y axis. We want to look at the resolution
    // of x/y: in that case, every step on the X axis means an increase
    // of 1 in the Y axis at the intercept point. We can assume gcd(x,y)=1,
    // so we look at steps of 1/y.
    // Changing the order a bit. We want to order by the complexity
    // of the beam, which is log(x) + log(y) ~ xy.
    std::vector<std::pair<int,int> > xyangles;
    for ( int xangle = 1; xangle <= 2*LOS_MAX_RANGE; ++xangle )
        for ( int yangle = 1; yangle <= 2*LOS_MAX_RANGE; ++yangle )
        {
            if ( _gcd(xangle, yangle) == 1 )
                xyangles.push_back(std::pair<int,int>(xangle, yangle));
        }
    std::sort( xyangles.begin(), xyangles.end(), complexity_lt );
    for ( unsigned int i = 0; i < xyangles.size(); ++i )
    {
        const int xangle = xyangles[i].first;
        const int yangle = xyangles[i].second;
        const double slope = ((double)(yangle)) / xangle;
        const double rslope = ((double)(xangle)) / yangle;
        for ( int intercept = 1; intercept <= 2*yangle; ++intercept )
        {
            double xstart = ((double)(intercept)) / (2*yangle);
            double ystart = 1;
            // now move back just inside the cell
            // y should be "about to change"
            xstart -= EPSILON_VALUE * xangle;
            ystart -= EPSILON_VALUE * yangle;
            _register_ray( xstart, ystart, slope );
            // also draw the identical ray in octant 2
            _register_ray( ystart, xstart, rslope );
        }
    }
    // Now create the appropriate blockrays array
    _create_blockrays();
}
static void _set_ray_quadrant( ray_def& ray, int sx, int sy, int tx, int ty )
{
    if ( tx >= sx && ty >= sy )
        ray.quadrant = 0;
    else if ( tx < sx && ty >= sy )
        ray.quadrant = 1;
    else if ( tx < sx && ty < sy )
        ray.quadrant = 2;
    else if ( tx >= sx && ty < sy )
        ray.quadrant = 3;
    else
        mpr("Bad ray quadrant!", MSGCH_DIAGNOSTICS);
}
static int _cyclic_offset( unsigned int ui, int cycle_dir, int startpoint,
                           int maxvalue )
{
    const int i = (int)ui;
    if ( startpoint < 0 )
        return i;
    switch ( cycle_dir )
    {
    case 1:
        return (i + startpoint + 1) % maxvalue;
    case -1:
        return (i - 1 - startpoint + maxvalue) % maxvalue;
    case 0:
    default:
        return i;
    }
}
static const double VERTICAL_SLOPE = 10000.0;
static double _calc_slope(double x, double y)
{
    if (double_is_zero(x))
        return (VERTICAL_SLOPE);
    const double slope = y / x;
    return (slope > VERTICAL_SLOPE? VERTICAL_SLOPE : slope);
}
static double _slope_factor(const ray_def &ray)
{
    double xdiff = fabs(ray.accx - 0.5), ydiff = fabs(ray.accy - 0.5);
    if (double_is_zero(xdiff) && double_is_zero(ydiff))
        return ray.slope;
    const double slope = _calc_slope(ydiff, xdiff);
    return (slope + ray.slope) / 2.0;
}
static bool _superior_ray(int shortest, int imbalance,
                          int raylen, int rayimbalance,
                          double slope_diff, double ray_slope_diff)
{
    if (shortest != raylen)
        return (shortest > raylen);
    if (imbalance != rayimbalance)
        return (imbalance > rayimbalance);
    return (slope_diff > ray_slope_diff);
}
// Find a nonblocked ray from source to target. Return false if no
// such ray could be found, otherwise return true and fill ray
// appropriately.
// If allow_fallback is true, fall back to a center-to-center ray
// if range is too great or all rays are blocked.
// If cycle_dir is 0, find the first fitting ray. If it is 1 or -1,
// assume that ray is appropriately filled in, and look for the next
// ray in that cycle direction.
// If find_shortest is true, examine all rays that hit the target and
// take the shortest (starting at ray.fullray_idx).
bool find_ray( const coord_def& source, const coord_def& target,
               bool allow_fallback, ray_def& ray, int cycle_dir,
               bool find_shortest, bool ignore_solid )
{
    int cellray, inray;
    const int sourcex = source.x;
    const int sourcey = source.y;
    const int targetx = target.x;
    const int targety = target.y;
    const int signx = ((targetx - sourcex >= 0) ? 1 : -1);
    const int signy = ((targety - sourcey >= 0) ? 1 : -1);
    const int absx  = signx * (targetx - sourcex);
    const int absy  = signy * (targety - sourcey);
    int cur_offset  = 0;
    int shortest    = INFINITE_DISTANCE;
    int imbalance   = INFINITE_DISTANCE;
    const double want_slope = _calc_slope(absx, absy);
    double slope_diff       = VERTICAL_SLOPE * 10.0;
    std::vector<coord_def> unaliased_ray;
    for ( unsigned int fray = 0; fray < fullrays.size(); ++fray )
    {
        const int fullray = _cyclic_offset( fray, cycle_dir, ray.fullray_idx,
                                            fullrays.size() );
        // Yeah, yeah, this is O(n^2). I know.
        cur_offset = 0;
        for (int i = 0; i < fullray; ++i)
            cur_offset += raylengths[i];
        for (cellray = 0; cellray < raylengths[fullray]; ++cellray)
        {
            if (ray_coord_x[cellray + cur_offset] == absx
                && ray_coord_y[cellray + cur_offset] == absy)
            {
                if (find_shortest)
                {
                    unaliased_ray.clear();
                    unaliased_ray.push_back(coord_def(0, 0));
                }
                // Check if we're blocked so far.
                bool blocked = false;
                coord_def c1, c3;
                int real_length = 0;
                for (inray = 0; inray <= cellray; ++inray)
                {
                    const int xi = signx * ray_coord_x[inray + cur_offset];
                    const int yi = signy * ray_coord_y[inray + cur_offset];
                    if (inray < cellray && !ignore_solid
                        && grid_is_solid(grd[sourcex + xi][sourcey + yi]))
                    {
                        blocked = true;
                        break;
                    }
                    if (find_shortest)
                    {
                        c3 = coord_def(xi, yi);
                        // We've moved at least two steps if inray > 0.
                        if (inray)
                        {
                            // Check for a perpendicular corner on the ray and
                            // pretend that it's a diagonal.
                            if ((c3 - c1).abs() != 2)
                                ++real_length;
                            else
                            {
                                // c2 was a dud move, pop it off
                                unaliased_ray.pop_back();
                            }
                        }
                        else
                            ++real_length;
                        unaliased_ray.push_back(c3);
                        c1 = unaliased_ray[real_length - 1];
                    }
                }
                int cimbalance = 0;
                // If this ray is a candidate for shortest, calculate
                // the imbalance. I'm defining 'imbalance' as the
                // number of consecutive diagonal or orthogonal moves
                // in the ray. This is a reasonable measure of deviation from
                // the Bresenham line between our selected source and
                // destination.
                if (!blocked && find_shortest && shortest >= real_length)
                {
                    int diags = 0, straights = 0;
                    for (int i = 1, size = unaliased_ray.size(); i < size; ++i)
                    {
                        const int dist =
                            (unaliased_ray[i] - unaliased_ray[i - 1]).abs();
                        if (dist == 2)
                        {
                            straights = 0;
                            if (++diags > cimbalance)
                                cimbalance = diags;
                        }
                        else
                        {
                            diags = 0;
                            if (++straights > cimbalance)
                                cimbalance = straights;
                        }
                    }
                }
                const double ray_slope_diff = find_shortest ?
                    fabs(_slope_factor(fullrays[fullray]) - want_slope) : 0.0;
                if (!blocked
                    &&  (!find_shortest
                         || _superior_ray(shortest, imbalance,
                                          real_length, cimbalance,
                                          slope_diff, ray_slope_diff)))
                {
                    // Success!
                    ray             = fullrays[fullray];
                    ray.fullray_idx = fullray;
                    shortest   = real_length;
                    imbalance  = cimbalance;
                    slope_diff = ray_slope_diff;
                    if (sourcex > targetx)
                        ray.accx = 1.0 - ray.accx;
                    if (sourcey > targety)
                        ray.accy = 1.0 - ray.accy;
                    ray.accx += sourcex;
                    ray.accy += sourcey;
                    _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety);
                    if (!find_shortest)
                        return (true);
                }
            }
        }
    }
    if (find_shortest && shortest != INFINITE_DISTANCE)
        return (true);
    if (allow_fallback)
    {
        ray.accx = sourcex + 0.5;
        ray.accy = sourcey + 0.5;
        if (targetx == sourcex)
            ray.slope = VERTICAL_SLOPE;
        else
        {
            ray.slope  = targety - sourcey;
            ray.slope /= targetx - sourcex;
            if (ray.slope < 0)
                ray.slope = -ray.slope;
        }
        _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety);
        ray.fullray_idx = -1;
        return (true);
    }
    return (false);
}
// Count the number of matching features between two points along
// a beam-like path; the path will pass through solid features.
// By default, it excludes end points from the count.
// If just_check is true, the function will return early once one
// such feature is encountered.
int num_feats_between(const coord_def& source, const coord_def& target,
                      dungeon_feature_type min_feat,
                      dungeon_feature_type max_feat,
                      bool exclude_endpoints, bool just_check)
{
    ray_def ray;
    int     count    = 0;
    int     max_dist = grid_distance(source, target);
    ray.fullray_idx = -1; // to quiet valgrind
    // We don't need to find the shortest beam, any beam will suffice.
    find_ray( source, target, true, ray, 0, false, true );
    if (exclude_endpoints && ray.pos() == source)
    {
        ray.advance(true);
        max_dist--;
    }
    int dist = 0;
    bool reached_target = false;
    while (dist++ <= max_dist)
    {
        const dungeon_feature_type feat = grd(ray.pos());
        if (ray.pos() == target)
            reached_target = true;
        if (feat >= min_feat && feat <= max_feat
            && (!exclude_endpoints || !reached_target))
        {
            count++;
            if (just_check) // Only needs to be > 0.
                return (count);
        }
        if (reached_target)
            break;
        ray.advance(true);
    }
    return (count);
}
// The rule behind LOS is:
// Two cells can see each other if there is any line from some point
// of the first to some point of the second ("generous" LOS.)
//
// We use raycasting. The algorithm:
// PRECOMPUTATION:
// Create a large bundle of rays and cast them.
// Mark, for each one, which cells kill it (and where.)
// Also, for each one, note which cells it passes.
// ACTUAL LOS:
// Unite the ray-killers for the given map; this tells you which rays
// are dead.
// Look up which cells the surviving rays have, and that's your LOS!
// OPTIMIZATIONS:
// WLOG, we can assume that we're in a specific quadrant - say the
// first quadrant - and just mirror everything after that.  We can
// likely get away with a single octant, but we don't do that. (To
// do...)
// Rays are actually split by each cell they pass. So each "ray" only
// identifies a single cell, and we can do logical ORs.  Once a cell
// kills a cellray, it will kill all remaining cellrays of that ray.
// Also, rays are checked to see if they are duplicates of each
// other. If they are, they're eliminated.
// Some cellrays can also be eliminated. In general, a cellray is
// unnecessary if there is another cellray with the same coordinates,
// and whose path (up to those coordinates) is a subset, not necessarily
// proper, of the original path. We still store the original cellrays
// fully for beam detection and such.
// PERFORMANCE:
// With reasonable values we have around 6000 cellrays, meaning
// around 600Kb (75 KB) of data. This gets cut down to 700 cellrays
// after removing duplicates. That means that we need to do
// around 22*100*4 ~ 9,000 memory reads + writes per LOS call on a
// 32-bit system. Not too bad.
// IMPROVEMENTS:
// Smoke will now only block LOS after two cells of smoke. This is
// done by updating with a second array.
void losight(env_show_grid &sh,
             feature_grid &gr, const coord_def& center,
             bool clear_walls_block, bool ignore_clouds)
{
    raycast();
    const int x_p = center.x;
    const int y_p = center.y;
    // go quadrant by quadrant
    const int quadrant_x[4] = {  1, -1, -1,  1 };
    const int quadrant_y[4] = {  1,  1, -1, -1 };
    // clear out sh
    sh.init(0);
    if (crawl_state.arena || crawl_state.arena_suspended)
    {
        for (int y = -ENV_SHOW_OFFSET; y <= ENV_SHOW_OFFSET; ++y)
            for (int x = -ENV_SHOW_OFFSET; x <= ENV_SHOW_OFFSET; ++x)
            {
                const coord_def pos = center + coord_def(x, y);
                if (map_bounds(pos))
                    sh[x + sh_xo][y + sh_yo] = gr(pos);
            }
        return;
    }
    const unsigned int num_cellrays = compressed_ray_x.size();
    const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE;
    for (int quadrant = 0; quadrant < 4; ++quadrant)
    {
        const int xmult = quadrant_x[quadrant];
        const int ymult = quadrant_y[quadrant];
        // clear out the dead rays array
        memset( (void*)dead_rays,  0, sizeof(unsigned long) * num_words);
        memset( (void*)smoke_rays, 0, sizeof(unsigned long) * num_words);
        // kill all blocked rays
        const unsigned long* inptr = los_blockrays;
        for (int xdiff = 0; xdiff <= LOS_MAX_RANGE_X; ++xdiff)
            for (int ydiff = 0; ydiff <= LOS_MAX_RANGE_Y;
                 ++ydiff, inptr += num_words)
            {
                const int realx = x_p + xdiff * xmult;
                const int realy = y_p + ydiff * ymult;
                if (!map_bounds(realx, realy))
                    continue;
                coord_def real(realx, realy);
                dungeon_feature_type dfeat = grid_appearance(gr, real);
                // if this cell is opaque...
                // ... or something you can see but not walk through ...
                if (grid_is_opaque(dfeat)
                    || clear_walls_block && dfeat < DNGN_MINMOVE)
                {
                    // then block the appropriate rays
                    for (unsigned int i = 0; i < num_words; ++i)
                        dead_rays[i] |= inptr[i];
                }
                else if (!ignore_clouds
                         && is_opaque_cloud(env.cgrid[realx][realy]))
                {
                    // block rays which have already seen a cloud
                    for (unsigned int i = 0; i < num_words; ++i)
                    {
                        dead_rays[i]  |= (smoke_rays[i] & inptr[i]);
                        smoke_rays[i] |= inptr[i];
                    }
                }
            }
        // ray calculation done, now work out which cells in this
        // quadrant are visible
        unsigned int rayidx = 0;
        for (unsigned int wordloc = 0; wordloc < num_words; ++wordloc)
        {
            const unsigned long curword = dead_rays[wordloc];
            // Note: the last word may be incomplete
            for (unsigned int bitloc = 0; bitloc < LONGSIZE; ++bitloc)
            {
                // make the cells seen by this ray at this point visible
                if ( ((curword >> bitloc) & 1UL) == 0 )
                {
                    // this ray is alive!
                    const int realx = xmult * compressed_ray_x[rayidx];
                    const int realy = ymult * compressed_ray_y[rayidx];
                    // update shadow map
                    if (x_p + realx >= 0 && x_p + realx < GXM
                        && y_p + realy >= 0 && y_p + realy < GYM
                        && realx * realx + realy * realy <= los_radius_squared)
                    {
                        sh[sh_xo+realx][sh_yo+realy] = gr[x_p+realx][y_p+realy];

Deletion in crawl-ref/source/view.cc at line 1926 [15.16817]
B:BD[24.35521] → [24.35521:35547]
B:BD[24.35547] → [19.1604:1648]
∅:D[19.1648] → [24.35593:35620]
B:BD[24.35593] → [24.35593:35620]
```
                ++rayidx;
                if (rayidx == num_cellrays)
                    break;
```

Deletion in crawl-ref/source/view.cc at line 1929 [15.16817]

B:BD[24.35650] → [67.5:112]

B:BD[67.112] → [17.886:968]


    // [dshaligram] The player's current position is always visible.
    sh[sh_xo][sh_yo] = gr[x_p][y_p];
    *dead_rays     = NULL;
    *smoke_rays    = NULL;
    *los_blockrays = NULL;

Deletion in crawl-ref/source/view.cc at line 2996 [15.16817]
B:BD[68.245] → [69.387:393]
∅:D[69.393] → [68.245:247]
B:BD[68.245] → [68.245:247]
∅:D[68.247] → [15.89193:89194]
B:BD[15.89193] → [15.89193:89194]
B:BD[15.89194] → [18.667:782]
∅:D[18.782] → [24.39450:39452]
B:BD[24.39450] → [24.39450:39452]
B:BD[24.39452] → [18.783:801]
∅:D[18.801] → [24.39551:39574]
B:BD[24.39551] → [24.39551:39574]
∅:D[24.39574] → [15.89194:89195]
B:BD[15.89194] → [15.89194:89195]
B:BD[15.89195] → [18.802:874]
∅:D[18.874] → [24.39664:39670]
B:BD[24.39664] → [24.39664:39670]
B:BD[24.39670] → [18.875:975]
∅:D[18.975] → [24.39789:39816]
B:BD[24.39789] → [24.39789:39816]
```
    }
}
bool see_grid( const env_show_grid &show,
               const coord_def &c,
               const coord_def &pos )
{
    if (c == pos)
        return (true);
    const coord_def ip = pos - c;
    if (ip.rdist() < ENV_SHOW_OFFSET)
    {
        const coord_def sp(ip + coord_def(ENV_SHOW_OFFSET, ENV_SHOW_OFFSET));
        if (show(sp))
            return (true);
```
Deletion in crawl-ref/source/view.cc at line 2997 [15.16817]
B:BD[24.39822] → [18.976:998]
∅:D[18.998] → [24.39822:39823]
B:BD[24.39822] → [24.39822:39823]
B:BD[24.39823] → [59.1429:1500]
∅:D[59.1500] → [18.1070:1108]
B:BD[18.1070] → [18.1070:1108]
B:BD[18.1108] → [61.198:261]
B:BD[61.261] → [21.146:241]
∅:D[21.241] → [18.1153:1155]
∅:D[62.954] → [18.1153:1155]
B:BD[18.1153] → [18.1153:1155]
∅:D[18.1155] → [20.2153:2154]
B:BD[24.39865] → [20.2153:2154]
B:BD[20.2154] → [25.194:270]
∅:D[25.270] → [20.2230:2288]
B:BD[20.2230] → [20.2230:2288]
B:BD[20.2288] → [18.1156:1201]
∅:D[18.1201] → [20.2331:2333]
B:BD[20.2331] → [20.2331:2333]
B:BD[20.2333] → [18.1202:1256]
∅:D[18.1256] → [20.2738:2803]
B:BD[20.2738] → [20.2738:2803]
B:BD[20.2803] → [18.1257:1304]
∅:D[18.1304] → [20.2848:2850]
B:BD[20.2848] → [20.2848:2850]
B:BD[20.2850] → [18.1305:1354]
```
    return (false);
}
// Answers the question: "Is a grid within character's line of sight?"
bool see_grid( const coord_def &p )
{
    return ((crawl_state.arena || crawl_state.arena_suspended)
                && crawl_view.in_grid_los(p))
            || see_grid(env.show, you.pos(), p);
}
// Answers the question: "Would a grid be within character's line of sight,
// even if all translucent/clear walls were made opaque?"
bool see_grid_no_trans( const coord_def &p )
{
    return see_grid(env.no_trans_show, you.pos(), p);
}
// Is the grid visible, but a translucent wall is in the way?
bool trans_wall_blocking( const coord_def &p )
{
    return see_grid(p) && !see_grid_no_trans(p);
```

Deletion in crawl-ref/source/view.cc at line 2999 [15.16817]

B:BD[24.39866] → [25.271:503]

B:BD[25.503] → [59.1501:1617]

B:BD[59.1617] → [22.3539:3600]

∅:D[22.3600] → [25.570:621]

B:BD[25.570] → [25.570:621]

B:BD[25.621] → [12.6:53]

∅:D[12.53] → [25.697:923]

∅:D[22.3653] → [25.697:923]

B:BD[25.697] → [25.697:923]

B:BD[25.923] → [22.3654:3767]

∅:D[35.862] → [25.1051:1054]

∅:D[22.3767] → [25.1051:1054]

B:BD[25.1051] → [25.1051:1054]

// Usually calculates whether from one grid someone could see the other.
// Depending on the viewer's habitat, 'allowed' can be set to DNGN_FLOOR,
// DNGN_SHALLOW_WATER or DNGN_DEEP_WATER.
// Yes, this ignores lava-loving monsters.
// XXX: It turns out the beams are not symmetrical, i.e. switching
// pos1 and pos2 may result in small variations.
bool grid_see_grid(const coord_def& p1, const coord_def& p2,
                   dungeon_feature_type allowed)
{
    if (distance(p1, p2) > los_radius_squared)
        return (false);
    dungeon_feature_type max_disallowed = DNGN_MAXOPAQUE;
    if (allowed != DNGN_UNSEEN)
        max_disallowed = static_cast<dungeon_feature_type>(allowed - 1);
    // XXX: Ignoring clouds for now.
    return (!num_feats_between(p1, p2, DNGN_UNSEEN, max_disallowed,
                               true, true));
}

Deletion in crawl-ref/source/view.cc at line 4058 [15.16817]

B:BD[4.31] → [4.31:194]

∅:D[4.194] → [70.5496:5497]

B:BD[70.5496] → [70.5496:5497]

B:BD[70.5497] → [4.195:430]

void calc_show_los()
{
    if (!crawl_state.arena && !crawl_state.arena_suspended)
    {
        // Must be done first.
        losight(env.show, grd, you.pos());
        // What would be visible, if all of the translucent walls were
        // made opaque.
        losight(env.no_trans_show, grd, you.pos(), true);
    }
    else
    {
        losight(env.show, grd, crawl_view.glosc());
    }
}

Deletion in crawl-ref/source/view.cc at line 4772 [15.16817]

B:BD[37.1392] → [37.1392:1513]

B:BD[37.1513] → [39.107:172]

∅:D[39.172] → [37.1559:1597]

B:BD[37.1559] → [37.1559:1597]

B:BD[37.1597] → [39.173:236]

B:BD[39.236] → [38.164:196]

∅:D[38.196] → [39.338:565]

B:BD[39.338] → [39.338:565]

∅:D[39.565] → [37.1597:2462]

B:BD[37.1597] → [37.1597:2462]

B:BD[37.2462] → [12.54:113]

∅:D[12.113] → [37.2526:3293]

B:BD[37.2526] → [37.2526:3293]

B:BD[37.3585] → [37.3585:3647]

B:BD[37.3647] → [39.566:603]

∅:D[39.603] → [37.3689:4695]

B:BD[37.3689] → [37.3689:4695]

B:BD[37.4695] → [39.604:705]

∅:D[39.705] → [37.4756:4903]

B:BD[37.4756] → [37.4756:4903]

B:BD[37.4903] → [39.706:794]

∅:D[39.794] → [37.5011:5433]

B:BD[37.5011] → [37.5011:5433]

B:BD[37.5433] → [71.7:119]

∅:D[71.119] → [37.5541:5704]

B:BD[37.5541] → [37.5541:5704]

B:BD[37.5704] → [71.120:188]

∅:D[71.188] → [37.5760:5939]

B:BD[37.5760] → [37.5760:5939]

B:BD[37.5939] → [39.795:885]

∅:D[39.885] → [37.6039:6139]

B:BD[37.6039] → [37.6039:6139]

B:BD[37.6139] → [39.886:976]

∅:D[39.976] → [37.6239:6434]

B:BD[37.6239] → [37.6239:6434]

B:BD[37.6434] → [39.977:1049]

∅:D[39.1049] → [37.6516:6549]

B:BD[37.6516] → [37.6516:6549]

B:BD[37.6549] → [39.1050:1122]

∅:D[39.1122] → [37.6631:6948]

B:BD[37.6631] → [37.6631:6948]

B:BD[37.6948] → [39.1123:1167]

∅:D[39.1167] → [37.6997:7054]

B:BD[37.6997] → [37.6997:7054]

B:BD[37.7054] → [39.1168:1212]

∅:D[39.1212] → [37.7103:7291]

B:BD[37.7103] → [37.7103:7291]

B:BD[37.7291] → [39.1213:1257]

∅:D[39.1257] → [37.7340:7469]

B:BD[37.7340] → [37.7340:7469]

B:BD[37.7469] → [39.1258:1302]

∅:D[39.1302] → [37.7518:7689]

B:BD[37.7518] → [37.7518:7689]

B:BD[37.7689] → [39.1303:1375]

∅:D[39.1375] → [37.7771:7826]

B:BD[37.7771] → [37.7771:7826]

B:BD[37.7826] → [39.1376:1448]

∅:D[39.1448] → [37.7908:8169]

B:BD[37.7908] → [37.7908:8169]

B:BD[37.8169] → [39.1449:1493]

∅:D[39.1493] → [37.8218:8347]

B:BD[37.8218] → [37.8218:8347]

B:BD[37.8347] → [39.1494:1538]

∅:D[39.1538] → [37.8396:8573]

B:BD[37.8396] → [37.8396:8573]

B:BD[37.8573] → [39.1539:1583]

∅:D[39.1583] → [37.8622:8679]

B:BD[37.8622] → [37.8622:8679]

B:BD[37.8679] → [39.1584:1628]

∅:D[39.1628] → [37.8728:9140]

B:BD[37.8728] → [37.8728:9140]

B:BD[37.9140] → [39.1629:1685]

∅:D[39.1685] → [37.9189:9242]

B:BD[37.9189] → [37.9189:9242]

B:BD[37.9242] → [71.189:494]

∅:D[71.494] → [37.9242:9249]

B:BD[37.9242] → [37.9242:9249]

B:BD[37.9249] → [39.1686:1718]

∅:D[39.1718] → [37.9286:9444]

B:BD[37.9286] → [37.9286:9444]

B:BD[37.9444] → [72.7:312]

B:BD[72.312] → [8.6:43]

∅:D[8.43] → [72.350:377]

B:BD[72.350] → [72.350:377]

∅:D[72.377] → [37.9444:9658]

B:BD[37.9444] → [37.9444:9658]

B:BD[37.9658] → [22.4330:4446]

∅:D[22.4446] → [37.9730:9731]

B:BD[37.9730] → [37.9730:9731]

B:BD[37.9780] → [37.9780:9923]

B:BD[37.9923] → [73.7:76]

∅:D[73.76] → [72.447:679]

B:BD[72.447] → [72.447:679]

∅:D[72.679] → [37.9976:10976]

B:BD[37.9976] → [37.9976:10976]

/////////////////////////////////////////////////////////////////////////////
// monster_los
monster_los::monster_los()
    : gridx(0), gridy(0), mons(), range(LOS_RADIUS), los_field()
{
}
monster_los::~monster_los()
{
}
void monster_los::set_monster(monsters *mon)
{
    mons = mon;
    set_los_centre(mon->pos());
}
void monster_los::set_los_centre(int x, int y)
{
    if (!in_bounds(x, y))
        return;
    gridx = x;
    gridy = y;
}
void monster_los::set_los_range(int r)
{
    ASSERT (r >= 1 && r <= LOS_RADIUS);
    range = r;
}
coord_def monster_los::pos_to_index(coord_def &p)
{
    int ix = LOS_RADIUS + p.x - gridx;
    int iy = LOS_RADIUS + p.y - gridy;
    ASSERT(ix >= 0 && ix < LSIZE);
    ASSERT(iy >= 0 && iy < LSIZE);
    return (coord_def(ix, iy));
}
coord_def monster_los::index_to_pos(coord_def &i)
{
    int px = i.x + gridx - LOS_RADIUS;
    int py = i.y + gridy - LOS_RADIUS;
    ASSERT(in_bounds(px, py));
    return (coord_def(px, py));
}
void monster_los::set_los_value(int x, int y, bool blocked, bool override)
{
    if (!override && !is_unknown(x,y))
        return;
    coord_def c(x,y);
    coord_def lpos = pos_to_index(c);
    int value = (blocked ? L_BLOCKED : L_VISIBLE);
    if (value != los_field[lpos.x][lpos.y])
        los_field[lpos.x][lpos.y] = value;
}
int monster_los::get_los_value(int x, int y)
{
    // Too far away -> definitely out of sight!
    if (distance(x, y, gridx, gridy) > los_radius_squared)
        return (L_BLOCKED);
    coord_def c(x,y);
    coord_def lpos = pos_to_index(c);
    return (los_field[lpos.x][lpos.y]);
}
bool monster_los::in_sight(int x, int y)
{
    // Is the path to (x,y) clear?
    return (get_los_value(x,y) == L_VISIBLE);
}
bool monster_los::is_blocked(int x, int y)
{
    // Is the path to (x,y) blocked?
    return (get_los_value(x, y) == L_BLOCKED);
}
bool monster_los::is_unknown(int x, int y)
{
    return (get_los_value(x, y) == L_UNKNOWN);
}
static bool _blocks_movement_sight(monsters *mon, dungeon_feature_type feat)
{
    if (feat < DNGN_MINMOVE)
        return (true);
    if (!mon) // No monster defined?
        return (false);
    if (!mon->can_pass_through_feat(feat))
        return (true);
    return (false);
}
void monster_los::fill_los_field()
{
    int pos_x, pos_y;
    for (int k = 1; k <= range; k++)
        for (int i = -1; i <= 1; i++)
            for (int j = -1; j <= 1; j++)
            {
                if (i == 0 && j == 0) // Ignore centre grid.
                    continue;
                pos_x = gridx + k*i;
                pos_y = gridy + k*j;
                if (!in_bounds(pos_x, pos_y))
                    continue;
                if (!_blocks_movement_sight(mons, grd[pos_x][pos_y]))
                    set_los_value(pos_x, pos_y, false);
                else
                {
                    set_los_value(pos_x, pos_y, true);
                    // Check all beam potentially going through a blocked grid.
                    check_los_beam(pos_x, pos_y);
                }
            }
}
// (cx, cy) is the centre point
// (dx, dy) is the target we're aiming *through*
// target1 and target2 are targets we'll be aiming *at* to fire through (dx,dy)
static bool _set_beam_target(int cx, int cy, int dx, int dy,
                             int &target1_x, int &target1_y,
                             int &target2_x, int &target2_y,
                             int range)
{
    const int xdist = dx - cx;
    const int ydist = dy - cy;
    if (xdist == 0 && ydist == 0)
        return (false); // Nothing to be done.
    if (xdist <= -range || xdist >= range
        || ydist <= -range || ydist >= range)
    {
        // Grids on the edge of a monster's LOS don't block sight any further.
        return (false);
    }
/*
 *   The following code divides the field into eights of different directions.
 *
 *    \  NW | NE  /
 *      \   |   /
 *    WN  \ | /   EN
 *   ----------------
 *    WS  / | \   ES
 *      /   |   \
 *    /  SW | SE  \
 *
 *   target1_x and target1_y mark the base line target, so the base beam ends
 *   on the diagonal line closest to the target (or on one of the straight
 *   lines if cx == dx or dx == dy).
 *
 *   target2_x and target2_y then mark the second target our beam finder should
 *   cycle through. It'll always be target2_x = dx or target2_y = dy, the other
 *   being on the edge of LOS, which one depending on the quadrant.
 *
 *   The beam finder can then cycle from the nearest corner (target1) to the
 *   second edge target closest to (dx,dy).
 */
    if (xdist == 0)
    {
        target1_x = cx;
        target1_y = (ydist > 0 ? cy + range
                               : cy - range);
        target2_x = target1_x;
        target2_y = target1_y;
    }
    else if (ydist == 0)
    {
        target1_x = (xdist > 0 ? cx + range
                               : cx - range);
        target1_y = cy;
        target2_x = target1_x;
        target2_y = target1_y;
    }
    else if (xdist < 0 && ydist < 0 || xdist > 0 && ydist > 0)
    {
        if (xdist < 0)
        {
            target1_x = cx - range;
            target1_y = cy - range;
        }
        else
        {
            target1_x = cx + range;
            target1_y = cy + range;
        }
        if (xdist == ydist)
        {
            target2_x = target1_x;
            target2_y = target1_y;
        }
        else
        {
            if (xdist < 0) // both are negative (upper left corner)
            {
                if (dx > dy)
                {
                    target2_x = dx;
                    target2_y = cy - range;
                }
                else
                {
                    target2_x = cx - range;
                    target2_y = dy;
                }
            }
            else // both are positive (lower right corner)
            {
                if (dx > dy)
                {
                    target2_x = cx + range;
                    target2_y = dy;
                }
                else
                {
                    target2_x = dx;
                    target2_y = cy + range;
                }
            }
        }
    }
    else if (xdist < 0 && ydist > 0 || xdist > 0 && ydist < 0)
    {
        if (xdist < 0) // lower left corner
        {
            target1_x = cx - range;
            target1_y = cy + range;
        }
        else // upper right corner
        {
            target1_x = cx + range;
            target1_y = cy - range;
        }
        if (xdist == -ydist)
        {
            target2_x = target1_x;
            target2_y = target1_y;
        }
        else
        {
            if (xdist < 0) // ydist > 0
            {
                if (-xdist > ydist)
                {
                    target2_x = cx - range;
                    target2_y = dy;
                }
                else
                {
                    target2_x = dx;
                    target2_y = cy + range;
                }
            }
            else // xdist > 0, ydist < 0
            {
                if (-xdist > ydist)
                {
                    target2_x = dx;
                    target2_y = cy - range;
                }
                else
                {
                    target2_x = cx + range;
                    target2_y = dy;
                }
            }
        }
    }
    else
    {
        // Everything should have been handled above.
        ASSERT(false);
    }
    return (true);
}
void monster_los::check_los_beam(int dx, int dy)
{
    ray_def ray;
    int target1_x = 0, target1_y = 0, target2_x = 0, target2_y = 0;
    if (!_set_beam_target(gridx, gridy, dx, dy, target1_x, target1_y,
                          target2_x, target2_y, range))
    {
        // Nothing to be done.
        return;
    }
    if (target1_x > target2_x || target1_y > target2_y)
    {
        // Swap the two targets so our loop will work correctly.
        int help = target1_x;
        target1_x = target2_x;
        target2_x = help;
        help = target1_y;
        target1_y = target2_y;
        target2_y = help;
    }
    const int max_dist = range;
    int dist;
    bool blocked = false;
    for (int tx = target1_x; tx <= target2_x; tx++)
        for (int ty = target1_y; ty <= target2_y; ty++)
        {
            // If (tx, ty) lies outside the level boundaries, there's nothing
            // that shooting a ray into that direction could bring us, esp.
            // as earlier grids in the ray will already have been handled, and
            // out of bounds grids are simply skipped in any LoS check.
            if (!map_bounds(tx, ty))
                continue;
            // Already calculated a beam to (tx, ty), don't do so again.
            if (!is_unknown(tx, ty))
                continue;
            dist = 0;
            ray.fullray_idx = -1; // to quiet valgrind
            find_ray( coord_def(gridx, gridy), coord_def(tx, ty),
                      true, ray, 0, true, true );
            if (ray.x() == gridx && ray.y() == gridy)
                ray.advance(true);
            while (dist++ <= max_dist)
            {
                // The ray brings us out of bounds of the level map.
                // Since we're always shooting outwards there's nothing more
                // to look at in that direction, and we can break the loop.
                if (!map_bounds(ray.x(), ray.y()))
                    break;
                if (blocked)
                {
                    // Earlier grid blocks this beam, set to blocked if
                    // unknown, but don't overwrite visible grids.
                    set_los_value(ray.x(), ray.y(), true);
                }
                else if (_blocks_movement_sight(mons, grd[ray.x()][ray.y()]))
                {
                    set_los_value(ray.x(), ray.y(), true);
                    // The rest of the beam will now be blocked.
                    blocked = true;
                }
                else
                {
                    // Allow overriding in case another beam has marked this
                    // field as blocked, because we've found a solution where
                    // that isn't the case.
                    set_los_value(ray.x(), ray.y(), false, true);
                }
                if (ray.x() == tx && ray.y() == ty)
                    break;
                ray.advance(true);
            }
        }
}

Insertion in crawl-ref/source/tutorial.cc at line 33 [45.5936]
[11.266]
[74.1421]
```
#include "los.h"
```
Insertion in crawl-ref/source/travel.cc at line 27 [16.39949]
[75.575]
[33.2959]
```
#include "los.h"
```
Insertion in crawl-ref/source/traps.cc at line 25 [33.5308]
[76.474]
[33.5791]
```
#include "los.h"
```
Insertion in crawl-ref/source/terrain.cc at line 21 [33.26938]
[33.27390]
[33.27390]
```
#include "los.h"
```
Insertion in crawl-ref/source/stuff.cc at line 14 [15.224557]
[77.570]
[78.136]
```
#include "los.h"
```
Insertion in crawl-ref/source/state.cc at line 14 [79.1546]
[77.596]
[79.1874]
```
#include "los.h"
```
Insertion in crawl-ref/source/stash.cc at line 26 [16.147324]
[16.147642]
[16.147642]
```
#include "los.h"
```
Insertion in crawl-ref/source/spl-util.cc at line 27 [15.245665]
[15.246468]
[15.246468]
```
#include "los.h"
```
Insertion in crawl-ref/source/spl-cast.cc at line 29 [15.293070]
[24.124714]
[15.293806]
```
#include "los.h"
```
Insertion in crawl-ref/source/spells4.cc at line 34 [15.436250]
[15.436942]
[80.143]
```
#include "los.h"
```
Insertion in crawl-ref/source/spells3.cc at line 34 [15.531613]
[81.478]
[33.46772]
```
#include "los.h"
```
Insertion in crawl-ref/source/spells2.cc at line 33 [15.569242]
[82.886]
[33.46850]
```
#include "los.h"
```
Insertion in crawl-ref/source/spells1.cc at line 31 [15.616635]
[24.152806]
[33.46929]
```
#include "los.h"
```
Insertion in crawl-ref/source/religion.cc at line 47 [15.804403]
[11.3086]
[83.172]
```
#include "los.h"
```

Insertion in crawl-ref/source/ray.h at line 10 [33.47173]

[33.47509]

int shoot_ray(double accx, double accy, const double slope,
                int maxrange, int xpos[], int ypos[]);

File addition: ray.cc (----------)

[84.24]

/*
 *  File:       ray.cc
 *  Summary:    Ray definition
 */
#include "AppHdr.h"
REVISION("$Rev$");
#include "ray.h"
#include <cmath>
#include "los.h"
#include "terrain.h"
// note that slope must be nonnegative!
// returns 0 if the advance was in x, 1 if it was in y, 2 if it was
// the diagonal
static int _find_next_intercept(double* accx, double* accy, const double slope)
{
    // handle perpendiculars
    if ( double_is_zero(slope) )
    {
        *accx += 1.0;
        return 0;
    }
    if ( slope > 100.0 )
    {
        *accy += 1.0;
        return 1;
    }
    const double xtarget = (static_cast<int>(*accx) + 1);
    const double ytarget = (static_cast<int>(*accy) + 1);
    const double xdistance = xtarget - *accx;
    const double ydistance = ytarget - *accy;
    double distdiff = (xdistance * slope - ydistance);
    // exact corner
    if ( double_is_zero( distdiff ) )
    {
        // move somewhat away from the corner
        if ( slope > 1.0 )
        {
            *accx = xtarget + EPSILON_VALUE * 2;
            *accy = ytarget + EPSILON_VALUE * 2 * slope;
        }
        else
        {
            *accx = xtarget + EPSILON_VALUE * 2 / slope;
            *accy = ytarget + EPSILON_VALUE * 2;
        }
        return 2;
    }
    // move to the boundary
    double traveldist;
    int rc = -1;
    if ( distdiff > 0.0 )
    {
        traveldist = ydistance / slope;
        rc = 1;
    }
    else
    {
        traveldist = xdistance;
        rc = 0;
    }
    // and a little into the next cell, taking care
    // not to go too far
    if ( distdiff < 0.0 )
        distdiff = -distdiff;
    traveldist += std::min(EPSILON_VALUE * 10.0, 0.5 * distdiff / slope);
    *accx += traveldist;
    *accy += traveldist * slope;
    return rc;
}
// Shoot a ray from the given start point (accx, accy) with the given
// slope, with a maximum distance (in either x or y coordinate) of
// maxrange. Store the visited cells in xpos[] and ypos[], and
// return the number of cells visited.
int shoot_ray( double accx, double accy, const double slope,
                int maxrange, int xpos[], int ypos[] )
{
    int curx, cury;
    int cellnum;
    for (cellnum = 0; true; ++cellnum)
    {
        _find_next_intercept( &accx, &accy, slope );
        curx = static_cast<int>(accx);
        cury = static_cast<int>(accy);
        if (curx*curx + cury*cury > get_los_radius_squared())
            break;
        // Work with the new square.
        xpos[cellnum] = curx;
        ypos[cellnum] = cury;
    }
    return cellnum;
}
ray_def::ray_def() : accx(0.0), accy(0.0), slope(0.0), quadrant(0),
                     fullray_idx(0)
{
}
double ray_def::reflect(double p, double c) const
{
    return (c + c - p);
}
double ray_def::reflect(bool rx, double oldx, double newx) const
{
    if (rx? fabs(slope) > 1.0 : fabs(slope) < 1.0)
        return (reflect(oldx, floor(oldx) + 0.5));
    const double flnew = floor(newx);
    const double flold = floor(oldx);
    return (reflect(oldx,
                    flnew > flold? flnew :
                    flold > flnew? flold :
                    (newx + oldx) / 2));
}
void ray_def::set_reflect_point(const double oldx, const double oldy,
                                double *newx, double *newy,
                                bool blocked_x, bool blocked_y)
{
    if (blocked_x == blocked_y)
    {
        // What to do?
        *newx = oldx;
        *newy = oldy;
        return;
    }
    if (blocked_x)
    {
        ASSERT(int(oldy) != int(*newy));
        *newy = oldy;
        *newx = reflect(true, oldx, *newx);
    }
    else
    {
        ASSERT(int(oldx) != int(*newx));
        *newx = oldx;
        *newy = reflect(false, oldy, *newy);
    }
}
void ray_def::advance_and_bounce()
{
    // 0 = down-right, 1 = down-left, 2 = up-left, 3 = up-right
    int bouncequad[4][3] =
    {
        { 1, 3, 2 }, { 0, 2, 3 }, { 3, 1, 0 }, { 2, 0, 1 }
    };
    int oldx = x(), oldy = y();
    const double oldaccx = accx, oldaccy = accy;
    int rc = advance(false);
    int newx = x(), newy = y();
    ASSERT( grid_is_solid(grd[newx][newy]) );
    const bool blocked_x = grid_is_solid(grd[oldx][newy]);
    const bool blocked_y = grid_is_solid(grd[newx][oldy]);
    if ( double_is_zero(slope) || slope > 100.0 )
        quadrant = bouncequad[quadrant][2];
    else if ( rc != 2 )
        quadrant = bouncequad[quadrant][rc];
    else
    {
        ASSERT( (oldx != newx) && (oldy != newy) );
        if ( blocked_x && blocked_y )
            quadrant = bouncequad[quadrant][rc];
        else if ( blocked_x )
            quadrant = bouncequad[quadrant][1];
        else
            quadrant = bouncequad[quadrant][0];
    }
    set_reflect_point(oldaccx, oldaccy, &accx, &accy, blocked_x, blocked_y);
}
double ray_def::get_degrees() const
{
    if (slope > 100.0)
    {
        if (quadrant == 3 || quadrant == 2)
            return (90.0);
        else
            return (270.0);
    }
    else if (double_is_zero(slope))
    {
        if (quadrant == 0 || quadrant == 3)
            return (0.0);
        else
            return (180.0);
    }
    double deg = atan(slope) * 180.0 / M_PI;
    switch (quadrant)
    {
    case 0:
        return (360.0 - deg);
    case 1:
        return (180.0 + deg);
    case 2:
        return (180.0 - deg);
    case 3:
        return (deg);
    }
    ASSERT(!"ray has illegal quadrant");
    return (0.0);
}
void ray_def::set_degrees(double deg)
{
    while (deg < 0.0)
        deg += 360.0;
    while (deg >= 360.0)
        deg -= 360.0;
    double _slope = tan(deg / 180.0 * M_PI);
    if (double_is_zero(_slope))
    {
        slope = 0.0;
        if (deg < 90.0 || deg > 270.0)
            quadrant = 0; // right/east
        else
            quadrant = 1; // left/west
    }
    else if (_slope > 0)
    {
        slope = _slope;
        if (deg >= 180.0 && deg <= 270.0)
            quadrant = 1;
        else
            quadrant = 3;
    }
    else
    {
        slope = -_slope;
        if (deg >= 90 && deg <= 180)
            quadrant = 2;
        else
            quadrant = 0;
    }
    if (slope > 1000.0)
        slope = 1000.0;
}
void ray_def::regress()
{
    int opp_quadrant[4] = { 2, 3, 0, 1 };
    quadrant = opp_quadrant[quadrant];
    advance(false);
    quadrant = opp_quadrant[quadrant];
}
int ray_def::advance_through(const coord_def &target)
{
    return (advance(true, &target));
}
int ray_def::advance(bool shortest_possible, const coord_def *target)
{
    if (!shortest_possible)
        return (raw_advance());
    // If we want to minimise the number of moves on the ray, look one
    // step ahead and see if we can get a diagonal.
    const coord_def old(static_cast<int>(accx), static_cast<int>(accy));
    const int ret = raw_advance();
    if (ret == 2 || (target && pos() == *target))
        return (ret);
    const double maccx = accx, maccy = accy;
    if (raw_advance() != 2)
    {
        const coord_def second(static_cast<int>(accx), static_cast<int>(accy));
        // If we can convert to a diagonal, do so.
        if ((second - old).abs() == 2)
            return (2);
    }
    // No diagonal, so roll back.
    accx = maccx;
    accy = maccy;
    return (ret);
}
int ray_def::raw_advance()
{
    int rc;
    switch ( quadrant )
    {
    case 0:
        // going down-right
        rc = _find_next_intercept( &accx, &accy, slope );
        return rc;
    case 1:
        // going down-left
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        rc   = _find_next_intercept( &accx, &accy, slope );
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        return rc;
    case 2:
        // going up-left
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        rc   = _find_next_intercept( &accx, &accy, slope );
        accx = 100.0 - EPSILON_VALUE/10.0 - accx;
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        return rc;
    case 3:
        // going up-right
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        rc   = _find_next_intercept( &accx, &accy, slope );
        accy = 100.0 - EPSILON_VALUE/10.0 - accy;
        return rc;
    default:
        return -1;
    }
}

Insertion in crawl-ref/source/player.cc at line 41 [15.962854]
[11.3120]
[15.963695]
```
#include "los.h"
```
Insertion in crawl-ref/source/ouch.cc at line 48 [15.1104358]
[15.1106166]
[15.1106166]
```
#include "los.h"
```
Insertion in crawl-ref/source/mstuff2.cc at line 32 [15.1340842]
[11.3181]
[33.58895]
```
#include "los.h"
```
Insertion in crawl-ref/source/monstuff.cc at line 40 [15.1396662]
[11.3204]
[80.326]
```
#include "los.h"
```
Insertion in crawl-ref/source/monstuff.cc at line 47 [15.1396662]
[15.1397774]
[24.411209]
```
#include "mon-los.h"
```
Insertion in crawl-ref/source/monplace.cc at line 20 [15.1641732]
[50.278]
[80.448]
```
#include "los.h"
```
Insertion in crawl-ref/source/mon-util.cc at line 39 [15.1699344]
[11.3230]
[33.71988]
```
#include "los.h"
```

File addition: mon-los.h (----------)

[84.24]

#ifndef MON_LOS_H
/*
 *  File:       mon-los.cc
 *  Summary:    Monster line-of-sight.
 */
#define MON_LOS_H
#define _monster_los_LSIZE (2 * LOS_RADIUS + 1)
// This class can be used to fill the entire surroundings (los_range)
// of a monster or other position with seen/unseen values, so as to be able
// to compare several positions within this range.
class monster_los
{
public:
    monster_los();
    virtual ~monster_los();
    // public methods
    void set_monster(monsters *mon);
    void set_los_centre(int x, int y);
    void set_los_centre(const coord_def& p) { this->set_los_centre(p.x, p.y); }
    void set_los_range(int r);
    void fill_los_field(void);
    bool in_sight(int x, int y);
    bool in_sight(const coord_def& p) { return this->in_sight(p.x, p.y); }
protected:
    // protected methods
    coord_def pos_to_index(coord_def &p);
    coord_def index_to_pos(coord_def &i);
    void set_los_value(int x, int y, bool blocked, bool override = false);
    int get_los_value(int x, int y);
    bool is_blocked(int x, int y);
    bool is_unknown(int x, int y);
    void check_los_beam(int dx, int dy);
    // The (fixed) size of the array.
    static const int LSIZE;
    static const int L_VISIBLE;
    static const int L_UNKNOWN;
    static const int L_BLOCKED;
    // The centre of our los field.
    int gridx, gridy;
    // Habitat checks etc. should be done for this monster.
    // Usually the monster whose LOS we're trying to calculate
    // (if mon->x == gridx, mon->y == gridy).
    // Else, any monster trying to move around within this los field.
    monsters *mons;
    // Range may never be greater than LOS_RADIUS!
    int range;
    // The array to store the LOS values.
    int los_field[_monster_los_LSIZE][_monster_los_LSIZE];
};
#endif

File addition: mon-los.cc (----------)

[84.24]

/*
 *  File:       mon-los.cc
 *  Summary:    Monster line-of-sight.
 */
#include "AppHdr.h"
REVISION("$Rev$");
#include "mon-los.h"
#include "los.h"
#include "ray.h"
#include "stuff.h"
// Static class members must be initialised outside of the class
// declaration, or gcc won't define them in view.o and we'll get a
// linking error.
const int monster_los::LSIZE     =  _monster_los_LSIZE;
const int monster_los::L_VISIBLE =  1;
const int monster_los::L_UNKNOWN =  0;
const int monster_los::L_BLOCKED = -1;
/////////////////////////////////////////////////////////////////////////////
// monster_los
monster_los::monster_los()
    : gridx(0), gridy(0), mons(), range(LOS_RADIUS), los_field()
{
}
monster_los::~monster_los()
{
}
void monster_los::set_monster(monsters *mon)
{
    mons = mon;
    set_los_centre(mon->pos());
}
void monster_los::set_los_centre(int x, int y)
{
    if (!in_bounds(x, y))
        return;
    gridx = x;
    gridy = y;
}
void monster_los::set_los_range(int r)
{
    ASSERT (r >= 1 && r <= LOS_RADIUS);
    range = r;
}
coord_def monster_los::pos_to_index(coord_def &p)
{
    int ix = LOS_RADIUS + p.x - gridx;
    int iy = LOS_RADIUS + p.y - gridy;
    ASSERT(ix >= 0 && ix < LSIZE);
    ASSERT(iy >= 0 && iy < LSIZE);
    return (coord_def(ix, iy));
}
coord_def monster_los::index_to_pos(coord_def &i)
{
    int px = i.x + gridx - LOS_RADIUS;
    int py = i.y + gridy - LOS_RADIUS;
    ASSERT(in_bounds(px, py));
    return (coord_def(px, py));
}
void monster_los::set_los_value(int x, int y, bool blocked, bool override)
{
    if (!override && !is_unknown(x,y))
        return;
    coord_def c(x,y);
    coord_def lpos = pos_to_index(c);
    int value = (blocked ? L_BLOCKED : L_VISIBLE);
    if (value != los_field[lpos.x][lpos.y])
        los_field[lpos.x][lpos.y] = value;
}
int monster_los::get_los_value(int x, int y)
{
    // Too far away -> definitely out of sight!
    if (distance(x, y, gridx, gridy) > get_los_radius_squared())
        return (L_BLOCKED);
    coord_def c(x,y);
    coord_def lpos = pos_to_index(c);
    return (los_field[lpos.x][lpos.y]);
}
bool monster_los::in_sight(int x, int y)
{
    // Is the path to (x,y) clear?
    return (get_los_value(x,y) == L_VISIBLE);
}
bool monster_los::is_blocked(int x, int y)
{
    // Is the path to (x,y) blocked?
    return (get_los_value(x, y) == L_BLOCKED);
}
bool monster_los::is_unknown(int x, int y)
{
    return (get_los_value(x, y) == L_UNKNOWN);
}
static bool _blocks_movement_sight(monsters *mon, dungeon_feature_type feat)
{
    if (feat < DNGN_MINMOVE)
        return (true);
    if (!mon) // No monster defined?
        return (false);
    if (!mon->can_pass_through_feat(feat))
        return (true);
    return (false);
}
void monster_los::fill_los_field()
{
    int pos_x, pos_y;
    for (int k = 1; k <= range; k++)
        for (int i = -1; i <= 1; i++)
            for (int j = -1; j <= 1; j++)
            {
                if (i == 0 && j == 0) // Ignore centre grid.
                    continue;
                pos_x = gridx + k*i;
                pos_y = gridy + k*j;
                if (!in_bounds(pos_x, pos_y))
                    continue;
                if (!_blocks_movement_sight(mons, grd[pos_x][pos_y]))
                    set_los_value(pos_x, pos_y, false);
                else
                {
                    set_los_value(pos_x, pos_y, true);
                    // Check all beam potentially going through a blocked grid.
                    check_los_beam(pos_x, pos_y);
                }
            }
}
// (cx, cy) is the centre point
// (dx, dy) is the target we're aiming *through*
// target1 and target2 are targets we'll be aiming *at* to fire through (dx,dy)
static bool _set_beam_target(int cx, int cy, int dx, int dy,
                             int &target1_x, int &target1_y,
                             int &target2_x, int &target2_y,
                             int range)
{
    const int xdist = dx - cx;
    const int ydist = dy - cy;
    if (xdist == 0 && ydist == 0)
        return (false); // Nothing to be done.
    if (xdist <= -range || xdist >= range
        || ydist <= -range || ydist >= range)
    {
        // Grids on the edge of a monster's LOS don't block sight any further.
        return (false);
    }
/*
 *   The following code divides the field into eights of different directions.
 *
 *    \  NW | NE  /
 *      \   |   /
 *    WN  \ | /   EN
 *   ----------------
 *    WS  / | \   ES
 *      /   |   \
 *    /  SW | SE  \
 *
 *   target1_x and target1_y mark the base line target, so the base beam ends
 *   on the diagonal line closest to the target (or on one of the straight
 *   lines if cx == dx or dx == dy).
 *
 *   target2_x and target2_y then mark the second target our beam finder should
 *   cycle through. It'll always be target2_x = dx or target2_y = dy, the other
 *   being on the edge of LOS, which one depending on the quadrant.
 *
 *   The beam finder can then cycle from the nearest corner (target1) to the
 *   second edge target closest to (dx,dy).
 */
    if (xdist == 0)
    {
        target1_x = cx;
        target1_y = (ydist > 0 ? cy + range
                               : cy - range);
        target2_x = target1_x;
        target2_y = target1_y;
    }
    else if (ydist == 0)
    {
        target1_x = (xdist > 0 ? cx + range
                               : cx - range);
        target1_y = cy;
        target2_x = target1_x;
        target2_y = target1_y;
    }
    else if (xdist < 0 && ydist < 0 || xdist > 0 && ydist > 0)
    {
        if (xdist < 0)
        {
            target1_x = cx - range;
            target1_y = cy - range;
        }
        else
        {
            target1_x = cx + range;
            target1_y = cy + range;
        }
        if (xdist == ydist)
        {
            target2_x = target1_x;
            target2_y = target1_y;
        }
        else
        {
            if (xdist < 0) // both are negative (upper left corner)
            {
                if (dx > dy)
                {
                    target2_x = dx;
                    target2_y = cy - range;
                }
                else
                {
                    target2_x = cx - range;
                    target2_y = dy;
                }
            }
            else // both are positive (lower right corner)
            {
                if (dx > dy)
                {
                    target2_x = cx + range;
                    target2_y = dy;
                }
                else
                {
                    target2_x = dx;
                    target2_y = cy + range;
                }
            }
        }
    }
    else if (xdist < 0 && ydist > 0 || xdist > 0 && ydist < 0)
    {
        if (xdist < 0) // lower left corner
        {
            target1_x = cx - range;
            target1_y = cy + range;
        }
        else // upper right corner
        {
            target1_x = cx + range;
            target1_y = cy - range;
        }
        if (xdist == -ydist)
        {
            target2_x = target1_x;
            target2_y = target1_y;
        }
        else
        {
            if (xdist < 0) // ydist > 0
            {
                if (-xdist > ydist)
                {
                    target2_x = cx - range;
                    target2_y = dy;
                }
                else
                {
                    target2_x = dx;
                    target2_y = cy + range;
                }
            }
            else // xdist > 0, ydist < 0
            {
                if (-xdist > ydist)
                {
                    target2_x = dx;
                    target2_y = cy - range;
                }
                else
                {
                    target2_x = cx + range;
                    target2_y = dy;
                }
            }
        }
    }
    else
    {
        // Everything should have been handled above.
        ASSERT(false);
    }
    return (true);
}
void monster_los::check_los_beam(int dx, int dy)
{
    ray_def ray;
    int target1_x = 0, target1_y = 0, target2_x = 0, target2_y = 0;
    if (!_set_beam_target(gridx, gridy, dx, dy, target1_x, target1_y,
                          target2_x, target2_y, range))
    {
        // Nothing to be done.
        return;
    }
    if (target1_x > target2_x || target1_y > target2_y)
    {
        // Swap the two targets so our loop will work correctly.
        int help = target1_x;
        target1_x = target2_x;
        target2_x = help;
        help = target1_y;
        target1_y = target2_y;
        target2_y = help;
    }
    const int max_dist = range;
    int dist;
    bool blocked = false;
    for (int tx = target1_x; tx <= target2_x; tx++)
        for (int ty = target1_y; ty <= target2_y; ty++)
        {
            // If (tx, ty) lies outside the level boundaries, there's nothing
            // that shooting a ray into that direction could bring us, esp.
            // as earlier grids in the ray will already have been handled, and
            // out of bounds grids are simply skipped in any LoS check.
            if (!map_bounds(tx, ty))
                continue;
            // Already calculated a beam to (tx, ty), don't do so again.
            if (!is_unknown(tx, ty))
                continue;
            dist = 0;
            ray.fullray_idx = -1; // to quiet valgrind
            find_ray( coord_def(gridx, gridy), coord_def(tx, ty),
                      true, ray, 0, true, true );
            if (ray.x() == gridx && ray.y() == gridy)
                ray.advance(true);
            while (dist++ <= max_dist)
            {
                // The ray brings us out of bounds of the level map.
                // Since we're always shooting outwards there's nothing more
                // to look at in that direction, and we can break the loop.
                if (!map_bounds(ray.x(), ray.y()))
                    break;
                if (blocked)
                {
                    // Earlier grid blocks this beam, set to blocked if
                    // unknown, but don't overwrite visible grids.
                    set_los_value(ray.x(), ray.y(), true);
                }
                else if (_blocks_movement_sight(mons, grd[ray.x()][ray.y()]))
                {
                    set_los_value(ray.x(), ray.y(), true);
                    // The rest of the beam will now be blocked.
                    blocked = true;
                }
                else
                {
                    // Allow overriding in case another beam has marked this
                    // field as blocked, because we've found a solution where
                    // that isn't the case.
                    set_los_value(ray.x(), ray.y(), false, true);
                }
                if (ray.x() == tx && ray.y() == ty)
                    break;
                ray.advance(true);
            }
        }
}

Insertion in crawl-ref/source/misc.cc at line 54 [15.1933596]
[15.1934340]
[79.10054]
```
#include "los.h"
```
Insertion in crawl-ref/source/makefile.obj at line 39 [85.79]
[85.407]
[86.17065]
```
los.o \
```
Insertion in crawl-ref/source/makefile.obj at line 50 [85.79]
[85.447]
[85.447]
```
mon-los.o \
```
Insertion in crawl-ref/source/makefile.obj at line 67 [85.79]
[87.12549]
[85.604]
```
ray.o \
```
Insertion in crawl-ref/source/luadgn.cc at line 26 [89.1232]
[88.102947]
[89.1453]
```
#include "los.h"
```

File addition: los.h (----------)

[84.24]

/*
 *  File:       los.h
 *  Summary:    Line-of-sight algorithm.
 */
#ifndef LOS_H
#define LOS_H
#include "externs.h"
#define EPSILON_VALUE 0.00001
bool double_is_zero(const double x);
void setLOSRadius(int newLR);
int get_los_radius_squared(); // XXX
struct ray_def;
bool find_ray( const coord_def& source, const coord_def& target,
               bool allow_fallback, ray_def& ray, int cycle_dir = 0,
               bool find_shortest = false, bool ignore_solid = false );
int num_feats_between(const coord_def& source, const coord_def& target,
                      dungeon_feature_type min_feat,
                      dungeon_feature_type max_feat,
                      bool exclude_endpoints = true,
                      bool just_check = false);
bool grid_see_grid(const coord_def& p1, const coord_def& p2,
                   dungeon_feature_type allowed = DNGN_UNSEEN);
void clear_rays_on_exit();
void losight(env_show_grid &sh, feature_grid &gr,
             const coord_def& center, bool clear_walls_block = false,
             bool ignore_clouds = false);
void calc_show_los();
bool see_grid( const env_show_grid &show,
               const coord_def &c,
               const coord_def &pos );
bool see_grid(const coord_def &p);
bool see_grid_no_trans( const coord_def &p );
bool trans_wall_blocking( const coord_def &p );
inline bool see_grid( int grx, int gry )
{
    return see_grid(coord_def(grx, gry));
}
inline bool see_grid_no_trans(int x, int y)
{
    return see_grid_no_trans(coord_def(x, y));
}
inline bool trans_wall_blocking(int x, int y)
{
    return trans_wall_blocking(coord_def(x, y));
}
#endif

File addition: los.cc (----------)

[84.24]

/*
 *  File:       los.cc
 *  Summary:    Line-of-sight algorithm.
 */
#include "AppHdr.h"
REVISION("$Rev$");
#include "los.h"
#include <cmath>
#include "cloud.h"
#include "debug.h"
#include "directn.h"
#include "externs.h"
#include "ray.h"
#include "state.h"
#include "stuff.h"
#include "terrain.h"
// The LOS code now uses raycasting -- haranp
#define LONGSIZE (sizeof(unsigned long)*8)
#define LOS_MAX_RANGE_X 9
#define LOS_MAX_RANGE_Y 9
#define LOS_MAX_RANGE 9
// the following two constants represent the 'middle' of the sh array.
// since the current shown area is 19x19, centering the view at (9,9)
// means it will be exactly centered.
// This is done to accomodate possible future changes in viewable screen
// area - simply change sh_xo and sh_yo to the new view center.
const int sh_xo = 9;            // X and Y origins for the sh array
const int sh_yo = 9;
unsigned long* los_blockrays = NULL;
unsigned long* dead_rays     = NULL;
unsigned long* smoke_rays    = NULL;
std::vector<short> ray_coord_x;
std::vector<short> ray_coord_y;
std::vector<short> compressed_ray_x;
std::vector<short> compressed_ray_y;
std::vector<int> raylengths;
std::vector<ray_def> fullrays;
void clear_rays_on_exit()
{
    delete[] dead_rays;
    delete[] smoke_rays;
    delete[] los_blockrays;
}
int _los_radius_squared = LOS_RADIUS * LOS_RADIUS + 1;
void setLOSRadius(int newLR)
{
    _los_radius_squared = newLR * newLR + 1*1;
}
// XXX: just for monster_los
int get_los_radius_squared()
{
    return _los_radius_squared;
}
bool _get_bit_in_long_array( const unsigned long* data, int where )
{
    int wordloc = where / LONGSIZE;
    int bitloc = where % LONGSIZE;
    return ((data[wordloc] & (1UL << bitloc)) != 0);
}
static void _set_bit_in_long_array( unsigned long* data, int where )
{
    int wordloc = where / LONGSIZE;
    int bitloc = where % LONGSIZE;
    data[wordloc] |= (1UL << bitloc);
}
bool double_is_zero( const double x )
{
    return (x > -EPSILON_VALUE) && (x < EPSILON_VALUE);
}
// Check if the passed ray has already been created.
static bool _is_duplicate_ray( int len, int xpos[], int ypos[] )
{
    int cur_offset = 0;
    for (unsigned int i = 0; i < raylengths.size(); ++i)
    {
        // Only compare equal-length rays.
        if (raylengths[i] != len)
        {
            cur_offset += raylengths[i];
            continue;
        }
        int j;
        for (j = 0; j < len; ++j)
        {
            if (ray_coord_x[j + cur_offset] != xpos[j]
                || ray_coord_y[j + cur_offset] != ypos[j])
            {
                break;
            }
        }
        // Exact duplicate?
        if (j == len)
            return (true);
        // Move to beginning of next ray.
        cur_offset += raylengths[i];
    }
    return (false);
}
// 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_coord_x[curb] > ray_coord_x[cura])
            return (false);
        if (ray_coord_y[curb] > ray_coord_y[cura])
            return (false);
        if (ray_coord_x[cura] == ray_coord_x[curb]
            && ray_coord_y[cura] == ray_coord_y[curb])
        {
            ++cura;
        }
        ++curb;
    }
    return (cura == enda);
}
// Returns a vector which lists all the nonduped cellrays (by index).
static std::vector<int> _find_nonduped_cellrays()
{
    // A cellray c in a fullray f is duped if there is a fullray g
    // such that g contains c and g[:c] is a subset of f[:c].
    int raynum, cellnum, curidx, testidx, testray, testcell;
    bool is_duplicate;
    std::vector<int> result;
    for (curidx = 0, raynum = 0;
         raynum < static_cast<int>(raylengths.size());
         curidx += raylengths[raynum++])
    {
        for (cellnum = 0; cellnum < raylengths[raynum]; ++cellnum)
        {
            // Is the cellray raynum[cellnum] duplicated?
            is_duplicate = false;
            // XXX: We should really check everything up to now
            // completely, and all further rays to see if they're
            // proper subsets.
            const int curx = ray_coord_x[curidx + cellnum];
            const int cury = ray_coord_y[curidx + cellnum];
            for (testidx = 0, testray = 0; testray < raynum;
                 testidx += raylengths[testray++])
            {
                // Scan ahead to see if there's an intersect.
                for (testcell = 0; testcell < raylengths[raynum]; ++testcell)
                {
                    const int testx = ray_coord_x[testidx + testcell];
                    const int testy = ray_coord_y[testidx + testcell];
                    // We can short-circuit sometimes.
                    if (testx > curx || testy > cury)
                        break;
                    // Bingo!
                    if (testx == curx && testy == cury)
                    {
                        is_duplicate = _is_subset(testidx, curidx,
                                                  testcell, cellnum);
                        break;
                    }
                }
                if (is_duplicate)
                    break;      // No point in checking further rays.
            }
            if (!is_duplicate)
                result.push_back(curidx + cellnum);
        }
    }
    return result;
}
// Create and register the ray defined by the arguments.
// Return true if the ray was actually registered (i.e., not a duplicate.)
static bool _register_ray( double accx, double accy, double slope )
{
    int xpos[LOS_MAX_RANGE * 2 + 1], ypos[LOS_MAX_RANGE * 2 + 1];
    int raylen = shoot_ray( accx, accy, slope, LOS_MAX_RANGE, xpos, ypos );
    // Early out if ray already exists.
    if (_is_duplicate_ray(raylen, xpos, ypos))
        return (false);
    // Not duplicate, register.
    for (int i = 0; i < raylen; ++i)
    {
        // Create the cellrays.
        ray_coord_x.push_back(xpos[i]);
        ray_coord_y.push_back(ypos[i]);
    }
    // Register the fullray.
    raylengths.push_back(raylen);
    ray_def ray;
    ray.accx = accx;
    ray.accy = accy;
    ray.slope = slope;
    ray.quadrant = 0;
    fullrays.push_back(ray);
    return (true);
}
static void _create_blockrays()
{
    // determine nonduplicated rays
    std::vector<int> nondupe_cellrays    = _find_nonduped_cellrays();
    const unsigned int num_nondupe_rays  = nondupe_cellrays.size();
    const unsigned int num_nondupe_words =
        (num_nondupe_rays + LONGSIZE - 1) / LONGSIZE;
    const unsigned int num_cellrays = ray_coord_x.size();
    const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE;
    // first build all the rays: easier to do blocking calculations there
    unsigned long* full_los_blockrays;
    full_los_blockrays = new unsigned long[num_words * (LOS_MAX_RANGE_X+1) *
                                           (LOS_MAX_RANGE_Y+1)];
    memset((void*)full_los_blockrays, 0, sizeof(unsigned long) * num_words *
           (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1));
    int cur_offset = 0;
    for (unsigned int ray = 0; ray < raylengths.size(); ++ray)
    {
        for (int i = 0; i < raylengths[ray]; ++i)
        {
            // every cell blocks...
            unsigned long* const inptr = full_los_blockrays +
                (ray_coord_x[i + cur_offset] * (LOS_MAX_RANGE_Y + 1) +
                 ray_coord_y[i + cur_offset]) * num_words;
            // ...all following cellrays
            for (int j = i+1; j < raylengths[ray]; ++j)
                _set_bit_in_long_array( inptr, j + cur_offset );
        }
        cur_offset += raylengths[ray];
    }
    // we've built the basic blockray array; now compress it, keeping
    // only the nonduplicated cellrays.
    // allocate and clear memory
    los_blockrays = new unsigned long[num_nondupe_words * (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y + 1)];
    memset((void*)los_blockrays, 0, sizeof(unsigned long) * num_nondupe_words *
           (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1));
    // we want to only keep the cellrays from nondupe_cellrays.
    compressed_ray_x.resize(num_nondupe_rays);
    compressed_ray_y.resize(num_nondupe_rays);
    for (unsigned int i = 0; i < num_nondupe_rays; ++i)
    {
        compressed_ray_x[i] = ray_coord_x[nondupe_cellrays[i]];
        compressed_ray_y[i] = ray_coord_y[nondupe_cellrays[i]];
    }
    unsigned long* oldptr = full_los_blockrays;
    unsigned long* newptr = los_blockrays;
    for (int x = 0; x <= LOS_MAX_RANGE_X; ++x)
        for (int y = 0; y <= LOS_MAX_RANGE_Y; ++y)
        {
            for (unsigned int i = 0; i < num_nondupe_rays; ++i)
                if (_get_bit_in_long_array(oldptr, nondupe_cellrays[i]))
                    _set_bit_in_long_array(newptr, i);
            oldptr += num_words;
            newptr += num_nondupe_words;
        }
    // we can throw away full_los_blockrays now
    delete[] full_los_blockrays;
    dead_rays  = new unsigned long[num_nondupe_words];
    smoke_rays = new unsigned long[num_nondupe_words];
#ifdef DEBUG_DIAGNOSTICS
    mprf( MSGCH_DIAGNOSTICS, "Cellrays: %d Fullrays: %u Compressed: %u",
          num_cellrays, raylengths.size(), num_nondupe_rays );
#endif
}
static int _gcd( int x, int y )
{
    int tmp;
    while (y != 0)
    {
        x %= y;
        tmp = x;
        x = y;
        y = tmp;
    }
    return x;
}
bool complexity_lt( const std::pair<int,int>& lhs,
                    const std::pair<int,int>& rhs )
{
    return lhs.first * lhs.second < rhs.first * rhs.second;
}
// Cast all rays
void raycast()
{
    static bool done_raycast = false;
    if (done_raycast)
        return;
    // Creating all rays for first quadrant
    // We have a considerable amount of overkill.
    done_raycast = true;
    // register perpendiculars FIRST, to make them top choice
    // when selecting beams
    _register_ray( 0.5, 0.5, 1000.0 );
    _register_ray( 0.5, 0.5, 0.0 );
    // For a slope of M = y/x, every x we move on the X axis means
    // that we move y on the y axis. We want to look at the resolution
    // of x/y: in that case, every step on the X axis means an increase
    // of 1 in the Y axis at the intercept point. We can assume gcd(x,y)=1,
    // so we look at steps of 1/y.
    // Changing the order a bit. We want to order by the complexity
    // of the beam, which is log(x) + log(y) ~ xy.
    std::vector<std::pair<int,int> > xyangles;
    for ( int xangle = 1; xangle <= 2*LOS_MAX_RANGE; ++xangle )
        for ( int yangle = 1; yangle <= 2*LOS_MAX_RANGE; ++yangle )
        {
            if ( _gcd(xangle, yangle) == 1 )
                xyangles.push_back(std::pair<int,int>(xangle, yangle));
        }
    std::sort( xyangles.begin(), xyangles.end(), complexity_lt );
    for ( unsigned int i = 0; i < xyangles.size(); ++i )
    {
        const int xangle = xyangles[i].first;
        const int yangle = xyangles[i].second;
        const double slope = ((double)(yangle)) / xangle;
        const double rslope = ((double)(xangle)) / yangle;
        for ( int intercept = 1; intercept <= 2*yangle; ++intercept )
        {
            double xstart = ((double)(intercept)) / (2*yangle);
            double ystart = 1;
            // now move back just inside the cell
            // y should be "about to change"
            xstart -= EPSILON_VALUE * xangle;
            ystart -= EPSILON_VALUE * yangle;
            _register_ray( xstart, ystart, slope );
            // also draw the identical ray in octant 2
            _register_ray( ystart, xstart, rslope );
        }
    }
    // Now create the appropriate blockrays array
    _create_blockrays();
}
static void _set_ray_quadrant( ray_def& ray, int sx, int sy, int tx, int ty )
{
    if ( tx >= sx && ty >= sy )
        ray.quadrant = 0;
    else if ( tx < sx && ty >= sy )
        ray.quadrant = 1;
    else if ( tx < sx && ty < sy )
        ray.quadrant = 2;
    else if ( tx >= sx && ty < sy )
        ray.quadrant = 3;
    else
        mpr("Bad ray quadrant!", MSGCH_DIAGNOSTICS);
}
static int _cyclic_offset( unsigned int ui, int cycle_dir, int startpoint,
                           int maxvalue )
{
    const int i = (int)ui;
    if ( startpoint < 0 )
        return i;
    switch ( cycle_dir )
    {
    case 1:
        return (i + startpoint + 1) % maxvalue;
    case -1:
        return (i - 1 - startpoint + maxvalue) % maxvalue;
    case 0:
    default:
        return i;
    }
}
static const double VERTICAL_SLOPE = 10000.0;
static double _calc_slope(double x, double y)
{
    if (double_is_zero(x))
        return (VERTICAL_SLOPE);
    const double slope = y / x;
    return (slope > VERTICAL_SLOPE? VERTICAL_SLOPE : slope);
}
static double _slope_factor(const ray_def &ray)
{
    double xdiff = fabs(ray.accx - 0.5), ydiff = fabs(ray.accy - 0.5);
    if (double_is_zero(xdiff) && double_is_zero(ydiff))
        return ray.slope;
    const double slope = _calc_slope(ydiff, xdiff);
    return (slope + ray.slope) / 2.0;
}
static bool _superior_ray(int shortest, int imbalance,
                          int raylen, int rayimbalance,
                          double slope_diff, double ray_slope_diff)
{
    if (shortest != raylen)
        return (shortest > raylen);
    if (imbalance != rayimbalance)
        return (imbalance > rayimbalance);
    return (slope_diff > ray_slope_diff);
}
// Find a nonblocked ray from source to target. Return false if no
// such ray could be found, otherwise return true and fill ray
// appropriately.
// If allow_fallback is true, fall back to a center-to-center ray
// if range is too great or all rays are blocked.
// If cycle_dir is 0, find the first fitting ray. If it is 1 or -1,
// assume that ray is appropriately filled in, and look for the next
// ray in that cycle direction.
// If find_shortest is true, examine all rays that hit the target and
// take the shortest (starting at ray.fullray_idx).
bool find_ray( const coord_def& source, const coord_def& target,
               bool allow_fallback, ray_def& ray, int cycle_dir,
               bool find_shortest, bool ignore_solid )
{
    int cellray, inray;
    const int sourcex = source.x;
    const int sourcey = source.y;
    const int targetx = target.x;
    const int targety = target.y;
    const int signx = ((targetx - sourcex >= 0) ? 1 : -1);
    const int signy = ((targety - sourcey >= 0) ? 1 : -1);
    const int absx  = signx * (targetx - sourcex);
    const int absy  = signy * (targety - sourcey);
    int cur_offset  = 0;
    int shortest    = INFINITE_DISTANCE;
    int imbalance   = INFINITE_DISTANCE;
    const double want_slope = _calc_slope(absx, absy);
    double slope_diff       = VERTICAL_SLOPE * 10.0;
    std::vector<coord_def> unaliased_ray;
    for ( unsigned int fray = 0; fray < fullrays.size(); ++fray )
    {
        const int fullray = _cyclic_offset( fray, cycle_dir, ray.fullray_idx,
                                            fullrays.size() );
        // Yeah, yeah, this is O(n^2). I know.
        cur_offset = 0;
        for (int i = 0; i < fullray; ++i)
            cur_offset += raylengths[i];
        for (cellray = 0; cellray < raylengths[fullray]; ++cellray)
        {
            if (ray_coord_x[cellray + cur_offset] == absx
                && ray_coord_y[cellray + cur_offset] == absy)
            {
                if (find_shortest)
                {
                    unaliased_ray.clear();
                    unaliased_ray.push_back(coord_def(0, 0));
                }
                // Check if we're blocked so far.
                bool blocked = false;
                coord_def c1, c3;
                int real_length = 0;
                for (inray = 0; inray <= cellray; ++inray)
                {
                    const int xi = signx * ray_coord_x[inray + cur_offset];
                    const int yi = signy * ray_coord_y[inray + cur_offset];
                    if (inray < cellray && !ignore_solid
                        && grid_is_solid(grd[sourcex + xi][sourcey + yi]))
                    {
                        blocked = true;
                        break;
                    }
                    if (find_shortest)
                    {
                        c3 = coord_def(xi, yi);
                        // We've moved at least two steps if inray > 0.
                        if (inray)
                        {
                            // Check for a perpendicular corner on the ray and
                            // pretend that it's a diagonal.
                            if ((c3 - c1).abs() != 2)
                                ++real_length;
                            else
                            {
                                // c2 was a dud move, pop it off
                                unaliased_ray.pop_back();
                            }
                        }
                        else
                            ++real_length;
                        unaliased_ray.push_back(c3);
                        c1 = unaliased_ray[real_length - 1];
                    }
                }
                int cimbalance = 0;
                // If this ray is a candidate for shortest, calculate
                // the imbalance. I'm defining 'imbalance' as the
                // number of consecutive diagonal or orthogonal moves
                // in the ray. This is a reasonable measure of deviation from
                // the Bresenham line between our selected source and
                // destination.
                if (!blocked && find_shortest && shortest >= real_length)
                {
                    int diags = 0, straights = 0;
                    for (int i = 1, size = unaliased_ray.size(); i < size; ++i)
                    {
                        const int dist =
                            (unaliased_ray[i] - unaliased_ray[i - 1]).abs();
                        if (dist == 2)
                        {
                            straights = 0;
                            if (++diags > cimbalance)
                                cimbalance = diags;
                        }
                        else
                        {
                            diags = 0;
                            if (++straights > cimbalance)
                                cimbalance = straights;
                        }
                    }
                }
                const double ray_slope_diff = find_shortest ?
                    fabs(_slope_factor(fullrays[fullray]) - want_slope) : 0.0;
                if (!blocked
                    &&  (!find_shortest
                         || _superior_ray(shortest, imbalance,
                                          real_length, cimbalance,
                                          slope_diff, ray_slope_diff)))
                {
                    // Success!
                    ray             = fullrays[fullray];
                    ray.fullray_idx = fullray;
                    shortest   = real_length;
                    imbalance  = cimbalance;
                    slope_diff = ray_slope_diff;
                    if (sourcex > targetx)
                        ray.accx = 1.0 - ray.accx;
                    if (sourcey > targety)
                        ray.accy = 1.0 - ray.accy;
                    ray.accx += sourcex;
                    ray.accy += sourcey;
                    _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety);
                    if (!find_shortest)
                        return (true);
                }
            }
        }
    }
    if (find_shortest && shortest != INFINITE_DISTANCE)
        return (true);
    if (allow_fallback)
    {
        ray.accx = sourcex + 0.5;
        ray.accy = sourcey + 0.5;
        if (targetx == sourcex)
            ray.slope = VERTICAL_SLOPE;
        else
        {
            ray.slope  = targety - sourcey;
            ray.slope /= targetx - sourcex;
            if (ray.slope < 0)
                ray.slope = -ray.slope;
        }
        _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety);
        ray.fullray_idx = -1;
        return (true);
    }
    return (false);
}
// Count the number of matching features between two points along
// a beam-like path; the path will pass through solid features.
// By default, it excludes end points from the count.
// If just_check is true, the function will return early once one
// such feature is encountered.
int num_feats_between(const coord_def& source, const coord_def& target,
                      dungeon_feature_type min_feat,
                      dungeon_feature_type max_feat,
                      bool exclude_endpoints, bool just_check)
{
    ray_def ray;
    int     count    = 0;
    int     max_dist = grid_distance(source, target);
    ray.fullray_idx = -1; // to quiet valgrind
    // We don't need to find the shortest beam, any beam will suffice.
    find_ray( source, target, true, ray, 0, false, true );
    if (exclude_endpoints && ray.pos() == source)
    {
        ray.advance(true);
        max_dist--;
    }
    int dist = 0;
    bool reached_target = false;
    while (dist++ <= max_dist)
    {
        const dungeon_feature_type feat = grd(ray.pos());
        if (ray.pos() == target)
            reached_target = true;
        if (feat >= min_feat && feat <= max_feat
            && (!exclude_endpoints || !reached_target))
        {
            count++;
            if (just_check) // Only needs to be > 0.
                return (count);
        }
        if (reached_target)
            break;
        ray.advance(true);
    }
    return (count);
}
// Usually calculates whether from one grid someone could see the other.
// Depending on the viewer's habitat, 'allowed' can be set to DNGN_FLOOR,
// DNGN_SHALLOW_WATER or DNGN_DEEP_WATER.
// Yes, this ignores lava-loving monsters.
// XXX: It turns out the beams are not symmetrical, i.e. switching
// pos1 and pos2 may result in small variations.
bool grid_see_grid(const coord_def& p1, const coord_def& p2,
                   dungeon_feature_type allowed)
{
    if (distance(p1, p2) > _los_radius_squared)
        return (false);
    dungeon_feature_type max_disallowed = DNGN_MAXOPAQUE;
    if (allowed != DNGN_UNSEEN)
        max_disallowed = static_cast<dungeon_feature_type>(allowed - 1);
    // XXX: Ignoring clouds for now.
    return (!num_feats_between(p1, p2, DNGN_UNSEEN, max_disallowed,
                               true, true));
}
// The rule behind LOS is:
// Two cells can see each other if there is any line from some point
// of the first to some point of the second ("generous" LOS.)
//
// We use raycasting. The algorithm:
// PRECOMPUTATION:
// Create a large bundle of rays and cast them.
// Mark, for each one, which cells kill it (and where.)
// Also, for each one, note which cells it passes.
// ACTUAL LOS:
// Unite the ray-killers for the given map; this tells you which rays
// are dead.
// Look up which cells the surviving rays have, and that's your LOS!
// OPTIMIZATIONS:
// WLOG, we can assume that we're in a specific quadrant - say the
// first quadrant - and just mirror everything after that.  We can
// likely get away with a single octant, but we don't do that. (To
// do...)
// Rays are actually split by each cell they pass. So each "ray" only
// identifies a single cell, and we can do logical ORs.  Once a cell
// kills a cellray, it will kill all remaining cellrays of that ray.
// Also, rays are checked to see if they are duplicates of each
// other. If they are, they're eliminated.
// Some cellrays can also be eliminated. In general, a cellray is
// unnecessary if there is another cellray with the same coordinates,
// and whose path (up to those coordinates) is a subset, not necessarily
// proper, of the original path. We still store the original cellrays
// fully for beam detection and such.
// PERFORMANCE:
// With reasonable values we have around 6000 cellrays, meaning
// around 600Kb (75 KB) of data. This gets cut down to 700 cellrays
// after removing duplicates. That means that we need to do
// around 22*100*4 ~ 9,000 memory reads + writes per LOS call on a
// 32-bit system. Not too bad.
// IMPROVEMENTS:
// Smoke will now only block LOS after two cells of smoke. This is
// done by updating with a second array.
void losight(env_show_grid &sh,
             feature_grid &gr, const coord_def& center,
             bool clear_walls_block, bool ignore_clouds)
{
    raycast();
    const int x_p = center.x;
    const int y_p = center.y;
    // go quadrant by quadrant
    const int quadrant_x[4] = {  1, -1, -1,  1 };
    const int quadrant_y[4] = {  1,  1, -1, -1 };
    // clear out sh
    sh.init(0);
    if (crawl_state.arena || crawl_state.arena_suspended)
    {
        for (int y = -ENV_SHOW_OFFSET; y <= ENV_SHOW_OFFSET; ++y)
            for (int x = -ENV_SHOW_OFFSET; x <= ENV_SHOW_OFFSET; ++x)
            {
                const coord_def pos = center + coord_def(x, y);
                if (map_bounds(pos))
                    sh[x + sh_xo][y + sh_yo] = gr(pos);
            }
        return;
    }
    const unsigned int num_cellrays = compressed_ray_x.size();
    const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE;
    for (int quadrant = 0; quadrant < 4; ++quadrant)
    {
        const int xmult = quadrant_x[quadrant];
        const int ymult = quadrant_y[quadrant];
        // clear out the dead rays array
        memset( (void*)dead_rays,  0, sizeof(unsigned long) * num_words);
        memset( (void*)smoke_rays, 0, sizeof(unsigned long) * num_words);
        // kill all blocked rays
        const unsigned long* inptr = los_blockrays;
        for (int xdiff = 0; xdiff <= LOS_MAX_RANGE_X; ++xdiff)
            for (int ydiff = 0; ydiff <= LOS_MAX_RANGE_Y;
                 ++ydiff, inptr += num_words)
            {
                const int realx = x_p + xdiff * xmult;
                const int realy = y_p + ydiff * ymult;
                if (!map_bounds(realx, realy))
                    continue;
                coord_def real(realx, realy);
                dungeon_feature_type dfeat = grid_appearance(gr, real);
                // if this cell is opaque...
                // ... or something you can see but not walk through ...
                if (grid_is_opaque(dfeat)
                    || clear_walls_block && dfeat < DNGN_MINMOVE)
                {
                    // then block the appropriate rays
                    for (unsigned int i = 0; i < num_words; ++i)
                        dead_rays[i] |= inptr[i];
                }
                else if (!ignore_clouds
                         && is_opaque_cloud(env.cgrid[realx][realy]))
                {
                    // block rays which have already seen a cloud
                    for (unsigned int i = 0; i < num_words; ++i)
                    {
                        dead_rays[i]  |= (smoke_rays[i] & inptr[i]);
                        smoke_rays[i] |= inptr[i];
                    }
                }
            }
        // ray calculation done, now work out which cells in this
        // quadrant are visible
        unsigned int rayidx = 0;
        for (unsigned int wordloc = 0; wordloc < num_words; ++wordloc)
        {
            const unsigned long curword = dead_rays[wordloc];
            // Note: the last word may be incomplete
            for (unsigned int bitloc = 0; bitloc < LONGSIZE; ++bitloc)
            {
                // make the cells seen by this ray at this point visible
                if ( ((curword >> bitloc) & 1UL) == 0 )
                {
                    // this ray is alive!
                    const int realx = xmult * compressed_ray_x[rayidx];
                    const int realy = ymult * compressed_ray_y[rayidx];
                    // update shadow map
                    if (x_p + realx >= 0 && x_p + realx < GXM
                        && y_p + realy >= 0 && y_p + realy < GYM
                        && realx * realx + realy * realy <= _los_radius_squared)
                    {
                        sh[sh_xo+realx][sh_yo+realy] = gr[x_p+realx][y_p+realy];
                    }
                }
                ++rayidx;
                if (rayidx == num_cellrays)
                    break;
            }
        }
    }
    // [dshaligram] The player's current position is always visible.
    sh[sh_xo][sh_yo] = gr[x_p][y_p];
    *dead_rays     = NULL;
    *smoke_rays    = NULL;
    *los_blockrays = NULL;
}
void calc_show_los()
{
    if (!crawl_state.arena && !crawl_state.arena_suspended)
    {
        // Must be done first.
        losight(env.show, grd, you.pos());
        // What would be visible, if all of the translucent walls were
        // made opaque.
        losight(env.no_trans_show, grd, you.pos(), true);
    }
    else
    {
        losight(env.show, grd, crawl_view.glosc());
    }
}
bool see_grid( const env_show_grid &show,
               const coord_def &c,
               const coord_def &pos )
{
    if (c == pos)
        return (true);
    const coord_def ip = pos - c;
    if (ip.rdist() < ENV_SHOW_OFFSET)
    {
        const coord_def sp(ip + coord_def(ENV_SHOW_OFFSET, ENV_SHOW_OFFSET));
        if (show(sp))
            return (true);
    }
    return (false);
}
// Answers the question: "Is a grid within character's line of sight?"
bool see_grid( const coord_def &p )
{
    return ((crawl_state.arena || crawl_state.arena_suspended)
                && crawl_view.in_grid_los(p))
            || see_grid(env.show, you.pos(), p);
}
// Answers the question: "Would a grid be within character's line of sight,
// even if all translucent/clear walls were made opaque?"
bool see_grid_no_trans( const coord_def &p )
{
    return see_grid(env.no_trans_show, you.pos(), p);
}
// Is the grid visible, but a translucent wall is in the way?
bool trans_wall_blocking( const coord_def &p )
{
    return see_grid(p) && !see_grid_no_trans(p);
}

Insertion in crawl-ref/source/it_use3.cc at line 33 [15.2870456]
[24.763529]
[27.28044]
```
#include "los.h"
```
Insertion in crawl-ref/source/files.cc at line 59 [15.3084589]
[24.857110]
[27.28362]
```
#include "los.h"
```
Insertion in crawl-ref/source/fight.cc at line 38 [15.3140790]
[11.3534]
[15.3142494]
```
#include "los.h"
```
Insertion in crawl-ref/source/effects.cc at line 38 [15.3382105]
[15.3382514]
[80.131021]
```
#include "los.h"
```
Insertion in crawl-ref/source/dungeon.cc at line 34 [15.3429798]
[15.3431113]
[80.131046]
```
#include "los.h"
```
Insertion in crawl-ref/source/directn.cc at line 36 [15.3697945]
[90.3743]
[27.35440]
```
#include "los.h"
```
Insertion in crawl-ref/source/decks.cc at line 28 [15.3987460]
[15.3987813]
[91.332]
```
#include "los.h"
```
Insertion in crawl-ref/source/beam.cc at line 40 [15.4128068]
[24.1220025]
[33.108450]
```
#include "los.h"
```
Insertion in crawl-ref/source/acr.cc at line 76 [15.4397395]
[15.4400378]
[86.21117]
```
#include "los.h"
```
Insertion in crawl-ref/source/abyss.cc at line 30 [15.4482606]
[15.4483100]
[7.3152]
```
#include "los.h"
```

Split LOS code from view.cc.

Dependencies

In channels

Change contents

Insertion in crawl-ref/source/xom.cc at line 21 [13.3]

Deletion in crawl-ref/source/view.h at line 71 [15.13254]

Deletion in crawl-ref/source/view.h at line 176 [15.13254]

Deletion in crawl-ref/source/view.h at line 177 [15.13254]

Deletion in crawl-ref/source/view.h at line 191 [15.13254]

Deletion in crawl-ref/source/view.h at line 195 [15.13254]

Deletion in crawl-ref/source/view.h at line 204 [15.13254]

Insertion in crawl-ref/source/view.cc at line 38 [15.16817]

Deletion in crawl-ref/source/view.cc at line 82 [15.16817]

Deletion in crawl-ref/source/view.cc at line 1924 [15.16817]

Deletion in crawl-ref/source/view.cc at line 1926 [15.16817]

Deletion in crawl-ref/source/view.cc at line 1929 [15.16817]

Deletion in crawl-ref/source/view.cc at line 2996 [15.16817]

Deletion in crawl-ref/source/view.cc at line 2997 [15.16817]

Deletion in crawl-ref/source/view.cc at line 2999 [15.16817]

Deletion in crawl-ref/source/view.cc at line 4058 [15.16817]

Deletion in crawl-ref/source/view.cc at line 4772 [15.16817]

Insertion in crawl-ref/source/tutorial.cc at line 33 [45.5936]

Insertion in crawl-ref/source/travel.cc at line 27 [16.39949]

Insertion in crawl-ref/source/traps.cc at line 25 [33.5308]

Insertion in crawl-ref/source/terrain.cc at line 21 [33.26938]

Insertion in crawl-ref/source/stuff.cc at line 14 [15.224557]

Insertion in crawl-ref/source/state.cc at line 14 [79.1546]

Insertion in crawl-ref/source/stash.cc at line 26 [16.147324]

Insertion in crawl-ref/source/spl-util.cc at line 27 [15.245665]

Insertion in crawl-ref/source/spl-cast.cc at line 29 [15.293070]

Insertion in crawl-ref/source/spells4.cc at line 34 [15.436250]

Insertion in crawl-ref/source/spells3.cc at line 34 [15.531613]

Insertion in crawl-ref/source/spells2.cc at line 33 [15.569242]

Insertion in crawl-ref/source/spells1.cc at line 31 [15.616635]

Insertion in crawl-ref/source/religion.cc at line 47 [15.804403]

Insertion in crawl-ref/source/ray.h at line 10 [33.47173]

File addition: ray.cc (----------)

Insertion in crawl-ref/source/player.cc at line 41 [15.962854]

Insertion in crawl-ref/source/ouch.cc at line 48 [15.1104358]

Insertion in crawl-ref/source/mstuff2.cc at line 32 [15.1340842]

Insertion in crawl-ref/source/monstuff.cc at line 40 [15.1396662]

Insertion in crawl-ref/source/monstuff.cc at line 47 [15.1396662]

Insertion in crawl-ref/source/monplace.cc at line 20 [15.1641732]

Insertion in crawl-ref/source/mon-util.cc at line 39 [15.1699344]

File addition: mon-los.h (----------)

File addition: mon-los.cc (----------)

Insertion in crawl-ref/source/misc.cc at line 54 [15.1933596]

Insertion in crawl-ref/source/makefile.obj at line 39 [85.79]

Insertion in crawl-ref/source/makefile.obj at line 50 [85.79]

Insertion in crawl-ref/source/makefile.obj at line 67 [85.79]

Insertion in crawl-ref/source/luadgn.cc at line 26 [89.1232]

File addition: los.h (----------)

File addition: los.cc (----------)

Insertion in crawl-ref/source/it_use3.cc at line 33 [15.2870456]

Insertion in crawl-ref/source/files.cc at line 59 [15.3084589]

Insertion in crawl-ref/source/fight.cc at line 38 [15.3140790]

Insertion in crawl-ref/source/effects.cc at line 38 [15.3382105]

Insertion in crawl-ref/source/dungeon.cc at line 34 [15.3429798]

Insertion in crawl-ref/source/directn.cc at line 36 [15.3697945]

Insertion in crawl-ref/source/decks.cc at line 28 [15.3987460]

Insertion in crawl-ref/source/beam.cc at line 40 [15.4128068]

Insertion in crawl-ref/source/acr.cc at line 76 [15.4397395]

Insertion in crawl-ref/source/abyss.cc at line 30 [15.4482606]