server/common/object.C

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2005,2006,2007,2008,2009,2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * Copyright (©) 2001 Mark Wedel & Crossfire Development Team
 * Copyright (©) 1992 Frank Tore Johansen
 * 
 * Deliantra is free software: you can redistribute it and/or modify it under
 * the terms of the Affero GNU General Public License as published by the
 * Free Software Foundation, either version 3 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 Affero GNU General Public License
 * and the GNU General Public License along with this program. If not, see
 * <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

#include <global.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <object.h>
#include <sproto.h>

#include <bitset>

UUID UUID::cur;
static uint64_t seq_next_save;
static const uint64 UUID_GAP = 1<<19;
uint32_t mapspace::smellcount = 10000;

objectvec objects;
activevec actives;

freelist_item *object::freelist;
uint32_t object::object_count;
uint32_t object::free_count;
uint32_t object::create_count;
uint32_t object::destroy_count;

//+GPL

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

const char *wall_suffix[16] = {
  "0", 
  "1_3", 
  "1_4", 
  "2_1_2", 
  "1_2", 
  "2_2_4", 
  "2_2_1", 
  "3_1", 
  "1_1", 
  "2_2_3", 
  "2_2_2", 
  "3_3", 
  "2_1_1", 
  "3_4", 
  "3_2", 
  "4" 
};

static void
write_uuid (uval64 skip, bool sync)
{
  CALL_BEGIN (2);
  CALL_ARG_SV (newSVval64 (skip));
  CALL_ARG_SV (boolSV (sync));
  CALL_CALL ("cf::write_uuid", G_DISCARD);
  CALL_END;
}

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

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

  seq_next_save = 0;

  FILE *fp;

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

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

  char buf [UUID::MAX_LEN];
  buf[0] = 0;
  fgets (buf, sizeof (buf), fp);

  if (!UUID::cur.parse (buf))
    {
      LOG (llevError, "FATAL: error reading uid from %s (%s)!\n", filename, buf);
      _exit (1);
    }

  LOG (llevDebug, "read UUID: %s\n", UUID::cur.c_str ());

  write_uuid (UUID_GAP, true);
  fclose (fp);
}

UUID
UUID::gen ()
{
  UUID uid;

  uid.seq = ++cur.seq;

  if (expect_false (cur.seq >= seq_next_save))
    {
      seq_next_save = UUID::cur.seq + (UUID_GAP >> 1);
      write_uuid (UUID_GAP, false);
    }


  return uid;
}

void
UUID::init ()
{
  read_uuid ();
}

bool
UUID::parse (const char *s)
{
  if (*s++ != '<' || *s++ != '1' || *s++ != '.')
    return false;

  seq = 0;

  while (*s != '>')
    {
      if (*s < '0')
        return false;

      // this gives nice branchless code with gcc
      assert ('0' < 'a' && '0' == 48 && 'a' == 97);
      int digit = (*s + (*s & 0x40 ? 9 : 0)) & 15;

      seq = (seq << 4) | digit;

      ++s;
    }

  return true;
}

char *
UUID::append (char *buf) const
{
  *buf++ = '<';
  *buf++ = '1';
  *buf++ = '.';

  uint64_t seq = this->seq;
  const int bits = 64;
  char nz = 0;
  static const char tohex [] = "0123456789abcdef";

  // assert (len >= 3 + bits / 4 + 1 + 1);
  for (int i = bits / 4; --i; )
    {
      uint8_t digit = seq >> (bits - 4);

      *buf = tohex [digit];
      nz |= digit;
      buf += nz ? 1 : 0;
      seq <<= 4;
    }

  // last digit is special - always emit
  uint8_t digit = seq >> (bits - 4);
  *buf++ = tohex [digit];

  *buf++ = '>';

  return buf;
}

char *
UUID::c_str () const
{
  static char buf [MAX_LEN];
  *append (buf) = 0;
  return buf;
}

