server/common/object.C

/*
 * CrossFire, A Multiplayer game
 * 
 * Copyright (C) 2005, 2006, 2007 Marc Lehmann & Crossfire+ Development Team
 * Copyright (C) 2001 Mark Wedel & Crossfire Development Team
 * Copyright (C) 1992 Frank Tore Johansen
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * The authors can be reached via e-mail at <crossfire@schmorp.de>
 */

/* Eneq(@csd.uu.se): Added weight-modifiers in environment of objects.
   sub/add_weight will transcend the environment updating the carrying
   variable. */
#include <global.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <object.h>
#include <funcpoint.h>
#include <loader.h>

#include <bitset>

int nrofallocobjects = 0;
static UUID uuid;
const uint64 UUID_SKIP = 1<<19;

objectvec objects;
activevec actives;

short freearr_x[SIZEOFFREE] = { 0, 0, 1, 1, 1, 0, -1, -1, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1,
  0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0, -1, -2, -3, -3, -3, -3, -3, -3, -3, -2, -1
};
short freearr_y[SIZEOFFREE] = { 0, -1, -1, 0, 1, 1, 1, 0, -1, -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2,
  -3, -3, -3, -3, -2, -1, 0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0, -1, -2, -3, -3, -3
};
int maxfree[SIZEOFFREE] = { 0, 9, 10, 13, 14, 17, 18, 21, 22, 25, 26, 27, 30, 31, 32, 33, 36, 37, 39, 39, 42, 43, 44, 45,
  48, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49
};
int freedir[SIZEOFFREE] = {
  0, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 8,
  1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 8
};

static void
write_uuid (void)
{
  char filename1[MAX_BUF], filename2[MAX_BUF];

  sprintf (filename1, "%s/uuid", settings.localdir);
  sprintf (filename2, "%s/uuid~", settings.localdir);

  FILE *fp;

  if (!(fp = fopen (filename2, "w")))
    {
      LOG (llevError, "ERROR: cannot open %s for writing, unable to write UUID!\n", filename2);
      return;
    }

  fprintf (fp, "<1,%llx>\n", (unsigned long long)uuid.seq + UUID_SKIP * 2);
  fclose (fp);
  rename (filename2, filename1);
}

static void
read_uuid (void)
{
  char filename[MAX_BUF];

  sprintf (filename, "%s/uuid", settings.localdir);

  FILE *fp;

  if (!(fp = fopen (filename, "r")))
    {
      if (errno == ENOENT)
        {
          LOG (llevInfo, "RESET uid to 1\n");
          uuid.seq = 0;
          write_uuid ();
          return;
        }

      LOG (llevError, "FATAL: cannot open %s for reading!\n", filename);
      _exit (1);
    }

  int version;
  unsigned long long uid;
  if (2 != fscanf (fp, "<%d,%llx>\n", &version, &uid) || version != 1)
    {
      LOG (llevError, "FATAL: error reading uid from %s!\n", filename);
      _exit (1);
    }

  uuid.seq = uid;
  write_uuid ();
  LOG (llevDebug, "read UID: %" PRId64 "\n", uid);
  fclose (fp);
}

UUID
gen_uuid ()
{
  UUID uid;

  uid.seq = ++uuid.seq;

  if (!(uuid.seq & (UUID_SKIP - 1)))
    write_uuid ();

  return uid;
}

void
init_uuid ()
{
  read_uuid ();
}

/* Returns TRUE if every key_values in wants has a partner with the same value in has. */
static int
compare_ob_value_lists_one (const object *wants, const object *has)
{
  key_value *wants_field;

  /* n-squared behaviour (see get_ob_key_link()), but I'm hoping both
   * objects with lists are rare, and lists stay short. If not, use a
   * different structure or at least keep the lists sorted... 
   */

  /* For each field in wants, */
  for (wants_field = wants->key_values; wants_field; wants_field = wants_field->next)
    {
      key_value *has_field;

      /* Look for a field in has with the same key. */
      has_field = get_ob_key_link (has, wants_field->key);

      if (has_field == NULL)
        {
          /* No field with that name. */
          return FALSE;
        }

      /* Found the matching field. */
      if (has_field->value != wants_field->value)
        {
          /* Values don't match, so this half of the comparison is false. */
          return FALSE;
        }

      /* If we get here, we found a match. Now for the next field in wants. */
    }

  /* If we get here, every field in wants has a matching field in has. */
  return TRUE;
}

/* Returns TRUE if ob1 has the same key_values as ob2. */
static int
compare_ob_value_lists (const object *ob1, const object *ob2)
{
  /* However, there may be fields in has which aren't partnered in wants,
   * so we need to run the comparison *twice*. :(
   */
  return compare_ob_value_lists_one (ob1, ob2) && compare_ob_value_lists_one (ob2, ob1);
}

/* Function examines the 2 objects given to it, and returns true if
 * they can be merged together.
 *
 * Note that this function appears a lot longer than the macro it
 * replaces - this is mostly for clarity - a decent compiler should hopefully
 * reduce this to the same efficiency.
 *
 * Check nrof variable *before* calling can_merge()
 *
 * Improvements made with merge:  Better checking on potion, and also
 * check weight
 */
bool object::can_merge_slow (object *ob1, object *ob2)
{
  /* A couple quicksanity checks */
  if (ob1 == ob2
      || ob1->type  != ob2->type
      || ob1->speed != ob2->speed
      || ob1->value != ob2->value
      || ob1->name  != ob2->name)
    return 0;

  //TODO: this ain't working well, use nicer and correct overflow check
  /* Do not merge objects if nrof would overflow. We use 1UL<<31 since that
   * value could not be stored in a sint32 (which unfortunately sometimes is
   * used to store nrof).
   */
  if (ob1->nrof + ob2->nrof >= 1UL << 31)
    return 0;

  /* If the objects have been identified, set the BEEN_APPLIED flag.
   * This is to the comparison of the flags below will be OK.  We
   * just can't ignore the been applied or identified flags, as they
   * are not equal - just if it has been identified, the been_applied
   * flags lose any meaning.
   */
  if (QUERY_FLAG (ob1, FLAG_IDENTIFIED))
    SET_FLAG (ob1, FLAG_BEEN_APPLIED);

  if (QUERY_FLAG (ob2, FLAG_IDENTIFIED))
    SET_FLAG (ob2, FLAG_BEEN_APPLIED);

  if ((ob1->flag ^ ob2->flag).reset (FLAG_INV_LOCKED).reset (FLAG_CLIENT_SENT).any ()
      || ob1->arch         != ob2->arch
      || ob1->name         != ob2->name
      || ob1->title        != ob2->title
      || ob1->msg          != ob2->msg
      || ob1->weight       != ob2->weight
      || memcmp (&ob1->resist, &ob2->resist, sizeof (ob1->resist))
      || memcmp (&ob1->stats , &ob2->stats , sizeof (ob1->stats) )
      || ob1->attacktype   != ob2->attacktype
      || ob1->magic        != ob2->magic
      || ob1->slaying      != ob2->slaying
      || ob1->skill        != ob2->skill
      || ob1->value        != ob2->value
      || ob1->animation_id != ob2->animation_id
      || ob1->client_type  != ob2->client_type
      || ob1->materialname != ob2->materialname
      || ob1->lore         != ob2->lore
      || ob1->subtype      != ob2->subtype
      || ob1->move_type    != ob2->move_type
      || ob1->move_block   != ob2->move_block
      || ob1->move_allow   != ob2->move_allow
      || ob1->move_on      != ob2->move_on
      || ob1->move_off     != ob2->move_off
      || ob1->move_slow    != ob2->move_slow
      || ob1->move_slow_penalty != ob2->move_slow_penalty)
    return 0;

  /* This is really a spellbook check - really, we should
   * check all objects in the inventory.
   */
  if (ob1->inv || ob2->inv)
    {
      /* if one object has inventory but the other doesn't, not equiv */
      if ((ob1->inv && !ob2->inv) || (ob2->inv && !ob1->inv))
        return 0;

      /* Now check to see if the two inventory objects could merge */
      if (!object::can_merge (ob1->inv, ob2->inv))
        return 0;

      /* inventory ok - still need to check rest of this object to see
       * if it is valid.
       */
    }

  /* Don't merge objects that are applied.  With the new 'body' code,
   * it is possible for most any character to have more than one of
   * some items equipped, and we don't want those to merge.
   */
  if (QUERY_FLAG (ob1, FLAG_APPLIED) || QUERY_FLAG (ob2, FLAG_APPLIED))
    return 0;

  /* Note sure why the following is the case - either the object has to
   * be animated or have a very low speed.  Is this an attempted monster
   * check?
   */
  if (!QUERY_FLAG (ob1, FLAG_ANIMATE) && ob1->has_active_speed ())
    return 0;

  switch (ob1->type)
    {
      case SCROLL:
        if (ob1->level != ob2->level)
          return 0;
        break;
    }

  if (ob1->key_values != NULL || ob2->key_values != NULL)
    {
      /* At least one of these has key_values. */
      if ((ob1->key_values == NULL) != (ob2->key_values == NULL))
        /* One has fields, but the other one doesn't. */
        return 0;
      else if (!compare_ob_value_lists (ob1, ob2))
        return 0;
    }

  //TODO: generate an event or call into perl for additional checks
  if (ob1->self || ob2->self)
    {
      ob1->optimise ();
      ob2->optimise ();

      if (ob1->self || ob2->self)
        return 0;
    }

  /* Everything passes, must be OK. */
  return 1;
}

