// 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}

        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)

    // no idea how well this will be handled elsewhere: {dlb}

    // No idea how well this will be handled elsewhere. {dlb}

}                               // end trap_at_xy()

}

    // NOTE: If the const versions of get_value() or [] are given a

    // NOTE: If the const versions of get_value() or [] are given an

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;
};

#include "directn.h" // for the Compass

    // Restricted fountains during generation, so we don't monsters

    // Restricted fountains during generation, so we don't get monsters

}
/////////////////////////////////////////////////////////////////////////////
// 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);
}

        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));

        you.inv[obj].quantity = 0;

        you.inv[obj].quantity  = 0;

    CMD_TARGET_WIZARD_PATHFIND,

            break;
        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);

            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'))

        if ( old_tx != moves.tx || old_ty != moves.ty )

        if (old_tx != moves.tx || old_ty != moves.ty)

            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)

        if ( have_moved )

        if (have_moved)

            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() )

    case 'w':  return CMD_TARGET_WIZARD_PATHFIND;

void debug_pathfind(int mid);

}
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());
    }

    // print out targeted spell:

    // Print targeted spell.

    // Select target slot

    // Select target slot.

    "<w>w</w>: calculate shortest path to any point on the map\n"

        // this command isn't very exciting... feel free to replace

        // This command isn't very exciting... feel free to replace.

        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 );

        // set j == equipment slot of chosen item, remove old randart benefits

        // Set j == equipment slot of chosen item, remove old randart benefits.

        // create all unrandarts

        // Create all unrandarts.

        // create all fixed artefacts

        // Create all fixed artefacts.