/* Returns TRUE if every key_values in wants has a partner with the same value in has. */
static bool
compare_ob_value_lists_one (const object *wants, const object *has)
{
  /* n-squared behaviour (see kv_get), 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 (key_value *kv = wants->key_values; kv; kv = kv->next)
    if (has->kv_get (kv->key) != kv->value)
      return false;

  /* 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 bool
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 quick sanity checks */
  if (ob1 == ob2
      || ob1->type        != ob2->type
      || ob1->value       != ob2->value
      || ob1->name        != ob2->name
      || ob1->custom_name != ob2->custom_name
      || fabs (ob1->speed - ob2->speed) >= MIN_ACTIVE_SPEED)
    return 0;

  /* Do not merge objects if nrof would overflow, assume nrof
   * is always 0 .. 2**31-1 */
  if (ob1->nrof > 0x7fffffff - ob2->nrof)
    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 (ob1->flag [FLAG_IDENTIFIED])
    ob1->set_flag (FLAG_BEEN_APPLIED);

  if (ob2->flag [FLAG_IDENTIFIED])
    ob2->set_flag (FLAG_BEEN_APPLIED);

  if (ob1->arch->archname  != ob2->arch->archname
      || ob1->name         != ob2->name
      || ob1->title        != ob2->title
      || ob1->msg          != ob2->msg
      || ob1->weight       != ob2->weight
      || 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->face != ob2->face && !ob1->animation_id) // face and animation are dependend on each other
      || ob1->client_type  != ob2->client_type
      || ob1->material     != ob2->material
      || 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
      || fabs (ob1->move_slow_penalty - ob2->move_slow_penalty) >= (1.f / 1024.f)
      || memcmp (&ob1->resist, &ob2->resist, sizeof (ob1->resist))
      || memcmp (&ob1->stats , &ob2->stats , sizeof (ob1->stats)))
    return 0;

  if ((ob1->flag ^ ob2->flag)
      .reset (FLAG_INV_LOCKED)
      .reset (FLAG_REMOVED)
      .any ())
    return 0;

  /* This is really a spellbook check - we should in general
   * not merge objects with real inventories, as splitting them
   * is hard.
   */
  if (ob1->inv || ob2->inv)
    {
      if (!(ob1->inv && ob2->inv))
        return 0; /* inventories differ in length */

      if (ob1->inv->below || ob2->inv->below)
        return 0; /* more than one object in inv */

      if (!object::can_merge (ob1->inv, ob2->inv))
        return 0; /* inventory objects differ */

      /* 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 (ob1->flag [FLAG_APPLIED] || ob2->flag [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 (!ob1->flag [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 || ob2->key_values)
    {
      /* At least one of these has key_values. */
      if ((!ob1->key_values) != (!ob2->key_values))
        return 0; /* One has fields, but the other one doesn't. */

      if (!compare_ob_value_lists (ob1, ob2))
        return 0;
    }

  if (ob1->self || ob2->self)
    {
      ob1->optimise ();
      ob2->optimise ();

      if (ob1->self || ob2->self)
        {
          int k1 = ob1->self ? HvTOTALKEYS (ob1->self) : 0;
          int k2 = ob2->self ? HvTOTALKEYS (ob2->self) : 0;

          if (k1 != k2)
            return 0;

          if (k1 == 0)
            return 1;

          if (!cfperl_can_merge (ob1, ob2))
            return 0;
        }
    }

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

// find player who can see this object
object *
object::visible_to () const
{
  if (client_visible () && !flag [FLAG_REMOVED])
    {
      // see if we are in a container of sorts
      if (env)
        {
          // the player inventory itself is always visible
          if (env->is_player ())
            return env;

          // else a player could have our env open
          object *envest = env->outer_env_or_self ();

          // the player itself is always on a map, so we will find him here
          // even if our inv is in a player.
          if (envest->is_on_map ())
            if (object *pl = envest->ms ().player ())
              if (pl->container_ () == env)
                return pl;
        }
      else
        {
          // maybe there is a player standing on the same mapspace
          // this will catch the case where "this" is a player
          if (object *pl = ms ().player ())
            if ((pl->contr->ns && !pl->container_ () && !pl->contr->ns->update_look)
                || pl->container_ () == this)
              return pl;
        }
    }

  return 0;
}

// adjust weight per container type ("of holding")
static uint32
weight_adjust_for (object *op, uint32 weight)
{
  return op->type == CONTAINER
         ? weight - weight * op->stats.Str / 100
         : weight;
}

/*
 * subtracts, then adds, the specified weight to an object,
 * and also updates how much the environment(s) is/are carrying.
 */
static void
adjust_weight (object *op, sint32 sub, sint32 add)
{
  while (op)
    {
      sint32 ocarrying = op->carrying;

      op->carrying -= weight_adjust_for (op, sub);
      op->carrying += weight_adjust_for (op, add);

      if (object *pl = op->visible_to ())
        if (pl != op) // player is handled lazily
          esrv_update_item (UPD_WEIGHT, pl, op);

      sub = ocarrying;
      add = op->carrying;

      op = op->env;
    }
}

/*
 * this is a recursive function which calculates the weight
 * an object is carrying. It goes through op and figures out how much
 * containers are carrying, and sums it up.
 */
void
object::update_weight ()
{
  sint32 sum = 0;

  for (object *op = inv; op; op = op->below)
    {
      op->update_weight ();

      sum += weight_adjust_for (this, op->total_weight ());
    }

  if (sum != carrying)
    {
      if (carrying != sum && carrying)//D
        LOG (llevDebug, "updating carrying got %ld, expected %ld (%s)\n",
             (long long)sum, (long long)carrying, debug_desc ());

      carrying = sum;

      if (object *pl = visible_to ())
        if (pl != this) // player is handled lazily
          esrv_update_item (UPD_WEIGHT, pl, this);
    }
}