/*
 * sum_weight() is a recursive function which calculates the weight
 * an object is carrying.  It goes through in figures out how much
 * containers are carrying, and sums it up.
 */
long
sum_weight (object *op)
{
  long sum;
  object *inv;

  for (sum = 0, inv = op->inv; inv; inv = inv->below)
    {
      if (inv->inv)
        sum_weight (inv);

      sum += inv->carrying + inv->weight * (inv->nrof ? inv->nrof : 1);
    }

  if (op->type == CONTAINER && op->stats.Str)
    sum = (sum * (100 - op->stats.Str)) / 100;

  if (op->carrying != sum)
    op->carrying = sum;

  return sum;
}

/**
 * Return the outermost environment object for a given object.
 */

object *
object_get_env_recursive (object *op)
{
  while (op->env != NULL)
    op = op->env;
  return op;
}

/*
 * Used by: Crossedit: dump. Server DM commands: dumpbelow, dump.
 *      Some error messages.
 * The result of the dump is stored in the static global errmsg array.
 */
char *
dump_object (object *op)
{
  if (!op)
    return strdup ("[NULLOBJ]");

  object_freezer freezer;
  op->write (freezer);
  return freezer.as_string ();
}

/*
 * get_nearest_part(multi-object, object 2) returns the part of the
 * multi-object 1 which is closest to the second object.
 * If it's not a multi-object, it is returned.
 */

object *
get_nearest_part (object *op, const object *pl)
{
  object *tmp, *closest;
  int last_dist, i;

  if (op->more == NULL)
    return op;
  for (last_dist = distance (op, pl), closest = op, tmp = op->more; tmp != NULL; tmp = tmp->more)
    if ((i = distance (tmp, pl)) < last_dist)
      closest = tmp, last_dist = i;
  return closest;
}

/*
 * Returns the object which has the count-variable equal to the argument.
 */
object *
find_object (tag_t i)
{
  for_all_objects (op)
   if (op->count == i)
     return op;

  return 0;
}

/*
 * Returns the first object which has a name equal to the argument.
 * Used only by the patch command, but not all that useful.
 * Enables features like "patch <name-of-other-player> food 999"
 */
object *
find_object_name (const char *str)
{
  shstr_cmp str_ (str);
  object *op;

  for_all_objects (op)
    if (op->name == str_)
      break;

  return op;
}

void
free_all_object_data ()
{
  LOG (llevDebug, "%d allocated objects\n", nrofallocobjects);
}

/*
 * Sets the owner and sets the skill and exp pointers to owner's current
 * skill and experience objects.
 */
void
object::set_owner (object *owner)
{
  if (!owner)
    return;

  /* next line added to allow objects which own objects */
  /* Add a check for ownercounts in here, as I got into an endless loop
   * with the fireball owning a poison cloud which then owned the
   * fireball.  I believe that was caused by one of the objects getting
   * freed and then another object replacing it.  Since the ownercounts
   * didn't match, this check is valid and I believe that cause is valid.
   */
  while (owner->owner)
    owner = owner->owner;

  this->owner = owner;
}

/* Zero the key_values on op, decrementing the shared-string
 * refcounts and freeing the links. 
 */
static void
free_key_values (object *op)
{
  for (key_value *i = op->key_values; i; )
    {
      key_value *next = i->next;
      delete i;

      i = next;
    }

  op->key_values = 0;
}

object &
object::operator =(const object &src)
{
  bool is_freed   = flag [FLAG_FREED];
  bool is_removed = flag [FLAG_REMOVED];

  *(object_copy *)this = src;

  flag [FLAG_FREED]   = is_freed;
  flag [FLAG_REMOVED] = is_removed;

  /* Copy over key_values, if any. */
  if (src.key_values)
    {
      key_value *tail = 0;
      key_values = 0;

      for (key_value *i = src.key_values; i; i = i->next)
        {
          key_value *new_link = new key_value;

          new_link->next = 0;
          new_link->key = i->key;
          new_link->value = i->value;

          /* Try and be clever here, too. */
          if (!key_values)
            {
              key_values = new_link;
              tail = new_link;
            }
          else
            {
              tail->next = new_link;
              tail = new_link;
            }
        }
    }
}

/*
 * copy_to first frees everything allocated by the dst object,
 * and then copies the contents of itself into the second
 * object, allocating what needs to be allocated.  Basically, any
 * data that is malloc'd needs to be re-malloc/copied.  Otherwise,
 * if the first object is freed, the pointers in the new object
 * will point at garbage.
 */
void
object::copy_to (object *dst)
{
  *dst = *this;

  if (speed < 0)
    dst->speed_left = speed_left - rndm ();

  dst->set_speed (dst->speed);
}

void
object::instantiate ()
{
  if (!uuid.seq) // HACK
    uuid = gen_uuid ();

  speed_left = -0.1f;
  /* copy the body_info to the body_used - this is only really
   * need for monsters, but doesn't hurt to do it for everything.
   * by doing so, when a monster is created, it has good starting
   * values for the body_used info, so when items are created 
   * for it, they can be properly equipped.
   */
  memcpy (body_used, body_info, sizeof (body_used));

  attachable::instantiate ();
}

object *
object::clone ()
{
  object *neu = create ();
  copy_to (neu);
  return neu;
}

/*
 * If an object with the IS_TURNABLE() flag needs to be turned due
 * to the closest player being on the other side, this function can
 * be called to update the face variable, _and_ how it looks on the map.
 */
void
update_turn_face (object *op)
{
  if (!QUERY_FLAG (op, FLAG_IS_TURNABLE) || !op->arch)
    return;

  SET_ANIMATION (op, op->direction);
  update_object (op, UP_OBJ_FACE);
}

/*
 * Updates the speed of an object.  If the speed changes from 0 to another
 * value, or vice versa, then add/remove the object from the active list.
 * This function needs to be called whenever the speed of an object changes.
 */
void
object::set_speed (float speed)
{
  if (flag [FLAG_FREED] && speed)
    {
      LOG (llevError, "Object %s is freed but has speed.\n", &name);
      speed = 0;
    }

  this->speed = speed;

  if (has_active_speed ())
    activate ();
  else
    deactivate ();
}

/*
 * update_object() updates the the map.
 * It takes into account invisible objects (and represent squares covered
 * by invisible objects by whatever is below them (unless it's another
 * invisible object, etc...)
 * If the object being updated is beneath a player, the look-window
 * of that player is updated (this might be a suboptimal way of
 * updating that window, though, since update_object() is called _often_)
 *
 * action is a hint of what the caller believes need to be done.
 * current action are:
 * UP_OBJ_INSERT: op was inserted
 * UP_OBJ_REMOVE: op was removed
 * UP_OBJ_CHANGE: object has somehow changed.  In this case, we always update
 *  as that is easier than trying to look at what may have changed.
 * UP_OBJ_FACE: only the objects face has changed.
 */
void
update_object (object *op, int action)
{
  if (op == NULL)
    {
      /* this should never happen */
      LOG (llevDebug, "update_object() called for NULL object.\n");
      return;
    }

  if (op->env)
    {
      /* Animation is currently handled by client, so nothing
       * to do in this case.
       */
      return;
    }

  /* If the map is saving, don't do anything as everything is
   * going to get freed anyways.
   */
  if (!op->map || op->map->in_memory == MAP_SAVING)
    return;

  /* make sure the object is within map boundaries */
  if (op->x < 0 || op->x >= op->map->width || op->y < 0 || op->y >= op->map->height)
    {
      LOG (llevError, "update_object() called for object out of map!\n");
#ifdef MANY_CORES
      abort ();
#endif
      return;
    }

  mapspace &m = op->ms ();

  if (!(m.flags_ & P_UPTODATE))
    /* nop */;
  else if (action == UP_OBJ_INSERT)
    {
      // this is likely overkill, TODO: revisit (schmorp)
      if ((QUERY_FLAG (op, FLAG_BLOCKSVIEW)  && !(m.flags_ & P_BLOCKSVIEW))
          || (QUERY_FLAG (op, FLAG_NO_MAGIC) && !(m.flags_ & P_NO_MAGIC))
          || (op->type == PLAYER             && !(m.flags_ & P_PLAYER))
          || (op->type == SAFE_GROUND        && !(m.flags_ & P_SAFE))
          || (QUERY_FLAG (op, FLAG_ALIVE)    && !(m.flags_ & P_IS_ALIVE))
          || (QUERY_FLAG (op, FLAG_DAMNED)   && !(m.flags_ & P_NO_CLERIC))
          || (m.move_on   | op->move_on  ) != m.move_on
          || (m.move_off  | op->move_off ) != m.move_off
          || (m.move_slow | op->move_slow) != m.move_slow
          /* This isn't perfect, but I don't expect a lot of objects to
           * to have move_allow right now.    
           */
          || ((m.move_block | op->move_block) & ~op->move_allow) != m.move_block
          || 1) // the above is not strong enough a test to skip updating. los maybe? TODO (Schmorp)
        m.flags_ = 0;
    }
    /* if the object is being removed, we can't make intelligent
     * decisions, because remove_ob can't really pass the object
     * that is being removed.
     */
  else if (action == UP_OBJ_CHANGE || action == UP_OBJ_REMOVE)
    m.flags_ = 0;
  else if (action == UP_OBJ_FACE)
    /* Nothing to do for that case */ ;
  else
    LOG (llevError, "update_object called with invalid action: %d\n", action);

  if (op->more)
    update_object (op->more, action);
}

