diff options
| -rw-r--r-- | crawl-ref/source/acr.cc | 12 | ||||
| -rw-r--r-- | crawl-ref/source/command.cc | 5 | ||||
| -rw-r--r-- | crawl-ref/source/debug.cc | 34 | ||||
| -rw-r--r-- | crawl-ref/source/debug.h | 1 | ||||
| -rw-r--r-- | crawl-ref/source/directn.cc | 37 | ||||
| -rw-r--r-- | crawl-ref/source/enum.h | 1 | ||||
| -rw-r--r-- | crawl-ref/source/items.cc | 2 | ||||
| -rw-r--r-- | crawl-ref/source/mon-util.cc | 4 | ||||
| -rw-r--r-- | crawl-ref/source/monplace.cc | 246 | ||||
| -rw-r--r-- | crawl-ref/source/monplace.h | 39 | ||||
| -rw-r--r-- | crawl-ref/source/store.h | 2 | ||||
| -rw-r--r-- | crawl-ref/source/traps.cc | 12 |
12 files changed, 361 insertions, 34 deletions
diff --git a/crawl-ref/source/acr.cc b/crawl-ref/source/acr.cc index 6a93a94b73..969fff663f 100644 --- a/crawl-ref/source/acr.cc +++ b/crawl-ref/source/acr.cc @@ -537,7 +537,7 @@ static void _handle_wizard_command( void ) break; case 'v': - // this command isn't very exciting... feel free to replace + // This command isn't very exciting... feel free to replace. i = prompt_invent_item( "Value of which item?", MT_INVLIST, -1 ); if (i == PROMPT_ABORT || !is_random_artefact( you.inv[i] )) { @@ -551,8 +551,8 @@ static void _handle_wizard_command( void ) break; case '+': - i = prompt_invent_item( - "Make an artefact out of which item?", MT_INVLIST, -1 ); + i = prompt_invent_item( "Make an artefact out of which item?", + MT_INVLIST, -1 ); if (i == PROMPT_ABORT) { canned_msg( MSG_OK ); @@ -565,7 +565,7 @@ static void _handle_wizard_command( void ) break; } - // set j == equipment slot of chosen item, remove old randart benefits + // Set j == equipment slot of chosen item, remove old randart benefits. for (j = 0; j < NUM_EQUIP; j++) { if (you.equip[j] == i) @@ -590,7 +590,7 @@ static void _handle_wizard_command( void ) break; case '|': - // create all unrandarts + // Create all unrandarts. for (tmp = 1; tmp < NO_UNRANDARTS; tmp++) { int islot = get_item_slot(); @@ -609,7 +609,7 @@ static void _handle_wizard_command( void ) move_item_to_grid( &islot, you.x_pos, you.y_pos ); } - // create all fixed artefacts + // Create all fixed artefacts. for (tmp = SPWPN_START_FIXEDARTS; tmp < SPWPN_START_NOGEN_FIXEDARTS; tmp++) { diff --git a/crawl-ref/source/command.cc b/crawl-ref/source/command.cc index 5f4b35fef0..eb04dafcd5 100644 --- a/crawl-ref/source/command.cc +++ b/crawl-ref/source/command.cc @@ -305,10 +305,10 @@ static void _adjust_spells(void) return; } - // print out targeted spell: + // Print targeted spell. mprf( "%c - %s", keyin, spell_title( spell ) ); - // Select target slot + // Select target slot. keyin = 0; while ( !isalpha(keyin) ) { @@ -662,6 +662,7 @@ static const char *targeting_help_1 = "<w>F</w>: cycle monster friendly/good neutral/neutral/hostile\n" "<w>P</w>: apply divine blessing to monster\n" "<w>m</w>: move monster or player\n" + "<w>w</w>: calculate shortest path to any point on the map\n" #endif ; diff --git a/crawl-ref/source/debug.cc b/crawl-ref/source/debug.cc index 5dd91441a7..7337faa475 100644 --- a/crawl-ref/source/debug.cc +++ b/crawl-ref/source/debug.cc @@ -3989,7 +3989,6 @@ void wizard_give_monster_item(monsters *mon) #endif #ifdef WIZARD - static void _move_player(int x, int y) { // no longer held in net @@ -4064,6 +4063,39 @@ void wizard_move_player_or_monster(int x, int y) already_moving = false; } + +void debug_pathfind(int mid) +{ + if (mid == NON_MONSTER) + return; + + mpr("Choose a destination!"); +#ifdef USE_TILE + more(); +#endif + coord_def dest; + show_map(dest, true); + redraw_screen(); + + monsters &mon = menv[mid]; + mprf("Attempting to calculate a path from (%d, %d) to (%d, %d)...", + mon.x, mon.y, dest.x, dest.y); + monster_pathfind mp; + bool success = mp.start_pathfind(&mon, dest, true); + if (success) + { + std::vector<coord_def> path = mp.backtrack(); + std::string path_str = ""; + mpr("Here's the shortest path: "); + for (unsigned int i = 0; i < path.size(); i++) + { + snprintf(info, INFO_SIZE, "(%d, %d) ", path[i].x, path[i].y); + path_str += info; + } + + mpr(path_str.c_str()); + } +} #endif #ifdef DEBUG_DIAGNOSTICS diff --git a/crawl-ref/source/debug.h b/crawl-ref/source/debug.h index 6b4039bd8b..700fce055f 100644 --- a/crawl-ref/source/debug.h +++ b/crawl-ref/source/debug.h @@ -165,6 +165,7 @@ void debug_make_monster_shout(monsters* mon); void debug_apply_monster_blessing(monsters* mon); void wizard_give_monster_item(monsters* mon); void wizard_move_player_or_monster(int x, int y); +void debug_pathfind(int mid); #ifdef DEBUG_DIAGNOSTICS void generate_map_stats(); diff --git a/crawl-ref/source/directn.cc b/crawl-ref/source/directn.cc index feb805e7dc..2933230868 100644 --- a/crawl-ref/source/directn.cc +++ b/crawl-ref/source/directn.cc @@ -915,8 +915,17 @@ void direction(dist& moves, targeting_type restricts, skip_iter = true; break; -#endif + case CMD_TARGET_WIZARD_PATHFIND: + if (!you.wizard || !in_bounds(moves.tx, moves.ty)) + break; + mid = mgrd[moves.tx][moves.ty]; + if (mid == NON_MONSTER) + break; + + debug_pathfind(mid); + break; +#endif case CMD_TARGET_DESCRIBE: full_describe_square(moves.target()); force_redraw = true; @@ -947,10 +956,10 @@ void direction(dist& moves, targeting_type restricts, // Confirm self-targeting on TARG_ENEMY. // Conceivably we might want to confirm on TARG_ANY too. - if ( moves.isTarget - && moves.tx == you.x_pos && moves.ty == you.y_pos - && mode == TARG_ENEMY - && !yesno("Really target yourself?", false, 'n')) + if (moves.isTarget + && moves.tx == you.x_pos && moves.ty == you.y_pos + && mode == TARG_ENEMY + && !yesno("Really target yourself?", false, 'n')) { mesclr(); show_prompt = true; @@ -983,18 +992,17 @@ void direction(dist& moves, targeting_type restricts, bool have_moved = false; - if ( old_tx != moves.tx || old_ty != moves.ty ) + if (old_tx != moves.tx || old_ty != moves.ty) { have_moved = true; - show_beam = show_beam && - find_ray(you.x_pos, you.y_pos, moves.tx, moves.ty, true, ray, - 0, true); + show_beam = show_beam && find_ray(you.x_pos, you.y_pos, moves.tx, + moves.ty, true, ray, 0, true); } - if ( force_redraw ) + if (force_redraw) have_moved = true; - if ( have_moved ) + if (have_moved) { // If the target x,y has changed, the beam must have changed. if ( show_beam ) @@ -1017,9 +1025,9 @@ void direction(dist& moves, targeting_type restricts, { viewwindow(true, false); #endif - if ( show_beam - && in_vlos(grid2viewX(moves.tx), grid2viewY(moves.ty)) - && moves.target() != you.pos() ) + if (show_beam + && in_vlos(grid2viewX(moves.tx), grid2viewY(moves.ty)) + && moves.target() != you.pos() ) { // Draw the new ray with magenta '*'s, not including // your square or the target square. @@ -2494,6 +2502,7 @@ command_type targeting_behaviour::get_command(int key) case 's': return CMD_TARGET_WIZARD_MAKE_SHOUT; case 'g': return CMD_TARGET_WIZARD_GIVE_ITEM; case 'm': return CMD_TARGET_WIZARD_MOVE; + case 'w': return CMD_TARGET_WIZARD_PATHFIND; #endif case 'v': return CMD_TARGET_DESCRIBE; case '?': return CMD_TARGET_HELP; diff --git a/crawl-ref/source/enum.h b/crawl-ref/source/enum.h index 38dae10512..a267d894af 100644 --- a/crawl-ref/source/enum.h +++ b/crawl-ref/source/enum.h @@ -601,6 +601,7 @@ enum command_type CMD_TARGET_WIZARD_MAKE_SHOUT, CMD_TARGET_WIZARD_GIVE_ITEM, CMD_TARGET_WIZARD_MOVE, + CMD_TARGET_WIZARD_PATHFIND, CMD_TARGET_HELP, #ifdef USE_TILE diff --git a/crawl-ref/source/items.cc b/crawl-ref/source/items.cc index 96b3f907a2..0e9dd58955 100644 --- a/crawl-ref/source/items.cc +++ b/crawl-ref/source/items.cc @@ -260,7 +260,7 @@ bool dec_inv_item_quantity( int obj, int amount ) } you.inv[obj].base_type = OBJ_UNASSIGNED; - you.inv[obj].quantity = 0; + you.inv[obj].quantity = 0; you.inv[obj].props.clear(); ret = true; diff --git a/crawl-ref/source/mon-util.cc b/crawl-ref/source/mon-util.cc index bccde8e679..6e13d29153 100644 --- a/crawl-ref/source/mon-util.cc +++ b/crawl-ref/source/mon-util.cc @@ -2772,8 +2772,8 @@ bool mons_class_can_pass(const int mclass, const dungeon_feature_type grid) if (mons_is_wall_shielded(mclass)) { // Permanent walls can't be passed through. - return (!grid_is_solid(grid) || - (grid_is_rock(grid) && !grid_is_permarock(grid))); + return (!grid_is_solid(grid) + || grid_is_rock(grid) && !grid_is_permarock(grid)); } return !grid_is_solid(grid); diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc index 83db1833da..5ea9a3b5d7 100644 --- a/crawl-ref/source/monplace.cc +++ b/crawl-ref/source/monplace.cc @@ -17,6 +17,7 @@ #include "monplace.h" #include "branch.h" +#include "directn.h" // for the Compass #include "externs.h" #include "ghost.h" #include "lev-pand.h" @@ -76,7 +77,7 @@ bool grid_compatible(dungeon_feature_type grid_wanted, && actual_grid <= DNGN_CLEAR_PERMAROCK_WALL); } - // Restricted fountains during generation, so we don't monsters + // Restricted fountains during generation, so we don't get monsters // "trapped" in fountains for easy killing. return (grid_wanted == actual_grid || (grid_wanted == DNGN_DEEP_WATER @@ -2222,3 +2223,246 @@ monster_type rand_dragon( dragon_class_type type ) return (summoned); } + + +///////////////////////////////////////////////////////////////////////////// +// monster_pathfind + +monster_pathfind::monster_pathfind() + : mons(), target(), min_length(0), dist(), prev() +{ +} + +monster_pathfind::~monster_pathfind() +{ +} + +// Returns true if a path was found, else false. +bool monster_pathfind::start_pathfind(monsters *mon, coord_def dest, bool msg) +{ + mons = mon; + + // We're doing a reverse search from target to monster. + start = dest; + target = coord_def(mon->x, mon->y); + pos = start; + + // Easy enough. :P + if (start == target) + { + if (msg) + mpr("The monster is already there!"); + + return (true); + } + + max_length = min_length = grid_distance(pos.x, pos.y, target.x, target.y); +// memset(dist, INFINITE_DISTANCE, sizeof(dist)); + 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 + { + success = calc_path_to_neighbours(); + if (success) + return (true); + + 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() +{ +// mprf("in calc_path_to_neighbours() for (%d,%d)", pos.x, pos.y); + coord_def npos; + int distance, old_dist, total; + for (int dir = 0; dir < 8; dir++) + { + npos = pos + Compass[dir]; + +// mprf("Looking at neighbour (%d,%d)", npos.x, npos.y); + if (!in_bounds(npos)) + continue; + + if (!traversable(npos)) + continue; + + distance = dist[pos.x][pos.y] + travel_cost(npos); + old_dist = dist[npos.x][npos.y]; +// mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance, +// INFINITE_DISTANCE); + if (distance < old_dist) + { + // Calculate new total path length. + total = distance + estimated_cost(npos); + if (old_dist == INFINITE_DISTANCE) + { + mprf("Adding (%d,%d) to hash (total dist = %d)", + npos.x, npos.y, total); + + add_new_pos(npos, total); + if (total > max_length) + max_length = total; + } + else + { + mprf("Improving (%d,%d) to total dist %d", + npos.x, npos.y, total); + + update_pos(npos, total); + } + + // Update distance start->pos. + dist[npos.x][npos.y] = distance; + + // Set backtracking information. + // Converts the Compass direction to their counterpart. + // 7 0 1 + // 6 . 2 + // 5 4 3 + + prev[npos.x][npos.y] = (dir + 4) % 8; + + // Are we finished? + if (npos == target) + { + mpr("Arrived at target."); + return (true); + } + } + } + return (false); +} + +bool monster_pathfind::get_best_position() +{ +// mprf("minlength: %d, maxlength: %d", min_length, max_length); + 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]; + pos = vec[vec.size()-1]; + vec.pop_back(); + mprf("Returning (%d, %d) as best pos with total dist %d.", + pos.x, pos.y, min_length); + + return (true); + } +// mprf("No positions for path length %d.", i); + } + + // Nothing found? Then there's no path! :( + return (false); +} + +std::vector<coord_def> monster_pathfind::backtrack() +{ + mpr("Backtracking..."); + 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)); + mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y, + pos.x, pos.y); + path.push_back(pos); + + if (pos.x == 0 && pos.y == 0) + break; + } + while (pos != start); + ASSERT(pos == start); + + return path; +} + +bool monster_pathfind::traversable(coord_def p) +{ + const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons) + : mons->type; + + if (!monster_habitable_grid(montype, grd(p))) + { +// mprf("Feature %d is not a habitable grid.", grd(p)); + return (false); + } + + // Don't generate monsters on top of teleport traps. + const int trap = trap_at_xy(p.x, p.y); + if (trap >= 0) + { +// mpr("There's a trap here!"); + if (!_can_place_on_trap(montype, env.trap[trap].type)) + { +// mpr("Monster can't be placed on trap."); + return (false); + } + } +// mprf("Grid (%d, %d) is traversable.", p.x, p.y); + return (true); +} + +int monster_pathfind::travel_cost(coord_def npos) +{ + ASSERT(grid_distance(pos.x, pos.y, npos.x, npos.y) <= 1); + + // TODO: Make traps/shallow water more expensive, etc. + return 1; +} + +int monster_pathfind::estimated_cost(coord_def p) +{ + return (grid_distance(p.x, p.y, target.x, target.y)); +} + +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) + { +// mpr("Attempting to erase entry."); + vec.erase(vec.begin() + i); + break; + } + } + + add_new_pos(npos, total); +} diff --git a/crawl-ref/source/monplace.h b/crawl-ref/source/monplace.h index a4752a9b52..cfa3f9ca4d 100644 --- a/crawl-ref/source/monplace.h +++ b/crawl-ref/source/monplace.h @@ -294,4 +294,43 @@ coord_def find_newmons_square_contiguous(monster_type mons_class, void spawn_random_monsters(); +class monster_pathfind +{ +public: + monster_pathfind(); + virtual ~monster_pathfind(); + + // public methods + bool start_pathfind(monsters *mon, coord_def dest, bool msg = false); + std::vector<coord_def> backtrack(void); + +protected: + // protected methods + bool calc_path_to_neighbours(void); + bool traversable(coord_def p); + int 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. + monsters *mons; + + // Our destination, and the current position we're looking at. + coord_def start, target, pos; + + // 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<std::vector<coord_def>, GXM * GYM> hash; +}; + #endif // MONPLACE_H diff --git a/crawl-ref/source/store.h b/crawl-ref/source/store.h index f5f3f52b4a..23277348a3 100644 --- a/crawl-ref/source/store.h +++ b/crawl-ref/source/store.h @@ -352,7 +352,7 @@ public: void set_max_size(vec_size size); vec_size get_max_size() const; - // NOTE: If the const versions of get_value() or [] are given a + // NOTE: If the const versions of get_value() or [] are given an // index which doesn't exist, they will assert. const CrawlStoreValue& get_value(const vec_size &index) const; const CrawlStoreValue& operator[] (const vec_size &index) const; diff --git a/crawl-ref/source/traps.cc b/crawl-ref/source/traps.cc index a12d2a8bfe..d6646e9dba 100644 --- a/crawl-ref/source/traps.cc +++ b/crawl-ref/source/traps.cc @@ -925,23 +925,23 @@ dungeon_feature_type trap_category(trap_type type) } } // end trap_category() -// returns index of the trap for a given (x,y) coordinate pair {dlb} +// Returns index of the trap for a given (x,y) coordinate pair {dlb} int trap_at_xy(int which_x, int which_y) { for (int which_trap = 0; which_trap < MAX_TRAPS; which_trap++) { - if (env.trap[which_trap].x == which_x && - env.trap[which_trap].y == which_y && - env.trap[which_trap].type != TRAP_UNASSIGNED) + if (env.trap[which_trap].x == which_x + && env.trap[which_trap].y == which_y + && env.trap[which_trap].type != TRAP_UNASSIGNED) { return (which_trap); } } - // no idea how well this will be handled elsewhere: {dlb} + // No idea how well this will be handled elsewhere. {dlb} return (-1); -} // end trap_at_xy() +} trap_type trap_type_at_xy(int x, int y) { |