/*
 * Used by: Server DM commands: dumpbelow, dump. Some error messages.
 */
char *
dump_object (object *op)
{
  if (!op)
    return strdup ("[NULLOBJ]");

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

char *
object::as_string ()
{
  return dump_object (this);
}

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

  return 0;
}

/*
 * Returns the object which has the uuid equal to the argument.
 * MOAR VERRRY slow.
 */

object *
find_object_uuid (UUID i)
{
  for_all_objects (op)
   if (op->uuid == 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);

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

  return 0;
}

/*
 * Sets the owner and sets the skill and exp pointers to owner's current
 * skill and experience objects.
 * ACTUALLY NO! investigate! TODO
 */
void
object::set_owner (object *owner)
{
  // allow objects which own objects
  if (owner)
    while (owner->owner)
      owner = owner->owner;

  if (flag [FLAG_FREED])
    {
      LOG (llevError | logBacktrace, "tried to set owner of %s to %s\n", debug_desc (), owner->debug_desc ());
      return;
    }

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

/*
 * 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->remove ();
  *(object_copy *)dst = *this;
  dst->flag [FLAG_REMOVED] = true;

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

      for (key_value *i = 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 (!dst->key_values)
            {
              dst->key_values = new_link;
              tail = new_link;
            }
          else
            {
              tail->next = new_link;
              tail = new_link;
            }
        }
    }

  dst->activate ();
}

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

  // TODO: unclean state changes, should not be done in copy_to AND instantiate
  if (flag [FLAG_RANDOM_SPEED] && speed)
    speed_left = - speed - rndm (); // TODO animation
  else
    speed_left = -1.;

  /* 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.
   */
  for (int i = NUM_BODY_LOCATIONS; i--; )
    slot[i].used = slot[i].info;