object::object ()
{
  SET_FLAG (this, FLAG_REMOVED);

  expmul = 1.0;
  face = blank_face;
}

object::~object ()
{
  unlink ();

  free_key_values (this);
}

static int object_count;

void object::link ()
{
  assert (!index);//D
  uuid = gen_uuid ();
  count = ++object_count;

  refcnt_inc ();
  objects.insert (this);
}

void object::unlink ()
{
  if (!index)
    return;

  objects.erase (this);
  refcnt_dec ();
}

void
object::activate ()
{
  /* If already on active list, don't do anything */
  if (active)
    return;

  if (has_active_speed ())
    actives.insert (this);
}

void
object::activate_recursive ()
{
  activate ();

  for (object *op = inv; op; op = op->below)
    op->activate_recursive ();
}

/* This function removes object 'op' from the list of active
 * objects.
 * This should only be used for style maps or other such 
 * reference maps where you don't want an object that isn't
 * in play chewing up cpu time getting processed.
 * The reverse of this is to call update_ob_speed, which
 * will do the right thing based on the speed of the object.
 */
void
object::deactivate ()
{
  /* If not on the active list, nothing needs to be done */
  if (!active)
    return;

  actives.erase (this);
}

void
object::deactivate_recursive ()
{
  for (object *op = inv; op; op = op->below)
    op->deactivate_recursive ();

  deactivate ();
}

void
object::set_flag_inv (int flag, int value)
{
  for (object *op = inv; op; op = op->below)
    {
      op->flag [flag] = value;
      op->set_flag_inv (flag, value);
    }
}

/*
 * Remove and free all objects in the inventory of the given object.
 * object.c ?
 */
void
object::destroy_inv (bool drop_to_ground)
{
  // need to check first, because the checks below might segfault
  // as we might be on an invalid mapspace and crossfire code
  // is too buggy to ensure that the inventory is empty.
  // corollary: if you create arrows etc. with stuff in tis inventory,
  // cf will crash below with off-map x and y
  if (!inv)
    return;

  /* Only if the space blocks everything do we not process -
   * if some form of movement is allowed, let objects
   * drop on that space.
   */
  if (!drop_to_ground
      || !map
      || map->in_memory != MAP_IN_MEMORY
      || map->nodrop
      || ms ().move_block == MOVE_ALL)
    {
      while (inv)
        {
          inv->destroy_inv (drop_to_ground);
          inv->destroy ();
        }
    }
  else
    {                       /* Put objects in inventory onto this space */
      while (inv)
        {
          object *op = inv;

          if (op->flag [FLAG_STARTEQUIP]
              || op->flag [FLAG_NO_DROP]
              || op->type == RUNE
              || op->type == TRAP
              || op->flag [FLAG_IS_A_TEMPLATE]
              || op->flag [FLAG_DESTROY_ON_DEATH])
            op->destroy ();
          else
            map->insert (op, x, y);
        }
    }
}

object *object::create ()
{
  object *op = new object;
  op->link ();
  return op;
}

void
object::do_destroy ()
{
  attachable::do_destroy ();

  if (flag [FLAG_IS_LINKED])
    remove_button_link (this);

  if (flag [FLAG_FRIENDLY])
    remove_friendly_object (this);

  if (!flag [FLAG_REMOVED])
    remove ();

  destroy_inv (true);

  deactivate ();
  unlink ();

  flag [FLAG_FREED] = 1;

  // hack to ensure that freed objects still have a valid map
  {
    static maptile *freed_map; // freed objects are moved here to avoid crashes

    if (!freed_map)
      {
        freed_map = new maptile;

        freed_map->name   = "/internal/freed_objects_map";
        freed_map->width  = 3;
        freed_map->height = 3;

        freed_map->alloc ();
        freed_map->in_memory = MAP_IN_MEMORY;
      }

    map = freed_map;
    x = 1;
    y = 1;
  }

  head = 0;

  if (more)
    {
      more->destroy ();
      more = 0;
    }

  // clear those pointers that likely might have circular references to us
  owner       = 0;
  enemy       = 0;
  attacked_by = 0;
}

void
object::destroy (bool destroy_inventory)
{
  if (destroyed ())
    return;

  if (destroy_inventory)
    destroy_inv (false);

  attachable::destroy ();
}

/*
 * sub_weight() recursively (outwards) subtracts a number from the
 * weight of an object (and what is carried by it's environment(s)).
 */
void
sub_weight (object *op, signed long weight)
{
  while (op != NULL)
    {
      if (op->type == CONTAINER)
        weight = (signed long) (weight * (100 - op->stats.Str) / 100);

      op->carrying -= weight;
      op = op->env;
    }
}

/* op->remove ():
 *   This function removes the object op from the linked list of objects
 *   which it is currently tied to.  When this function is done, the
 *   object will have no environment.  If the object previously had an
 *   environment, the x and y coordinates will be updated to
 *   the previous environment.
 */
void
object::do_remove ()
{
  object *tmp, *last = 0;
  object *otmp;

  if (QUERY_FLAG (this, FLAG_REMOVED))
    return;

  SET_FLAG (this, FLAG_REMOVED);
  INVOKE_OBJECT (REMOVE, this);

  if (more)
    more->remove ();

  /* 
   * In this case, the object to be removed is in someones
   * inventory.
   */
  if (env)
    {
      if (nrof)
        sub_weight (env, weight * nrof);
      else
        sub_weight (env, weight + carrying);

      /* NO_FIX_PLAYER is set when a great many changes are being
       * made to players inventory.  If set, avoiding the call
       * to save cpu time.
       */
      if ((otmp = in_player ()) && otmp->contr && !QUERY_FLAG (otmp, FLAG_NO_FIX_PLAYER))
        otmp->update_stats ();

      if (above)
        above->below = below;
      else
        env->inv = below;

      if (below)
        below->above = above;

      /* we set up values so that it could be inserted into
       * the map, but we don't actually do that - it is up
       * to the caller to decide what we want to do.
       */
      x = env->x, y = env->y;
      map = env->map;
      above = 0, below = 0;
      env = 0;
    }
  else if (map)
    {
      if (type == PLAYER)
        {
          // leaving a spot always closes any open container on the ground
          if (container && !container->env)
            // this causes spurious floorbox updates, but it ensures
            // that the CLOSE event is being sent.
            close_container ();

          --map->players;
          map->touch ();
        }

      map->dirty = true;
      mapspace &ms = this->ms ();

      /* link the object above us */
      if (above)
        above->below = below;
      else
        ms.top = below;       /* we were top, set new top */

      /* Relink the object below us, if there is one */
      if (below)
        below->above = above;
      else
        {
          /* Nothing below, which means we need to relink map object for this space 
           * use translated coordinates in case some oddness with map tiling is
           * evident
           */
          if (GET_MAP_OB (map, x, y) != this)
            LOG (llevError, "remove_ob: GET_MAP_OB does not return object to be removed even though it appears to be on the bottom? %s\n", debug_desc ());

          ms.bot = above;      /* goes on above it. */
        }

      above = 0;
      below = 0;

      if (map->in_memory == MAP_SAVING)
        return;

      int check_walk_off = !flag [FLAG_NO_APPLY];

      for (tmp = ms.bot; tmp; tmp = tmp->above)
        {
          /* No point updating the players look faces if he is the object
           * being removed.
           */

          if (tmp->type == PLAYER && tmp != this)
            {
              /* If a container that the player is currently using somehow gets
               * removed (most likely destroyed), update the player view
               * appropriately.
               */
              if (tmp->container == this)
                {
                  flag [FLAG_APPLIED] = 0;
                  tmp->container = 0;
                }

              if (tmp->contr->ns)
                tmp->contr->ns->floorbox_update ();
            }

          /* See if object moving off should effect something */
          if (check_walk_off
              && ((move_type & tmp->move_off)
                  && (move_type & ~tmp->move_off & ~tmp->move_block) == 0))
            {
              move_apply (tmp, this, 0);

              if (destroyed ())
                LOG (llevError, "BUG: remove_ob(): name %s, destroyed leaving object\n", tmp->debug_desc ());
            }

          /* Eneq(@csd.uu.se): Fixed this to skip tmp->above=tmp */
          //TODO: why is this horrible hacka fix? get rid of this code=bug! (schmorp)
          if (tmp->above == tmp)
            tmp->above = 0;

          last = tmp;
        }

      /* last == NULL if there are no objects on this space */
      //TODO: this makes little sense, why only update the topmost object?
      if (!last)
        map->at (x, y).flags_ = 0;
      else
        update_object (last, UP_OBJ_REMOVE);

      if (flag [FLAG_BLOCKSVIEW] || glow_radius)
        update_all_los (map, x, y);
    }
}

