diff options
| -rw-r--r-- | crawl-ref/source/makefile.obj | 5 | ||||
| -rw-r--r-- | crawl-ref/source/mon-behv.cc | 973 | ||||
| -rw-r--r-- | crawl-ref/source/mon-movetarget.cc | 972 | ||||
| -rw-r--r-- | crawl-ref/source/mon-movetarget.h | 19 |
4 files changed, 1004 insertions, 965 deletions
diff --git a/crawl-ref/source/makefile.obj b/crawl-ref/source/makefile.obj index 54c3a0d705..ab77aadb21 100644 --- a/crawl-ref/source/makefile.obj +++ b/crawl-ref/source/makefile.obj @@ -105,14 +105,15 @@ mon-gear.o \ mon-grow.o \ mon-info.o \ mon-iter.o \ +mon-movetarget.o \ mon-pathfind.o \ mon-pick.o \ -mon-util.o \ mon-place.o \ +mon-util.o \ mon-speak.o \ -monster.o \ mon-stuff.o \ mon-transit.o \ +monster.o \ mt19937ar.o \ mutation.o \ newgame.o \ diff --git a/crawl-ref/source/mon-behv.cc b/crawl-ref/source/mon-behv.cc index 685beec247..02cecb0ab9 100644 --- a/crawl-ref/source/mon-behv.cc +++ b/crawl-ref/source/mon-behv.cc @@ -16,6 +16,7 @@ #include "exclude.h" #include "los.h" #include "mon-iter.h" +#include "mon-movetarget.h" #include "mon-place.h" #include "mon-pathfind.h" #include "mon-stuff.h" @@ -30,960 +31,6 @@ static void _set_nearest_monster_foe(monsters *monster); -// Check all grids in LoS and mark lava and/or water as seen if the -// appropriate grids are encountered, so we later only need to do the -// visibility check for monsters that can't pass a feature potentially in -// the way. We don't care about shallow water as most monsters can safely -// cross that, and fire elementals alone aren't really worth the extra -// hassle. :) -static void _check_lava_water_in_sight() -{ - you.lava_in_sight = you.water_in_sight = 0; - for (radius_iterator ri(you.pos(), LOS_RADIUS); ri; ++ri) - { - const dungeon_feature_type feat = grd(*ri); - if (feat == DNGN_LAVA) - { - you.lava_in_sight = 1; - if (you.water_in_sight > 0) - break; - } - else if (feat == DNGN_DEEP_WATER) - { - you.water_in_sight = 1; - if (you.lava_in_sight > 0) - break; - } - } -} - -// If a monster can see but not directly reach the target, and then fails to -// find a path to get there, mark all surrounding (in a radius of 2) monsters -// of the same (or greater) movement restrictions as also being unable to -// find a path, so we won't need to calculate again. -// Should there be a direct path to the target for a monster thus marked, it -// will still be able to come nearer (and the mark will then be cleared). -static void _mark_neighbours_target_unreachable(monsters *mon) -{ - // Highly intelligent monsters are perfectly capable of pathfinding - // and don't need their neighbour's advice. - const mon_intel_type intel = mons_intel(mon); - if (intel > I_NORMAL) - return; - - const bool flies = mons_flies(mon); - const bool amphibious = mons_amphibious(mon); - const habitat_type habit = mons_primary_habitat(mon); - - for (radius_iterator ri(mon->pos(), 2, true, false); ri; ++ri) - { - if (*ri == mon->pos()) - continue; - - // Don't alert monsters out of sight (e.g. on the other side of - // a wall). - if (!mon->see_cell(*ri)) - continue; - - monsters* const m = monster_at(*ri); - if (m == NULL) - continue; - - // Don't restrict smarter monsters as they might find a path - // a dumber monster wouldn't. - if (mons_intel(m) > intel) - continue; - - // Monsters of differing habitats might prefer different routes. - if (mons_primary_habitat(m) != habit) - continue; - - // A flying monster has an advantage over a non-flying one. - if (!flies && mons_flies(m)) - continue; - - // Same for a swimming one, around water. - if (you.water_in_sight > 0 && !amphibious && mons_amphibious(m)) - continue; - - if (m->travel_target == MTRAV_NONE) - m->travel_target = MTRAV_UNREACHABLE; - } -} - -static void _set_no_path_found(monsters *mon) -{ -#ifdef DEBUG_PATHFIND - mpr("No path found!"); -#endif - - mon->travel_target = MTRAV_UNREACHABLE; - // Pass information on to nearby monsters. - _mark_neighbours_target_unreachable(mon); -} - -static bool _target_is_unreachable(monsters *mon) -{ - return (mon->travel_target == MTRAV_UNREACHABLE - || mon->travel_target == MTRAV_KNOWN_UNREACHABLE); -} - -//#define DEBUG_PATHFIND - -// The monster is trying to get to the player (MHITYOU). -// Check whether there's an unobstructed path to the player (in sight!), -// either by using an existing travel_path or calculating a new one. -// Returns true if no further handling necessary, else false. -static bool _try_pathfind(monsters *mon, const dungeon_feature_type can_move, - bool potentially_blocking) -{ - // Just because we can *see* the player, that doesn't mean - // we can actually get there. To find about that, we first - // check for transparent walls. If there are transparent - // walls in the way we'll need pathfinding, no matter what. - // (Though monsters with a los attack don't need to get any - // closer to hurt the player.) - // If no walls are detected, there could still be a river - // or a pool of lava in the way. So we check whether there - // is water or lava in LoS (boolean) and if so, try to find - // a way around it. It's possible that the player can see - // lava but it actually has no influence on the monster's - // movement (because it's lying in the opposite direction) - // but if so, we'll find that out during path finding. - // In another attempt of optimization, don't bother with - // path finding if the monster in question has no trouble - // travelling through water or flying across lava. - // Also, if no path is found (too far away, perhaps) set a - // flag, so we don't directly calculate the whole thing again - // next turn, and even extend that flag to neighbouring - // monsters of similar movement restrictions. - - // Smart monsters that can fire through walls won't use - // pathfinding, and it's also not necessary if the monster - // is already adjacent to you. - if (potentially_blocking && mons_intel(mon) >= I_NORMAL - && !mon->friendly() && mons_has_los_ability(mon->type) - || grid_distance(mon->pos(), you.pos()) == 1) - { - potentially_blocking = false; - } - else - { - // If we don't already know whether there's water or lava - // in LoS of the player, find out now. - if (you.lava_in_sight == -1 || you.water_in_sight == -1) - _check_lava_water_in_sight(); - - // Flying monsters don't see water/lava as obstacle. - // Also don't use pathfinding if the monster can shoot - // across the blocking terrain, and is smart enough to - // realise that. - if (!potentially_blocking && !mons_flies(mon) - && (mons_intel(mon) < I_NORMAL - || mon->friendly() - || (!mons_has_ranged_spell(mon, true) - && !mons_has_ranged_attack(mon)))) - { - const habitat_type habit = mons_primary_habitat(mon); - if (you.lava_in_sight > 0 && habit != HT_LAVA - || you.water_in_sight > 0 && habit != HT_WATER - && can_move != DNGN_DEEP_WATER) - { - potentially_blocking = true; - } - } - } - - if (!potentially_blocking - || can_go_straight(mon->pos(), you.pos(), can_move)) - { - // The player is easily reachable. - // Clear travel path and target, if necessary. - if (mon->travel_target != MTRAV_PATROL - && mon->travel_target != MTRAV_NONE) - { - if (mon->is_travelling()) - mon->travel_path.clear(); - mon->travel_target = MTRAV_NONE; - } - return (false); - } - - // Even if the target has been to "unreachable" (the monster already tried, - // and failed, to find a path) there's a chance of trying again. - if (!_target_is_unreachable(mon) || one_chance_in(12)) - { -#ifdef DEBUG_PATHFIND - mprf("%s: Player out of reach! What now?", - mon->name(DESC_PLAIN).c_str()); -#endif - // If we're already on our way, do nothing. - if (mon->is_travelling() && mon->travel_target == MTRAV_PLAYER) - { - const int len = mon->travel_path.size(); - const coord_def targ = mon->travel_path[len - 1]; - - // Current target still valid? - if (can_go_straight(targ, you.pos(), can_move)) - { - // Did we reach the target? - if (mon->pos() == mon->travel_path[0]) - { - // Get next waypoint. - mon->travel_path.erase( mon->travel_path.begin() ); - - if (!mon->travel_path.empty()) - { - mon->target = mon->travel_path[0]; - return (true); - } - } - else if (can_go_straight(mon->pos(), mon->travel_path[0], - can_move)) - { - mon->target = mon->travel_path[0]; - return (true); - } - } - } - - // Use pathfinding to find a (new) path to the player. - const int dist = grid_distance(mon->pos(), you.pos()); - -#ifdef DEBUG_PATHFIND - mprf("Need to calculate a path... (dist = %d)", dist); -#endif - const int range = mons_tracking_range(mon); - if (range > 0 && dist > range) - { - mon->travel_target = MTRAV_UNREACHABLE; -#ifdef DEBUG_PATHFIND - mprf("Distance too great, don't attempt pathfinding! (%s)", - mon->name(DESC_PLAIN).c_str()); -#endif - return (false); - } - -#ifdef DEBUG_PATHFIND - mprf("Need a path for %s from (%d, %d) to (%d, %d), max. dist = %d", - mon->name(DESC_PLAIN).c_str(), mon->pos(), you.pos(), range); -#endif - monster_pathfind mp; - if (range > 0) - mp.set_range(range); - - if (mp.init_pathfind(mon, you.pos())) - { - mon->travel_path = mp.calc_waypoints(); - if (!mon->travel_path.empty()) - { - // Okay then, we found a path. Let's use it! - mon->target = mon->travel_path[0]; - mon->travel_target = MTRAV_PLAYER; - return (true); - } - else - _set_no_path_found(mon); - } - else - _set_no_path_found(mon); - } - - // We didn't find a path. - return (false); -} - -static bool _is_level_exit(const coord_def& pos) -{ - // All types of stairs. - if (feat_is_stair(grd(pos))) - return (true); - - // Teleportation and shaft traps. - const trap_type tt = get_trap_type(pos); - if (tt == TRAP_TELEPORT || tt == TRAP_SHAFT) - return (true); - - return (false); -} - -// Returns true if a monster left the level. -static bool _pacified_leave_level(monsters *mon, std::vector<level_exit> e, - int e_index) -{ - // If a pacified monster is leaving the level, and has reached an - // exit (whether that exit was its target or not), handle it here. - // Likewise, if a pacified monster is far enough away from the - // player, make it leave the level. - if (_is_level_exit(mon->pos()) - || (e_index != -1 && mon->pos() == e[e_index].target) - || grid_distance(mon->pos(), you.pos()) >= LOS_RADIUS * 4) - { - make_mons_leave_level(mon); - return (true); - } - - return (false); -} - -// Counts deep water twice. -static int _count_water_neighbours(coord_def p) -{ - int water_count = 0; - for (adjacent_iterator ai(p); ai; ++ai) - { - if (grd(*ai) == DNGN_SHALLOW_WATER) - water_count++; - else if (grd(*ai) == DNGN_DEEP_WATER) - water_count += 2; - } - return (water_count); -} - -// Pick the nearest water grid that is surrounded by the most -// water squares within LoS. -static bool _find_siren_water_target(monsters *mon) -{ - ASSERT(mon->type == MONS_SIREN); - - // Moving away could break the entrancement, so don't do this. - if ((mon->pos() - you.pos()).rdist() >= 6) - return (false); - - // Already completely surrounded by deep water. - if (_count_water_neighbours(mon->pos()) >= 16) - return (true); - - if (mon->travel_target == MTRAV_SIREN) - { - coord_def targ_pos(mon->travel_path[mon->travel_path.size() - 1]); -#ifdef DEBUG_PATHFIND - mprf("siren target is (%d, %d), dist = %d", - targ_pos.x, targ_pos.y, (int) (mon->pos() - targ_pos).rdist()); -#endif - if ((mon->pos() - targ_pos).rdist() > 2) - return (true); - } - - int best_water_count = 0; - coord_def best_target; - bool first = true; - - while (true) - { - int best_num = 0; - for (radius_iterator ri(mon->pos(), LOS_RADIUS, true, false); - ri; ++ri) - { - if (!feat_is_water(grd(*ri))) - continue; - - // In the first iteration only count water grids that are - // not closer to the player than to the siren. - if (first && (mon->pos() - *ri).rdist() > (you.pos() - *ri).rdist()) - continue; - - // Counts deep water twice. - const int water_count = _count_water_neighbours(*ri); - if (water_count < best_water_count) - continue; - - if (water_count > best_water_count) - { - best_water_count = water_count; - best_target = *ri; - best_num = 1; - } - else // water_count == best_water_count - { - const int old_dist = (mon->pos() - best_target).rdist(); - const int new_dist = (mon->pos() - *ri).rdist(); - if (new_dist > old_dist) - continue; - - if (new_dist < old_dist) - { - best_target = *ri; - best_num = 1; - } - else if (one_chance_in(++best_num)) - best_target = *ri; - } - } - - if (!first || best_water_count > 0) - break; - - // Else start the second iteration. - first = false; - } - - if (!best_water_count) - return (false); - - // We're already optimally placed. - if (best_target == mon->pos()) - return (true); - - monster_pathfind mp; -#ifdef WIZARD - // Remove old highlighted areas to make place for the new ones. - for (rectangle_iterator ri(1); ri; ++ri) - env.pgrid(*ri) &= ~(FPROP_HIGHLIGHT); -#endif - - if (mp.init_pathfind(mon, best_target)) - { - mon->travel_path = mp.calc_waypoints(); - - if (!mon->travel_path.empty()) - { -#ifdef WIZARD - for (unsigned int i = 0; i < mon->travel_path.size(); i++) - env.pgrid(mon->travel_path[i]) |= FPROP_HIGHLIGHT; -#endif -#ifdef DEBUG_PATHFIND - mprf("Found a path to (%d, %d) with %d surrounding water squares", - best_target.x, best_target.y, best_water_count); -#endif - // Okay then, we found a path. Let's use it! - mon->target = mon->travel_path[0]; - mon->travel_target = MTRAV_SIREN; - return (true); - } - } - - return (false); -} - -static bool _find_wall_target(monsters *mon) -{ - ASSERT(mons_wall_shielded(mon)); - - if (mon->travel_target == MTRAV_WALL) - { - coord_def targ_pos(mon->travel_path[mon->travel_path.size() - 1]); - - // Target grid might have changed since we started, like if the - // player destroys the wall the monster wants to hide in. - if (cell_is_solid(targ_pos) - && monster_habitable_grid(mon, grd(targ_pos))) - { - // Wall is still good. -#ifdef DEBUG_PATHFIND - mprf("%s target is (%d, %d), dist = %d", - mon->name(DESC_PLAIN, true).c_str(), - targ_pos.x, targ_pos.y, (int) (mon->pos() - targ_pos).rdist()); -#endif - return (true); - } - - mon->travel_path.clear(); - mon->travel_target = MTRAV_NONE; - } - - int best_dist = INT_MAX; - bool best_closer_to_player = false; - coord_def best_target; - - for (radius_iterator ri(mon->pos(), LOS_RADIUS, true, false); - ri; ++ri) - { - if (!cell_is_solid(*ri) - || !monster_habitable_grid(mon, grd(*ri))) - { - continue; - } - - int dist = (mon->pos() - *ri).rdist(); - bool closer_to_player = false; - if (dist > (you.pos() - *ri).rdist()) - closer_to_player = true; - - if (dist < best_dist) - { - best_dist = dist; - best_closer_to_player = closer_to_player; - best_target = *ri; - } - else if (best_closer_to_player && !closer_to_player - && dist == best_dist) - { - best_closer_to_player = false; - best_target = *ri; - } - } - - if (best_dist == INT_MAX || !in_bounds(best_target)) - return (false); - - monster_pathfind mp; -#ifdef WIZARD - // Remove old highlighted areas to make place for the new ones. - for (rectangle_iterator ri(1); ri; ++ri) - env.pgrid(*ri) &= ~(FPROP_HIGHLIGHT); -#endif - - if (mp.init_pathfind(mon, best_target)) - { - mon->travel_path = mp.calc_waypoints(); - - if (!mon->travel_path.empty()) - { -#ifdef WIZARD - for (unsigned int i = 0; i < mon->travel_path.size(); i++) - env.pgrid(mon->travel_path[i]) |= FPROP_HIGHLIGHT; -#endif -#ifdef DEBUG_PATHFIND - mprf("Found a path to (%d, %d)", best_target.x, best_target.y); -#endif - // Okay then, we found a path. Let's use it! - mon->target = mon->travel_path[0]; - mon->travel_target = MTRAV_WALL; - return (true); - } - } - return (false); -} - -// Returns true if further handling neeeded. -static bool _handle_monster_travelling(monsters *mon, - const dungeon_feature_type can_move) -{ -#ifdef DEBUG_PATHFIND - mprf("Monster %s reached target (%d, %d)", - mon->name(DESC_PLAIN).c_str(), mon->target.x, mon->target.y); -#endif - - // Hey, we reached our first waypoint! - if (mon->pos() == mon->travel_path[0]) - { -#ifdef DEBUG_PATHFIND - mpr("Arrived at first waypoint."); -#endif - mon->travel_path.erase( mon->travel_path.begin() ); - if (mon->travel_path.empty()) - { -#ifdef DEBUG_PATHFIND - mpr("We reached the end of our path: stop travelling."); -#endif - mon->travel_target = MTRAV_NONE; - return (true); - } - else - { - mon->target = mon->travel_path[0]; -#ifdef DEBUG_PATHFIND - mprf("Next waypoint: (%d, %d)", mon->target.x, mon->target.y); -#endif - return (false); - } - } - - // Can we still see our next waypoint? - if (!can_go_straight(mon->pos(), mon->travel_path[0], can_move)) - { -#ifdef DEBUG_PATHFIND - mpr("Can't see waypoint grid."); -#endif - // Apparently we got sidetracked a bit. - // Check the waypoints vector backwards and pick the first waypoint - // we can see. - - // XXX: Note that this might still not be the best thing to do - // since another path might be even *closer* to our actual target now. - // Not by much, though, since the original path was optimal (A*) and - // the distance between the waypoints is rather small. - - int erase = -1; // Erase how many waypoints? - const int size = mon->travel_path.size(); - for (int i = size - 1; i >= 0; --i) - { - if (can_go_straight(mon->pos(), mon->travel_path[i], can_move)) - { - mon->target = mon->travel_path[i]; - erase = i; - break; - } - } - - if (erase > 0) - { -#ifdef DEBUG_PATHFIND - mprf("Need to erase %d of %d waypoints.", - erase, size); -#endif - // Erase all waypoints that came earlier: - // we don't need them anymore. - while (0 < erase--) - mon->travel_path.erase( mon->travel_path.begin() ); - } - else - { - // We can't reach our old path from our current - // position, so calculate a new path instead. - monster_pathfind mp; - - // The last coordinate in the path vector is our destination. - const int len = mon->travel_path.size(); - if (mp.init_pathfind(mon, mon->travel_path[len-1])) - { - mon->travel_path = mp.calc_waypoints(); - if (!mon->travel_path.empty()) - { - mon->target = mon->travel_path[0]; -#ifdef DEBUG_PATHFIND - mprf("Next waypoint: (%d, %d)", - mon->target.x, mon->target.y); -#endif - } - else - { - mon->travel_target = MTRAV_NONE; - return (true); - } - } - else - { - // Or just forget about the whole thing. - mon->travel_path.clear(); - mon->travel_target = MTRAV_NONE; - return (true); - } - } - } - - // Else, we can see the next waypoint and are making good progress. - // Carry on, then! - return (false); -} - -static bool _choose_random_patrol_target_grid(monsters *mon) -{ - const int intel = mons_intel(mon); - - // Zombies will occasionally just stand around. - // This does not mean that they don't move every second turn. Rather, - // once they reach their chosen target, there's a 50% chance they'll - // just remain there until next turn when this function is called - // again. - if (intel == I_PLANT && coinflip()) - return (true); - - // If there's no chance we'll find the patrol point, quit right away. - if (grid_distance(mon->pos(), mon->patrol_point) > 2 * LOS_RADIUS) - return (false); - - // Can the monster see the patrol point from its current position? - const bool patrol_seen = mon->mon_see_cell(mon->patrol_point, - habitat2grid(mons_primary_habitat(mon))); - - if (intel == I_PLANT && !patrol_seen) - { - // Really stupid monsters won't even try to get back into the - // patrol zone. - return (false); - } - - // While the patrol point is in easy reach, monsters of insect/plant - // intelligence will only use a range of 5 (distance from the patrol point). - // Otherwise, try to get back using the full LOS. - const int rad = (intel >= I_ANIMAL || !patrol_seen) ? LOS_RADIUS : 5; - const bool is_smart = (intel >= I_NORMAL); - - los_def patrol(mon->patrol_point, opacity_monmove(*mon), - circle_def(rad, C_ROUND)); - patrol.update(); - los_def lm(mon->pos(), opacity_monmove(*mon)); - if (is_smart || !patrol_seen) - { - // For stupid monsters, don't bother if the patrol point is in sight. - lm.update(); - } - - int count_grids = 0; - for (radius_iterator ri(mon->patrol_point, LOS_RADIUS, true, false); - ri; ++ri) - { - // Don't bother for the current position. If everything fails, - // we'll stay here anyway. - if (*ri == mon->pos()) - continue; - - if (!mon->can_pass_through_feat(grd(*ri))) - continue; - - // Don't bother moving to squares (currently) occupied by a - // monster. We'll usually be able to find other target squares - // (and if we're not, we couldn't move anyway), and this avoids - // monsters trying to move onto a grid occupied by a plant or - // sleeping monster. - if (monster_at(*ri)) - continue; - - if (patrol_seen) - { - // If the patrol point can be easily (within LOS) reached - // from the current position, it suffices if the target is - // within reach of the patrol point OR the current position: - // we can easily get there. - // Only smart monsters will even attempt to move out of the - // patrol area. - // NOTE: Either of these can take us into a position where the - // target cannot be easily reached (e.g. blocked by a wall) - // and the patrol point is out of sight, too. Such a case - // will be handled below, though it might take a while until - // a monster gets out of a deadlock. (5% chance per turn.) - if (!patrol.see_cell(*ri) && - (!is_smart || !lm.see_cell(*ri))) - { - continue; - } - } - else - { - // If, however, the patrol point is out of reach, we have to - // make sure the new target brings us into reach of it. - // This means that the target must be reachable BOTH from - // the patrol point AND the current position. - if (!patrol.see_cell(*ri) || - !lm.see_cell(*ri)) - { - continue; - } - - // If this fails for all surrounding squares (probably because - // we're too far away), we fall back to heading directly for - // the patrol point. - } - - bool set_target = false; - if (intel == I_PLANT && *ri == mon->patrol_point) - { - // Slightly greater chance to simply head for the centre. - count_grids += 3; - if (x_chance_in_y(3, count_grids)) - set_target = true; - } - else if (one_chance_in(++count_grids)) - set_target = true; - - if (set_target) - mon->target = *ri; - } - - return (count_grids); -}// Returns true if further handling neeeded. -static bool _handle_monster_patrolling(monsters *mon) -{ - if (!_choose_random_patrol_target_grid(mon)) - { - // If we couldn't find a target that is within easy reach - // of the monster and close to the patrol point, depending - // on monster intelligence, do one of the following: - // * set current position as new patrol point - // * forget about patrolling - // * head back to patrol point - - if (mons_intel(mon) == I_PLANT) - { - // Really stupid monsters forget where they're supposed to be. - if (mon->friendly()) - { - // Your ally was told to wait, and wait it will! - // (Though possibly not where you told it to.) - mon->patrol_point = mon->pos(); - } - else - { - // Stop patrolling. - mon->patrol_point.reset(); - mon->travel_target = MTRAV_NONE; - return (true); - } - } - else - { - // It's time to head back! - // Other than for tracking the player, there's currently - // no distinction between smart and stupid monsters when - // it comes to travelling back to the patrol point. This - // is in part due to the flavour of e.g. bees finding - // their way back to the Hive (and patrolling should - // really be restricted to cases like this), and for the - // other part it's not all that important because we - // calculate the path once and then follow it home, and - // the player won't ever see the orderly fashion the - // bees will trudge along. - // What he will see is them swarming back to the Hive - // entrance after some time, and that is what matters. - monster_pathfind mp; - if (mp.init_pathfind(mon, mon->patrol_point)) - { - mon->travel_path = mp.calc_waypoints(); - if (!mon->travel_path.empty()) - { - mon->target = mon->travel_path[0]; - mon->travel_target = MTRAV_PATROL; - } - else - { - // We're so close we don't even need a path. - mon->target = mon->patrol_point; - } - } - else - { - // Stop patrolling. - mon->patrol_point.reset(); - mon->travel_target = MTRAV_NONE; - return (true); - } - } - } - else - { -#ifdef DEBUG_PATHFIND - mprf("Monster %s (pp: %d, %d) is now patrolling to (%d, %d)", - mon->name(DESC_PLAIN).c_str(), - mon->patrol_point.x, mon->patrol_point.y, - mon->target.x, mon->target.y); -#endif - } - - return (false); -} - -void set_random_target(monsters* mon) -{ - mon->target = random_in_bounds(); // If we don't find anything better. - for (int tries = 0; tries < 150; ++tries) - { - coord_def delta = coord_def(random2(13), random2(13)) - coord_def(6, 6); - if (delta.origin()) - continue; - - const coord_def newtarget = delta + mon->pos(); - if (!in_bounds(newtarget)) - continue; - - mon->target = newtarget; - break; - } -} - -static void _check_wander_target(monsters *mon, bool isPacified = false, - dungeon_feature_type can_move = DNGN_UNSEEN) -{ - // default wander behaviour - if (mon->pos() == mon->target - || mons_is_batty(mon) || !isPacified && one_chance_in(20)) - { - bool need_target = true; - - if (!can_move) - { - can_move = (mons_amphibious(mon) ? DNGN_DEEP_WATER - : DNGN_SHALLOW_WATER); - } - - if (mon->is_travelling()) - need_target = _handle_monster_travelling(mon, can_move); - - // If we still need a target because we're not travelling - // (any more), check for patrol routes instead. - if (need_target && mon->is_patrolling()) - need_target = _handle_monster_patrolling(mon); - - // XXX: This is really dumb wander behaviour... instead of - // changing the goal square every turn, better would be to - // have the monster store a direction and have the monster - // head in that direction for a while, then shift the - // direction to the left or right. We're changing this so - // wandering monsters at least appear to have some sort of - // attention span. -- bwr - if (need_target) - set_random_target(mon); - } -} - -static void _find_all_level_exits(std::vector<level_exit> &e) -{ - e.clear(); - - for (rectangle_iterator ri(1); ri; ++ri) - { - if (!in_bounds(*ri)) - continue; - - if (_is_level_exit(*ri)) - e.push_back(level_exit(*ri, false)); - } -} - -static int _mons_find_nearest_level_exit(const monsters *mon, - std::vector<level_exit> &e, - bool reset = false) -{ - if (e.empty() || reset) - _find_all_level_exits(e); - - int retval = -1; - int old_dist = -1; - - for (unsigned int i = 0; i < e.size(); ++i) - { - if (e[i].unreachable) - continue; - - int dist = grid_distance(mon->pos(), e[i].target); - - if (old_dist == -1 || old_dist >= dist) - { - // Ignore teleportation and shaft traps that the monster - // shouldn't know about. - if (!mons_is_native_in_branch(mon) - && grd(e[i].target) == DNGN_UNDISCOVERED_TRAP) - { - continue; - } - - retval = i; - old_dist = dist; - } - } - - return (retval); -} - -static void _set_random_slime_target(monsters* mon) -{ - // Strictly neutral slimes will go for the nearest item. - int item_idx; - coord_def orig_target = mon->target; - - for (radius_iterator ri(mon->pos(), LOS_RADIUS, true, false); ri; ++ri) - { - item_idx = igrd(*ri); - if (item_idx != NON_ITEM) - { - for (stack_iterator si(*ri); si; ++si) - { - item_def& item(*si); - - if (is_item_jelly_edible(item)) - { - mon->target = *ri; - break; - } - } - } - } - - if (mon->target == mon->pos() || mon->target == you.pos()) - set_random_target(mon); -} - static void _guess_invis_foe_pos(monsters *mon, bool strict = true) { const actor* foe = mon->get_foe(); @@ -1363,12 +410,12 @@ void handle_behaviour(monsters *mon) // The foe is the player. if (mon->type == MONS_SIREN && you.beheld_by(mon) - && _find_siren_water_target(mon)) + && find_siren_water_target(mon)) { break; } - if (_try_pathfind(mon, can_move, trans_wall_block)) + if (try_pathfind(mon, can_move, trans_wall_block)) break; // Whew. If we arrived here, path finding didn't yield anything @@ -1417,10 +464,10 @@ void handle_behaviour(monsters *mon) new_foe = MHITNOT; mon->travel_path.clear(); - e_index = _mons_find_nearest_level_exit(mon, e); + e_index = mons_find_nearest_level_exit(mon, e); if (e_index == -1 || one_chance_in(20)) - e_index = _mons_find_nearest_level_exit(mon, e, true); + e_index = mons_find_nearest_level_exit(mon, e, true); if (e_index != -1) { @@ -1438,14 +485,14 @@ void handle_behaviour(monsters *mon) } } - if (_pacified_leave_level(mon, e, e_index)) + if (pacified_leave_level(mon, e, e_index)) return; } if (mon->strict_neutral() && mons_is_slime(mon) && you.religion == GOD_JIYVA) { - _set_random_slime_target(mon); + set_random_slime_target(mon); } // Is our foe in LOS? @@ -1458,7 +505,7 @@ void handle_behaviour(monsters *mon) break; } - _check_wander_target(mon, isPacified, can_move); + check_wander_target(mon, isPacified, can_move); // During their wanderings, monsters will eventually relax // their guard (stupid ones will do so faster, smart @@ -1500,7 +547,7 @@ void handle_behaviour(monsters *mon) if (mon->foe == MHITYOU) mon->target = you.pos(); } - else if (mons_wall_shielded(mon) && _find_wall_target(mon)) + else if (mons_wall_shielded(mon) && find_wall_target(mon)) ; // Wall target found. else if (proxFoe) { @@ -1772,7 +819,7 @@ void behaviour_event(monsters *mon, mon_event_type event, int src, (mons_amphibious(mon)) ? DNGN_DEEP_WATER : DNGN_SHALLOW_WATER; - _try_pathfind(mon, can_move, true); + try_pathfind(mon, can_move, true); } } break; diff --git a/crawl-ref/source/mon-movetarget.cc b/crawl-ref/source/mon-movetarget.cc new file mode 100644 index 0000000000..8bdec65fb4 --- /dev/null +++ b/crawl-ref/source/mon-movetarget.cc @@ -0,0 +1,972 @@ +#include "AppHdr.h" + +#include "mon-movetarget.h" + +#include "coord.h" +#include "coordit.h" +#include "env.h" +#include "fprop.h" +#include "mon-behv.h" +#include "mon-pathfind.h" +#include "mon-place.h" +#include "mon-stuff.h" +#include "monster.h" +#include "player.h" +#include "random.h" +#include "stuff.h" +#include "terrain.h" +#include "traps.h" + +// Check all grids in LoS and mark lava and/or water as seen if the +// appropriate grids are encountered, so we later only need to do the +// visibility check for monsters that can't pass a feature potentially in +// the way. We don't care about shallow water as most monsters can safely +// cross that, and fire elementals alone aren't really worth the extra +// hassle. :) +static void _check_lava_water_in_sight() +{ + you.lava_in_sight = you.water_in_sight = 0; + for (radius_iterator ri(you.pos(), LOS_RADIUS); ri; ++ri) + { + const dungeon_feature_type feat = grd(*ri); + if (feat == DNGN_LAVA) + { + you.lava_in_sight = 1; + if (you.water_in_sight > 0) + break; + } + else if (feat == DNGN_DEEP_WATER) + { + you.water_in_sight = 1; + if (you.lava_in_sight > 0) + break; + } + } +} + +// If a monster can see but not directly reach the target, and then fails to +// find a path to get there, mark all surrounding (in a radius of 2) monsters +// of the same (or greater) movement restrictions as also being unable to +// find a path, so we won't need to calculate again. +// Should there be a direct path to the target for a monster thus marked, it +// will still be able to come nearer (and the mark will then be cleared). +static void _mark_neighbours_target_unreachable(monsters *mon) +{ + // Highly intelligent monsters are perfectly capable of pathfinding + // and don't need their neighbour's advice. + const mon_intel_type intel = mons_intel(mon); + if (intel > I_NORMAL) + return; + + const bool flies = mons_flies(mon); + const bool amphibious = mons_amphibious(mon); + const habitat_type habit = mons_primary_habitat(mon); + + for (radius_iterator ri(mon->pos(), 2, true, false); ri; ++ri) + { + if (*ri == mon->pos()) + continue; + + // Don't alert monsters out of sight (e.g. on the other side of + // a wall). + if (!mon->see_cell(*ri)) + continue; + + monsters* const m = monster_at(*ri); + if (m == NULL) + continue; + + // Don't restrict smarter monsters as they might find a path + // a dumber monster wouldn't. + if (mons_intel(m) > intel) + continue; + + // Monsters of differing habitats might prefer different routes. + if (mons_primary_habitat(m) != habit) + continue; + + // A flying monster has an advantage over a non-flying one. + if (!flies && mons_flies(m)) + continue; + + // Same for a swimming one, around water. + if (you.water_in_sight > 0 && !amphibious && mons_amphibious(m)) + continue; + + if (m->travel_target == MTRAV_NONE) + m->travel_target = MTRAV_UNREACHABLE; + } +} + +static void _set_no_path_found(monsters *mon) +{ +#ifdef DEBUG_PATHFIND + mpr("No path found!"); +#endif + + mon->travel_target = MTRAV_UNREACHABLE; + // Pass information on to nearby monsters. + _mark_neighbours_target_unreachable(mon); +} + +static bool _target_is_unreachable(monsters *mon) +{ + return (mon->travel_target == MTRAV_UNREACHABLE + || mon->travel_target == MTRAV_KNOWN_UNREACHABLE); +} + +//#define DEBUG_PATHFIND + +// The monster is trying to get to the player (MHITYOU). +// Check whether there's an unobstructed path to the player (in sight!), +// either by using an existing travel_path or calculating a new one. +// Returns true if no further handling necessary, else false. +bool try_pathfind(monsters *mon, const dungeon_feature_type can_move, + bool potentially_blocking) +{ + // Just because we can *see* the player, that doesn't mean + // we can actually get there. To find about that, we first + // check for transparent walls. If there are transparent + // walls in the way we'll need pathfinding, no matter what. + // (Though monsters with a los attack don't need to get any + // closer to hurt the player.) + // If no walls are detected, there could still be a river + // or a pool of lava in the way. So we check whether there + // is water or lava in LoS (boolean) and if so, try to find + // a way around it. It's possible that the player can see + // lava but it actually has no influence on the monster's + // movement (because it's lying in the opposite direction) + // but if so, we'll find that out during path finding. + // In another attempt of optimization, don't bother with + // path finding if the monster in question has no trouble + // travelling through water or flying across lava. + // Also, if no path is found (too far away, perhaps) set a + // flag, so we don't directly calculate the whole thing again + // next turn, and even extend that flag to neighbouring + // monsters of similar movement restrictions. + + // Smart monsters that can fire through walls won't use + // pathfinding, and it's also not necessary if the monster + // is already adjacent to you. + if (potentially_blocking && mons_intel(mon) >= I_NORMAL + && !mon->friendly() && mons_has_los_ability(mon->type) + || grid_distance(mon->pos(), you.pos()) == 1) + { + potentially_blocking = false; + } + else + { + // If we don't already know whether there's water or lava + // in LoS of the player, find out now. + if (you.lava_in_sight == -1 || you.water_in_sight == -1) + _check_lava_water_in_sight(); + + // Flying monsters don't see water/lava as obstacle. + // Also don't use pathfinding if the monster can shoot + // across the blocking terrain, and is smart enough to + // realise that. + if (!potentially_blocking && !mons_flies(mon) + && (mons_intel(mon) < I_NORMAL + || mon->friendly() + || (!mons_has_ranged_spell(mon, true) + && !mons_has_ranged_attack(mon)))) + { + const habitat_type habit = mons_primary_habitat(mon); + if (you.lava_in_sight > 0 && habit != HT_LAVA + || you.water_in_sight > 0 && habit != HT_WATER + && can_move != DNGN_DEEP_WATER) + { + potentially_blocking = true; + } + } + } + + if (!potentially_blocking + || can_go_straight(mon->pos(), you.pos(), can_move)) + { + // The player is easily reachable. + // Clear travel path and target, if necessary. + if (mon->travel_target != MTRAV_PATROL + && mon->travel_target != MTRAV_NONE) + { + if (mon->is_travelling()) + mon->travel_path.clear(); + mon->travel_target = MTRAV_NONE; + } + return (false); + } + + // Even if the target has been to "unreachable" (the monster already tried, + // and failed, to find a path) there's a chance of trying again. + if (!_target_is_unreachable(mon) || one_chance_in(12)) + { +#ifdef DEBUG_PATHFIND + mprf("%s: Player out of reach! What now?", + mon->name(DESC_PLAIN).c_str()); +#endif + // If we're already on our way, do nothing. + if (mon->is_travelling() && mon->travel_target == MTRAV_PLAYER) + { + const int len = mon->travel_path.size(); + const coord_def targ = mon->travel_path[len - 1]; + + // Current target still valid? + if (can_go_straight(targ, you.pos(), can_move)) + { + // Did we reach the target? + if (mon->pos() == mon->travel_path[0]) + { + // Get next waypoint. + mon->travel_path.erase( mon->travel_path.begin() ); + + if (!mon->travel_path.empty()) + { + mon->target = mon->travel_path[0]; + return (true); + } + } + else if (can_go_straight(mon->pos(), mon->travel_path[0], + can_move)) + { + mon->target = mon->travel_path[0]; + return (true); + } + } + } + + // Use pathfinding to find a (new) path to the player. + const int dist = grid_distance(mon->pos(), you.pos()); + +#ifdef DEBUG_PATHFIND + mprf("Need to calculate a path... (dist = %d)", dist); +#endif + const int range = mons_tracking_range(mon); + if (range > 0 && dist > range) + { + mon->travel_target = MTRAV_UNREACHABLE; +#ifdef DEBUG_PATHFIND + mprf("Distance too great, don't attempt pathfinding! (%s)", + mon->name(DESC_PLAIN).c_str()); +#endif + return (false); + } + +#ifdef DEBUG_PATHFIND + mprf("Need a path for %s from (%d, %d) to (%d, %d), max. dist = %d", + mon->name(DESC_PLAIN).c_str(), mon->pos(), you.pos(), range); +#endif + monster_pathfind mp; + if (range > 0) + mp.set_range(range); + + if (mp.init_pathfind(mon, you.pos())) + { + mon->travel_path = mp.calc_waypoints(); + if (!mon->travel_path.empty()) + { + // Okay then, we found a path. Let's use it! + mon->target = mon->travel_path[0]; + mon->travel_target = MTRAV_PLAYER; + return (true); + } + else + _set_no_path_found(mon); + } + else + _set_no_path_found(mon); + } + + // We didn't find a path. + return (false); +} + +static bool _is_level_exit(const coord_def& pos) +{ + // All types of stairs. + if (feat_is_stair(grd(pos))) + return (true); + + // Teleportation and shaft traps. + const trap_type tt = get_trap_type(pos); + if (tt == TRAP_TELEPORT || tt == TRAP_SHAFT) + return (true); + + return (false); +} + +// Returns true if a monster left the level. +bool pacified_leave_level(monsters *mon, std::vector<level_exit> e, + int e_index) +{ + // If a pacified monster is leaving the level, and has reached an + // exit (whether that exit was its target or not), handle it here. + // Likewise, if a pacified monster is far enough away from the + // player, make it leave the level. + if (_is_level_exit(mon->pos()) + || (e_index != -1 && mon->pos() == e[e_index].target) + || grid_distance(mon->pos(), you.pos()) >= LOS_RADIUS * 4) + { + make_mons_leave_level(mon); + return (true); + } + + return (false); +} + +// Counts deep water twice. +static int _count_water_neighbours(coord_def p) +{ + int water_count = 0; + for (adjacent_iterator ai(p); ai; ++ai) + { + if (grd(*ai) == DNGN_SHALLOW_WATER) + water_count++; + else if (grd(*ai) == DNGN_DEEP_WATER) + water_count += 2; + } + return (water_count); +} + +// Pick the nearest water grid that is surrounded by the most +// water squares within LoS. +bool find_siren_water_target(monsters *mon) +{ + ASSERT(mon->type == MONS_SIREN); + + // Moving away could break the entrancement, so don't do this. + if ((mon->pos() - you.pos()).rdist() >= 6) + return (false); + + // Already completely surrounded by deep water. + if (_count_water_neighbours(mon->pos()) >= 16) + return (true); + + if (mon->travel_target == MTRAV_SIREN) + { + coord_def targ_pos(mon->travel_path[mon->travel_path.size() - 1]); +#ifdef DEBUG_PATHFIND + mprf("siren target is (%d, %d), dist = %d", + targ_pos.x, targ_pos.y, (int) (mon->pos() - targ_pos).rdist()); +#endif + if ((mon->pos() - targ_pos).rdist() > 2) + return (true); + } + + int best_water_count = 0; + coord_def best_target; + bool first = true; + + while (true) + { + int best_num = 0; + for (radius_iterator ri(mon->pos(), LOS_RADIUS, true, false); + ri; ++ri) + { + if (!feat_is_water(grd(*ri))) + continue; + + // In the first iteration only count water grids that are + // not closer to the player than to the siren. + if (first && (mon->pos() - *ri).rdist() > (you.pos() - *ri).rdist()) + continue; + + // Counts deep water twice. + const int water_count = _count_water_neighbours(*ri); + if (water_count < best_water_count) + continue; + + if (water_count > best_water_count) + { + best_water_count = water_count; + best_target = *ri; + best_num = 1; + } + else // water_count == best_water_count + { + const int old_dist = (mon->pos() - best_target).rdist(); + const int new_dist = (mon->pos() - *ri).rdist(); + if (new_dist > old_dist) + continue; + + if (new_dist < old_dist) + { + best_target = *ri; + best_num = 1; + } + else if (one_chance_in(++best_num)) + best_target = *ri; + } + } + + if (!first || best_water_count > 0) + break; + + // Else start the second iteration. + first = false; + } + + if (!best_water_count) + return (false); + + // We're already optimally placed. + if (best_target == mon->pos()) + return (true); + + monster_pathfind mp; +#ifdef WIZARD + // Remove old highlighted areas to make place for the new ones. + for (rectangle_iterator ri(1); ri; ++ri) + env.pgrid(*ri) &= ~(FPROP_HIGHLIGHT); +#endif + + if (mp.init_pathfind(mon, best_target)) + { + mon->travel_path = mp.calc_waypoints(); + + if (!mon->travel_path.empty()) + { +#ifdef WIZARD + for (unsigned int i = 0; i < mon->travel_path.size(); i++) + env.pgrid(mon->travel_path[i]) |= FPROP_HIGHLIGHT; +#endif +#ifdef DEBUG_PATHFIND + mprf("Found a path to (%d, %d) with %d surrounding water squares", + best_target.x, best_target.y, best_water_count); +#endif + // Okay then, we found a path. Let's use it! + mon->target = mon->travel_path[0]; + mon->travel_target = MTRAV_SIREN; + return (true); + } + } + + return (false); +} + +bool find_wall_target(monsters *mon) +{ + ASSERT(mons_wall_shielded(mon)); + + if (mon->travel_target == MTRAV_WALL) + { + coord_def targ_pos(mon->travel_path[mon->travel_path.size() - 1]); + + // Target grid might have changed since we started, like if the + // player destroys the wall the monster wants to hide in. + if (cell_is_solid(targ_pos) + && monster_habitable_grid(mon, grd(targ_pos))) + { + // Wall is still good. +#ifdef DEBUG_PATHFIND + mprf("%s target is (%d, %d), dist = %d", + mon->name(DESC_PLAIN, true).c_str(), + targ_pos.x, targ_pos.y, (int) (mon->pos() - targ_pos).rdist()); +#endif + return (true); + } + + mon->travel_path.clear(); + mon->travel_target = MTRAV_NONE; + } + + int best_dist = INT_MAX; + bool best_closer_to_player = false; + coord_def best_target; + + for (radius_iterator ri(mon->pos(), LOS_RADIUS, true, false); + ri; ++ri) + { + if (!cell_is_solid(*ri) + || !monster_habitable_grid(mon, grd(*ri))) + { + continue; + } + + int dist = (mon->pos() - *ri).rdist(); + bool closer_to_player = false; + if (dist > (you.pos() - *ri).rdist()) + closer_to_player = true; + + if (dist < best_dist) + { + best_dist = dist; + best_closer_to_player = closer_to_player; + best_target = *ri; + } + else if (best_closer_to_player && !closer_to_player + && dist == best_dist) + { + best_closer_to_player = false; + best_target = *ri; + } + } + + if (best_dist == INT_MAX || !in_bounds(best_target)) + return (false); + + monster_pathfind mp; +#ifdef WIZARD + // Remove old highlighted areas to make place for the new ones. + for (rectangle_iterator ri(1); ri; ++ri) + env.pgrid(*ri) &= ~(FPROP_HIGHLIGHT); +#endif + + if (mp.init_pathfind(mon, best_target)) + { + mon->travel_path = mp.calc_waypoints(); + + if (!mon->travel_path.empty()) + { +#ifdef WIZARD + for (unsigned int i = 0; i < mon->travel_path.size(); i++) + env.pgrid(mon->travel_path[i]) |= FPROP_HIGHLIGHT; +#endif +#ifdef DEBUG_PATHFIND + mprf("Found a path to (%d, %d)", best_target.x, best_target.y); +#endif + // Okay then, we found a path. Let's use it! + mon->target = mon->travel_path[0]; + mon->travel_target = MTRAV_WALL; + return (true); + } + } + return (false); +} + +// Returns true if further handling neeeded. +static bool _handle_monster_travelling(monsters *mon, + const dungeon_feature_type can_move) +{ +#ifdef DEBUG_PATHFIND + mprf("Monster %s reached target (%d, %d)", + mon->name(DESC_PLAIN).c_str(), mon->target.x, mon->target.y); +#endif + + // Hey, we reached our first waypoint! + if (mon->pos() == mon->travel_path[0]) + { +#ifdef DEBUG_PATHFIND + mpr("Arrived at first waypoint."); +#endif + mon->travel_path.erase( mon->travel_path.begin() ); + if (mon->travel_path.empty()) + { +#ifdef DEBUG_PATHFIND + mpr("We reached the end of our path: stop travelling."); +#endif + mon->travel_target = MTRAV_NONE; + return (true); + } + else + { + mon->target = mon->travel_path[0]; +#ifdef DEBUG_PATHFIND + mprf("Next waypoint: (%d, %d)", mon->target.x, mon->target.y); +#endif + return (false); + } + } + + // Can we still see our next waypoint? + if (!can_go_straight(mon->pos(), mon->travel_path[0], can_move)) + { +#ifdef DEBUG_PATHFIND + mpr("Can't see waypoint grid."); +#endif + // Apparently we got sidetracked a bit. + // Check the waypoints vector backwards and pick the first waypoint + // we can see. + + // XXX: Note that this might still not be the best thing to do + // since another path might be even *closer* to our actual target now. + // Not by much, though, since the original path was optimal (A*) and + // the distance between the waypoints is rather small. + + int erase = -1; // Erase how many waypoints? + const int size = mon->travel_path.size(); + for (int i = size - 1; i >= 0; --i) + { + if (can_go_straight(mon->pos(), mon->travel_path[i], can_move)) + { + mon->target = mon->travel_path[i]; + erase = i; + break; + } + } + + if (erase > 0) + { +#ifdef DEBUG_PATHFIND + mprf("Need to erase %d of %d waypoints.", + erase, size); +#endif + // Erase all waypoints that came earlier: + // we don't need them anymore. + while (0 < erase--) + mon->travel_path.erase( mon->travel_path.begin() ); + } + else + { + // We can't reach our old path from our current + // position, so calculate a new path instead. + monster_pathfind mp; + + // The last coordinate in the path vector is our destination. + const int len = mon->travel_path.size(); + if (mp.init_pathfind(mon, mon->travel_path[len-1])) + { + mon->travel_path = mp.calc_waypoints(); + if (!mon->travel_path.empty()) + { + mon->target = mon->travel_path[0]; +#ifdef DEBUG_PATHFIND + mprf("Next waypoint: (%d, %d)", + mon->target.x, mon->target.y); +#endif + } + else + { + mon->travel_target = MTRAV_NONE; + return (true); + } + } + else + { + // Or just forget about the whole thing. + mon->travel_path.clear(); + mon->travel_target = MTRAV_NONE; + return (true); + } + } + } + + // Else, we can see the next waypoint and are making good progress. + // Carry on, then! + return (false); +} + +static bool _choose_random_patrol_target_grid(monsters *mon) +{ + const int intel = mons_intel(mon); + + // Zombies will occasionally just stand around. + // This does not mean that they don't move every second turn. Rather, + // once they reach their chosen target, there's a 50% chance they'll + // just remain there until next turn when this function is called + // again. + if (intel == I_PLANT && coinflip()) + return (true); + + // If there's no chance we'll find the patrol point, quit right away. + if (grid_distance(mon->pos(), mon->patrol_point) > 2 * LOS_RADIUS) + return (false); + + // Can the monster see the patrol point from its current position? + const bool patrol_seen = mon->mon_see_cell(mon->patrol_point, + habitat2grid(mons_primary_habitat(mon))); + + if (intel == I_PLANT && !patrol_seen) + { + // Really stupid monsters won't even try to get back into the + // patrol zone. + return (false); + } + + // While the patrol point is in easy reach, monsters of insect/plant + // intelligence will only use a range of 5 (distance from the patrol point). + // Otherwise, try to get back using the full LOS. + const int rad = (intel >= I_ANIMAL || !patrol_seen) ? LOS_RADIUS : 5; + const bool is_smart = (intel >= I_NORMAL); + + los_def patrol(mon->patrol_point, opacity_monmove(*mon), + circle_def(rad, C_ROUND)); + patrol.update(); + los_def lm(mon->pos(), opacity_monmove(*mon)); + if (is_smart || !patrol_seen) + { + // For stupid monsters, don't bother if the patrol point is in sight. + lm.update(); + } + + int count_grids = 0; + for (radius_iterator ri(mon->patrol_point, LOS_RADIUS, true, false); + ri; ++ri) + { + // Don't bother for the current position. If everything fails, + // we'll stay here anyway. + if (*ri == mon->pos()) + continue; + + if (!mon->can_pass_through_feat(grd(*ri))) + continue; + + // Don't bother moving to squares (currently) occupied by a + // monster. We'll usually be able to find other target squares + // (and if we're not, we couldn't move anyway), and this avoids + // monsters trying to move onto a grid occupied by a plant or + // sleeping monster. + if (monster_at(*ri)) + continue; + + if (patrol_seen) + { + // If the patrol point can be easily (within LOS) reached + // from the current position, it suffices if the target is + // within reach of the patrol point OR the current position: + // we can easily get there. + // Only smart monsters will even attempt to move out of the + // patrol area. + // NOTE: Either of these can take us into a position where the + // target cannot be easily reached (e.g. blocked by a wall) + // and the patrol point is out of sight, too. Such a case + // will be handled below, though it might take a while until + // a monster gets out of a deadlock. (5% chance per turn.) + if (!patrol.see_cell(*ri) && + (!is_smart || !lm.see_cell(*ri))) + { + continue; + } + } + else + { + // If, however, the patrol point is out of reach, we have to + // make sure the new target brings us into reach of it. + // This means that the target must be reachable BOTH from + // the patrol point AND the current position. + if (!patrol.see_cell(*ri) || + !lm.see_cell(*ri)) + { + continue; + } + + // If this fails for all surrounding squares (probably because + // we're too far away), we fall back to heading directly for + // the patrol point. + } + + bool set_target = false; + if (intel == I_PLANT && *ri == mon->patrol_point) + { + // Slightly greater chance to simply head for the centre. + count_grids += 3; + if (x_chance_in_y(3, count_grids)) + set_target = true; + } + else if (one_chance_in(++count_grids)) + set_target = true; + + if (set_target) + mon->target = *ri; + } + + return (count_grids); +}// Returns true if further handling neeeded. +static bool _handle_monster_patrolling(monsters *mon) +{ + if (!_choose_random_patrol_target_grid(mon)) + { + // If we couldn't find a target that is within easy reach + // of the monster and close to the patrol point, depending + // on monster intelligence, do one of the following: + // * set current position as new patrol point + // * forget about patrolling + // * head back to patrol point + + if (mons_intel(mon) == I_PLANT) + { + // Really stupid monsters forget where they're supposed to be. + if (mon->friendly()) + { + // Your ally was told to wait, and wait it will! + // (Though possibly not where you told it to.) + mon->patrol_point = mon->pos(); + } + else + { + // Stop patrolling. + mon->patrol_point.reset(); + mon->travel_target = MTRAV_NONE; + return (true); + } + } + else + { + // It's time to head back! + // Other than for tracking the player, there's currently + // no distinction between smart and stupid monsters when + // it comes to travelling back to the patrol point. This + // is in part due to the flavour of e.g. bees finding + // their way back to the Hive (and patrolling should + // really be restricted to cases like this), and for the + // other part it's not all that important because we + // calculate the path once and then follow it home, and + // the player won't ever see the orderly fashion the + // bees will trudge along. + // What he will see is them swarming back to the Hive + // entrance after some time, and that is what matters. + monster_pathfind mp; + if (mp.init_pathfind(mon, mon->patrol_point)) + { + mon->travel_path = mp.calc_waypoints(); + if (!mon->travel_path.empty()) + { + mon->target = mon->travel_path[0]; + mon->travel_target = MTRAV_PATROL; + } + else + { + // We're so close we don't even need a path. + mon->target = mon->patrol_point; + } + } + else + { + // Stop patrolling. + mon->patrol_point.reset(); + mon->travel_target = MTRAV_NONE; + return (true); + } + } + } + else + { +#ifdef DEBUG_PATHFIND + mprf("Monster %s (pp: %d, %d) is now patrolling to (%d, %d)", + mon->name(DESC_PLAIN).c_str(), + mon->patrol_point.x, mon->patrol_point.y, + mon->target.x, mon->target.y); +#endif + } + + return (false); +} + +void set_random_target(monsters* mon) +{ + mon->target = random_in_bounds(); // If we don't find anything better. + for (int tries = 0; tries < 150; ++tries) + { + coord_def delta = coord_def(random2(13), random2(13)) - coord_def(6, 6); + if (delta.origin()) + continue; + + const coord_def newtarget = delta + mon->pos(); + if (!in_bounds(newtarget)) + continue; + + mon->target = newtarget; + break; + } +} + +void check_wander_target(monsters *mon, bool isPacified, + dungeon_feature_type can_move) +{ + // default wander behaviour + if (mon->pos() == mon->target + || mons_is_batty(mon) || !isPacified && one_chance_in(20)) + { + bool need_target = true; + + if (!can_move) + { + can_move = (mons_amphibious(mon) ? DNGN_DEEP_WATER + : DNGN_SHALLOW_WATER); + } + + if (mon->is_travelling()) + need_target = _handle_monster_travelling(mon, can_move); + + // If we still need a target because we're not travelling + // (any more), check for patrol routes instead. + if (need_target && mon->is_patrolling()) + need_target = _handle_monster_patrolling(mon); + + // XXX: This is really dumb wander behaviour... instead of + // changing the goal square every turn, better would be to + // have the monster store a direction and have the monster + // head in that direction for a while, then shift the + // direction to the left or right. We're changing this so + // wandering monsters at least appear to have some sort of + // attention span. -- bwr + if (need_target) + set_random_target(mon); + } +} + +static void _find_all_level_exits(std::vector<level_exit> &e) +{ + e.clear(); + + for (rectangle_iterator ri(1); ri; ++ri) + { + if (!in_bounds(*ri)) + continue; + + if (_is_level_exit(*ri)) + e.push_back(level_exit(*ri, false)); + } +} + +int mons_find_nearest_level_exit(const monsters *mon, + std::vector<level_exit> &e, + bool reset) +{ + if (e.empty() || reset) + _find_all_level_exits(e); + + int retval = -1; + int old_dist = -1; + + for (unsigned int i = 0; i < e.size(); ++i) + { + if (e[i].unreachable) + continue; + + int dist = grid_distance(mon->pos(), e[i].target); + + if (old_dist == -1 || old_dist >= dist) + { + // Ignore teleportation and shaft traps that the monster + // shouldn't know about. + if (!mons_is_native_in_branch(mon) + && grd(e[i].target) == DNGN_UNDISCOVERED_TRAP) + { + continue; + } + + retval = i; + old_dist = dist; + } + } + + return (retval); +} + +void set_random_slime_target(monsters* mon) +{ + // Strictly neutral slimes will go for the nearest item. + int item_idx; + coord_def orig_target = mon->target; + + for (radius_iterator ri(mon->pos(), LOS_RADIUS, true, false); ri; ++ri) + { + item_idx = igrd(*ri); + if (item_idx != NON_ITEM) + { + for (stack_iterator si(*ri); si; ++si) + { + item_def& item(*si); + + if (is_item_jelly_edible(item)) + { + mon->target = *ri; + break; + } + } + } + } + + if (mon->target == mon->pos() || mon->target == you.pos()) + set_random_target(mon); +} diff --git a/crawl-ref/source/mon-movetarget.h b/crawl-ref/source/mon-movetarget.h new file mode 100644 index 0000000000..2fdbe99559 --- /dev/null +++ b/crawl-ref/source/mon-movetarget.h @@ -0,0 +1,19 @@ +#ifndef MON_MOVE_TARGET_H +#define MON_MOVE_TARGET_H + +struct level_exit; + +bool try_pathfind(monsters *mon, const dungeon_feature_type can_move, + bool potentially_blocking); +bool find_wall_target(monsters *mon); +void check_wander_target(monsters *mon, bool isPacified = false, + dungeon_feature_type can_move = DNGN_UNSEEN); +int mons_find_nearest_level_exit(const monsters *mon, + std::vector<level_exit> &e, + bool reset = false); +void set_random_slime_target(monsters* mon); +bool find_siren_water_target(monsters *mon); +bool pacified_leave_level(monsters *mon, std::vector<level_exit> e, + int e_index); + +#endif |