From 0f68e18e6422e140cb992aa7b1723cacffaa980d Mon Sep 17 00:00:00 2001 From: Robert Vollmert Date: Mon, 16 Nov 2009 15:49:44 +0100 Subject: Split monster_pathfind out into mon-pathfind.cc. --- crawl-ref/source/dungeon.cc | 1 + crawl-ref/source/effects.cc | 1 + crawl-ref/source/makefile.obj | 1 + crawl-ref/source/misc.cc | 1 + crawl-ref/source/mon-behv.cc | 1 + crawl-ref/source/mon-pathfind.cc | 535 +++++++++++++++++++++++++++++++++++++++ crawl-ref/source/mon-pathfind.h | 69 +++++ crawl-ref/source/mon-place.cc | 532 +------------------------------------- crawl-ref/source/mon-place.h | 63 +---- crawl-ref/source/shout.cc | 1 + crawl-ref/source/wiz-mon.cc | 1 + 11 files changed, 618 insertions(+), 588 deletions(-) create mode 100644 crawl-ref/source/mon-pathfind.cc create mode 100644 crawl-ref/source/mon-pathfind.h diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc index 8e59c7f94b..b4c0600289 100644 --- a/crawl-ref/source/dungeon.cc +++ b/crawl-ref/source/dungeon.cc @@ -43,6 +43,7 @@ #include "misc.h" #include "mon-util.h" #include "mon-place.h" +#include "mon-pathfind.h" #include "notes.h" #include "place.h" #include "player.h" diff --git a/crawl-ref/source/effects.cc b/crawl-ref/source/effects.cc index 99f01b41f9..f79a6a95d9 100644 --- a/crawl-ref/source/effects.cc +++ b/crawl-ref/source/effects.cc @@ -44,6 +44,7 @@ #include "mon-cast.h" #include "mon-iter.h" #include "mon-place.h" +#include "mon-pathfind.h" #include "mon-stuff.h" #include "mon-util.h" #include "mutation.h" diff --git a/crawl-ref/source/makefile.obj b/crawl-ref/source/makefile.obj index c67b008aad..54c3a0d705 100644 --- a/crawl-ref/source/makefile.obj +++ b/crawl-ref/source/makefile.obj @@ -105,6 +105,7 @@ mon-gear.o \ mon-grow.o \ mon-info.o \ mon-iter.o \ +mon-pathfind.o \ mon-pick.o \ mon-util.o \ mon-place.o \ diff --git a/crawl-ref/source/misc.cc b/crawl-ref/source/misc.cc index e78751def9..9030989fc0 100644 --- a/crawl-ref/source/misc.cc +++ b/crawl-ref/source/misc.cc @@ -51,6 +51,7 @@ #include "mapmark.h" #include "message.h" #include "mon-place.h" +#include "mon-pathfind.h" #include "mon-iter.h" #include "mon-util.h" #include "mon-stuff.h" diff --git a/crawl-ref/source/mon-behv.cc b/crawl-ref/source/mon-behv.cc index 9868e8dcda..685beec247 100644 --- a/crawl-ref/source/mon-behv.cc +++ b/crawl-ref/source/mon-behv.cc @@ -17,6 +17,7 @@ #include "los.h" #include "mon-iter.h" #include "mon-place.h" +#include "mon-pathfind.h" #include "mon-stuff.h" #include "mon-util.h" #include "random.h" diff --git a/crawl-ref/source/mon-pathfind.cc b/crawl-ref/source/mon-pathfind.cc new file mode 100644 index 0000000000..a919adc204 --- /dev/null +++ b/crawl-ref/source/mon-pathfind.cc @@ -0,0 +1,535 @@ +#include "AppHdr.h" + +#include "mon-pathfind.h" + +#include "coord.h" +#include "directn.h" +#include "env.h" +#include "mon-place.h" +#include "mon-stuff.h" +#include "mon-util.h" +#include "monster.h" +#include "terrain.h" +#include "traps.h" + +///////////////////////////////////////////////////////////////////////////// +// monster_pathfind + +// The pathfinding is an implementation of the A* algorithm. Beginning at the +// destination square we check all neighbours of a given grid, estimate the +// distance needed for any shortest path including this grid and push the +// result into a hash. We can then easily access all points with the shortest +// distance estimates and then check _their_ neighbours and so on. +// The algorithm terminates once we reach the monster position since - because +// of the sorting of grids by shortest distance in the hash - there can be no +// path between start and target that is shorter than the current one. There +// could be other paths that have the same length but that has no real impact. +// If the hash has been cleared and the start grid has not been encountered, +// then there's no path that matches the requirements fed into monster_pathfind. +// (These requirements are usually preference of habitat of a specific monster +// or a limit of the distance between start and any grid on the path.) + +int mons_tracking_range(const monsters *mon) +{ + + int range = 0; + switch (mons_intel(mon)) + { + case I_PLANT: + range = 2; + break; + case I_INSECT: + range = 4; + break; + case I_ANIMAL: + range = 5; + break; + case I_NORMAL: + range = LOS_RADIUS; + break; + default: + // Highly intelligent monsters can find their way + // anywhere. (range == 0 means no restriction.) + break; + } + + if (range) + { + if (mons_is_native_in_branch(mon)) + range += 3; + else if (mons_class_flag(mon->type, M_BLOOD_SCENT)) + range++; + } + + return (range); +} + +//#define DEBUG_PATHFIND +monster_pathfind::monster_pathfind() + : mons(), target(), range(0), min_length(0), max_length(0), dist(), prev() +{ +} + +monster_pathfind::~monster_pathfind() +{ +} + +void monster_pathfind::set_range(int r) +{ + if (r >= 0) + range = r; +} + +coord_def monster_pathfind::next_pos(const coord_def &c) const +{ + return c + Compass[prev[c.x][c.y]]; +} + +// The main method in the monster_pathfind class. +// Returns true if a path was found, else false. +bool monster_pathfind::init_pathfind(const monsters *mon, coord_def dest, + bool diag, bool msg, bool pass_unmapped) +{ + mons = mon; + + // We're doing a reverse search from target to monster. + start = dest; + target = mon->pos(); + pos = start; + allow_diagonals = diag; + traverse_unmapped = pass_unmapped; + + // Easy enough. :P + if (start == target) + { + if (msg) + mpr("The monster is already there!"); + + return (true); + } + + return start_pathfind(msg); +} + +bool monster_pathfind::init_pathfind(coord_def src, coord_def dest, bool diag, + bool msg) +{ + start = src; + target = dest; + pos = start; + allow_diagonals = diag; + + // Easy enough. :P + if (start == target) + return (true); + + return start_pathfind(msg); +} + +bool monster_pathfind::start_pathfind(bool msg) +{ + // NOTE: We never do any traversable() check for the starting square + // (target). This means that even if the target cannot be reached + // we may still find a path leading adjacent to this position, which + // is desirable if e.g. the player is hovering over deep water + // surrounded by shallow water or floor, or if a foe is hiding in + // a wall. + // If the surrounding squares also are not traversable, we return + // early that no path could be found. + + max_length = min_length = grid_distance(pos.x, pos.y, target.x, target.y); + for (int i = 0; i < GXM; i++) + for (int j = 0; j < GYM; j++) + dist[i][j] = INFINITE_DISTANCE; + + dist[pos.x][pos.y] = 0; + + bool success = false; + do + { + // Calculate the distance to all neighbours of the current position, + // and add them to the hash, if they haven't already been looked at. + success = calc_path_to_neighbours(); + if (success) + return (true); + + // Pull the position with shortest distance estimate to our target grid. + success = get_best_position(); + + if (!success) + { + if (msg) + { + mprf("Couldn't find a path from (%d,%d) to (%d,%d).", + target.x, target.y, start.x, start.y); + } + return (false); + } + } + while (true); +} + +// Returns true as soon as we encounter the target. +bool monster_pathfind::calc_path_to_neighbours() +{ + coord_def npos; + int distance, old_dist, total; + + // For each point, we look at all neighbour points. Check the orthogonals + // last, so that, should an orthogonal and a diagonal direction have the + // same total travel cost, the orthogonal will be picked first, and thus + // zigzagging will be significantly reduced. + // + // 1 0 3 This means directions are looked at, in order, + // \ | / 1, 3, 5, 7 (diagonals) followed by 0, 2, 4, 6 + // 6--.--2 (orthogonals). This is achieved by the assignment + // / | \ of (dir = 0) once dir has passed 7. + // 7 4 5 + // + for (int dir = 1; dir < 8; (dir += 2) == 9 && (dir = 0)) + { + // Skip diagonal movement. + if (!allow_diagonals && (dir % 2)) + continue; + + npos = pos + Compass[dir]; + +#ifdef DEBUG_PATHFIND + mprf("Looking at neighbour (%d,%d)", npos.x, npos.y); +#endif + if (!in_bounds(npos)) + continue; + + if (!traversable(npos)) + continue; + + // Ignore this grid if it takes us above the allowed distance. + if (range && estimated_cost(npos) > range) + continue; + + distance = dist[pos.x][pos.y] + travel_cost(npos); + old_dist = dist[npos.x][npos.y]; +#ifdef DEBUG_PATHFIND + mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance, + INFINITE_DISTANCE); +#endif + // If the new distance is better than the old one (initialised with + // INFINITE), update the position. + if (distance < old_dist) + { + // Calculate new total path length. + total = distance + estimated_cost(npos); + if (old_dist == INFINITE_DISTANCE) + { +#ifdef DEBUG_PATHFIND + mprf("Adding (%d,%d) to hash (total dist = %d)", + npos.x, npos.y, total); +#endif + add_new_pos(npos, total); + if (total > max_length) + max_length = total; + } + else + { +#ifdef DEBUG_PATHFIND + mprf("Improving (%d,%d) to total dist %d", + npos.x, npos.y, total); +#endif + + update_pos(npos, total); + } + + // Update distance start->pos. + dist[npos.x][npos.y] = distance; + + // Set backtracking information. + // Converts the Compass direction to its counterpart. + // 0 1 2 4 5 6 + // 7 . 3 ==> 3 . 7 e.g. (3 + 4) % 8 = 7 + // 6 5 4 2 1 0 (7 + 4) % 8 = 11 % 8 = 3 + + prev[npos.x][npos.y] = (dir + 4) % 8; + + // Are we finished? + if (npos == target) + { +#ifdef DEBUG_PATHFIND + mpr("Arrived at target."); +#endif + return (true); + } + } + } + return (false); +} + +// Starting at known min_length (minimum total estimated path distance), check +// the hash for existing vectors, then pick the last entry of the first vector +// that matches. Update min_length, if necessary. +bool monster_pathfind::get_best_position() +{ + for (int i = min_length; i <= max_length; i++) + { + if (!hash[i].empty()) + { + if (i > min_length) + min_length = i; + + std::vector &vec = hash[i]; + // Pick the last position pushed into the vector as it's most + // likely to be close to the target. + pos = vec[vec.size()-1]; + vec.pop_back(); + +#ifdef DEBUG_PATHFIND + mprf("Returning (%d, %d) as best pos with total dist %d.", + pos.x, pos.y, min_length); +#endif + + return (true); + } +#ifdef DEBUG_PATHFIND + mprf("No positions for path length %d.", i); +#endif + } + + // Nothing found? Then there's no path! :( + return (false); +} + +// Using the prev vector backtrack from start to target to find all steps to +// take along the shortest path. +std::vector monster_pathfind::backtrack() +{ +#ifdef DEBUG_PATHFIND + mpr("Backtracking..."); +#endif + std::vector path; + pos = target; + path.push_back(pos); + + if (pos == start) + return path; + + int dir; + do + { + dir = prev[pos.x][pos.y]; + pos = pos + Compass[dir]; + ASSERT(in_bounds(pos)); +#ifdef DEBUG_PATHFIND + mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y, + pos.x, pos.y); +#endif + path.push_back(pos); + + if (pos.x == 0 && pos.y == 0) + break; + } + while (pos != start); + ASSERT(pos == start); + + return (path); +} + +// Reduces the path coordinates to only a couple of key waypoints needed +// to reach the target. Waypoints are chosen such that from one waypoint you +// can see (and, more importantly, reach) the next one. Note that +// can_go_straight() is probably rather too conservative in these estimates. +// This is done because Crawl's pathfinding - once a target is in sight and easy +// reach - is both very robust and natural, especially if we want to flexibly +// avoid plants and other monsters in the way. +std::vector monster_pathfind::calc_waypoints() +{ + std::vector path = backtrack(); + + // If no path found, nothing to be done. + if (path.empty()) + return path; + + dungeon_feature_type can_move; + if (mons_amphibious(mons)) + can_move = DNGN_DEEP_WATER; + else + can_move = DNGN_SHALLOW_WATER; + + std::vector waypoints; + pos = path[0]; + +#ifdef DEBUG_PATHFIND + mpr(EOL "Waypoints:"); +#endif + for (unsigned int i = 1; i < path.size(); i++) + { + if (can_go_straight(pos, path[i], can_move)) + continue; + else + { + pos = path[i-1]; + waypoints.push_back(pos); +#ifdef DEBUG_PATHFIND + mprf("waypoint: (%d, %d)", pos.x, pos.y); +#endif + } + } + + // Add the actual target to the list of waypoints, so we can later check + // whether a tracked enemy has moved too much, in case we have to update + // the path. + if (pos != path[path.size() - 1]) + waypoints.push_back(path[path.size() - 1]); + + return (waypoints); +} + +bool monster_pathfind::traversable(const coord_def p) +{ + if (traverse_unmapped && grd(p) == DNGN_UNSEEN) + return (true); + + if (mons) + return mons_traversable(p); + + return (!feat_is_solid(grd(p)) && !feat_destroys_items(grd(p))); +} + +// Checks whether a given monster can pass over a certain position, respecting +// its preferred habit and capability of flight or opening doors. +bool monster_pathfind::mons_traversable(const coord_def p) +{ + const monster_type montype = mons_is_zombified(mons) ? mons_zombie_base(mons) + : mons->type; + + if (!mons->is_habitable_feat(grd(p))) + return (false); + + // Monsters that can't open doors won't be able to pass them. + if (feat_is_closed_door(grd(p)) || grd(p) == DNGN_SECRET_DOOR) + { + if (mons_is_zombified(mons)) + { + if (mons_class_itemuse(montype) < MONUSE_OPEN_DOORS) + return (false); + } + else if (mons_itemuse(mons) < MONUSE_OPEN_DOORS) + return (false); + } + + // Your friends only know about doors you know about, unless they feel + // at home in this branch. + if (grd(p) == DNGN_SECRET_DOOR && mons->friendly() + && (mons_intel(mons) < I_NORMAL || !mons_is_native_in_branch(mons))) + { + return (false); + } + + const trap_def* ptrap = find_trap(p); + if (ptrap) + { + const trap_type tt = ptrap->type; + + // Don't allow allies to pass over known (to them) Zot traps. + if (tt == TRAP_ZOT + && ptrap->is_known(mons) + && mons->friendly()) + { + return (false); + } + + // Monsters cannot travel over teleport traps. + if (!can_place_on_trap(montype, tt)) + return (false); + } + + return (true); +} + +int monster_pathfind::travel_cost(coord_def npos) +{ + if (mons) + return mons_travel_cost(npos); + + return (1); +} + +// Assumes that grids that really cannot be entered don't even get here. +// (Checked by traversable().) +int monster_pathfind::mons_travel_cost(coord_def npos) +{ + ASSERT(grid_distance(pos, npos) <= 1); + + // Doors need to be opened. + if (feat_is_closed_door(grd(npos)) || grd(npos) == DNGN_SECRET_DOOR) + return 2; + + const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons) + : mons->type; + + const bool airborne = mons_airborne(montype, -1, false); + + // Travelling through water, entering or leaving water is more expensive + // for non-amphibious monsters, so they'll avoid it where possible. + // (The resulting path might not be optimal but it will lead to a path + // a monster of such habits is likely to prefer.) + // Only tested for shallow water since they can't enter deep water anyway. + if (!airborne && !mons_class_amphibious(montype) + && (grd(pos) == DNGN_SHALLOW_WATER || grd(npos) == DNGN_SHALLOW_WATER)) + { + return 2; + } + + // Try to avoid (known) traps. + const trap_def* ptrap = find_trap(npos); + if (ptrap) + { + const bool knows_trap = ptrap->is_known(mons); + const trap_type tt = ptrap->type; + if (tt == TRAP_ALARM || tt == TRAP_ZOT) + { + // Your allies take extra precautions to avoid known alarm traps. + // Zot traps are considered intraversable. + if (knows_trap && mons->friendly()) + return (3); + + // To hostile monsters, these traps are completely harmless. + return 1; + } + + // Mechanical traps can be avoided by flying, as can shafts, and + // tele traps are never traversable anyway. + if (knows_trap && !airborne) + return 2; + } + + return 1; +} + +// The estimated cost to reach a grid is simply max(dx, dy). +int monster_pathfind::estimated_cost(coord_def p) +{ + return (grid_distance(p, target)); +} + +void monster_pathfind::add_new_pos(coord_def npos, int total) +{ + hash[total].push_back(npos); +} + +void monster_pathfind::update_pos(coord_def npos, int total) +{ + // Find hash position of old distance and delete it, + // then call_add_new_pos. + int old_total = dist[npos.x][npos.y] + estimated_cost(npos); + + std::vector &vec = hash[old_total]; + for (unsigned int i = 0; i < vec.size(); i++) + { + if (vec[i] == npos) + { + vec.erase(vec.begin() + i); + break; + } + } + + add_new_pos(npos, total); +} diff --git a/crawl-ref/source/mon-pathfind.h b/crawl-ref/source/mon-pathfind.h new file mode 100644 index 0000000000..590fb3f777 --- /dev/null +++ b/crawl-ref/source/mon-pathfind.h @@ -0,0 +1,69 @@ +#ifndef MON_PATHFIND_H +#define MON_PATHFIND_H + +class monsters; + +int mons_tracking_range(const monsters *mon); + +class monster_pathfind +{ +public: + monster_pathfind(); + virtual ~monster_pathfind(); + + // public methods + void set_range(int r); + coord_def next_pos(const coord_def &p) const; + bool init_pathfind(const monsters *mon, coord_def dest, + bool diag = true, bool msg = false, + bool pass_unmapped = false); + bool init_pathfind(coord_def src, coord_def dest, + bool diag = true, bool msg = false); + bool start_pathfind(bool msg = false); + std::vector backtrack(void); + std::vector calc_waypoints(void); + +protected: + // protected methods + bool calc_path_to_neighbours(void); + bool traversable(coord_def p); + int travel_cost(coord_def npos); + bool mons_traversable(coord_def p); + int mons_travel_cost(coord_def npos); + int estimated_cost(coord_def npos); + void add_new_pos(coord_def pos, int total); + void update_pos(coord_def pos, int total); + bool get_best_position(void); + + + // The monster trying to find a path. + const monsters *mons; + + // Our destination, and the current position we're looking at. + coord_def start, target, pos; + + // If false, do not move diagonally along the path. + bool allow_diagonals; + + // If true, unmapped terrain is treated as traversable no matter the + // monster involved. + // (Used for player estimates of whether a monster can travel somewhere.) + bool traverse_unmapped; + + // Maximum range to search between start and target. None, if zero. + int range; + + // Currently shortest and longest possible total length of the path. + int min_length; + int max_length; + + // The array of distances from start to any already tried point. + int dist[GXM][GYM]; + // An array to store where we came from on a given shortest path. + int prev[GXM][GYM]; + + FixedVector, GXM * GYM> hash; +}; + +#endif + diff --git a/crawl-ref/source/mon-place.cc b/crawl-ref/source/mon-place.cc index 57990844ff..e03177d26d 100644 --- a/crawl-ref/source/mon-place.cc +++ b/crawl-ref/source/mon-place.cc @@ -124,7 +124,7 @@ bool monster_habitable_grid(const monsters *m, m->cannot_move())); } -inline static bool _mons_airborne(int mcls, int flies, bool paralysed) +bool mons_airborne(int mcls, int flies, bool paralysed) { if (flies == -1) flies = mons_class_flies(mcls); @@ -171,7 +171,7 @@ bool monster_habitable_grid(monster_type montype, // [dshaligram] Flying creatures are all DNGN_FLOOR, so we // only have to check for the additional valid grids of deep // water and lava. - if (_mons_airborne(montype, flies, paralysed) + if (mons_airborne(montype, flies, paralysed) && (actual_grid == DNGN_LAVA || actual_grid == DNGN_DEEP_WATER)) { return (true); @@ -467,7 +467,7 @@ monster_type pick_random_monster(const level_id &place, int power, return (mon_type); } -static bool _can_place_on_trap(int mon_type, trap_type trap) +bool can_place_on_trap(int mon_type, trap_type trap) { if (trap == TRAP_TELEPORT) return (false); @@ -544,7 +544,7 @@ static monster_type _resolve_monster_type(monster_type mon_type, // Don't generate monsters on top of teleport traps. const trap_def* ptrap = find_trap(pos); - if (ptrap && !_can_place_on_trap(mon_type, ptrap->type)) + if (ptrap && !can_place_on_trap(mon_type, ptrap->type)) continue; // Check whether there's a stair @@ -713,7 +713,7 @@ static bool _valid_monster_generation_location( // Don't generate monsters on top of teleport traps. // (How did they get there?) const trap_def* ptrap = find_trap(mg_pos); - if (ptrap && !_can_place_on_trap(mg.cls, ptrap->type)) + if (ptrap && !can_place_on_trap(mg.cls, ptrap->type)) return (false); return (true); @@ -2980,528 +2980,6 @@ monster_type summon_any_dragon(dragon_class_type dct) return (mon); } -///////////////////////////////////////////////////////////////////////////// -// monster_pathfind - -// The pathfinding is an implementation of the A* algorithm. Beginning at the -// destination square we check all neighbours of a given grid, estimate the -// distance needed for any shortest path including this grid and push the -// result into a hash. We can then easily access all points with the shortest -// distance estimates and then check _their_ neighbours and so on. -// The algorithm terminates once we reach the monster position since - because -// of the sorting of grids by shortest distance in the hash - there can be no -// path between start and target that is shorter than the current one. There -// could be other paths that have the same length but that has no real impact. -// If the hash has been cleared and the start grid has not been encountered, -// then there's no path that matches the requirements fed into monster_pathfind. -// (These requirements are usually preference of habitat of a specific monster -// or a limit of the distance between start and any grid on the path.) - -int mons_tracking_range(const monsters *mon) -{ - - int range = 0; - switch (mons_intel(mon)) - { - case I_PLANT: - range = 2; - break; - case I_INSECT: - range = 4; - break; - case I_ANIMAL: - range = 5; - break; - case I_NORMAL: - range = LOS_RADIUS; - break; - default: - // Highly intelligent monsters can find their way - // anywhere. (range == 0 means no restriction.) - break; - } - - if (range) - { - if (mons_is_native_in_branch(mon)) - range += 3; - else if (mons_class_flag(mon->type, M_BLOOD_SCENT)) - range++; - } - - return (range); -} - -//#define DEBUG_PATHFIND -monster_pathfind::monster_pathfind() - : mons(), target(), range(0), min_length(0), max_length(0), dist(), prev() -{ -} - -monster_pathfind::~monster_pathfind() -{ -} - -void monster_pathfind::set_range(int r) -{ - if (r >= 0) - range = r; -} - -coord_def monster_pathfind::next_pos(const coord_def &c) const -{ - return c + Compass[prev[c.x][c.y]]; -} - -// The main method in the monster_pathfind class. -// Returns true if a path was found, else false. -bool monster_pathfind::init_pathfind(const monsters *mon, coord_def dest, - bool diag, bool msg, bool pass_unmapped) -{ - mons = mon; - - // We're doing a reverse search from target to monster. - start = dest; - target = mon->pos(); - pos = start; - allow_diagonals = diag; - traverse_unmapped = pass_unmapped; - - // Easy enough. :P - if (start == target) - { - if (msg) - mpr("The monster is already there!"); - - return (true); - } - - return start_pathfind(msg); -} - -bool monster_pathfind::init_pathfind(coord_def src, coord_def dest, bool diag, - bool msg) -{ - start = src; - target = dest; - pos = start; - allow_diagonals = diag; - - // Easy enough. :P - if (start == target) - return (true); - - return start_pathfind(msg); -} - -bool monster_pathfind::start_pathfind(bool msg) -{ - // NOTE: We never do any traversable() check for the starting square - // (target). This means that even if the target cannot be reached - // we may still find a path leading adjacent to this position, which - // is desirable if e.g. the player is hovering over deep water - // surrounded by shallow water or floor, or if a foe is hiding in - // a wall. - // If the surrounding squares also are not traversable, we return - // early that no path could be found. - - max_length = min_length = grid_distance(pos.x, pos.y, target.x, target.y); - for (int i = 0; i < GXM; i++) - for (int j = 0; j < GYM; j++) - dist[i][j] = INFINITE_DISTANCE; - - dist[pos.x][pos.y] = 0; - - bool success = false; - do - { - // Calculate the distance to all neighbours of the current position, - // and add them to the hash, if they haven't already been looked at. - success = calc_path_to_neighbours(); - if (success) - return (true); - - // Pull the position with shortest distance estimate to our target grid. - success = get_best_position(); - - if (!success) - { - if (msg) - { - mprf("Couldn't find a path from (%d,%d) to (%d,%d).", - target.x, target.y, start.x, start.y); - } - return (false); - } - } - while (true); -} - -// Returns true as soon as we encounter the target. -bool monster_pathfind::calc_path_to_neighbours() -{ - coord_def npos; - int distance, old_dist, total; - - // For each point, we look at all neighbour points. Check the orthogonals - // last, so that, should an orthogonal and a diagonal direction have the - // same total travel cost, the orthogonal will be picked first, and thus - // zigzagging will be significantly reduced. - // - // 1 0 3 This means directions are looked at, in order, - // \ | / 1, 3, 5, 7 (diagonals) followed by 0, 2, 4, 6 - // 6--.--2 (orthogonals). This is achieved by the assignment - // / | \ of (dir = 0) once dir has passed 7. - // 7 4 5 - // - for (int dir = 1; dir < 8; (dir += 2) == 9 && (dir = 0)) - { - // Skip diagonal movement. - if (!allow_diagonals && (dir % 2)) - continue; - - npos = pos + Compass[dir]; - -#ifdef DEBUG_PATHFIND - mprf("Looking at neighbour (%d,%d)", npos.x, npos.y); -#endif - if (!in_bounds(npos)) - continue; - - if (!traversable(npos)) - continue; - - // Ignore this grid if it takes us above the allowed distance. - if (range && estimated_cost(npos) > range) - continue; - - distance = dist[pos.x][pos.y] + travel_cost(npos); - old_dist = dist[npos.x][npos.y]; -#ifdef DEBUG_PATHFIND - mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance, - INFINITE_DISTANCE); -#endif - // If the new distance is better than the old one (initialised with - // INFINITE), update the position. - if (distance < old_dist) - { - // Calculate new total path length. - total = distance + estimated_cost(npos); - if (old_dist == INFINITE_DISTANCE) - { -#ifdef DEBUG_PATHFIND - mprf("Adding (%d,%d) to hash (total dist = %d)", - npos.x, npos.y, total); -#endif - add_new_pos(npos, total); - if (total > max_length) - max_length = total; - } - else - { -#ifdef DEBUG_PATHFIND - mprf("Improving (%d,%d) to total dist %d", - npos.x, npos.y, total); -#endif - - update_pos(npos, total); - } - - // Update distance start->pos. - dist[npos.x][npos.y] = distance; - - // Set backtracking information. - // Converts the Compass direction to its counterpart. - // 0 1 2 4 5 6 - // 7 . 3 ==> 3 . 7 e.g. (3 + 4) % 8 = 7 - // 6 5 4 2 1 0 (7 + 4) % 8 = 11 % 8 = 3 - - prev[npos.x][npos.y] = (dir + 4) % 8; - - // Are we finished? - if (npos == target) - { -#ifdef DEBUG_PATHFIND - mpr("Arrived at target."); -#endif - return (true); - } - } - } - return (false); -} - -// Starting at known min_length (minimum total estimated path distance), check -// the hash for existing vectors, then pick the last entry of the first vector -// that matches. Update min_length, if necessary. -bool monster_pathfind::get_best_position() -{ - for (int i = min_length; i <= max_length; i++) - { - if (!hash[i].empty()) - { - if (i > min_length) - min_length = i; - - std::vector &vec = hash[i]; - // Pick the last position pushed into the vector as it's most - // likely to be close to the target. - pos = vec[vec.size()-1]; - vec.pop_back(); - -#ifdef DEBUG_PATHFIND - mprf("Returning (%d, %d) as best pos with total dist %d.", - pos.x, pos.y, min_length); -#endif - - return (true); - } -#ifdef DEBUG_PATHFIND - mprf("No positions for path length %d.", i); -#endif - } - - // Nothing found? Then there's no path! :( - return (false); -} - -// Using the prev vector backtrack from start to target to find all steps to -// take along the shortest path. -std::vector monster_pathfind::backtrack() -{ -#ifdef DEBUG_PATHFIND - mpr("Backtracking..."); -#endif - std::vector path; - pos = target; - path.push_back(pos); - - if (pos == start) - return path; - - int dir; - do - { - dir = prev[pos.x][pos.y]; - pos = pos + Compass[dir]; - ASSERT(in_bounds(pos)); -#ifdef DEBUG_PATHFIND - mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y, - pos.x, pos.y); -#endif - path.push_back(pos); - - if (pos.x == 0 && pos.y == 0) - break; - } - while (pos != start); - ASSERT(pos == start); - - return (path); -} - -// Reduces the path coordinates to only a couple of key waypoints needed -// to reach the target. Waypoints are chosen such that from one waypoint you -// can see (and, more importantly, reach) the next one. Note that -// can_go_straight() is probably rather too conservative in these estimates. -// This is done because Crawl's pathfinding - once a target is in sight and easy -// reach - is both very robust and natural, especially if we want to flexibly -// avoid plants and other monsters in the way. -std::vector monster_pathfind::calc_waypoints() -{ - std::vector path = backtrack(); - - // If no path found, nothing to be done. - if (path.empty()) - return path; - - dungeon_feature_type can_move; - if (mons_amphibious(mons)) - can_move = DNGN_DEEP_WATER; - else - can_move = DNGN_SHALLOW_WATER; - - std::vector waypoints; - pos = path[0]; - -#ifdef DEBUG_PATHFIND - mpr(EOL "Waypoints:"); -#endif - for (unsigned int i = 1; i < path.size(); i++) - { - if (can_go_straight(pos, path[i], can_move)) - continue; - else - { - pos = path[i-1]; - waypoints.push_back(pos); -#ifdef DEBUG_PATHFIND - mprf("waypoint: (%d, %d)", pos.x, pos.y); -#endif - } - } - - // Add the actual target to the list of waypoints, so we can later check - // whether a tracked enemy has moved too much, in case we have to update - // the path. - if (pos != path[path.size() - 1]) - waypoints.push_back(path[path.size() - 1]); - - return (waypoints); -} - -bool monster_pathfind::traversable(const coord_def p) -{ - if (traverse_unmapped && grd(p) == DNGN_UNSEEN) - return (true); - - if (mons) - return mons_traversable(p); - - return (!feat_is_solid(grd(p)) && !feat_destroys_items(grd(p))); -} - -// Checks whether a given monster can pass over a certain position, respecting -// its preferred habit and capability of flight or opening doors. -bool monster_pathfind::mons_traversable(const coord_def p) -{ - const monster_type montype = mons_is_zombified(mons) ? mons_zombie_base(mons) - : mons->type; - - if (!monster_habitable_grid(montype, grd(p))) - return (false); - - // Monsters that can't open doors won't be able to pass them. - if (feat_is_closed_door(grd(p)) || grd(p) == DNGN_SECRET_DOOR) - { - if (mons_is_zombified(mons)) - { - if (mons_class_itemuse(montype) < MONUSE_OPEN_DOORS) - return (false); - } - else if (mons_itemuse(mons) < MONUSE_OPEN_DOORS) - return (false); - } - - // Your friends only know about doors you know about, unless they feel - // at home in this branch. - if (grd(p) == DNGN_SECRET_DOOR && mons->friendly() - && (mons_intel(mons) < I_NORMAL || !mons_is_native_in_branch(mons))) - { - return (false); - } - - const trap_def* ptrap = find_trap(p); - if (ptrap) - { - const trap_type tt = ptrap->type; - - // Don't allow allies to pass over known (to them) Zot traps. - if (tt == TRAP_ZOT - && ptrap->is_known(mons) - && mons->friendly()) - { - return (false); - } - - // Monsters cannot travel over teleport traps. - if (!_can_place_on_trap(montype, tt)) - return (false); - } - - return (true); -} - -int monster_pathfind::travel_cost(coord_def npos) -{ - if (mons) - return mons_travel_cost(npos); - - return (1); -} - -// Assumes that grids that really cannot be entered don't even get here. -// (Checked by traversable().) -int monster_pathfind::mons_travel_cost(coord_def npos) -{ - ASSERT(grid_distance(pos, npos) <= 1); - - // Doors need to be opened. - if (feat_is_closed_door(grd(npos)) || grd(npos) == DNGN_SECRET_DOOR) - return 2; - - const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons) - : mons->type; - - const bool airborne = _mons_airborne(montype, -1, false); - - // Travelling through water, entering or leaving water is more expensive - // for non-amphibious monsters, so they'll avoid it where possible. - // (The resulting path might not be optimal but it will lead to a path - // a monster of such habits is likely to prefer.) - // Only tested for shallow water since they can't enter deep water anyway. - if (!airborne && !mons_class_amphibious(montype) - && (grd(pos) == DNGN_SHALLOW_WATER || grd(npos) == DNGN_SHALLOW_WATER)) - { - return 2; - } - - // Try to avoid (known) traps. - const trap_def* ptrap = find_trap(npos); - if (ptrap) - { - const bool knows_trap = ptrap->is_known(mons); - const trap_type tt = ptrap->type; - if (tt == TRAP_ALARM || tt == TRAP_ZOT) - { - // Your allies take extra precautions to avoid known alarm traps. - // Zot traps are considered intraversable. - if (knows_trap && mons->friendly()) - return (3); - - // To hostile monsters, these traps are completely harmless. - return 1; - } - - // Mechanical traps can be avoided by flying, as can shafts, and - // tele traps are never traversable anyway. - if (knows_trap && !airborne) - return 2; - } - - return 1; -} - -// The estimated cost to reach a grid is simply max(dx, dy). -int monster_pathfind::estimated_cost(coord_def p) -{ - return (grid_distance(p, target)); -} - -void monster_pathfind::add_new_pos(coord_def npos, int total) -{ - hash[total].push_back(npos); -} - -void monster_pathfind::update_pos(coord_def npos, int total) -{ - // Find hash position of old distance and delete it, - // then call_add_new_pos. - int old_total = dist[npos.x][npos.y] + estimated_cost(npos); - - std::vector &vec = hash[old_total]; - for (unsigned int i = 0; i < vec.size(); i++) - { - if (vec[i] == npos) - { - vec.erase(vec.begin() + i); - break; - } - } - - add_new_pos(npos, total); -} - ///////////////////////////////////////////////////////////////////////////// // // Random monsters for portal vaults. diff --git a/crawl-ref/source/mon-place.h b/crawl-ref/source/mon-place.h index 533f0943dc..dd3523acdc 100644 --- a/crawl-ref/source/mon-place.h +++ b/crawl-ref/source/mon-place.h @@ -346,68 +346,9 @@ void get_vault_mon_list(std::vector &list); void setup_vault_mon_list(); -int mons_tracking_range(const monsters *mon); - monsters* get_free_monster(); -class monster_pathfind -{ -public: - monster_pathfind(); - virtual ~monster_pathfind(); - - // public methods - void set_range(int r); - coord_def next_pos(const coord_def &p) const; - bool init_pathfind(const monsters *mon, coord_def dest, - bool diag = true, bool msg = false, - bool pass_unmapped = false); - bool init_pathfind(coord_def src, coord_def dest, - bool diag = true, bool msg = false); - bool start_pathfind(bool msg = false); - std::vector backtrack(void); - std::vector calc_waypoints(void); - -protected: - // protected methods - bool calc_path_to_neighbours(void); - bool traversable(coord_def p); - int travel_cost(coord_def npos); - bool mons_traversable(coord_def p); - int mons_travel_cost(coord_def npos); - int estimated_cost(coord_def npos); - void add_new_pos(coord_def pos, int total); - void update_pos(coord_def pos, int total); - bool get_best_position(void); - - - // The monster trying to find a path. - const monsters *mons; - - // Our destination, and the current position we're looking at. - coord_def start, target, pos; - - // If false, do not move diagonally along the path. - bool allow_diagonals; - - // If true, unmapped terrain is treated as traversable no matter the - // monster involved. - // (Used for player estimates of whether a monster can travel somewhere.) - bool traverse_unmapped; - - // Maximum range to search between start and target. None, if zero. - int range; - - // Currently shortest and longest possible total length of the path. - int min_length; - int max_length; - - // The array of distances from start to any already tried point. - int dist[GXM][GYM]; - // An array to store where we came from on a given shortest path. - int prev[GXM][GYM]; - - FixedVector, GXM * GYM> hash; -}; +bool can_place_on_trap(int mon_type, trap_type trap); +bool mons_airborne(int mcls, int flies, bool paralysed); #endif // MONPLACE_H diff --git a/crawl-ref/source/shout.cc b/crawl-ref/source/shout.cc index 64378ed7ad..25edbe3ee9 100644 --- a/crawl-ref/source/shout.cc +++ b/crawl-ref/source/shout.cc @@ -17,6 +17,7 @@ #include "mon-behv.h" #include "mon-iter.h" #include "mon-place.h" +#include "mon-pathfind.h" #include "monster.h" #include "mon-stuff.h" #include "options.h" diff --git a/crawl-ref/source/wiz-mon.cc b/crawl-ref/source/wiz-mon.cc index 3701d344a0..1bb1622dbb 100644 --- a/crawl-ref/source/wiz-mon.cc +++ b/crawl-ref/source/wiz-mon.cc @@ -21,6 +21,7 @@ #include "macro.h" #include "message.h" #include "mon-place.h" +#include "mon-pathfind.h" #include "mon-speak.h" #include "mon-stuff.h" #include "mon-iter.h" -- cgit v1.2.3-54-g00ecf