diff options
| -rw-r--r-- | crawl-ref/source/exclude.cc | 232 | ||||
| -rw-r--r-- | crawl-ref/source/exclude.h | 65 | ||||
| -rw-r--r-- | crawl-ref/source/travel.cc | 16 | ||||
| -rw-r--r-- | crawl-ref/source/travel.h | 4 |
4 files changed, 251 insertions, 66 deletions
diff --git a/crawl-ref/source/exclude.cc b/crawl-ref/source/exclude.cc index 25728fe67a..824affc669 100644 --- a/crawl-ref/source/exclude.cc +++ b/crawl-ref/source/exclude.cc @@ -8,6 +8,7 @@ #include "exclude.h" #include "coord.h" +#include "coordit.h" #include "map_knowledge.h" #include "mon-util.h" #include "options.h" @@ -123,6 +124,16 @@ travel_exclude::travel_exclude(const coord_def &p, int r, set_los(); } +// For exclude_map[p] = foo; +travel_exclude::travel_exclude() + : pos(-1, -1), radius(-1), + los(coord_def(-1, -1), opc_excl, circle_def(-1, C_ROUND)), + uptodate(false), autoex(false), mon(MONS_NO_MONSTER), vault(false) +{ +} + +extern exclude_set curr_excludes; // in travel.cc + void travel_exclude::set_los() { uptodate = true; @@ -154,28 +165,155 @@ bool travel_exclude::in_bounds(const coord_def &p) const || los.in_bounds(p)); } -void _mark_excludes_non_updated(const coord_def &p) +///////////////////////////////////////////////////////////////////////// + +exclude_set::exclude_set() { - for (exclvec::iterator it = curr_excludes.begin(); - it != curr_excludes.end(); ++it) +} + +void exclude_set::clear() +{ + exclude_roots.clear(); + exclude_points.clear(); +} + +void exclude_set::erase(const coord_def &p) +{ + exclude_set::iterator it = exclude_roots.find(p); + + if (it == exclude_roots.end()) + return; + + travel_exclude old_ex = it->second; + exclude_roots.erase(it); + + recompute_excluded_points(); +} + +void exclude_set::add_exclude(travel_exclude &ex) +{ + add_exclude_points(ex); + exclude_roots[ex.pos] = ex; +} + +void exclude_set::add_exclude(const coord_def &p, int radius, + bool autoexcl, monster_type mons, + bool vaultexcl) +{ + travel_exclude ex(p, radius, autoexcl, mons, vaultexcl); + add_exclude(ex); +} + +void exclude_set::add_exclude_points(travel_exclude& ex) +{ + if (ex.radius == 0) + { + exclude_points.insert(ex.pos); + return; + } + + if (!ex.uptodate) + ex.set_los(); + else + ex.los.update(); + + for (radius_iterator ri(ex.pos, ex.radius, C_ROUND); ri; ++ri) { - it->uptodate = it->uptodate && it->in_bounds(p); + if (ex.affects(*ri)) + exclude_points.insert(*ri); } } -void _update_exclusion_los(bool all=false) +void exclude_set::update_excluded_points() { - for (exclvec::iterator it = curr_excludes.begin(); + for (iterator it = exclude_roots.begin(); it != exclude_roots.end(); ++it) + { + travel_exclude &ex = it->second; + if (!ex.uptodate) + { + recompute_excluded_points(); + return; + } + } +} + +void exclude_set::recompute_excluded_points(bool recompute_los) +{ + exclude_points.clear(); + for (iterator it = exclude_roots.begin(); it != exclude_roots.end(); ++it) + { + travel_exclude &ex = it->second; + if (recompute_los) + ex.set_los(); + add_exclude_points(ex); + } +} + +bool exclude_set::is_excluded(const coord_def &p) const +{ + return (exclude_points.find(p) != exclude_points.end()); +} + +bool exclude_set::is_exclude_root(const coord_def &p) const +{ + return (exclude_roots.find(p) != exclude_roots.end()); +} + +travel_exclude* exclude_set::get_exclude_root(const coord_def &p) +{ + exclude_set::iterator it = exclude_roots.find(p); + + if (it != exclude_roots.end()) + return (&(it->second)); + + return (false); +} + +size_t exclude_set::size() const +{ + return exclude_roots.size(); +} + +bool exclude_set::empty() const +{ + return exclude_roots.empty(); +} + +exclude_set::const_iterator exclude_set::begin() const +{ + return exclude_roots.begin(); +} + +exclude_set::const_iterator exclude_set::end() const +{ + return exclude_roots.end(); +} + +exclude_set::iterator exclude_set::begin() +{ + return exclude_roots.end(); +} + +exclude_set::iterator exclude_set::end() +{ + return exclude_roots.end(); +} + +///////////////////////////////////////////////////////////////////////// + +void _mark_excludes_non_updated(const coord_def &p) +{ + for (exclude_set::iterator it = curr_excludes.begin(); it != curr_excludes.end(); ++it) { - if (all || !it->uptodate) - it->set_los(); + travel_exclude &ex = it->second; + ex.uptodate = ex.uptodate && ex.in_bounds(p); } } void init_exclusion_los() { - _update_exclusion_los(true); + curr_excludes.recompute_excluded_points(true); } /* @@ -191,28 +329,18 @@ void update_exclusion_los(std::vector<coord_def> changed) for (unsigned int i = 0; i < changed.size(); ++i) _mark_excludes_non_updated(changed[i]); - _update_exclusion_los(); -} -bool is_excluded(const coord_def &p, const exclvec &exc) -{ - for (unsigned int i = 0; i < exc.size(); ++i) - if (exc[i].affects(p)) - return (true); - return (false); + curr_excludes.update_excluded_points(); } -static travel_exclude *_find_exclude_root(const coord_def &p) +bool is_excluded(const coord_def &p, const exclude_set &exc) { - for (unsigned int i = 0; i < curr_excludes.size(); ++i) - if (curr_excludes[i].pos == p) - return (&curr_excludes[i]); - return (NULL); + return exc.is_excluded(p); } bool is_exclude_root(const coord_def &p) { - return (_find_exclude_root(p)); + return (curr_excludes.get_exclude_root(p)); } #ifdef USE_TILE @@ -256,8 +384,10 @@ void clear_excludes() return; #ifdef USE_TILE - for (int i = curr_excludes.size()-1; i >= 0; i--) - _tile_exclude_gmap_update(curr_excludes[i].pos); + exclude_set::iterator it; + //for (int i = curr_excludes.size()-1; i >= 0; i--) + for (it = curr_excludes.begin(); it != curr_excludes.end(); ++it) + _tile_exclude_gmap_update(it->second.pos); #endif curr_excludes.clear(); @@ -270,8 +400,7 @@ void clear_excludes() // may start at 0 < radius < LOS_RADIUS, but won't cycle there. void cycle_exclude_radius(const coord_def &p) { - // XXX: scanning through curr_excludes twice - if (travel_exclude *exc = _find_exclude_root(p)) + if (travel_exclude *exc = curr_excludes.get_exclude_root(p)) { if (exc->radius == LOS_RADIUS) set_exclude(p, 0); @@ -285,12 +414,7 @@ void cycle_exclude_radius(const coord_def &p) // Remove a possible exclude. void del_exclude(const coord_def &p) { - for (unsigned int i = 0; i < curr_excludes.size(); ++i) - if (curr_excludes[i].pos == p) - { - curr_excludes.erase(curr_excludes.begin() + i); - break; - } + curr_excludes.erase(p); _exclude_update(p); } @@ -305,10 +429,14 @@ void set_exclude(const coord_def &p, int radius, bool autoexcl, bool vaultexcl) if (!in_bounds(p)) return; - if (travel_exclude *exc = _find_exclude_root(p)) + if (travel_exclude *exc = curr_excludes.get_exclude_root(p)) { - exc->radius = radius; - exc->set_los(); + if (exc->radius == radius) + return; + + exc->radius = radius; + exc->uptodate = false; + curr_excludes.recompute_excluded_points(); } else { @@ -320,8 +448,7 @@ void set_exclude(const coord_def &p, int radius, bool autoexcl, bool vaultexcl) montype = m->type; } - curr_excludes.push_back(travel_exclude(p, radius, autoexcl, - montype, vaultexcl)); + curr_excludes.add_exclude(p, radius, autoexcl, montype, vaultexcl); } _exclude_update(p); @@ -331,7 +458,7 @@ void set_exclude(const coord_def &p, int radius, bool autoexcl, bool vaultexcl) // monster (or it is invisible), remove the exclusion. void maybe_remove_autoexclusion(const coord_def &p) { - if (travel_exclude *exc = _find_exclude_root(p)) + if (travel_exclude *exc = curr_excludes.get_exclude_root(p)) { const monsters *m = monster_at(p); if (exc->autoex && (!m || !you.can_see(m) || m->type != exc->mon @@ -347,10 +474,12 @@ std::string get_exclusion_desc() { std::vector<std::string> monsters; int count_other = 0; - for (unsigned int i = 0; i < curr_excludes.size(); ++i) + exclude_set::iterator it; + for (it = curr_excludes.begin(); it != curr_excludes.end(); ++it) { - if (!invalid_monster_type(curr_excludes[i].mon)) - monsters.push_back(mons_type_name(curr_excludes[i].mon, DESC_PLAIN)); + travel_exclude &ex = it->second; + if (!invalid_monster_type(ex.mon)) + monsters.push_back(mons_type_name(ex.mon, DESC_PLAIN)); else count_other++; } @@ -377,23 +506,25 @@ std::string get_exclusion_desc() } -void marshallExcludes(writer& outf, const exclvec& excludes) +void marshallExcludes(writer& outf, const exclude_set& excludes) { marshallShort(outf, excludes.size()); + exclude_set::const_iterator it; if (excludes.size()) { - for (int i = 0, count = excludes.size(); i < count; ++i) + for (it = excludes.begin(); it != excludes.end(); ++it) { - marshallCoord(outf, excludes[i].pos); - marshallShort(outf, excludes[i].radius); - marshallBoolean(outf, excludes[i].autoex); - marshallShort(outf, excludes[i].mon); + const travel_exclude &ex = it->second; + marshallCoord(outf, ex.pos); + marshallShort(outf, ex.radius); + marshallBoolean(outf, ex.autoex); + marshallShort(outf, ex.mon); // XXX: marshall travel_exclude::vault? } } } -void unmarshallExcludes(reader& inf, char minorVersion, exclvec &excludes) +void unmarshallExcludes(reader& inf, char minorVersion, exclude_set &excludes) { excludes.clear(); int nexcludes = unmarshallShort(inf); @@ -408,7 +539,8 @@ void unmarshallExcludes(reader& inf, char minorVersion, exclvec &excludes) monster_type mon = MONS_NO_MONSTER; autoexcl = unmarshallBoolean(inf); mon = static_cast<monster_type>(unmarshallShort(inf)); - excludes.push_back(travel_exclude(c, radius, autoexcl, mon)); + + excludes.add_exclude(c, radius, autoexcl, mon); } } } diff --git a/crawl-ref/source/exclude.h b/crawl-ref/source/exclude.h index 9f3e8dc566..e7e564072f 100644 --- a/crawl-ref/source/exclude.h +++ b/crawl-ref/source/exclude.h @@ -19,8 +19,9 @@ void maybe_remove_autoexclusion(const coord_def &p); std::string get_exclusion_desc(); void clear_excludes(); -struct travel_exclude +class travel_exclude { +public: coord_def pos; // exclusion centre int radius; // exclusion radius los_def los; // los from exclusion centre @@ -32,22 +33,72 @@ struct travel_exclude travel_exclude(const coord_def &p, int r = LOS_RADIUS, bool autoex = false, monster_type mons = MONS_NO_MONSTER, bool vault = false); + // For exclude_map[p] = foo; + travel_exclude(); int radius_sq() const; - void set_los(); bool in_bounds(const coord_def& p) const; bool affects(const coord_def& p) const; + +private: + void set_los(); + + friend class exclude_set; +}; + +class exclude_set +{ +public: + exclude_set(); + + typedef std::map<coord_def, travel_exclude> exclmap; + typedef exclmap::iterator iterator; + typedef exclmap::const_iterator const_iterator; + + void clear(); + + void erase(const coord_def &p); + void add_exclude(travel_exclude &ex); + void add_exclude(const coord_def &p, int radius = LOS_RADIUS, + bool autoexcl = false, + monster_type mons = MONS_NO_MONSTER, + bool vaultexcl = false); + + void update_excluded_points(); + void recompute_excluded_points(bool recompute_los = false); + + travel_exclude* get_exclude_root(const coord_def &p); + + bool is_excluded(const coord_def &p) const; + bool is_exclude_root(const coord_def &p) const; + + size_t size() const; + bool empty() const; + + const_iterator begin() const; + const_iterator end() const; + + iterator begin(); + iterator end(); + +private: + typedef std::set<coord_def> exclset; + + exclmap exclude_roots; + exclset exclude_points; + +private: + void add_exclude_points(travel_exclude& ex); }; -typedef std::vector<travel_exclude> exclvec; -extern exclvec curr_excludes; // in travel.cc +extern exclude_set curr_excludes; // in travel.cc -bool is_excluded(const coord_def &p, const exclvec &exc = curr_excludes); +bool is_excluded(const coord_def &p, const exclude_set &exc = curr_excludes); class writer; class reader; -void marshallExcludes(writer& outf, const exclvec& excludes); -void unmarshallExcludes(reader& inf, char minorVersion, exclvec& excludes); +void marshallExcludes(writer& outf, const exclude_set& excludes); +void unmarshallExcludes(reader& inf, char minorVersion, exclude_set& excludes); #endif diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc index 1f99918b30..060191bb50 100644 --- a/crawl-ref/source/travel.cc +++ b/crawl-ref/source/travel.cc @@ -89,8 +89,7 @@ TravelCache travel_cache; static std::vector<stair_info> curr_stairs; // Squares that are not safe to travel to on the current level. -typedef std::vector<travel_exclude> exclvec; -exclvec curr_excludes; +exclude_set curr_excludes; // This is where we last tried to take a stair during interlevel travel. // Note that last_stair.depth should be set to -1 before initiating interlevel @@ -1356,9 +1355,10 @@ coord_def travel_pathfind::pathfind(run_mode_type rmode) if (features && floodout) { - for (int i = 0, size = curr_excludes.size(); i < size; ++i) + exclude_set::const_iterator it; + for (it = curr_excludes.begin(); it != curr_excludes.end(); ++it) { - const travel_exclude &exc = curr_excludes[i]; + const travel_exclude &exc = it->second; // An exclude - wherever it is - is always a feature. if (std::find(features->begin(), features->end(), exc.pos) == features->end()) @@ -1400,9 +1400,11 @@ void travel_pathfind::get_features() } } - for (int i = 0, size = curr_excludes.size(); i < size; ++i) + exclude_set::const_iterator it; + for (it = curr_excludes.begin(); it != curr_excludes.end(); ++it) { - const travel_exclude &exc = curr_excludes[i]; + const travel_exclude &exc = it->second; + // An exclude - wherever it is - is always a feature. if (std::find(features->begin(), features->end(), exc.pos) == features->end()) @@ -2636,7 +2638,7 @@ static bool _loadlev_populate_stair_distances(const level_pos &target) if (travel_load_map(target.id.branch, absdungeon_depth(target.id.branch, target.id.depth))) { - exclvec old_excludes = curr_excludes; + exclude_set old_excludes = curr_excludes; curr_excludes.clear(); LevelInfo &li = travel_cache.get_level_info(target.id); diff --git a/crawl-ref/source/travel.h b/crawl-ref/source/travel.h index 739d4a5fac..87216aa6e1 100644 --- a/crawl-ref/source/travel.h +++ b/crawl-ref/source/travel.h @@ -375,7 +375,7 @@ struct LevelInfo void clear_distances(); void set_level_excludes(); - const std::vector<travel_exclude> &get_excludes() const + const exclude_set &get_excludes() const { return excludes; } @@ -413,7 +413,7 @@ private: std::vector<stair_info> stairs; // Squares that are not safe to travel to. - std::vector<travel_exclude> excludes; + exclude_set excludes; std::vector<short> stair_distances; // Dist between stairs level_id id; |