diff options
author | Robert Vollmert <rvollmert@gmx.net> | 2009-11-16 15:49:44 +0100 |
---|---|---|
committer | Robert Vollmert <rvollmert@gmx.net> | 2009-11-16 15:49:44 +0100 |
commit | 0f68e18e6422e140cb992aa7b1723cacffaa980d (patch) | |
tree | 128fe788004e0aee6bb5358ec539acb080eb2290 /crawl-ref/source/mon-pathfind.cc | |
parent | 3dc8e63fb4797dae63c42c76365449016cb777ac (diff) | |
download | crawl-ref-0f68e18e6422e140cb992aa7b1723cacffaa980d.tar.gz crawl-ref-0f68e18e6422e140cb992aa7b1723cacffaa980d.zip |
Split monster_pathfind out into mon-pathfind.cc.
Diffstat (limited to 'crawl-ref/source/mon-pathfind.cc')
-rw-r--r-- | crawl-ref/source/mon-pathfind.cc | 535 |
1 files changed, 535 insertions, 0 deletions
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<coord_def> &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<coord_def> monster_pathfind::backtrack() +{ +#ifdef DEBUG_PATHFIND + mpr("Backtracking..."); +#endif + std::vector<coord_def> 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<coord_def> monster_pathfind::calc_waypoints() +{ + std::vector<coord_def> 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<coord_def> 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<coord_def> &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); +} |