00001
00002
00003
00004
00005
00006 #ifndef FLOOD_FIND_H
00007 #define FLOOD_FIND_H
00008
00009 #include "terrain.h"
00010 #include "travel.h"
00011
00012 template <typename fgrd, typename bound_check>
00013 class flood_find : public travel_pathfind
00014 {
00015 public:
00016 flood_find(const fgrd &f, const bound_check &bc, bool avoid_vaults = false,
00017 bool _check_traversable = true);
00018
00019 void add_feat(int feat);
00020 void add_point(const coord_def &pos);
00021 coord_def find_first_from(const coord_def &c, const map_mask &vlts);
00022 bool points_connected_from(const coord_def &start);
00023 bool any_point_connected_from(const coord_def &start);
00024 bool has_exit_from(const coord_def &start);
00025
00026 bool did_leave_vault() const { return left_vault; }
00027
00028 protected:
00029 bool path_flood(const coord_def &c, const coord_def &dc);
00030 protected:
00031 bool point_hunt, want_exit, no_vault, check_traversable;
00032 bool needed_features[NUM_FEATURES];
00033 std::vector<coord_def> needed_points;
00034 bool left_vault;
00035 const map_mask *vaults;
00036
00037 const fgrd &fgrid;
00038 const bound_check &bcheck;
00039 };
00040
00041 template <typename fgrd, typename bound_check>
00042 flood_find<fgrd, bound_check>::flood_find(const fgrd &f, const bound_check &bc,
00043 bool avoid_vaults, bool _check_traversable)
00044 : travel_pathfind(), point_hunt(false), want_exit(false),
00045 no_vault(avoid_vaults), check_traversable(_check_traversable),
00046 needed_features(), needed_points(), left_vault(true), vaults(NULL),
00047 fgrid(f), bcheck(bc)
00048 {
00049 memset(needed_features, false, sizeof needed_features);
00050 }
00051
00052 template <typename fgrd, typename bound_check>
00053 void flood_find<fgrd, bound_check>::add_feat(int feat)
00054 {
00055 if (feat >= 0 && feat < NUM_FEATURES)
00056 needed_features[feat] = true;
00057 }
00058
00059 template <typename fgrd, typename bound_check>
00060 coord_def
00061 flood_find<fgrd, bound_check>::find_first_from(
00062 const coord_def &c,
00063 const map_mask &vlts)
00064 {
00065 set_floodseed(c);
00066 vaults = &vlts;
00067 return pathfind(RMODE_EXPLORE);
00068 }
00069
00070 template <typename fgrd, typename bound_check>
00071 void flood_find<fgrd, bound_check>::add_point(const coord_def &c)
00072 {
00073 needed_points.push_back(c);
00074 }
00075
00076 template <typename fgrd, typename bound_check>
00077 bool flood_find<fgrd, bound_check>::points_connected_from(
00078 const coord_def &sp)
00079 {
00080 if (needed_points.empty())
00081 return (true);
00082 set_floodseed(sp);
00083 pathfind(RMODE_EXPLORE);
00084 return (needed_points.empty());
00085 }
00086
00087 template <typename fgrd, typename bound_check>
00088 bool flood_find<fgrd, bound_check>::any_point_connected_from(
00089 const coord_def &sp)
00090 {
00091 if (needed_points.empty())
00092 return (true);
00093 set_floodseed(sp);
00094 const size_t sz = needed_points.size();
00095 pathfind(RMODE_EXPLORE);
00096 return (needed_points.size() < sz);
00097 }
00098
00099 template <typename fgrd, typename bound_check>
00100 bool flood_find<fgrd, bound_check>::has_exit_from(
00101 const coord_def &sp)
00102 {
00103 want_exit = true;
00104 set_floodseed(sp);
00105 return (pathfind(RMODE_EXPLORE) == coord_def(-1, -1));
00106 }
00107
00108 template <typename fgrd, typename bound_check>
00109 bool flood_find<fgrd, bound_check>::path_flood(
00110 const coord_def &c,
00111 const coord_def &dc)
00112 {
00113 if (!bcheck(dc))
00114 {
00115 if (want_exit)
00116 {
00117 greedy_dist = 100;
00118 greedy_place = coord_def(-1, -1);
00119 return (true);
00120 }
00121 return (false);
00122 }
00123
00124 if (no_vault && (*vaults)[dc.x][dc.y])
00125 return false;
00126
00127 if (!needed_points.empty())
00128 {
00129 std::vector<coord_def>::iterator i =
00130 std::find(needed_points.begin(), needed_points.end(), dc);
00131 if (i != needed_points.end())
00132 {
00133 needed_points.erase(i);
00134 if (needed_points.empty())
00135 return (true);
00136 }
00137 }
00138
00139 const dungeon_feature_type feat = fgrid(dc);
00140
00141 if (feat == NUM_FEATURES)
00142 {
00143 if (want_exit)
00144 {
00145 greedy_dist = 100;
00146 greedy_place = coord_def(-1, -1);
00147 return (true);
00148 }
00149 return (false);
00150 }
00151
00152 if (needed_features[ feat ])
00153 {
00154 unexplored_place = dc;
00155 unexplored_dist = traveled_distance;
00156 return (true);
00157 }
00158
00159 if (check_traversable && !feat_is_traversable(feat)
00160 && feat != DNGN_SECRET_DOOR
00161 && !feat_is_trap(feat))
00162 {
00163 return (false);
00164 }
00165
00166 if (!left_vault && vaults && !(*vaults)[dc.x][dc.y])
00167 left_vault = true;
00168
00169 good_square(dc);
00170
00171 return (false);
00172 }
00173
00174 #endif