/*
 * merge_ob(op,top):
 *
 * This function goes through all objects below and including top, and
 * merges op to the first matching object.
 * If top is NULL, it is calculated.
 * Returns pointer to object if it succeded in the merge, otherwise NULL
 */
object *
merge_ob (object *op, object *top)
{
  if (!op->nrof)
    return 0;

  if (top)
    for (top = op; top && top->above; top = top->above)
      ;

  for (; top; top = top->below)
    {
      if (top == op)
        continue;

      if (object::can_merge (op, top))
        {
          top->nrof += op->nrof;

/*      CLEAR_FLAG(top,FLAG_STARTEQUIP);*/
          op->weight = 0;       /* Don't want any adjustements now */
          op->destroy ();
          return top;
        }
    }

  return 0;
}

void
object::expand_tail ()
{
  if (more)
    return;

  object *prev = this;

  for (archetype *at = arch->more; at; at = at->more)
    {
      object *op = arch_to_object (at);

      op->name    = name;
      op->name_pl = name_pl;
      op->title   = title;

      op->head = this;
      prev->more = op;

      prev = op;
    }
}

/*
 * same as insert_ob_in_map except it handles separate coordinates and does a clean
 * job preparing multi-part monsters.
 */
object *
insert_ob_in_map_at (object *op, maptile *m, object *originator, int flag, int x, int y)
{
  for (object *tmp = op->head_ (); tmp; tmp = tmp->more)
    {
      tmp->x = x + tmp->arch->clone.x;
      tmp->y = y + tmp->arch->clone.y;
    }

  return insert_ob_in_map (op, m, originator, flag);
}

/*
 * insert_ob_in_map (op, map, originator, flag):
 * This function inserts the object in the two-way linked list
 * which represents what is on a map.
 * The second argument specifies the map, and the x and y variables
 * in the object about to be inserted specifies the position.
 *
 * originator: Player, monster or other object that caused 'op' to be inserted
 * into 'map'.  May be NULL.
 *
 * flag is a bitmask about special things to do (or not do) when this
 * function is called.  see the object.h file for the INS_ values.
 * Passing 0 for flag gives proper default values, so flag really only needs
 * to be set if special handling is needed.
 *
 * Return value:
 *   new object if 'op' was merged with other object
 *   NULL if 'op' was destroyed
 *   just 'op' otherwise
 */
object *
insert_ob_in_map (object *op, maptile *m, object *originator, int flag)
{
  assert (!op->flag [FLAG_FREED]);

  object *tmp, *top, *floor = NULL;

  op->remove ();

#if 0
  if (!m->active != !op->active)
    if (m->active)
      op->activate_recursive ();
    else
      op->deactivate_recursive ();
#endif

  if (out_of_map (m, op->x, op->y))
    {
      LOG (llevError, "Trying to insert object outside the map.\n%s\n", op->debug_desc ());
#ifdef MANY_CORES
      /* Better to catch this here, as otherwise the next use of this object
       * is likely to cause a crash.  Better to find out where it is getting
       * improperly inserted.
       */
      abort ();
#endif
      return op;
    }

  if (object *more = op->more)
    {
      if (!insert_ob_in_map (more, m, originator, flag))
        {
          if (!op->head)
            LOG (llevError, "BUG: insert_ob_in_map(): inserting op->more killed op\n");

          return 0;
        }
    }

  CLEAR_FLAG (op, FLAG_REMOVED);

  /* Ideally, the caller figures this out.  However, it complicates a lot
   * of areas of callers (eg, anything that uses find_free_spot would now
   * need extra work
   */
  if (!xy_normalise (m, op->x, op->y))
    return 0;

  op->map = m;
  mapspace &ms = op->ms ();

  /* this has to be done after we translate the coordinates.
   */
  if (op->nrof && !(flag & INS_NO_MERGE))
    for (tmp = ms.bot; tmp; tmp = tmp->above)
      if (object::can_merge (op, tmp))
        {
          op->nrof += tmp->nrof;
          tmp->destroy ();
        }

  CLEAR_FLAG (op, FLAG_APPLIED);        /* hack for fixing F_APPLIED in items of dead people */
  CLEAR_FLAG (op, FLAG_INV_LOCKED);

  if (!QUERY_FLAG (op, FLAG_ALIVE))
    CLEAR_FLAG (op, FLAG_NO_STEAL);

  if (flag & INS_BELOW_ORIGINATOR)
    {
      if (originator->map != op->map || originator->x != op->x || originator->y != op->y)
        {
          LOG (llevError, "insert_ob_in_map called with INS_BELOW_ORIGINATOR when originator not on same space!\n");
          abort ();
        }

      op->above = originator;
      op->below = originator->below;

      if (op->below)
        op->below->above = op;
      else
        ms.bot = op;

      /* since *below* originator, no need to update top */
      originator->below = op;
    }
  else
    {
      top = ms.bot;

      /* If there are other objects, then */
      if ((!(flag & INS_MAP_LOAD)) && top)
        {
          object *last = 0;

          /*
           * If there are multiple objects on this space, we do some trickier handling.
           * We've already dealt with merging if appropriate.
           * Generally, we want to put the new object on top. But if
           * flag contains INS_ABOVE_FLOOR_ONLY, once we find the last
           * floor, we want to insert above that and no further.
           * Also, if there are spell objects on this space, we stop processing
           * once we get to them.  This reduces the need to traverse over all of 
           * them when adding another one - this saves quite a bit of cpu time
           * when lots of spells are cast in one area.  Currently, it is presumed
           * that flying non pickable objects are spell objects.
           */
          for (top = ms.bot; top; top = top->above)
            {
              if (QUERY_FLAG (top, FLAG_IS_FLOOR) || QUERY_FLAG (top, FLAG_OVERLAY_FLOOR))
                floor = top;

              if (QUERY_FLAG (top, FLAG_NO_PICK) && (top->move_type & (MOVE_FLY_LOW | MOVE_FLY_HIGH)) && !QUERY_FLAG (top, FLAG_IS_FLOOR))
                {
                  /* We insert above top, so we want this object below this */
                  top = top->below;
                  break;
                }

              last = top;
            }

          /* Don't want top to be NULL, so set it to the last valid object */
          top = last;

          /* We let update_position deal with figuring out what the space
           * looks like instead of lots of conditions here.
           * makes things faster, and effectively the same result.
           */

          /* Have object 'fall below' other objects that block view.
           * Unless those objects are exits.
           * If INS_ON_TOP is used, don't do this processing
           * Need to find the object that in fact blocks view, otherwise
           * stacking is a bit odd.
           */
          if (!(flag & INS_ON_TOP)
              && ms.flags () & P_BLOCKSVIEW
              && (op->face && !faces [op->face].visibility))
            {
              for (last = top; last != floor; last = last->below)
                if (QUERY_FLAG (last, FLAG_BLOCKSVIEW) && (last->type != EXIT))
                  break;

              /* Check to see if we found the object that blocks view,
               * and make sure we have a below pointer for it so that
               * we can get inserted below this one, which requires we
               * set top to the object below us.
               */
              if (last && last->below && last != floor)
                top = last->below;
            }
        }                       /* If objects on this space */

      if (flag & INS_MAP_LOAD)
        top = ms.top;

      if (flag & INS_ABOVE_FLOOR_ONLY)
        top = floor;

      /* Top is the object that our object (op) is going to get inserted above.
       */

      /* First object on this space */
      if (!top)
        {
          op->above = ms.bot;

          if (op->above)
            op->above->below = op;

          op->below = 0;
          ms.bot = op;
        }
      else
        {                       /* get inserted into the stack above top */
          op->above = top->above;

          if (op->above)
            op->above->below = op;

          op->below = top;
          top->above = op;
        }

      if (!op->above)
        ms.top = op;
    }                           /* else not INS_BELOW_ORIGINATOR */

  if (op->type == PLAYER)
    {
      op->contr->do_los = 1;
      ++op->map->players;
      op->map->touch ();
    }

  op->map->dirty = true;

  /* If we have a floor, we know the player, if any, will be above
   * it, so save a few ticks and start from there.
   */
  if (!(flag & INS_MAP_LOAD))
    if (object *pl = ms.player ())
      if (pl->contr->ns)
        pl->contr->ns->floorbox_update ();

  /* If this object glows, it may affect lighting conditions that are
   * visible to others on this map.  But update_all_los is really
   * an inefficient way to do this, as it means los for all players
   * on the map will get recalculated.  The players could very well
   * be far away from this change and not affected in any way -
   * this should get redone to only look for players within range,
   * or just updating the P_UPTODATE for spaces within this area
   * of effect may be sufficient.
   */
  if (op->map->darkness && (op->glow_radius != 0))
    update_all_los (op->map, op->x, op->y);

  /* updates flags (blocked, alive, no magic, etc) for this map space */
  update_object (op, UP_OBJ_INSERT);

  INVOKE_OBJECT (INSERT, op);

  /* Don't know if moving this to the end will break anything.  However,
   * we want to have floorbox_update called before calling this.
   *
   * check_move_on() must be after this because code called from
   * check_move_on() depends on correct map flags (so functions like
   * blocked() and wall() work properly), and these flags are updated by
   * update_object().
   */

  /* if this is not the head or flag has been passed, don't check walk on status */
  if (!(flag & INS_NO_WALK_ON) && !op->head)
    {
      if (check_move_on (op, originator))
        return 0;

      /* If we are a multi part object, lets work our way through the check
       * walk on's.
       */
      for (tmp = op->more; tmp != NULL; tmp = tmp->more)
        if (check_move_on (tmp, originator))
          return 0;
    }

  return op;
}