  attachable::instantiate ();
}

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

  // TODO: unclean state changes, should not be done in clone AND instantiate
  if (neu->flag [FLAG_RANDOM_SPEED] && neu->speed)
    neu->speed_left = - neu->speed - rndm (); // TODO animation

  neu->map = map; // not copied by copy_to
  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 (!op->flag [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)
{
  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)
    {
      /* this should never happen */
      LOG (llevError | logBacktrace, "update_object() called for NULL object.\n");
      return;
    }

  if (!op->is_on_map ())
    {
      /* Animation is currently handled by client, so nothing
       * to do in this case.
       */
      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)
    {
#if 0
      // this is likely overkill, TODO: revisit (schmorp)
      if ((op->flag [FLAG_BLOCKSVIEW]  && !(m.flags_ & P_BLOCKSVIEW))
          || (op->flag [FLAG_NO_MAGIC] && !(m.flags_ & P_NO_MAGIC))
          || (op->is_player ()               && !(m.flags_ & P_PLAYER))
          || (op->type == SAFE_GROUND        && !(m.flags_ & P_SAFE))
          || (op->flag [FLAG_ALIVE]    && !(m.flags_ & P_IS_ALIVE))
          || (op->flag [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
           * have move_allow right now.    
           */
          || ((m.move_block | op->move_block) & ~op->move_allow) != m.move_block
        m.invalidate ();
#else
      // the above is not strong enough a test to skip updating. los maybe? TODO (schmorp)
      m.invalidate ();
#endif
    }
    /* 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.invalidate ();
  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 ()
{
  this->set_flag (FLAG_REMOVED);

  //expmul = 1.0; declared const for the time being
  face     = blank_face;
  material = MATERIAL_NULL;
}

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

  free_key_values (this);
}

void object::link ()
{
  assert (!index);//D
  uuid = UUID::gen ();

  refcnt_inc ();
  objects.insert (this);

  ++create_count;

}

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

  ++destroy_count;

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

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

  if (has_active_speed ())
    {
      if (flag [FLAG_FREED])
        LOG (llevError | logBacktrace, "BUG: tried to activate freed object %s\n", debug_desc ());//D

      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 its 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_ACTIVE
      || map->no_drop
      || ms ().move_block == MOVE_ALL)
    {
      while (inv)
        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);
        }
    }
}

/*
 * Remove and free all objects in the inventory of the given object.
 * Unlike destroy_inv, this assumes the *this is destroyed as well
 * well, so we can (and have to!) take shortcuts.
 */
void
object::destroy_inv_fast ()
{
  while (object *op = inv)
    {
      // remove from object the fast way
      op->flag [FLAG_REMOVED] = true;
      op->env = 0;
      if ((inv = inv->below))
        inv->above = 0;

      // then destroy
      op->destroy ();
    }
}

void
object::freelist_free (int count)
{
  while (count-- && freelist)
    {
      freelist_item *next = freelist->next;
      // count is being "destroyed"

      sfree ((char *)freelist, sizeof (object));

      freelist = next;
      --free_count;
    }
}

object *
object::create ()
{
  object *op;

  if (freelist)
    {
      freelist_item li = *freelist;
      memset (freelist, 0, sizeof (object));

      op = new (freelist) object;
      op->count = li.count;

      freelist = li.next;
      --free_count;
    }
  else
    {
      void *ni = salloc0<char> (sizeof (object));

      op = new(ni) object;

      op->count = ++object_count;
    }

  op->link ();

  return op;
}

void
object::do_delete ()
{
  uint32_t count = this->count;

  this->~object ();

  freelist_item *li = (freelist_item *)this;
  li->next  = freelist;
  li->count = count;

  freelist = li;
  ++free_count;
}

static struct freed_map : maptile
{
  freed_map ()
  : maptile (3, 3)
  {
    path     = "<freed objects map>";
    name     = "/internal/freed_objects_map";
    no_drop  = 1;
    no_reset = 1;

    in_memory = MAP_ACTIVE;
  }

  ~freed_map ()
  {
    destroy ();
  }
} freed_map; // freed objects are moved here to avoid crashes

void
object::do_destroy ()
{
  if (flag [FLAG_IS_LINKED])
    remove_link ();

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

  remove ();

  attachable::do_destroy ();

  deactivate ();
  unlink ();

  flag [FLAG_FREED] = 1;

  // hack to ensure that freed objects still have a valid map
  map = &freed_map;
  x = 1;
  y = 1;

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

  head = 0;

  // clear those pointers that likely might cause circular references
  owner          = 0;
  enemy          = 0;
  attacked_by    = 0;
  current_weapon = 0;
}

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

  if (!is_head () && !head->destroyed ())
    {
      LOG (llevError | logBacktrace, "tried to destroy the tail of an object");
      head->destroy ();
      return;
    }

  destroy_inv_fast ();

  if (is_head ())
    if (sound_destroy)
      play_sound (sound_destroy);
    else if (flag [FLAG_MONSTER])
      play_sound (sound_find ("monster_destroy")); // quick hack, too lazy to create a generic mechanism

  attachable::destroy ();
}

/* 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 ()
{
  if (flag [FLAG_REMOVED])
    return;

  INVOKE_OBJECT (REMOVE, this);

  flag [FLAG_REMOVED] = true;

  if (more)
    more->remove ();

  /* 
   * In this case, the object to be removed is in someones
   * inventory.
   */
  if (env)
    {
      flag [FLAG_REMOVED] = false; // hack around the issue of visible_to checking flag_removed
      if (object *pl = visible_to ())
        esrv_del_item (pl->contr, count);
      flag [FLAG_REMOVED] = true; // hack around the issue of visible_to checking flag_removed

      adjust_weight (env, total_weight (), 0);

      object *pl = in_player ();

      /* 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.
       */
      map   = env->map;
      x     = env->x;
      y     = env->y;

      // make sure cmov optimisation is applicable
      *(above ? &above->below : &env->inv) = below;
      *(below ? &below->above : &above   ) = above; // &above is just a dummy

      above = 0;
      below = 0;
      env   = 0;

      if (pl && pl->is_player ())
        {
          if (expect_false (pl->contr->combat_ob == this))
            {
              pl->apply (pl->contr->combat_ob, AP_UNAPPLY | AP_IGNORE_CURSE);
              pl->contr->combat_ob = 0;
              if (pl->contr->ranged_ob) pl->apply (pl->contr->ranged_ob);
            }

          if (expect_false (pl->contr->ranged_ob == this))
            {
              pl->apply (pl->contr->ranged_ob, AP_UNAPPLY | AP_IGNORE_CURSE);
              pl->contr->ranged_ob = 0;
              if (pl->contr->combat_ob) pl->apply (pl->contr->combat_ob);
            }

          pl->contr->queue_stats_update ();

          if (expect_false (glow_radius) && pl->is_on_map ())
            update_all_los (pl->map, pl->x, pl->y);
        }
    }
  else if (map)
    {
      map->dirty = true;
      mapspace &ms = this->ms ();

      if (object *pl = ms.player ())
        {
          if (is_player ())
            {
              if (!flag [FLAG_WIZPASS])
                ms.smell = ++mapspace::smellcount; // remember the smell of the 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 ();
            }
          else if (pl->container_ () == this)
            {
              // removing a container should close it
              close_container ();
            }
          else
            esrv_del_item (pl->contr, count);
        }

      /* link the object above us */
      // re-link, make sure compiler can easily use cmove
      *(above ? &above->below : &ms.top) = below;
      *(below ? &below->above : &ms.bot) = above;

      above = 0;
      below = 0;

      ms.invalidate ();

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

      int check_walk_off = !flag [FLAG_NO_APPLY];

      if (object *pl = ms.player ())
        {
          if (pl->container_ () == this)
            /* If a container that the player is currently using somehow gets
             * removed (most likely destroyed), update the player view
             * appropriately.
             */
            pl->close_container ();

          //TODO: the floorbox prev/next might need updating
          //esrv_del_item (pl->contr, count);
          //TODO: update floorbox to preserve ordering
          if (pl->contr->ns)
            pl->contr->ns->floorbox_update ();
        }

      if (check_walk_off)
        for (object *above, *tmp = ms.bot; tmp; tmp = above)
          {
            above = tmp->above;

            /* No point updating the players look faces if he is the object
             * being removed.
             */

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

      if (affects_los ())
        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 (object::can_merge (op, top))
      {
        top->nrof += op->nrof;

        if (object *pl = top->visible_to ())
          esrv_update_item (UPD_NROF, pl, top);

        op->weight   = 0; // cancel the addition above
        op->carrying = 0; // must be 0 already

        op->destroy ();

        return top;
      }

  return 0;
}

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

  object *prev = this;

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

      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)
{
  op->remove ();

  for (object *tmp = op->head_ (); tmp; tmp = tmp->more)
    {
      tmp->x = x + tmp->arch->x;
      tmp->y = y + tmp->arch->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 there was an error (destroyed, blocked etc.)
 *   just 'op' otherwise
 */
object *
insert_ob_in_map (object *op, maptile *m, object *originator, int flag)
{
  op->remove ();

  if (m == &freed_map)//D TODO: remove soon
    {//D
      LOG (llevError | logBacktrace, "tries to insret object on freed objects map: %s", op->debug_desc ());//D
    }//D

  /* 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
   */
  maptile *newmap = m;
  if (!xy_normalise (newmap, op->x, op->y))
    {
      op->head_ ()->destroy ();// remove head_ once all tail object destroyers found
      return 0;
    }

  if (object *more = op->more)
    if (!insert_ob_in_map (more, m, originator, flag))
      return 0;

  op->flag [FLAG_REMOVED] = false;
  op->env = 0;
  op->map = newmap;

  mapspace &ms = op->ms ();

  /* this has to be done after we translate the coordinates.
   */
  if (op->nrof && !(flag & INS_NO_MERGE))
    for (object *tmp = ms.bot; tmp; tmp = tmp->above)
      if (object::can_merge (op, tmp))
        {
          // TODO: we actually want to update tmp, not op,
          // but some caller surely breaks when we return tmp
          // from here :/
          op->nrof += tmp->nrof;
          tmp->destroy ();
        }

  op->clr_flag (FLAG_APPLIED);        /* hack for fixing F_APPLIED in items of dead people */
  op->clr_flag (FLAG_INV_LOCKED);

  if (!op->flag [FLAG_ALIVE])
    op->clr_flag (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 ();
        }

      if (!originator->is_on_map ())
        {
          LOG (llevError, "insert_ob_in_map(%s) called with INS_BELOW_ORIGINATOR when originator '%s' not on map",
               op->debug_desc (), originator->debug_desc ());
          abort ();
        }

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

      *(op->below ? &op->below->above : &ms.bot) = op;
    }
  else
    {
      object *floor = 0;
      object *top   = ms.top;

      /* If there are other objects, then */
      if (top)
        {
          /*
           * 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 (object *tmp = ms.bot; tmp; tmp = tmp->above)
            {
              if (tmp->flag [FLAG_IS_FLOOR] || tmp->flag [FLAG_OVERLAY_FLOOR])
                floor = tmp;

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

              top = tmp;
            }

          /* 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))
            {
              object *last;

              for (last = top; last != floor; last = last->below)
                if (last->flag [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_ABOVE_FLOOR_ONLY)
        top = floor;

      // insert object above top, or bottom-most if top = 0
      if (!top)
        {
          op->below = 0;
          op->above = ms.bot;
          ms.bot = op;

          *(op->above ? &op->above->below : &ms.top) = op;
        }
      else
        {
          op->above = top->above;
          top->above = op;

          op->below = top;
          *(op->above ? &op->above->below : &ms.top) = op;
        }
    }

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

  op->map->dirty = true;

  if (object *pl = ms.player ())
    //TODO: the floorbox prev/next might need updating
    //esrv_send_item (pl, op);
    //TODO: update floorbox to preserve ordering
    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->affects_los ())
    {
      op->ms ().invalidate ();
      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->is_head ())
    {
      if (check_move_on (op, originator, flag))
        return 0;

      /* If we are a multi part object, let's work our way through the check
       * walk on's.
       */
      for (object *tmp = op->more; tmp; tmp = tmp->more)
        if (check_move_on (tmp, originator, flag))
          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 (shstr_tmp archname, object *op)
{
  /* first search for itself and remove any old instances */

  for (object *tmp = op->ms ().bot; tmp; tmp = tmp->above)
    if (tmp->arch->archname == archname)       /* same archetype */
      tmp->destroy ();

  object *tmp = archetype::find (archname)->instance ();

  tmp->x = op->x;
  tmp->y = op->y;

  insert_ob_in_map (tmp, op->map, op, 0);
}

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

// check whether we can put this into the map, respect max_volume, max_items
bool
object::can_drop_at (maptile *m, int x, int y, object *originator)
{
  mapspace &ms = m->at (x, y);

  int items = ms.items ();

  if (!items // testing !items ensures we can drop at least one item
      || (items < m->max_items
          && ms.volume () < m->max_volume))
    return true;

  if (originator && originator->is_player ())
    originator->contr->failmsgf (
       "No matter how hard you try, you just cannot put the %s here H<Try to remove some items from the floor first.>",
       query_name ()
    );

  return false;
}

/*
 * decrease(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
 */
bool
object::decrease (sint32 nr)
{
  if (!nr)
    return true;

  nr = min (nr, nrof);

  if (nrof > nr)
    {
      sint64 oweight = total_weight ();

      nrof -= nr;

      if (object *pl = visible_to ())
        esrv_update_item (UPD_NROF, pl, this);

      adjust_weight (env, oweight, total_weight ());

      return true;
    }
  else
    {
      destroy ();
      return false;
    }
}

/*
 * split(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 returned if that number is 0).
 * On failure, NULL is returned.
 */
object *
object::split (sint32 nr)
{
  int have = number_of ();

  if (have < nr)
    return 0;
  else if (have == nr)
    {
      remove ();
      return this;
    }
  else
    {
      decrease (nr);

      object *op = deep_clone ();
      op->nrof = nr;
      return op;
    }
}

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_ () != where)
    {
      LOG (llevError | logBacktrace, "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)
{
  if (op->more)
    {
      LOG (llevError, "Tried to insert multipart object %s (%d)\n", &op->name, op->count);
      return op;
    }

  op->remove ();

  op->flag [FLAG_OBJ_ORIGINAL] = 0;

  if (op->nrof)
    for (object *tmp = inv; tmp; tmp = tmp->below)
      if (object::can_merge (tmp, op))
        {
          /* return the original object and remove inserted object
             (client prefers the original object) */

          // carring must be 0 for mergable objects
          sint64 oweight = tmp->weight * tmp->nrof;

          tmp->nrof += op->nrof;

          if (object *pl = tmp->visible_to ())
            esrv_update_item (UPD_NROF, pl, tmp);

          adjust_weight (this, oweight, tmp->weight * tmp->nrof);

          op->destroy ();
          op = tmp;
          goto inserted;
        }

  op->owner = 0; // it's his/hers now. period.
  op->map   = 0;
  op->x     = 0;
  op->y     = 0;

  op->above = 0;
  op->below = inv;
  op->env   = this;

  if (inv)
    inv->above = op;

  inv = op;

  op->flag [FLAG_REMOVED] = 0;

  if (object *pl = op->visible_to ())
    esrv_send_item (pl, op);

  adjust_weight (this, 0, op->total_weight ());

inserted:
  /* reset the light list and los of the players on the map */
  if (op->glow_radius && is_on_map ())
    {
      update_stats ();
      update_all_los (map, x, y);
    }
  else if (is_player ())
    // if this is a player's inventory, update stats
    contr->queue_stats_update ();

  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, int flags)
{
  if (op->flag [FLAG_NO_APPLY])
    return 0;

  object *tmp;
  maptile *m = op->map;
  int x = op->x, y = op->y;

  mapspace &ms = m->at (x, y);

  ms.update ();

  MoveType move_on    = ms.move_on;
  MoveType move_slow  = ms.move_slow;
  MoveType move_block = ms.move_block;

  /* 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 (object *next, *tmp = ms.top; tmp; tmp = next)
    {
      next = 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 (!op->flag [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->is_player ())
                if ((tmp->flag [FLAG_IS_HILLY ] && find_skill_by_number (op, SK_CLIMBING)) ||
                    (tmp->flag [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))
        {
          if ((flags & INS_NO_AUTO_EXIT)
              && (tmp->type == EXIT || tmp->type == TELEPORTER
                  || tmp->type == HOLE || tmp->type == TRAPDOOR)) //TODO: temporary, fix exits instead
            continue;

          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->archname == at->archname)
      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; tmp = tmp->below)
    if (tmp->arch->archname == at->archname)
      return tmp;

  return NULL;
}

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

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

/*
 * 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 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 altern[SIZEOFFREE];
  int index = 0, flag;

  for (int i = start; i < stop; i++)
    {
      mapxy pos (m, x, y); pos.move (i);

      if (!pos.normalise ())
        continue;

      mapspace &ms = *pos;

      if (ms.flags () & P_IS_ALIVE)
        continue;

      /* However, often
       * ob doesn't have any move type (when used to place exits)
       * so the AND operation in OB_TYPE_MOVE_BLOCK doesn't work.
       */
      if (ob && ob->move_type == 0 && ms.move_block != MOVE_ALL)
        {
          altern [index++] = i;
          continue;
        }

      /* 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.
       */
      if (ms.move_block == MOVE_ALL && maxfree[i] < stop)
        {
          stop = maxfree[i];
          continue;
        }

      /* Note it is intentional that we check ob - the movement type of the
       * head of the object should correspond for the entire object.
       */
      if (OB_TYPE_MOVE_BLOCK (ob, ms.move_block))
        continue;

      if (ob->blocked (pos.m, pos.x, pos.y))
        continue;

      altern [index++] = 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 (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 max = SIZEOFFREE, mflags;
  MoveType move_type;

  if (exclude && exclude->head_ () != exclude)
    {
      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 (int i = 1; i < max; i++)
    {
      mapxy pos (m, x, y);
      pos.move (i);

      if (!pos.normalise ())
        max = maxfree[i];
      else
        {
          mapspace &ms = *pos;

          if ((move_type & ms.move_block) == move_type)
            max = maxfree [i];
          else if (ms.flags () & P_IS_ALIVE)
            {
              for (object *tmp = ms.bot; tmp; tmp = tmp->above)
                if ((tmp->flag [FLAG_MONSTER] || tmp->is_player ())
                    && (tmp != exclude || (tmp->head_ () != tmp && tmp->head_ () != exclude)))
                  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 value
 * for running into direct [dx, dy].
 * (the opposite of crossfire's find_dir_2!)
 */
int
find_dir_2 (int x, int y)
{
#if 1 // new algorithm
  // this works by putting x, y into 16 sectors, which
  // are not equal sized, but are a better approximation
  // then the old algorithm, and then using a mapping
  // table to map it into a direction value.
  // basically, it maps these comparisons to each bit
  // bit #3: x < 0
  // bit #2: y < 0
  // bit #1: x > y
  // bit #0: x > 2y

  static const uint8 dir[16] = {
     4,  5,  4,  3,
     2,  1,  2,  3,
     6,  5,  6,  7,
     8,  1,  8,  7,
  };
  int sector = 0;

  // this is a bit ugly, but more likely to result in branchless code
  sector |= x < 0 ? 8 : 0;
  x      =  x < 0 ? -x : x; // abs

  sector |= y < 0 ? 4 : 0;
  y      =  y < 0 ? -y : y; // abs

  if (x > y)
    {
      sector |= 2;

      if (x > y * 2)
        sector |= 1;
    }
  else
    {
      if (y > x * 2)
        sector |= 1;
      else if (!y)
        return 0; // x == 0 here
    }

  return dir [sector];
#else // old algorithm
  int q;

  if (y)
    q = 128 * x / y;
  else if (x)
    q = -512 * x; // to make it > 309
  else
    return 0;

  if (y > 0)
    {
      if (q < -309) return 7;
      if (q <  -52) return 6;
      if (q <   52) return 5;
      if (q <  309) return 4;

      return 3;
    }
  else
    {
      if (q < -309) return 3;
      if (q <  -52) return 2;
      if (q <   52) return 1;
      if (q <  309) return 8;

      return 7;
    }
#endif
}

/*
 * 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 = abs (dir1 - dir2);

  return d > 4 ? 8 - d : 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.
 */
static const 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                        /*who->flag [FLAG_WIZ]|| */
    (item->weight > 0 && !item->flag [FLAG_NO_PICK] &&
     !item->flag [FLAG_ALIVE] && !item->invisible && (who->is_player () || item->weight < who->weight / 3));
}

/*
 * create clone from object to another
 */
object *
object::deep_clone ()
{
  assert (("deep_clone called on non-head object", is_head ()));

  object *dst = clone ();

  object *prev = dst;
  for (object *part = this->more; part; part = part->more)
    {
      object *tmp = part->clone ();
      tmp->head = dst;
      prev->more = tmp;
      prev = tmp;
    }

  for (object *item = inv; item; item = item->below)
    insert_ob_in_ob (item->deep_clone (), 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;
}

shstr_tmp
object::kv_get (shstr_tmp key) const
{
  for (key_value *kv = key_values; kv; kv = kv->next)
    if (kv->key == key)
      return kv->value;

  return shstr ();
}

void
object::kv_set (shstr_tmp key, shstr_tmp value)
{
  for (key_value *kv = key_values; kv; kv = kv->next)
    if (kv->key == key)
      {
        kv->value = value;
        return;
      }

  key_value *kv = new key_value;

  kv->next  = key_values;
  kv->key   = key;
  kv->value = value;

  key_values = kv;
}

void
object::kv_del (shstr_tmp key)
{
  for (key_value **kvp = &key_values; *kvp; kvp = &(*kvp)->next)
    if ((*kvp)->key == key)
      {
        key_value *kv = *kvp;
        *kvp = (*kvp)->next;
        delete kv;
        return;
      }
}

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:%s,name:\"%s\"%s%s%s,flags:[%s],type:%d}",
                 count,
                 uuid.c_str (),
                 &name,
                 title ? ",title:\"" : "",
                 title ? (const char *)title : "",
                 title ? "\"" : "",
                 flag_desc (flagdesc, 512), type);

  if (!flag[FLAG_REMOVED] && 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[3][256 * 4];
  static int info_idx;

  return debug_desc (info [++info_idx % 3]);
}

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

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

  object *old_container = container;

  if (old_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

      // make sure the container is available
      esrv_send_item (this, old_container);

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

      // client needs item update to make it work, client bug requires this to be separate
      esrv_update_item (UPD_FLAGS, this, old_container);

      new_draw_info_format (NDI_UNIQUE, 0, this, "You close %s.", old_container->query_name ());
      play_sound (sound_find ("chest_close"));
    }

  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 = new_container->other_arch->instance ();
          closer->flag [FLAG_NO_MAP_SAVE] = 1;
          new_container->insert (closer);
        }
#endif

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

      // make sure the container is available, client bug requires this to be separate
      esrv_send_item (this, new_container);

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

      // client needs flag change
      esrv_update_item (UPD_FLAGS, this, new_container);
      esrv_send_inventory (this, new_container);
      play_sound (sound_find ("chest_open"));
    }
//  else if (!old_container->env && contr && contr->ns)
//    contr->ns->floorbox_reset ();
}

object *
object::force_find (shstr_tmp name)
{
  /* cycle through his inventory to look for the MARK we want to 
   * place 
   */
  for (object *tmp = inv; tmp; tmp = tmp->below)
    if (tmp->type == FORCE && tmp->slaying == name)
      return splay (tmp);

  return 0;
}

//-GPL

void
object::force_set_timer (int duration)
{
  this->duration   = 1;
  this->speed_left = -1.f;

  this->set_speed (duration ? 1.f / duration : 0.f);
}

object *
object::force_add (shstr_tmp name, int duration)
{
  if (object *force = force_find (name))
    force->destroy ();

  object *force = get_archetype (FORCE_NAME);

  force->slaying = name;
  force->force_set_timer (duration);
  force->flag [FLAG_APPLIED] = true;

  return insert (force);
}

void
object::play_sound (faceidx sound) const
{
  if (!sound)
    return;

  if (is_on_map ())
    map->play_sound (sound, x, y);
  else if (object *pl = in_player ())
    pl->contr->play_sound (sound);
}

void
object::say_msg (const char *msg) const
{
  if (is_on_map ())
    map->say_msg (msg, x, y);
  else if (object *pl = in_player ())
    pl->contr->play_sound (sound);
}

void
object::make_noise ()
{
  // we do not model noise in the map, so instead put
  // a temporary light into the noise source
  // could use the map instead, but that's less reliable for our
  // goal, which is to make invisibility a bit harder to exploit

  // currently only works sensibly for players
  if (!is_player ())
    return;

  // find old force, or create new one
  object *force = force_find (shstr_noise_force);

  if (force)
    force->speed_left = -1.f; // patch old speed up
  else
    {
      force = archetype::get (shstr_noise_force);

      force->slaying    = shstr_noise_force;
      force->stats.food = 1;
      force->speed_left = -1.f;

      force->set_speed (1.f / 4.f);
      force->flag [FLAG_IS_USED_UP] = true;
      force->flag [FLAG_APPLIED]    = true;

      insert (force);
    }
}

void object::change_move_type (MoveType mt)
{
  if (move_type == mt)
    return;

  if (is_on_map ())
    {
      // we are on the map, so handle move_on/off effects
      remove ();
      move_type = mt;
      map->insert (this, x, y, this);
    }
  else
    move_type = mt;
}

/* object should be a player.
 * we return the object the player has marked with the 'mark' command
 * below. If no match is found (or object has changed), we return
 * NULL. We leave it up to the calling function to print messages if
 * nothing is found.
 */
object *
object::mark () const
{
  if (contr && contr->mark && contr->mark->env == this)
    return contr->mark;
  else
    return 0;
}

// put marked object first in the inventory
// this is used by identify-like spells so players can influence
// the order a bit.
void
object::splay_marked ()
{
  if (object *marked = mark ())
    splay (marked);
}

Revision:	1.342
Committed:	Sun Apr 10 20:30:53 2011 UTC (13 years, 1 month ago) by sf-kernelpanic
Content type:	text/plain
Branch:	MAIN
Changes since 1.341:	+4 -3 lines
Log Message:	object.C: don't merge "renamed" items Before, it was possible to just pickup one item from a stack, rename it and "taint" the stack with the new name by just dropping it. With this patch the renamed item will not be merged into the stack. Objects with the same "custom" name will still merge. Another use case would be the separation of certain types of items which are often found in dungeons, e.g. levitation boots. One could rename one pair of levitation boots and use it whenever he needs to, and other boots which would normally merge with it will form a new stack.