/* this function inserts an object in the map, but if it
 * finds an object of its own type, it'll remove that one first. 
 * op is the object to insert it under: supplies x and the map.
 */
void
replace_insert_ob_in_map (const char *arch_string, object *op)
{
  object *tmp, *tmp1;

  /* first search for itself and remove any old instances */

  for (tmp = op->ms ().bot; tmp; tmp = tmp->above)
    if (!strcmp (tmp->arch->name, arch_string))       /* same archetype */
      tmp->destroy ();

  tmp1 = arch_to_object (archetype::find (arch_string));

  tmp1->x = op->x;
  tmp1->y = op->y;
  insert_ob_in_map (tmp1, op->map, op, 0);
}

object *
object::insert_at (object *where, object *originator, int flags)
{
  return where->map->insert (this, where->x, where->y, originator, flags);
}

/*
 * get_split_ob(ob,nr) splits up ob into two parts.  The part which
 * is returned contains nr objects, and the remaining parts contains
 * the rest (or is removed and freed if that number is 0).
 * On failure, NULL is returned, and the reason put into the
 * global static errmsg array.
 */
object *
get_split_ob (object *orig_ob, uint32 nr)
{
  object *newob;
  int is_removed = (QUERY_FLAG (orig_ob, FLAG_REMOVED) != 0);

  if (orig_ob->nrof < nr)
    {
      sprintf (errmsg, "There are only %d %ss.", orig_ob->nrof ? orig_ob->nrof : 1, &orig_ob->name);
      return NULL;
    }

  newob = object_create_clone (orig_ob);

  if ((orig_ob->nrof -= nr) < 1)
    orig_ob->destroy (1);
  else if (!is_removed)
    {
      if (orig_ob->env != NULL)
        sub_weight (orig_ob->env, orig_ob->weight * nr);
      if (orig_ob->env == NULL && orig_ob->map->in_memory != MAP_IN_MEMORY)
        {
          strcpy (errmsg, "Tried to split object whose map is not in memory.");
          LOG (llevDebug, "Error, Tried to split object whose map is not in memory.\n");
          return NULL;
        }
    }

  newob->nrof = nr;

  return newob;
}

/*
 * decrease_ob_nr(object, number) decreases a specified number from
 * the amount of an object.  If the amount reaches 0, the object
 * is subsequently removed and freed.
 *
 * Return value: 'op' if something is left, NULL if the amount reached 0
 */
object *
decrease_ob_nr (object *op, uint32 i)
{
  object *tmp;

  if (i == 0)                   /* objects with op->nrof require this check */
    return op;

  if (i > op->nrof)
    i = op->nrof;

  if (QUERY_FLAG (op, FLAG_REMOVED))
    op->nrof -= i;
  else if (op->env)
    {
      /* is this object in the players inventory, or sub container
       * therein?
       */
      tmp = op->in_player ();
      /* nope.  Is this a container the player has opened?
       * If so, set tmp to that player.
       * IMO, searching through all the players will mostly
       * likely be quicker than following op->env to the map,
       * and then searching the map for a player.
       */
      if (!tmp)
        for_all_players (pl)
          if (pl->ob->container == op->env)
            {
              tmp = pl->ob;
              break;
            }

      if (i < op->nrof)
        {
          sub_weight (op->env, op->weight * i);
          op->nrof -= i;
          if (tmp)
            esrv_send_item (tmp, op);
        }
      else
        {
          op->remove ();
          op->nrof = 0;
          if (tmp)
            esrv_del_item (tmp->contr, op->count);
        }
    }
  else
    {
      object *above = op->above;

      if (i < op->nrof)
        op->nrof -= i;
      else
        {
          op->remove ();
          op->nrof = 0;
        }

      /* Since we just removed op, op->above is null */
      for (tmp = above; tmp; tmp = tmp->above)
        if (tmp->type == PLAYER)
          {
            if (op->nrof)
              esrv_send_item (tmp, op);
            else
              esrv_del_item (tmp->contr, op->count);
          }
    }

  if (op->nrof)
    return op;
  else
    {
      op->destroy ();
      return 0;
    }
}

/*
 * add_weight(object, weight) adds the specified weight to an object,
 * and also updates how much the environment(s) is/are carrying.
 */
void
add_weight (object *op, signed long weight)
{
  while (op != NULL)
    {
      if (op->type == CONTAINER)
        weight = (signed long) (weight * (100 - op->stats.Str) / 100);

      op->carrying += weight;
      op = op->env;
    }
}

object *
insert_ob_in_ob (object *op, object *where)
{
  if (!where)
    {
      char *dump = dump_object (op);
      LOG (llevError, "Trying to put object in NULL.\n%s\n", dump);
      free (dump);
      return op;
    }

  if (where->head)
    {
      LOG (llevDebug, "Warning: Tried to insert object into wrong part of multipart object.\n");
      where = where->head;
    }

  return where->insert (op);
}

/*
 * env->insert (op)
 *   This function inserts the object op in the linked list
 *   inside the object environment.
 *
 * The function returns now pointer to inserted item, and return value can 
 * be != op, if items are merged. -Tero
 */
object *
object::insert (object *op)
{
  object *tmp, *otmp;

  if (!QUERY_FLAG (op, FLAG_REMOVED))
    op->remove ();

  if (op->more)
    {
      LOG (llevError, "Tried to insert multipart object %s (%d)\n", &op->name, op->count);
      return op;
    }

  CLEAR_FLAG (op, FLAG_OBJ_ORIGINAL);
  CLEAR_FLAG (op, FLAG_REMOVED);
  if (op->nrof)
    {
      for (tmp = inv; tmp != NULL; tmp = tmp->below)
        if (object::can_merge (tmp, op))
          {
            /* return the original object and remove inserted object
               (client needs the original object) */
            tmp->nrof += op->nrof;
            /* Weight handling gets pretty funky.  Since we are adding to
             * tmp->nrof, we need to increase the weight.
             */
            add_weight (this, op->weight * op->nrof);
            SET_FLAG (op, FLAG_REMOVED);
            op->destroy ();   /* free the inserted object */
            op = tmp;
            op->remove ();     /* and fix old object's links */
            CLEAR_FLAG (op, FLAG_REMOVED);
            break;
          }

      /* I assume combined objects have no inventory
       * We add the weight - this object could have just been removed
       * (if it was possible to merge).  calling remove_ob will subtract
       * the weight, so we need to add it in again, since we actually do
       * the linking below
       */
      add_weight (this, op->weight * op->nrof);
    }
  else
    add_weight (this, (op->weight + op->carrying));

  otmp = this->in_player ();
  if (otmp && otmp->contr)
    if (!QUERY_FLAG (otmp, FLAG_NO_FIX_PLAYER))
      otmp->update_stats ();

  op->map = 0;
  op->env = this;
  op->above = 0;
  op->below = 0;
  op->x = 0, op->y = 0;

  /* reset the light list and los of the players on the map */
  if ((op->glow_radius != 0) && map)
    {
#ifdef DEBUG_LIGHTS
      LOG (llevDebug, " insert_ob_in_ob(): got %s to insert in map/op\n", op->name);
#endif /* DEBUG_LIGHTS */
      if (map->darkness)
        update_all_los (map, x, y);
    }

  /* Client has no idea of ordering so lets not bother ordering it here.
   * It sure simplifies this function...
   */
  if (!inv)
    inv = op;
  else
    {
      op->below = inv;
      op->below->above = op;
      inv = op;
    }

  INVOKE_OBJECT (INSERT, this);

  return op;
}

/*
 * Checks if any objects has a move_type that matches objects
 * that effect this object on this space.  Call apply() to process
 * these events.
 *
 * Any speed-modification due to SLOW_MOVE() of other present objects
 * will affect the speed_left of the object.
 *
 * originator: Player, monster or other object that caused 'op' to be inserted
 * into 'map'.  May be NULL.
 *
 * Return value: 1 if 'op' was destroyed, 0 otherwise.
 *
 * 4-21-95 added code to check if appropriate skill was readied - this will
 * permit faster movement by the player through this terrain. -b.t.
 *
 * MSW 2001-07-08: Check all objects on space, not just those below
 * object being inserted.  insert_ob_in_map may not put new objects
 * on top.
 */
int
check_move_on (object *op, object *originator)
{
  object *tmp;
  maptile *m = op->map;
  int x = op->x, y = op->y;

  MoveType move_on, move_slow, move_block;

  if (QUERY_FLAG (op, FLAG_NO_APPLY))
    return 0;

  move_on = GET_MAP_MOVE_ON (op->map, op->x, op->y);
  move_slow = GET_MAP_MOVE_SLOW (op->map, op->x, op->y);
  move_block = GET_MAP_MOVE_BLOCK (op->map, op->x, op->y);

  /* if nothing on this space will slow op down or be applied,
   * no need to do checking below.    have to make sure move_type
   * is set, as lots of objects don't have it set - we treat that
   * as walking.
   */
  if (op->move_type && !(op->move_type & move_on) && !(op->move_type & move_slow))
    return 0;

  /* This is basically inverse logic of that below - basically,
   * if the object can avoid the move on or slow move, they do so,
   * but can't do it if the alternate movement they are using is
   * blocked.  Logic on this seems confusing, but does seem correct.
   */
  if ((op->move_type & ~move_on & ~move_block) != 0 && (op->move_type & ~move_slow & ~move_block) != 0)
    return 0;

  /* The objects have to be checked from top to bottom.
   * Hence, we first go to the top: 
   */

  for (tmp = op->ms ().bot; tmp && tmp->above; tmp = tmp->above)
    {
      /* Trim the search when we find the first other spell effect 
       * this helps performance so that if a space has 50 spell objects,
       * we don't need to check all of them.
       */
      if ((tmp->move_type & MOVE_FLY_LOW) && QUERY_FLAG (tmp, FLAG_NO_PICK))
        break;
    }

  for (; tmp; tmp = tmp->below)
    {
      if (tmp == op)
        continue;               /* Can't apply yourself */

      /* Check to see if one of the movement types should be slowed down.
       * Second check makes sure that the movement types not being slowed
       * (~slow_move) is not blocked on this space - just because the
       * space doesn't slow down swimming (for example), if you can't actually
       * swim on that space, can't use it to avoid the penalty.
       */
      if (!QUERY_FLAG (op, FLAG_WIZPASS))
        {
          if ((!op->move_type && tmp->move_slow & MOVE_WALK) ||
              ((op->move_type & tmp->move_slow) && (op->move_type & ~tmp->move_slow & ~tmp->move_block) == 0))
            {

              float
                diff = tmp->move_slow_penalty * fabs (op->speed);

              if (op->type == PLAYER)
                if ((QUERY_FLAG (tmp, FLAG_IS_HILLY) && find_skill_by_number (op, SK_CLIMBING)) ||
                    (QUERY_FLAG (tmp, FLAG_IS_WOODED) && find_skill_by_number (op, SK_WOODSMAN)))
                  diff /= 4.0;

              op->speed_left -= diff;
            }
        }

      /* Basically same logic as above, except now for actual apply. */
      if ((!op->move_type && tmp->move_on & MOVE_WALK) ||
          ((op->move_type & tmp->move_on) && (op->move_type & ~tmp->move_on & ~tmp->move_block) == 0))
        {
          move_apply (tmp, op, originator);

          if (op->destroyed ())
            return 1;

          /* what the person/creature stepped onto has moved the object
           * someplace new.  Don't process any further - if we did,
           * have a feeling strange problems would result.
           */
          if (op->map != m || op->x != x || op->y != y)
            return 0;
        }
    }

  return 0;
}

/*
 * present_arch(arch, map, x, y) searches for any objects with
 * a matching archetype at the given map and coordinates.
 * The first matching object is returned, or NULL if none.
 */
object *
present_arch (const archetype *at, maptile *m, int x, int y)
{
  if (!m || out_of_map (m, x, y))
    {
      LOG (llevError, "Present_arch called outside map.\n");
      return NULL;
    }

  for (object *tmp = m->at (x, y).bot; tmp; tmp = tmp->above)
    if (tmp->arch == at)
      return tmp;

  return NULL;
}

/*
 * present(type, map, x, y) searches for any objects with
 * a matching type variable at the given map and coordinates.
 * The first matching object is returned, or NULL if none.
 */
object *
present (unsigned char type, maptile *m, int x, int y)
{
  if (out_of_map (m, x, y))
    {
      LOG (llevError, "Present called outside map.\n");
      return NULL;
    }

  for (object *tmp = m->at (x, y).bot; tmp; tmp = tmp->above)
    if (tmp->type == type)
      return tmp;

  return NULL;
}

/*
 * present_in_ob(type, object) searches for any objects with
 * a matching type variable in the inventory of the given object.
 * The first matching object is returned, or NULL if none.
 */
object *
present_in_ob (unsigned char type, const object *op)
{
  for (object *tmp = op->inv; tmp != NULL; tmp = tmp->below)
    if (tmp->type == type)
      return tmp;

  return NULL;
}

/*
 * present_in_ob (type, str, object) searches for any objects with
 * a matching type & name variable in the inventory of the given object.
 * The first matching object is returned, or NULL if none.
 * This is mostly used by spell effect code, so that we only
 * have one spell effect at a time.
 * type can be used to narrow the search - if type is set,
 * the type must also match.  -1 can be passed for the type,
 * in which case the type does not need to pass.
 * str is the string to match against.  Note that we match against
 * the object name, not the archetype name.  this is so that the
 * spell code can use one object type (force), but change it's name
 * to be unique.
 */
object *
present_in_ob_by_name (int type, const char *str, const object *op)
{
  for (object *tmp = op->inv; tmp; tmp = tmp->below)
    if ((type == -1 || tmp->type == type) && (!strcmp (str, tmp->name)))
      return tmp;

  return 0;
}

/*
 * present_arch_in_ob(archetype, object) searches for any objects with
 * a matching archetype in the inventory of the given object.
 * The first matching object is returned, or NULL if none.
 */
object *
present_arch_in_ob (const archetype *at, const object *op)
{
  for (object *tmp = op->inv; tmp != NULL; tmp = tmp->below)
    if (tmp->arch == at)
      return tmp;

  return NULL;
}

/*
 * activate recursively a flag on an object inventory
 */
void
flag_inv (object *op, int flag)
{
  if (op->inv)
    for (object *tmp = op->inv; tmp != NULL; tmp = tmp->below)
      {
        SET_FLAG (tmp, flag);
        flag_inv (tmp, flag);
      }
}

/*
 * deactivate recursively a flag on an object inventory
 */
void
unflag_inv (object *op, int flag)
{
  if (op->inv)
    for (object *tmp = op->inv; tmp != NULL; tmp = tmp->below)
      {
        CLEAR_FLAG (tmp, flag);
        unflag_inv (tmp, flag);
      }
}

/*
 * set_cheat(object) sets the cheat flag (WAS_WIZ) in the object and in
 * all it's inventory (recursively).
 * If checksums are used, a player will get set_cheat called for
 * him/her-self and all object carried by a call to this function.
 */
void
set_cheat (object *op)
{
  SET_FLAG (op, FLAG_WAS_WIZ);
  flag_inv (op, FLAG_WAS_WIZ);
}

/*
 * find_free_spot(object, map, x, y, start, stop) will search for
 * a spot at the given map and coordinates which will be able to contain
 * the given object.  start and stop specifies how many squares
 * to search (see the freearr_x/y[] definition).
 * It returns a random choice among the alternatives found.
 * start and stop are where to start relative to the free_arr array (1,9
 * does all 4 immediate directions).  This returns the index into the
 * array of the free spot, -1 if no spot available (dir 0 = x,y)
 * Note - this only checks to see if there is space for the head of the
 * object - if it is a multispace object, this should be called for all
 * pieces.
 * Note2: This function does correctly handle tiled maps, but does not
 * inform the caller.  However, insert_ob_in_map will update as
 * necessary, so the caller shouldn't need to do any special work.
 * Note - updated to take an object instead of archetype - this is necessary
 * because arch_blocked (now ob_blocked) needs to know the movement type
 * to know if the space in question will block the object.  We can't use
 * the archetype because that isn't correct if the monster has been 
 * customized, changed states, etc.
 */
int
find_free_spot (const object *ob, maptile *m, int x, int y, int start, int stop)
{
  int index = 0, flag;
  int altern[SIZEOFFREE];

  for (int i = start; i < stop; i++)
    {
      flag = ob_blocked (ob, m, x + freearr_x[i], y + freearr_y[i]);
      if (!flag)
        altern [index++] = i;

      /* Basically, if we find a wall on a space, we cut down the search size.
       * In this way, we won't return spaces that are on another side of a wall.
       * This mostly work, but it cuts down the search size in all directions - 
       * if the space being examined only has a wall to the north and empty
       * spaces in all the other directions, this will reduce the search space
       * to only the spaces immediately surrounding the target area, and
       * won't look 2 spaces south of the target space.
       */
      else if ((flag & P_NO_PASS) && maxfree[i] < stop)
        stop = maxfree[i];
    }

  if (!index)
    return -1;

  return altern [rndm (index)];
}

/*
 * find_first_free_spot(archetype, maptile, x, y) works like
 * find_free_spot(), but it will search max number of squares.
 * But it will return the first available spot, not a random choice.
 * Changed 0.93.2: Have it return -1 if there is no free spot available.
 */
int
find_first_free_spot (const object *ob, maptile *m, int x, int y)
{
  for (int i = 0; i < SIZEOFFREE; i++)
    if (!ob_blocked (ob, m, x + freearr_x[i], y + freearr_y[i]))
      return i;

  return -1;
}

/*
 * The function permute(arr, begin, end) randomly reorders the array
 * arr[begin..end-1].
 * now uses a fisher-yates shuffle, old permute was broken
 */
static void
permute (int *arr, int begin, int end)
{
  arr += begin;
  end -= begin;

  while (--end)
    swap (arr [end], arr [rndm (end + 1)]);
}

/* new function to make monster searching more efficient, and effective! 
 * This basically returns a randomized array (in the passed pointer) of
 * the spaces to find monsters.  In this way, it won't always look for
 * monsters to the north first.  However, the size of the array passed
 * covers all the spaces, so within that size, all the spaces within
 * the 3x3 area will be searched, just not in a predictable order.
 */
void
get_search_arr (int *search_arr)
{
  int i;

  for (i = 0; i < SIZEOFFREE; i++)
    search_arr[i] = i;

  permute (search_arr, 1, SIZEOFFREE1 + 1);
  permute (search_arr, SIZEOFFREE1 + 1, SIZEOFFREE2 + 1);
  permute (search_arr, SIZEOFFREE2 + 1, SIZEOFFREE);
}

/*
 * find_dir(map, x, y, exclude) will search some close squares in the
 * given map at the given coordinates for live objects.
 * It will not considered the object given as exclude among possible
 * live objects.
 * It returns the direction toward the first/closest live object if finds
 * any, otherwise 0.
 * Perhaps incorrectly, but I'm making the assumption that exclude
 * is actually want is going to try and move there.  We need this info
 * because we have to know what movement the thing looking to move
 * there is capable of.
 */
int
find_dir (maptile *m, int x, int y, object *exclude)
{
  int i, max = SIZEOFFREE, mflags;

  sint16 nx, ny;
  object *tmp;
  maptile *mp;

  MoveType blocked, move_type;

  if (exclude && exclude->head)
    {
      exclude = exclude->head;
      move_type = exclude->move_type;
    }
  else
    {
      /* If we don't have anything, presume it can use all movement types. */
      move_type = MOVE_ALL;
    }

  for (i = 1; i < max; i++)
    {
      mp = m;
      nx = x + freearr_x[i];
      ny = y + freearr_y[i];

      mflags = get_map_flags (m, &mp, nx, ny, &nx, &ny);

      if (mflags & P_OUT_OF_MAP)
        max = maxfree[i];
      else
        {
          mapspace &ms = mp->at (nx, ny);

          blocked = ms.move_block;

          if ((move_type & blocked) == move_type)
            max = maxfree[i];
          else if (mflags & P_IS_ALIVE)
            {
              for (tmp = ms.bot; tmp; tmp = tmp->above)
                if ((tmp->flag [FLAG_MONSTER] || tmp->type == PLAYER)
                    && (tmp != exclude || (tmp->head && tmp->head != exclude)))
                  break;

              if (tmp)
                return freedir[i];
            }
        }
    }

  return 0;
}

/*
 * distance(object 1, object 2) will return the square of the
 * distance between the two given objects.
 */
int
distance (const object *ob1, const object *ob2)
{
  return (ob1->x - ob2->x) * (ob1->x - ob2->x) + (ob1->y - ob2->y) * (ob1->y - ob2->y);
}

/*
 * find_dir_2(delta-x,delta-y) will return a direction in which
 * an object which has subtracted the x and y coordinates of another
 * object, needs to travel toward it.
 */
int
find_dir_2 (int x, int y)
{
  int q;

  if (y)
    q = x * 100 / y;
  else if (x)
    q = -300 * x;
  else
    return 0;

  if (y > 0)
    {
      if (q < -242)
        return 3;
      if (q < -41)
        return 2;
      if (q < 41)
        return 1;
      if (q < 242)
        return 8;
      return 7;
    }

  if (q < -242)
    return 7;
  if (q < -41)
    return 6;
  if (q < 41)
    return 5;
  if (q < 242)
    return 4;

  return 3;
}

/*
 * dirdiff(dir1, dir2) returns how many 45-degrees differences there is
 * between two directions (which are expected to be absolute (see absdir())
 */
int
dirdiff (int dir1, int dir2)
{
  int d;

  d = abs (dir1 - dir2);
  if (d > 4)
    d = 8 - d;

  return d;
}

/* peterm:
 * do LOS stuff for ball lightning.  Go after the closest VISIBLE monster.
 * Basically, this is a table of directions, and what directions
 * one could go to go back to us.  Eg, entry 15 below is 4, 14, 16.
 * This basically means that if direction is 15, then it could either go
 * direction 4, 14, or 16 to get back to where we are.
 * Moved from spell_util.c to object.c with the other related direction
 * functions.
 */
int reduction_dir[SIZEOFFREE][3] = {
  {0, 0, 0},                    /* 0 */
  {0, 0, 0},                    /* 1 */
  {0, 0, 0},                    /* 2 */
  {0, 0, 0},                    /* 3 */
  {0, 0, 0},                    /* 4 */
  {0, 0, 0},                    /* 5 */
  {0, 0, 0},                    /* 6 */
  {0, 0, 0},                    /* 7 */
  {0, 0, 0},                    /* 8 */
  {8, 1, 2},                    /* 9 */
  {1, 2, -1},                   /* 10 */
  {2, 10, 12},                  /* 11 */
  {2, 3, -1},                   /* 12 */
  {2, 3, 4},                    /* 13 */
  {3, 4, -1},                   /* 14 */
  {4, 14, 16},                  /* 15 */
  {5, 4, -1},                   /* 16 */
  {4, 5, 6},                    /* 17 */
  {6, 5, -1},                   /* 18 */
  {6, 20, 18},                  /* 19 */
  {7, 6, -1},                   /* 20 */
  {6, 7, 8},                    /* 21 */
  {7, 8, -1},                   /* 22 */
  {8, 22, 24},                  /* 23 */
  {8, 1, -1},                   /* 24 */
  {24, 9, 10},                  /* 25 */
  {9, 10, -1},                  /* 26 */
  {10, 11, -1},                 /* 27 */
  {27, 11, 29},                 /* 28 */
  {11, 12, -1},                 /* 29 */
  {12, 13, -1},                 /* 30 */
  {12, 13, 14},                 /* 31 */
  {13, 14, -1},                 /* 32 */
  {14, 15, -1},                 /* 33 */
  {33, 15, 35},                 /* 34 */
  {16, 15, -1},                 /* 35 */
  {17, 16, -1},                 /* 36 */
  {18, 17, 16},                 /* 37 */
  {18, 17, -1},                 /* 38 */
  {18, 19, -1},                 /* 39 */
  {41, 19, 39},                 /* 40 */
  {19, 20, -1},                 /* 41 */
  {20, 21, -1},                 /* 42 */
  {20, 21, 22},                 /* 43 */
  {21, 22, -1},                 /* 44 */
  {23, 22, -1},                 /* 45 */
  {45, 47, 23},                 /* 46 */
  {23, 24, -1},                 /* 47 */
  {24, 9, -1}
};                              /* 48 */

/* Recursive routine to step back and see if we can
 * find a path to that monster that we found.  If not,
 * we don't bother going toward it.  Returns 1 if we
 * can see a direct way to get it
 * Modified to be map tile aware -.MSW
 */
int
can_see_monsterP (maptile *m, int x, int y, int dir)
{
  sint16 dx, dy;
  int mflags;

  if (dir < 0)
    return 0;                   /* exit condition:  invalid direction */

  dx = x + freearr_x[dir];
  dy = y + freearr_y[dir];

  mflags = get_map_flags (m, &m, dx, dy, &dx, &dy);

  /* This functional arguably was incorrect before - it was
   * checking for P_WALL - that was basically seeing if
   * we could move to the monster - this is being more
   * literal on if we can see it.  To know if we can actually
   * move to the monster, we'd need the monster passed in or
   * at least its move type.
   */
  if (mflags & (P_OUT_OF_MAP | P_BLOCKSVIEW))
    return 0;

  /* yes, can see. */
  if (dir < 9)
    return 1;

  return can_see_monsterP (m, x, y, reduction_dir[dir][0])
         | can_see_monsterP (m, x, y, reduction_dir[dir][1])
         | can_see_monsterP (m, x, y, reduction_dir[dir][2]);
}

/*
 * can_pick(picker, item): finds out if an object is possible to be
 * picked up by the picker.  Returnes 1 if it can be
 * picked up, otherwise 0.
 *
 * Cf 0.91.3 - don't let WIZ's pick up anything - will likely cause
 * core dumps if they do.
 *
 * Add a check so we can't pick up invisible objects (0.93.8)
 */

int
can_pick (const object *who, const object *item)
{
  return                        /*QUERY_FLAG(who,FLAG_WIZ)|| */
    (item->weight > 0 && !QUERY_FLAG (item, FLAG_NO_PICK) &&
     !QUERY_FLAG (item, FLAG_ALIVE) && !item->invisible && (who->type == PLAYER || item->weight < who->weight / 3));
}

/*
 * create clone from object to another
 */
object *
object_create_clone (object *asrc)
{
  object *dst = 0, *tmp, *src, *part, *prev, *item;

  if (!asrc)
    return 0;

  src = asrc;
  if (src->head)
    src = src->head;

  prev = 0;
  for (part = src; part; part = part->more)
    {
      tmp = part->clone ();
      tmp->x -= src->x;
      tmp->y -= src->y;

      if (!part->head)
        {
          dst = tmp;
          tmp->head = 0;
        }
      else
        tmp->head = dst;

      tmp->more = 0;

      if (prev)
        prev->more = tmp;

      prev = tmp;
    }

  for (item = src->inv; item; item = item->below)
    insert_ob_in_ob (object_create_clone (item), dst);

  return dst;
}

/* This returns the first object in who's inventory that
 * has the same type and subtype match.
 * returns NULL if no match.
 */
object *
find_obj_by_type_subtype (const object *who, int type, int subtype)
{
  for (object *tmp = who->inv; tmp; tmp = tmp->below)
    if (tmp->type == type && tmp->subtype == subtype)
      return tmp;

  return 0;
}

/* If ob has a field named key, return the link from the list,
 * otherwise return NULL. 
 *
 * key must be a passed in shared string - otherwise, this won't
 * do the desired thing.
 */
key_value *
get_ob_key_link (const object *ob, const char *key)
{
  for (key_value *link = ob->key_values; link; link = link->next)
    if (link->key == key)
      return link;

  return 0;
}

/* 
 * Returns the value of op has an extra_field for key, or NULL.
 *
 * The argument doesn't need to be a shared string.
 *
 * The returned string is shared.
 */
const char *
get_ob_key_value (const object *op, const char *const key)
{
  key_value *link;
  shstr_cmp canonical_key (key);

  if (!canonical_key)
    {
      /* 1. There being a field named key on any object
       *    implies there'd be a shared string to find.
       * 2. Since there isn't, no object has this field.
       * 3. Therefore, *this* object doesn't have this field.
       */
      return 0;
    }

  /* This is copied from get_ob_key_link() above -
   * only 4 lines, and saves the function call overhead.
   */
  for (link = op->key_values; link; link = link->next)
    if (link->key == canonical_key)
      return link->value;

  return 0;
}

/*
 * Updates the canonical_key in op to value.
 *
 * canonical_key is a shared string (value doesn't have to be).
 *
 * Unless add_key is TRUE, it won't add fields, only change the value of existing
 * keys.
 *
 * Returns TRUE on success.
 */
int
set_ob_key_value_s (object *op, const shstr & canonical_key, const char *value, int add_key)
{
  key_value *field = NULL, *last = NULL;

  for (field = op->key_values; field != NULL; field = field->next)
    {
      if (field->key != canonical_key)
        {
          last = field;
          continue;
        }

      if (value)
        field->value = value;
      else
        {
          /* Basically, if the archetype has this key set,
           * we need to store the null value so when we save
           * it, we save the empty value so that when we load,
           * we get this value back again.
           */
          if (get_ob_key_link (&op->arch->clone, canonical_key))
            field->value = 0;
          else
            {
              if (last)
                last->next = field->next;
              else
                op->key_values = field->next;

              delete field;
            }
        }
      return TRUE;
    }
  /* IF we get here, key doesn't exist */

  /* No field, we'll have to add it. */

  if (!add_key)
    return FALSE;

  /* There isn't any good reason to store a null
   * value in the key/value list.  If the archetype has
   * this key, then we should also have it, so shouldn't
   * be here.  If user wants to store empty strings,
   * should pass in ""
   */
  if (value == NULL)
    return TRUE;

  field = new key_value;

  field->key = canonical_key;
  field->value = value;
  /* Usual prepend-addition. */
  field->next = op->key_values;
  op->key_values = field;

  return TRUE;
}

/*
 * Updates the key in op to value.
 *
 * If add_key is FALSE, this will only update existing keys,
 * and not add new ones.
 * In general, should be little reason FALSE is ever passed in for add_key
 *
 * Returns TRUE on success.
 */
int
set_ob_key_value (object *op, const char *key, const char *value, int add_key)
{
  shstr key_ (key);

  return set_ob_key_value_s (op, key_, value, add_key);
}

object::depth_iterator::depth_iterator (object *container)
: iterator_base (container)
{
  while (item->inv)
    item = item->inv;
}

void
object::depth_iterator::next ()
{
  if (item->below)
    {
      item = item->below;

      while (item->inv)
        item = item->inv;
    }
  else
    item = item->env;
}


const char *
object::flag_desc (char *desc, int len) const
{
  char *p = desc;
  bool first = true;

  *p = 0;

  for (int i = 0; i < NUM_FLAGS; i++)
    {
      if (len <= 10) // magic constant!
        {
          snprintf (p, len, ",...");
          break;
        }

      if (flag [i])
        {
          int cnt = snprintf (p, len, "%s%d", first ? "" : ",", i);
          len -= cnt;
          p += cnt;
          first = false;
        }
    }

  return desc;
}

// return a suitable string describing an object in enough detail to find it
const char *
object::debug_desc (char *info) const
{
  char flagdesc[512];
  char info2[256 * 4];
  char *p = info;

  p += snprintf (p, 512, "{cnt:%d,uuid:<1.%" PRIx64 ">,name:\"%s\"%s%s,flags:[%s],type:%d}",
                 count, uuid.seq,
                 &name,
                 title ? "\",title:\"" : "",
                 title ? (const char *)title : "",
                 flag_desc (flagdesc, 512), type);

  if (env)
    p += snprintf (p, 256, "(in %s)", env->debug_desc (info2));

  if (map)
    p += snprintf (p, 256, "(on %s@%d+%d)", &map->path, x, y);

  return info;
}

const char *
object::debug_desc () const
{
  static char info[256 * 4];
  return debug_desc (info);
}

const char *
object::debug_desc2 () const
{
  static char info[256 * 4];
  return debug_desc (info);
}

struct region *
object::region () const
{
  return map ? map->region (x, y)
             : region::default_region ();
}

const materialtype_t *
object::dominant_material () const
{
  if (materialtype_t *mat = name_to_material (materialname))
    return mat;

  // omfg this is slow, this has to be temporary :)
  shstr unknown ("unknown");

  return name_to_material (unknown);
}

void
object::open_container (object *new_container)
{
  if (container == new_container)
    return;

  if (object *old_container = container)
    {
      if (INVOKE_OBJECT (CLOSE, old_container, ARG_OBJECT (this)))
        return;

#if 0
      // remove the "Close old_container" object.
      if (object *closer = old_container->inv)
        if (closer->type == CLOSE_CON)
          closer->destroy ();
#endif

      old_container->flag [FLAG_APPLIED] = 0;
      container = 0;

      esrv_update_item (UPD_FLAGS, this, old_container);
      new_draw_info_format (NDI_UNIQUE, 0, this, "You close %s.", query_name (old_container));
    }

  if (new_container)
    {
      if (INVOKE_OBJECT (OPEN, new_container, ARG_OBJECT (this)))
        return;

      // TODO: this does not seem to serve any purpose anymore?
#if 0
      // insert the "Close Container" object.
      if (archetype *closer = new_container->other_arch)
        {
          object *closer = arch_to_object (new_container->other_arch);
          closer->flag [FLAG_NO_MAP_SAVE] = 1;
          new_container->insert (closer);
        }
#endif

      new_draw_info_format (NDI_UNIQUE, 0, this, "You open %s.", query_name (new_container));

      new_container->flag [FLAG_APPLIED] = 1;
      container = new_container;

      esrv_update_item (UPD_FLAGS, this, new_container);
      esrv_send_inventory (this, new_container);
    }
}


Revision:	1.142
Committed:	Mon Apr 30 04:25:29 2007 UTC (17 years, 1 month ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.141:	+2 -7 lines
Log Message:	This is the first rough cut of the skill use system (use the STABLE tag). Details will likely change, and combat skills do not work very well, but it works quite well. Players no longer have a shoottype or range slots, instead, each player has these members: combat_skill/combat_ob the currently selected skill (and weapon) for direct attacks. ranged_skill/ranged_ob the currently selected ranged skill (and bow/spell/item) golem the currently-controlled golem, if any.