From 7d23129b8f16dfa73e3842ac8e91c61e5a3393aa Mon Sep 17 00:00:00 2001 From: Guillaume Melquiond Date: Sat, 30 Dec 2006 13:29:03 +0000 Subject: Made attack code pixel-based and faster. Split State::update. Improved interface of MapComposite iterators. --- ChangeLog | 16 ++ src/Makefile.am | 4 +- src/being.cpp | 105 ++++----- src/being.h | 16 +- src/game-server/mapcomposite.cpp | 470 ++++++++++++++++++++++++++++++++++++ src/game-server/mapcomposite.hpp | 234 ++++++++++++++++++ src/game-server/state.cpp | 311 ++++++++++++------------ src/game-server/state.hpp | 64 ++--- src/mapcomposite.cpp | 497 --------------------------------------- src/mapcomposite.h | 239 ------------------- src/object.h | 13 +- src/player.cpp | 1 - 12 files changed, 967 insertions(+), 1003 deletions(-) create mode 100644 src/game-server/mapcomposite.cpp create mode 100644 src/game-server/mapcomposite.hpp delete mode 100644 src/mapcomposite.cpp delete mode 100644 src/mapcomposite.h diff --git a/ChangeLog b/ChangeLog index 2ac87b7b..575de9f7 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +2006-12-30 Guillaume Melquiond + + * src/mapcomposite.h, src/mapcomposite.cpp: Moved to src/game-server + directory and changed header extension to hpp. + * src/Makefile.am: Updated accordingly. + * src/object.h, src/being.h: Changed definition of directions. + * src/being.cpp: Relied on MapComposite iterators to scan only beings + in the vincinity one time instead of all objects of the map four times. + Used a pixel-based zone instead of tile-based zone for damaging. + * src/player.cpp: Removed useless dependency. + * src/game-server/mapcomposite.hpp, src/game-server/mapcomposite.cpp: + Added a radius parameter to iterator creators. Removed unused and + inefficient getObjectsOnTile. + * src/game-server/state.hpp, src/game-server/state.cpp: Split update + function into updateMap and informPlayer. Simplified code a bit. + 2006-12-29 Guillaume Melquiond * src/account.h, src/account.cpp, src/accountclient.h, diff --git a/src/Makefile.am b/src/Makefile.am index c92b516b..49e49fb4 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -94,8 +94,6 @@ tmwserv_game_SOURCES = \ item.cpp \ map.h \ map.cpp \ - mapcomposite.h \ - mapcomposite.cpp \ mapreader.h \ mapreader.cpp \ object.h \ @@ -116,6 +114,8 @@ tmwserv_game_SOURCES = \ game-server/gamehandler.cpp \ game-server/itemmanager.hpp \ game-server/itemmanager.cpp \ + game-server/mapcomposite.hpp \ + game-server/mapcomposite.cpp \ game-server/mapmanager.hpp \ game-server/mapmanager.cpp \ game-server/state.hpp \ diff --git a/src/being.cpp b/src/being.cpp index 6f8b7028..cece203a 100644 --- a/src/being.cpp +++ b/src/being.cpp @@ -21,7 +21,7 @@ */ #include "being.h" -#include "mapcomposite.h" +#include "game-server/mapcomposite.hpp" #include "utils/logger.h" void Being::damage(Damage damage) @@ -35,78 +35,53 @@ void Being::damage(Damage damage) LOG_DEBUG("Being " << getPublicID() << " got hit", 0); } -void Being::performAttack(MapComposite* map) +void Being::performAttack(MapComposite *map) { - std::list victimList; - std::list attackZone; + int SHORT_RANGE = 32; + Point ppos = getPosition(); + int dir = getDirection(); - Point attackPoint = getPosition(); + /* TODO: calculate real attack power and damage properties based on + character equipment and stats. */ + Damage damage = 1; - unsigned char direction = getDirection(); - if (direction & UP) + for (MovingObjectIterator i(map->getAroundObjectIterator(this, SHORT_RANGE)); i; ++i) { - attackPoint.y -= 32; - attackPoint.x -= 32; - attackZone.push_back(attackPoint); - attackPoint.x += 32; - attackZone.push_back(attackPoint); - attackPoint.x += 32; - attackZone.push_back(attackPoint); - } - else if (direction & RIGHT) - { - attackPoint.x += 32; - attackPoint.y -= 32; - attackZone.push_back(attackPoint); - attackPoint.y += 32; - attackZone.push_back(attackPoint); - attackPoint.y += 32; - attackZone.push_back(attackPoint); - } - else if (direction & DOWN) - { - attackPoint.y += 32; - attackPoint.x -= 32; - attackZone.push_back(attackPoint); - attackPoint.x += 32; - attackZone.push_back(attackPoint); - attackPoint.x += 32; - attackZone.push_back(attackPoint); - } - else { - attackPoint.x -= 32; - attackPoint.y -= 32; - attackZone.push_back(attackPoint); - attackPoint.y += 32; - attackZone.push_back(attackPoint); - attackPoint.y += 32; - attackZone.push_back(attackPoint); - } - - attackZone.push_back(attackPoint); // point player is facing - - // get enemies to hurt - for (std::list::iterator i = attackZone.begin(), - i_end = attackZone.end(); i != i_end; ++i) - { - std::list newVictimList = map->getObjectsOnTile((*i)); - victimList.splice(victimList.end(), newVictimList); - } + MovingObject *o = *i; + if (o == this) + { + continue; + } - // apply damage to victims - Damage damage; + int type = o->getType(); + Point opos = o->getPosition(); + int dx = opos.x - ppos.x, dy = opos.y - ppos.y; - /* TODO: calculate real attack power and damage properties based on - * character equipment and stats - */ - damage = 1; + if ((type != OBJECT_PLAYER && type != OBJECT_MONSTER) || + (std::abs(dx) > SHORT_RANGE || std::abs(dy) > SHORT_RANGE)) + { + continue; + } - for (std::list::iterator i = victimList.begin(), - i_end = victimList.end(); i != i_end; ++i) - { - if ((*i)->getType() == OBJECT_PLAYER || (*i)->getType() == OBJECT_MONSTER) + // basic triangle-shaped damage zone + switch (dir) { - static_cast(&**i)->damage(damage); + case DIRECTION_UP: + if (!(dy <= dx && dx <= -dy)) continue; + break; + case DIRECTION_DOWN: + if (!(-dy <= dx && dx <= dy)) continue; + break; + case DIRECTION_LEFT: + if (!(dx <= dy && dy <= -dx)) continue; + break; + case DIRECTION_RIGHT: + if (!(-dx <= dy && dy <= dx)) continue; + break; + default: + break; } + + static_cast< Being * >(o)->damage(damage); } } diff --git a/src/being.h b/src/being.h index 80d5d696..760bea73 100644 --- a/src/being.h +++ b/src/being.h @@ -90,16 +90,12 @@ typedef enum { /** * Beings and actors directions */ -typedef enum { - DIRECTION_NORTH, - DIRECTION_NORTHWEST, - DIRECTION_NORTHEAST, - DIRECTION_WEST, - DIRECTION_EAST, - DIRECTION_SOUTH, - DIRECTION_SOUTHWEST, - DIRECTION_SOUTHEAST -} SpriteDirection; +enum { + DIRECTION_DOWN = 1, + DIRECTION_UP, + DIRECTION_LEFT, + DIRECTION_RIGHT +}; /** * Raw statistics of a Player. diff --git a/src/game-server/mapcomposite.cpp b/src/game-server/mapcomposite.cpp new file mode 100644 index 00000000..1591ad9f --- /dev/null +++ b/src/game-server/mapcomposite.cpp @@ -0,0 +1,470 @@ +/* + * The Mana World Server + * Copyright 2006 The Mana World Development Team + * + * This file is part of The Mana World. + * + * The Mana World 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 + * any later version. + * + * The Mana World 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 The Mana World; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * $Id$ + */ + +#include +#include + +#include "map.h" +#include "game-server/mapcomposite.hpp" + +/* TODO: Implement overlapping map zones instead of strict partitioning. + Purpose: to decrease the number of zone changes, as overlapping allows for + hysteresis effect and prevents an object from changing zone each server + tick. It requires storing the zone in the object since it will not be + uniquely defined any longer. */ + +/* Pixel-based width and height of the squares used in partitioning the map. + Squares should be big enough so that a moving object cannot cross several + ones in one world tick. + TODO: Tune for decreasing server load. The higher the value, the closer we + regress to quadratic behavior; the lower the value, the more we waste time + in dealing with zone changes. */ +static int const zoneDiam = 256; + +void MapZone::insert(Object *obj) +{ + int type = obj->getType(); + switch (type) + { + case OBJECT_PLAYER: + { + if (nbPlayers != nbMovingObjects) + { + if (nbMovingObjects != objects.size()) + { + objects.push_back(objects[nbMovingObjects]); + objects[nbMovingObjects] = objects[nbPlayers]; + } + else + { + objects.push_back(objects[nbPlayers]); + } + objects[nbPlayers] = obj; + ++nbPlayers; + ++nbMovingObjects; + break; + } + ++nbPlayers; + } // no break! + case OBJECT_MONSTER: + case OBJECT_NPC: + { + if (nbMovingObjects != objects.size()) + { + objects.push_back(objects[nbMovingObjects]); + objects[nbMovingObjects] = obj; + ++nbMovingObjects; + break; + } + ++nbMovingObjects; + } // no break! + default: + { + objects.push_back(obj); + } + } +} + +void MapZone::remove(Object *obj) +{ + std::vector< Object * >::iterator i_beg = objects.begin(), i, i_end; + int type = obj->getType(); + switch (type) + { + case OBJECT_PLAYER: + { + i = i_beg; + i_end = objects.begin() + nbPlayers; + } break; + case OBJECT_MONSTER: + case OBJECT_NPC: + { + i = objects.begin() + nbPlayers; + i_end = objects.begin() + nbMovingObjects; + } break; + default: + { + i = objects.begin() + nbMovingObjects; + i_end = objects.end(); + } + } + i = std::find(i, i_end, obj); + assert(i != i_end); + unsigned pos = i - i_beg; + if (pos < nbPlayers) + { + objects[pos] = objects[nbPlayers - 1]; + pos = nbPlayers - 1; + --nbPlayers; + } + if (pos < nbMovingObjects) + { + objects[pos] = objects[nbMovingObjects - 1]; + pos = nbMovingObjects - 1; + --nbMovingObjects; + } + objects[pos] = objects[objects.size() - 1]; + objects.pop_back(); +} + +static void addZone(MapRegion &r, unsigned z) +{ + MapRegion::iterator i_end = r.end(), + i = std::lower_bound(r.begin(), i_end, z); + if (i == i_end || *i != z) + { + r.insert(i, z); + } +} + +ZoneIterator::ZoneIterator(MapRegion const &r, MapComposite const *m) + : region(r), pos(0), map(m) +{ + current = &map->zones[r.empty() ? 0 : r[0]]; +} + +void ZoneIterator::operator++() +{ + current = NULL; + if (!region.empty()) + { + if (++pos != region.size()) + { + current = &map->zones[region[pos]]; + } + } + else + { + if (++pos != (unsigned)map->mapWidth * map->mapHeight) + { + current = &map->zones[pos]; + } + } +} + +PlayerIterator::PlayerIterator(ZoneIterator const &it) + : iterator(it), pos(0) +{ + while (iterator && (*iterator)->nbPlayers == 0) ++iterator; + if (iterator) + { + current = static_cast< Player * >((*iterator)->objects[pos]); + } +} + +void PlayerIterator::operator++() +{ + if (++pos == (*iterator)->nbPlayers) + { + do ++iterator; while (iterator && (*iterator)->nbPlayers == 0); + pos = 0; + } + if (iterator) + { + current = static_cast< Player * >((*iterator)->objects[pos]); + } +} + +MovingObjectIterator::MovingObjectIterator(ZoneIterator const &it) + : iterator(it), pos(0) +{ + while (iterator && (*iterator)->nbMovingObjects == 0) ++iterator; + if (iterator) + { + current = static_cast< MovingObject * >((*iterator)->objects[pos]); + } +} + +void MovingObjectIterator::operator++() +{ + if (++pos == (*iterator)->nbMovingObjects) + { + do ++iterator; while (iterator && (*iterator)->nbMovingObjects == 0); + pos = 0; + } + if (iterator) + { + current = static_cast< MovingObject * >((*iterator)->objects[pos]); + } +} + +ObjectIterator::ObjectIterator(ZoneIterator const &it) + : iterator(it), pos(0) +{ + while (iterator && (*iterator)->objects.empty()) ++iterator; + if (iterator) + { + current = (*iterator)->objects[pos]; + } +} + +void ObjectIterator::operator++() +{ + if (++pos == (*iterator)->objects.size()) + { + do ++iterator; while (iterator && (*iterator)->objects.empty()); + pos = 0; + } + if (iterator) + { + current = (*iterator)->objects[pos]; + } +} + +ObjectBucket::ObjectBucket() + : free(256), next_object(0) +{ + for (unsigned i = 0; i < 256 / int_bitsize; ++i) + { + bitmap[i] = ~0; + } +} + +int ObjectBucket::allocate() +{ + if (!free) + { + return -1; + } + + if (bitmap[next_object / int_bitsize] & (1 << (next_object % int_bitsize))) + { + bitmap[next_object / int_bitsize] &= ~(1 << (next_object % int_bitsize)); + int i = next_object; + next_object = (i + 1) & 255; + --free; + return i; + } + + for (unsigned i = 0; i < 256 / int_bitsize; ++i) + { + int k = (i + next_object / int_bitsize) & 255; + if (unsigned b = bitmap[k]) + { + int j = 0; + while (!(b & 1)) + { + b >>= 1; + ++j; + } + bitmap[k] &= ~(1 << j); + j += k * int_bitsize; + next_object = (j + 1) & 255; + --free; + return j; + } + } + return -1; +} + +void ObjectBucket::deallocate(int i) +{ + assert(!(bitmap[i / int_bitsize] & (1 << (i % int_bitsize)))); + bitmap[i / int_bitsize] |= 1 << (i % int_bitsize); + ++free; +} + +MapComposite::MapComposite(Map *m) + : map(m), last_bucket(0) +{ + buckets[0] = new ObjectBucket; + for (int i = 1; i < 256; ++i) + { + buckets[i] = NULL; + } + mapWidth = (map->getWidth() * 32 + zoneDiam - 1) / zoneDiam; + mapHeight = (map->getHeight() * 32 + zoneDiam - 1) / zoneDiam; + zones = new MapZone[mapWidth * mapHeight]; +} + +MapComposite::~MapComposite() +{ + for (int i = 0; i < 256; ++i) + { + delete buckets[i]; + } + delete[] zones; + delete map; +} + +bool MapComposite::allocate(MovingObject *obj) +{ + // First, try allocating from the last used bucket. + ObjectBucket *b = buckets[last_bucket]; + int i = b->allocate(); + if (i >= 0) + { + b->objects[i] = obj; + obj->setPublicID(last_bucket * 256 + i); + return true; + } + + /* If the last used bucket is already full, scan all the buckets for an + empty place. If none is available, create a new bucket. */ + for (i = 0; i < 256; ++i) + { + b = buckets[i]; + if (!b) + { + b = new ObjectBucket; + buckets[i] = b; + } + int j = b->allocate(); + if (j >= 0) + { + last_bucket = i; + b->objects[j] = obj; + obj->setPublicID(last_bucket * 256 + j); + return true; + } + } + + // All the IDs are currently used, fail. + return false; +} + +void MapComposite::deallocate(MovingObject *obj) +{ + unsigned short id = obj->getPublicID(); + buckets[id / 256]->deallocate(id % 256); +} + +void MapComposite::fillRegion(MapRegion &r, Point const &p, int radius) const +{ + int ax = p.x > radius ? (p.x - radius) / zoneDiam : 0, + ay = p.y > radius ? (p.y - radius) / zoneDiam : 0, + bx = std::max((p.x + radius) / zoneDiam, mapWidth - 1), + by = std::max((p.y + radius) / zoneDiam, mapHeight - 1); + for (int y = ay; y <= by; ++y) + { + for (int x = ax; x <= bx; ++x) + { + addZone(r, x + y * mapWidth); + } + } +} + +ZoneIterator MapComposite::getAroundObjectIterator(Object *obj, int radius) const +{ + MapRegion r; + fillRegion(r, obj->getPosition(), radius); + return ZoneIterator(r, this); +} + +ZoneIterator MapComposite::getAroundPlayerIterator(Player *obj, int radius) const +{ + MapRegion r1; + fillRegion(r1, obj->getOldPosition(), radius); + MapRegion r2 = r1; + for (MapRegion::iterator i = r1.begin(), i_end = r1.end(); i != i_end; ++i) + { + /* Fills region with destinations taken around the old position. + This is necessary to detect two moving objects changing zones at the + same time and at the border, and going in opposite directions (or + more simply to detect teleportations, if any). */ + MapRegion &r4 = zones[*i].destinations; + if (!r4.empty()) + { + MapRegion r3; + r3.reserve(r2.size() + r4.size()); + std::set_union(r2.begin(), r2.end(), r4.begin(), r4.end(), + std::back_insert_iterator< MapRegion >(r3)); + r2.swap(r3); + } + } + fillRegion(r2, obj->getPosition(), radius); + return ZoneIterator(r2, this); +} + +bool MapComposite::insert(ObjectPtr obj) +{ + Point const &pos = obj->getPosition(); + zones[(pos.x / zoneDiam) + (pos.y / zoneDiam) * mapWidth].insert(obj.get()); + + int type = obj->getType(); + if (type == OBJECT_MONSTER || type == OBJECT_PLAYER || type == OBJECT_NPC) + { + if (!allocate(static_cast< MovingObject * >(obj.get()))) + { + return false; + } + } + + objects.push_back(obj); + return true; +} + +void MapComposite::remove(ObjectPtr obj) +{ + Point const &pos = obj->getPosition(); + zones[(pos.x / zoneDiam) + (pos.y / zoneDiam) * mapWidth].remove(obj.get()); + + int type = obj->getType(); + if (type == OBJECT_MONSTER || type == OBJECT_PLAYER || type == OBJECT_NPC) + { + deallocate(static_cast< MovingObject * >(obj.get())); + } + + for (Objects::iterator o = objects.begin(), + o_end = objects.end(); o != o_end; ++o) + { + if (o->get() == obj.get()) + { + *o = *(o_end - 1); + objects.pop_back(); + return; + } + } + assert(false); +} + +void MapComposite::update() +{ + for (int i = 0; i < mapHeight * mapWidth; ++i) + { + zones[i].destinations.clear(); + } + + // Cannot use a WholeMap iterator as objects will change zones under its feet. + for (Objects::iterator o = objects.begin(), + o_end = objects.end(); o != o_end; ++o) + { + int type = (*o)->getType(); + if (type != OBJECT_PLAYER && type != OBJECT_MONSTER && type != OBJECT_NPC) + { + continue; + } + MovingObject *obj = static_cast< MovingObject * >(o->get()); + + Point const &pos1 = obj->getOldPosition(), + &pos2 = obj->getPosition(); + int src = (pos1.x / zoneDiam) + (pos1.y / zoneDiam) * mapWidth, + dst = (pos2.x / zoneDiam) + (pos2.y / zoneDiam) * mapWidth; + if (src != dst) + { + addZone(zones[src].destinations, dst); + zones[src].remove(obj); + zones[dst].insert(obj); + } + } +} diff --git a/src/game-server/mapcomposite.hpp b/src/game-server/mapcomposite.hpp new file mode 100644 index 00000000..663271dd --- /dev/null +++ b/src/game-server/mapcomposite.hpp @@ -0,0 +1,234 @@ +/* + * The Mana World Server + * Copyright 2006 The Mana World Development Team + * + * This file is part of The Mana World. + * + * The Mana World 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 + * any later version. + * + * The Mana World 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 The Mana World; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * $Id$ + */ + +#ifndef _TMW_SERVER_MAPCOMPOSITE_ +#define _TMW_SERVER_MAPCOMPOSITE_ + +#include + +#include "object.h" +#include "player.h" + +class Map; +class MapComposite; + +/** + * Ordered sets of zones of a map. + */ +typedef std::vector< unsigned > MapRegion; + +/** + * Part of the map. + */ +struct MapZone +{ + unsigned short nbPlayers, nbMovingObjects; + /** + * Objects present in this zone. + * Players are stored first, then the remaining MovingObjects, then the + * remaining Objects. + */ + std::vector< Object * > objects; + + /** + * Destinations of the objects that left this zone. + * This is necessary in order to have an accurate iterator around moving + * objects. + */ + MapRegion destinations; + + MapZone(): nbPlayers(0), nbMovingObjects(0) {} + void insert(Object *); + void remove(Object *); +}; + +/** + * Iterates through the zones of a region of the map. + */ +struct ZoneIterator +{ + MapRegion region; /**< Zones to visit. Empty means the entire map. */ + unsigned pos; + MapZone *current; + MapComposite const *map; + + ZoneIterator(MapRegion const &, MapComposite const *); + void operator++(); + MapZone *operator*() const { return current; } + operator bool() const { return current; } +}; + +/** + * Iterates through the Players of a region. + */ +struct PlayerIterator +{ + ZoneIterator iterator; + unsigned short pos; + Player *current; + + PlayerIterator(ZoneIterator const &); + void operator++(); + Player *operator*() const { return current; } + operator bool() const { return iterator; } +}; + +/** + * Iterates through the MovingObjects of a region. + */ +struct MovingObjectIterator +{ + ZoneIterator iterator; + unsigned short pos; + MovingObject *current; + + MovingObjectIterator(ZoneIterator const &); + void operator++(); + MovingObject *operator*() const { return current; } + operator bool() const { return iterator; } +}; + +/** + * Iterates through the Objects of a region. + */ +struct ObjectIterator +{ + ZoneIterator iterator; + unsigned short pos; + Object *current; + + ObjectIterator(ZoneIterator const &); + void operator++(); + Object *operator*() const { return current; } + operator bool() const { return iterator; } +}; + +/** + * Pool of public IDs for MovingObjects on a map. + */ +struct ObjectBucket +{ + static int const int_bitsize = sizeof(unsigned) * 8; + unsigned bitmap[256 / int_bitsize]; /**< Bitmap of free locations. */ + short free; /**< Number of empty places. */ + short next_object; /**< Next object to look at. */ + MovingObject *objects[256]; + + ObjectBucket(); + int allocate(); + void deallocate(int); +}; + +/** + * Combined map/entity structure. + */ +class MapComposite { + + public: + MapComposite(Map *); + ~MapComposite(); + + Map *getMap() const + { return map; } + + /** + * Inserts an object on the map and sets its public ID. + */ + bool insert(ObjectPtr); + + /** + * Removes an object from the map. + */ + void remove(ObjectPtr); + + /** + * Updates zones of every moving beings. + */ + void update(); + + /** + * Gets an object given its ID. + */ + MovingObject *getObjectByID(int) const; + + /** + * Gets an iterator on the objects of the whole map. + */ + ZoneIterator getWholeMapIterator() const + { return ZoneIterator(MapRegion(), this); } + + /** + * Gets an iterator on the objects around a given object. + */ + ZoneIterator getAroundObjectIterator(Object *, int radius) const; + + /** + * Gets an iterator on the objects around the old and new positions of + * a player (including the ones that were but are now elsewhere). + */ + ZoneIterator getAroundPlayerIterator(Player *, int radius) const; + + private: + MapComposite(MapComposite const &); + + /** + * Allocates a unique ID for a moving object on this map. + */ + bool allocate(MovingObject *); + + /** + * Deallocates an ID. + */ + void deallocate(MovingObject *); + + /** + * Fills a region of zones within the range of a point. + */ + void fillRegion(MapRegion &, Point const &, int) const; + + Map *map; /**< Actual map. */ + + /** + * Objects (items, players, monsters, etc) located on the map. + */ + Objects objects; + + /** + * Buckets of MovingObjects located on the map, referenced by ID. + */ + ObjectBucket *buckets[256]; + + int last_bucket; /**< Last bucket acted upon. */ + + /** + * Partition of the Objects, depending on their position on the map. + */ + MapZone *zones; + + unsigned short mapWidth; /**< Width with respect to zones. */ + unsigned short mapHeight; /**< Height with respect to zones. */ + + friend class ZoneIterator; +}; + +#endif diff --git a/src/game-server/state.cpp b/src/game-server/state.cpp index 3bb2e478..95e093c2 100644 --- a/src/game-server/state.cpp +++ b/src/game-server/state.cpp @@ -24,10 +24,11 @@ #include #include "controller.h" +#include "defines.h" #include "map.h" -#include "mapcomposite.h" #include "point.h" #include "game-server/gamehandler.hpp" +#include "game-server/mapcomposite.hpp" #include "game-server/mapmanager.hpp" #include "game-server/state.hpp" #include "net/messageout.hpp" @@ -56,182 +57,190 @@ State::~State() } } -void -State::update() +void State::updateMap(MapComposite *map) { - /* - * Update game state (update AI, etc.) - */ - for (std::map< unsigned, MapComposite * >::iterator m = maps.begin(), - m_end = maps.end(); m != m_end; ++m) + // 1. update object status. + for (ObjectIterator i(map->getWholeMapIterator()); i; ++i) { - MapComposite *map = m->second; + (*i)->update(); + } - for (ObjectIterator o(map->getWholeMapIterator()); o; ++o) + // 2. perform attacks. + for (MovingObjectIterator i(map->getWholeMapIterator()); i; ++i) + { + MovingObject *o = *i; + if (o->getUpdateFlags() & ATTACK) { - (*o)->update(); - if ((*o)->getType() == OBJECT_PLAYER || (*o)->getType() == OBJECT_MONSTER) - { - static_cast< Being * >(*o)->clearHitsTaken(); - } + static_cast< Being * >(o)->performAttack(map); } + } + + // 3. move objects around and update zones. + for (MovingObjectIterator i(map->getWholeMapIterator()); i; ++i) + { + (*i)->move(); + } + map->update(); +} + +void State::informPlayer(MapComposite *map, Player *p) +{ + MessageOut moveMsg(GPMSG_BEINGS_MOVE); + MessageOut damageMsg(GPMSG_BEINGS_DAMAGE); + Point pold = p->getOldPosition(), ppos = p->getPosition(); + int pid = p->getPublicID(), pflags = p->getUpdateFlags(); + + for (MovingObjectIterator i(map->getAroundPlayerIterator(p, AROUND_AREA)); i; ++i) + { + MovingObject *o = *i; - for (MovingObjectIterator o(map->getWholeMapIterator()); o; ++o) + Point oold = o->getOldPosition(), opos = o->getPosition(); + int otype = o->getType(); + int oid = o->getPublicID(), oflags = o->getUpdateFlags(); + int flags = 0; + + // Send attack messages. + if ((oflags & ATTACK) && oid != pid && ppos.inRangeOf(opos)) { - if ((*o)->getUpdateFlags() & ATTACK) - { - static_cast< Being * >(*o)->performAttack(m->second); - } + MessageOut AttackMsg(GPMSG_BEING_ATTACK); + AttackMsg.writeShort(oid); + gameHandler->sendTo(p, AttackMsg); } - for (MovingObjectIterator o(map->getWholeMapIterator()); o; ++o) + // Send damage messages. + if (otype == OBJECT_PLAYER || otype == OBJECT_MONSTER) { - (*o)->move(); + Being *victim = static_cast< Being * >(o); + Hits const &hits = victim->getHitsTaken(); + for (Hits::const_iterator j = hits.begin(), + j_end = hits.end(); j != j_end; ++j) + { + damageMsg.writeShort(oid); + damageMsg.writeShort(*j); + } } - map->update(); + /* Check whether this player and this moving object were around + the last time and whether they will be around the next time. */ + bool wereInRange = pold.inRangeOf(oold) && + !((pflags | oflags) & NEW_ON_MAP); + bool willBeInRange = ppos.inRangeOf(opos); - /* - * Inform clients about changes in the game state - */ - for (PlayerIterator p(map->getWholeMapIterator()); p; ++p) + // Send enter/leaver messages. + if (!wereInRange) { - MessageOut moveMsg(GPMSG_BEINGS_MOVE); - MessageOut damageMsg(GPMSG_BEINGS_DAMAGE); - - for (MovingObjectIterator o(map->getAroundPlayerIterator(*p)); o; ++o) + // o was outside p's range. + if (!willBeInRange) { + // Nothing to report: o will not be inside p's range. + continue; + } + flags |= MOVING_DESTINATION; - Point os = (*o)->getOldPosition(); - Point on = (*o)->getPosition(); - - int flags = 0; - - // Send attack messages - if ( (*o)->getUpdateFlags() & ATTACK - && (*o)->getPublicID() != (*p)->getPublicID() - && (*p)->getPosition().inRangeOf(on) - ) + MessageOut enterMsg(GPMSG_BEING_ENTER); + enterMsg.writeByte(otype); + enterMsg.writeShort(oid); + switch (otype) { + case OBJECT_PLAYER: { - MessageOut AttackMsg (GPMSG_BEING_ATTACK); - AttackMsg.writeShort((*o)->getPublicID()); - - LOG_DEBUG("Sending attack packet from " << (*o)->getPublicID() - << " to " << (*p)->getPublicID(), 0); + Player *q = static_cast< Player * >(o); + enterMsg.writeString(q->getName()); + enterMsg.writeByte(q->getHairStyle()); + enterMsg.writeByte(q->getHairColor()); + enterMsg.writeByte(q->getGender()); + } break; + case OBJECT_MONSTER: + { + enterMsg.writeShort(0); // TODO: The monster ID + } break; + default: + assert(false); // TODO + } + gameHandler->sendTo(p, enterMsg); + } + else if (!willBeInRange) + { + // o is no longer visible from p. + MessageOut leaveMsg(GPMSG_BEING_LEAVE); + leaveMsg.writeShort(oid); + gameHandler->sendTo(p, leaveMsg); + continue; + } + else if (oold.x == opos.x && oold.y == opos.y) + { + // o does not move, nothing to report. + continue; + } - gameHandler->sendTo(*p, AttackMsg); - } + /* At this point, either o has entered p's range, either o is + moving inside p's range. Report o's movements. */ - // Send damage messages + Point odst = o->getDestination(); + if (opos.x != odst.x || opos.y != odst.y) + { + flags |= MOVING_POSITION; + if (oflags & NEW_DESTINATION) + { + flags |= MOVING_DESTINATION; + } + } + else + { + // No need to synchronize on the very last step. + flags |= MOVING_DESTINATION; + } - if ((*o)->getType() == OBJECT_PLAYER || (*o)->getType() == OBJECT_MONSTER) - { - Being *victim = static_cast< Being * >(*o); - Hits const &hits = victim->getHitsTaken(); - for (Hits::const_iterator i = hits.begin(), - i_end = hits.end(); i != i_end; ++i) - { - damageMsg.writeShort(victim->getPublicID()); - damageMsg.writeShort((*i)); - } - } - - // Send move messages - - /* Check whether this player and this moving object were around - * the last time and whether they will be around the next time. - */ - bool wereInRange = (*p)->getOldPosition().inRangeOf(os) && - !(((*p)->getUpdateFlags() | (*o)->getUpdateFlags()) & NEW_ON_MAP); - bool willBeInRange = (*p)->getPosition().inRangeOf(on); - if (!wereInRange) - { - // o was outside p's range. - if (!willBeInRange) - { - // Nothing to report: o will not be inside p's range. - continue; - } - flags |= MOVING_DESTINATION; - - int type = (*o)->getType(); - MessageOut enterMsg(GPMSG_BEING_ENTER); - enterMsg.writeByte(type); - enterMsg.writeShort((*o)->getPublicID()); - switch (type) { - case OBJECT_PLAYER: - { - Player *q = static_cast< Player * >(*o); - enterMsg.writeString(q->getName()); - enterMsg.writeByte(q->getHairStyle()); - enterMsg.writeByte(q->getHairColor()); - enterMsg.writeByte(q->getGender()); - } break; - case OBJECT_MONSTER: - { - enterMsg.writeShort(0); // TODO: The monster ID - } break; - default: - assert(false); // TODO - } - gameHandler->sendTo(*p, enterMsg); - } - else if (!willBeInRange) - { - // o is no longer visible from p. - MessageOut leaveMsg(GPMSG_BEING_LEAVE); - leaveMsg.writeShort((*o)->getPublicID()); - gameHandler->sendTo(*p, leaveMsg); - continue; - } - else if (os.x == on.x && os.y == on.y) - { - // o does not move, nothing to report. - continue; - } + // Send move messages. + moveMsg.writeShort(oid); + moveMsg.writeByte(flags); + if (flags & MOVING_POSITION) + { + moveMsg.writeCoordinates(opos.x / 32, opos.y / 32); + } + if (flags & MOVING_DESTINATION) + { + moveMsg.writeShort(odst.x); + moveMsg.writeShort(odst.y); + } + } - /* At this point, either o has entered p's range, either o is - moving inside p's range. Report o's movements. */ + // Do not send a packet if nothing happened in p's range. + if (moveMsg.getLength() > 2) + gameHandler->sendTo(p, moveMsg); - Point od = (*o)->getDestination(); - if (on.x != od.x || on.y != od.y) - { - flags |= MOVING_POSITION; - if ((*o)->getUpdateFlags() & NEW_DESTINATION) - { - flags |= MOVING_DESTINATION; - } - } - else - { - // no need to synchronize on the very last step - flags |= MOVING_DESTINATION; - } + if (damageMsg.getLength() > 2) + gameHandler->sendTo(p, damageMsg); +} - moveMsg.writeShort((*o)->getPublicID()); - moveMsg.writeByte(flags); - if (flags & MOVING_POSITION) - { - moveMsg.writeCoordinates(on.x / 32, on.y / 32); - } - if (flags & MOVING_DESTINATION) - { - moveMsg.writeShort(od.x); - moveMsg.writeShort(od.y); - } - } +void State::update() +{ + /* + * Update game state (update AI, etc.) + */ + for (std::map< unsigned, MapComposite * >::iterator m = maps.begin(), + m_end = maps.end(); m != m_end; ++m) + { + MapComposite *map = m->second; - // Don't send a packet if nothing happened in p's range. - if (moveMsg.getLength() > 2) - gameHandler->sendTo(*p, moveMsg); + updateMap(map); - if (damageMsg.getLength() > 2) - gameHandler->sendTo(*p, damageMsg); + /* + * Inform clients about changes in the game state + */ + for (PlayerIterator p(map->getWholeMapIterator()); p; ++p) + { + informPlayer(map, *p); } - for (ObjectIterator o(map->getWholeMapIterator()); o; ++o) + for (ObjectIterator i(map->getWholeMapIterator()); i; ++i) { - (*o)->clearUpdateFlags(); + Object *o = *i; + o->clearUpdateFlags(); + int type = o->getType(); + if (type == OBJECT_PLAYER || type == OBJECT_MONSTER) + { + static_cast< Being * >(o)->clearHitsTaken(); + } } } } @@ -278,7 +287,7 @@ State::removeObject(ObjectPtr objectPtr) msg.writeShort(obj->getPublicID()); Point objectPos = obj->getPosition(); - for (PlayerIterator p(map->getAroundObjectIterator(obj)); p; ++p) + for (PlayerIterator p(map->getAroundObjectIterator(obj, AROUND_AREA)); p; ++p) { if (*p != obj && objectPos.inRangeOf((*p)->getPosition())) { @@ -321,7 +330,7 @@ void State::sayAround(Object *obj, std::string text) MapComposite *map = m->second; Point speakerPosition = obj->getPosition(); - for (PlayerIterator i(map->getAroundObjectIterator(obj)); i; ++i) + for (PlayerIterator i(map->getAroundObjectIterator(obj, AROUND_AREA)); i; ++i) { if (speakerPosition.inRangeOf((*i)->getPosition())) { diff --git a/src/game-server/state.hpp b/src/game-server/state.hpp index 36bd87d0..7fcfcf2f 100644 --- a/src/game-server/state.hpp +++ b/src/game-server/state.hpp @@ -37,39 +37,49 @@ class MapComposite; */ class State { - /** - * List of maps. - */ - std::map maps; + /** + * List of maps. + */ + std::map maps; - public: - State(); - ~State(); + /** + * Updates object states on the map. + */ + void updateMap(MapComposite *); - /** - * Update game state (contains core server logic). - */ - void update(); + /** + * Informs a player of what happened around. + */ + void informPlayer(MapComposite *, Player *); - /** - * Load map into game world. - */ - MapComposite *loadMap(unsigned mapId); + public: + State(); + ~State(); - /** - * Add object to the map. - */ - void addObject(ObjectPtr objectPtr); + /** + * Updates game state (contains core server logic). + */ + void update(); - /** - * Remove an object from the map. - */ - void removeObject(ObjectPtr objectPtr); + /** + * Loads map into game world. + */ + MapComposite *loadMap(unsigned mapId); - /** - * Say around an object. - */ - void sayAround(Object *, std::string text); + /** + * Adds object to the map. + */ + void addObject(ObjectPtr objectPtr); + + /** + * Removes an object from the map. + */ + void removeObject(ObjectPtr objectPtr); + + /** + * Says something around an object. + */ + void sayAround(Object *, std::string text); }; extern State *gameState; diff --git a/src/mapcomposite.cpp b/src/mapcomposite.cpp deleted file mode 100644 index 35038abf..00000000 --- a/src/mapcomposite.cpp +++ /dev/null @@ -1,497 +0,0 @@ -/* - * The Mana World Server - * Copyright 2006 The Mana World Development Team - * - * This file is part of The Mana World. - * - * The Mana World 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 - * any later version. - * - * The Mana World 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 The Mana World; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - * - * $Id$ - */ - -#include "mapcomposite.h" - -#include -#include - -#include "defines.h" -#include "map.h" - -/* TODO: Implement overlapping map zones instead of strict partitioning. - Purpose: to decrease the number of zone changes, as overlapping allows for - hysteresis effect and prevents an object from changing zone each server - tick. It requires storing the zone in the object since it will not be - uniquely defined any longer. */ - -/* Pixel-based width and height of the squares used in partitioning the map. - TODO: Tune for decreasing server load. The higher the value, the closer we - regress to quadratic behavior; the lower the value, the more we waste time - in dealing with zone changes. */ -static int const zoneDiam = 256; - -void MapZone::insert(Object *obj) -{ - int type = obj->getType(); - switch (type) - { - case OBJECT_PLAYER: - { - if (nbPlayers != nbMovingObjects) - { - if (nbMovingObjects != objects.size()) - { - objects.push_back(objects[nbMovingObjects]); - objects[nbMovingObjects] = objects[nbPlayers]; - } - else - { - objects.push_back(objects[nbPlayers]); - } - objects[nbPlayers] = obj; - ++nbPlayers; - ++nbMovingObjects; - break; - } - ++nbPlayers; - } // no break! - case OBJECT_MONSTER: - case OBJECT_NPC: - { - if (nbMovingObjects != objects.size()) - { - objects.push_back(objects[nbMovingObjects]); - objects[nbMovingObjects] = obj; - ++nbMovingObjects; - break; - } - ++nbMovingObjects; - } // no break! - default: - { - objects.push_back(obj); - } - } -} - -void MapZone::remove(Object *obj) -{ - std::vector< Object * >::iterator i_beg = objects.begin(), i, i_end; - int type = obj->getType(); - switch (type) - { - case OBJECT_PLAYER: - { - i = i_beg; - i_end = objects.begin() + nbPlayers; - } break; - case OBJECT_MONSTER: - case OBJECT_NPC: - { - i = objects.begin() + nbPlayers; - i_end = objects.begin() + nbMovingObjects; - } break; - default: - { - i = objects.begin() + nbMovingObjects; - i_end = objects.end(); - } - } - i = std::find(i, i_end, obj); - assert(i != i_end); - unsigned pos = i - i_beg; - if (pos < nbPlayers) - { - objects[pos] = objects[nbPlayers - 1]; - pos = nbPlayers - 1; - --nbPlayers; - } - if (pos < nbMovingObjects) - { - objects[pos] = objects[nbMovingObjects - 1]; - pos = nbMovingObjects - 1; - --nbMovingObjects; - } - objects[pos] = objects[objects.size() - 1]; - objects.pop_back(); -} - -static void addZone(MapRegion &r, unsigned z) -{ - MapRegion::iterator i_end = r.end(), - i = std::lower_bound(r.begin(), i_end, z); - if (i == i_end || *i != z) - { - r.insert(i, z); - } -} - -ZoneIterator::ZoneIterator(MapRegion const &r, MapComposite const *m) - : region(r), pos(0), map(m) -{ - current = &map->zones[r.empty() ? 0 : r[0]]; -} - -void ZoneIterator::operator++() -{ - current = NULL; - if (!region.empty()) - { - if (++pos != region.size()) - { - current = &map->zones[region[pos]]; - } - } - else - { - if (++pos != (unsigned)map->mapWidth * map->mapHeight) - { - current = &map->zones[pos]; - } - } -} - -PlayerIterator::PlayerIterator(ZoneIterator const &it) - : iterator(it), pos(0) -{ - while (iterator && (*iterator)->nbPlayers == 0) ++iterator; - if (iterator) - { - current = static_cast< Player * >((*iterator)->objects[pos]); - } -} - -void PlayerIterator::operator++() -{ - if (++pos == (*iterator)->nbPlayers) - { - do ++iterator; while (iterator && (*iterator)->nbPlayers == 0); - pos = 0; - } - if (iterator) - { - current = static_cast< Player * >((*iterator)->objects[pos]); - } -} - -MovingObjectIterator::MovingObjectIterator(ZoneIterator const &it) - : iterator(it), pos(0) -{ - while (iterator && (*iterator)->nbMovingObjects == 0) ++iterator; - if (iterator) - { - current = static_cast< MovingObject * >((*iterator)->objects[pos]); - } -} - -void MovingObjectIterator::operator++() -{ - if (++pos == (*iterator)->nbMovingObjects) - { - do ++iterator; while (iterator && (*iterator)->nbMovingObjects == 0); - pos = 0; - } - if (iterator) - { - current = static_cast< MovingObject * >((*iterator)->objects[pos]); - } -} - -ObjectIterator::ObjectIterator(ZoneIterator const &it) - : iterator(it), pos(0) -{ - while (iterator && (*iterator)->objects.empty()) ++iterator; - if (iterator) - { - current = (*iterator)->objects[pos]; - } -} - -void ObjectIterator::operator++() -{ - if (++pos == (*iterator)->objects.size()) - { - do ++iterator; while (iterator && (*iterator)->objects.empty()); - pos = 0; - } - if (iterator) - { - current = (*iterator)->objects[pos]; - } -} - -ObjectBucket::ObjectBucket() - : free(256), next_object(0) -{ - for (unsigned i = 0; i < 256 / int_bitsize; ++i) - { - bitmap[i] = ~0; - } -} - -int ObjectBucket::allocate() -{ - if (!free) - { - return -1; - } - - if (bitmap[next_object / int_bitsize] & (1 << (next_object % int_bitsize))) - { - bitmap[next_object / int_bitsize] &= ~(1 << (next_object % int_bitsize)); - int i = next_object; - next_object = (i + 1) & 255; - --free; - return i; - } - - for (unsigned i = 0; i < 256 / int_bitsize; ++i) - { - int k = (i + next_object / int_bitsize) & 255; - if (unsigned b = bitmap[k]) - { - int j = 0; - while (!(b & 1)) - { - b >>= 1; - ++j; - } - bitmap[k] &= ~(1 << j); - j += k * int_bitsize; - next_object = (j + 1) & 255; - --free; - return j; - } - } - return -1; -} - -void ObjectBucket::deallocate(int i) -{ - assert(!(bitmap[i / int_bitsize] & (1 << (i % int_bitsize)))); - bitmap[i / int_bitsize] |= 1 << (i % int_bitsize); - ++free; -} - -MapComposite::MapComposite(Map *m) - : map(m), last_bucket(0) -{ - buckets[0] = new ObjectBucket; - for (int i = 1; i < 256; ++i) - { - buckets[i] = NULL; - } - mapWidth = (map->getWidth() * 32 + zoneDiam - 1) / zoneDiam; - mapHeight = (map->getHeight() * 32 + zoneDiam - 1) / zoneDiam; - zones = new MapZone[mapWidth * mapHeight]; -} - -MapComposite::~MapComposite() -{ - for (int i = 0; i < 256; ++i) - { - delete buckets[i]; - } - delete[] zones; - delete map; -} - -bool MapComposite::allocate(MovingObject *obj) -{ - // First, try allocating from the last used bucket. - ObjectBucket *b = buckets[last_bucket]; - int i = b->allocate(); - if (i >= 0) - { - b->objects[i] = obj; - obj->setPublicID(last_bucket * 256 + i); - return true; - } - - /* If the last used bucket is already full, scan all the buckets for an - empty place. If none is available, create a new bucket. */ - for (i = 0; i < 256; ++i) - { - b = buckets[i]; - if (!b) - { - b = new ObjectBucket; - buckets[i] = b; - } - int j = b->allocate(); - if (j >= 0) - { - last_bucket = i; - b->objects[j] = obj; - obj->setPublicID(last_bucket * 256 + j); - return true; - } - } - - // All the IDs are currently used, fail. - return false; -} - -void MapComposite::deallocate(MovingObject *obj) -{ - unsigned short id = obj->getPublicID(); - buckets[id / 256]->deallocate(id % 256); -} - -void MapComposite::fillRegion(MapRegion &r, Point const &p) const -{ - int radius = AROUND_AREA, - ax = p.x > radius ? (p.x - radius) / zoneDiam : 0, - ay = p.y > radius ? (p.y - radius) / zoneDiam : 0, - bx = std::max((p.x + radius) / zoneDiam, mapWidth - 1), - by = std::max((p.y + radius) / zoneDiam, mapHeight - 1); - for (int y = ay; y <= by; ++y) - { - for (int x = ax; x <= bx; ++x) - { - addZone(r, x + y * mapWidth); - } - } -} - -ZoneIterator MapComposite::getAroundObjectIterator(Object *obj) const -{ - MapRegion r; - fillRegion(r, obj->getPosition()); - return ZoneIterator(r, this); -} - -ZoneIterator MapComposite::getAroundPlayerIterator(Player *obj) const -{ - MapRegion r1; - fillRegion(r1, obj->getOldPosition()); - MapRegion r2 = r1; - for (MapRegion::iterator i = r1.begin(), i_end = r1.end(); i != i_end; ++i) - { - /* Fills region with destinations taken around the old position. - This is necessary to detect two moving objects changing zones at the - same time and at the border, and going in opposite directions (or - more simply to detect teleportations, if any). */ - MapRegion &r4 = zones[*i].destinations; - if (!r4.empty()) - { - MapRegion r3; - r3.reserve(r2.size() + r4.size()); - std::set_union(r2.begin(), r2.end(), r4.begin(), r4.end(), - std::back_insert_iterator< MapRegion >(r3)); - r2.swap(r3); - } - } - fillRegion(r2, obj->getPosition()); - return ZoneIterator(r2, this); -} - -std::list MapComposite::getObjectsOnTile(const Point &tile) const -{ - std::list objectList; - - Objects::const_iterator i; - - // convert pixel coordinates to tile coordinates - int tX = (int)((tile.x) / 32); - int tY = (int)((tile.y) / 32); - - for (i = objects.begin(); i != objects.end(); ++i) - { - // convert object coordinates to tile coordinates - Point objectPoint = (*i)->getPosition(); - int oX = (int)((objectPoint.x) / 32); - int oY = (int)((objectPoint.y) / 32); - - if (oX == tX && oY == tY) - { - objectList.push_back (*i); - } - } - - return objectList; -} - -bool MapComposite::insert(ObjectPtr obj) -{ - Point const &pos = obj->getPosition(); - zones[(pos.x / zoneDiam) + (pos.y / zoneDiam) * mapWidth].insert(obj.get()); - - int type = obj->getType(); - if (type == OBJECT_MONSTER || type == OBJECT_PLAYER || type == OBJECT_NPC) - { - if (!allocate(static_cast< MovingObject * >(obj.get()))) - { - return false; - } - } - - objects.push_back(obj); - return true; -} - -void MapComposite::remove(ObjectPtr obj) -{ - Point const &pos = obj->getPosition(); - zones[(pos.x / zoneDiam) + (pos.y / zoneDiam) * mapWidth].remove(obj.get()); - - int type = obj->getType(); - if (type == OBJECT_MONSTER || type == OBJECT_PLAYER || type == OBJECT_NPC) - { - deallocate(static_cast< MovingObject * >(obj.get())); - } - - for (Objects::iterator o = objects.begin(), - o_end = objects.end(); o != o_end; ++o) - { - if (o->get() == obj.get()) - { - *o = *(o_end - 1); - objects.pop_back(); - return; - } - } - assert(false); -} - -void MapComposite::update() -{ - for (int i = 0; i < mapHeight * mapWidth; ++i) - { - zones[i].destinations.clear(); - } - - // Cannot use a WholeMap iterator as objects will change zones under its feet. - for (Objects::iterator o = objects.begin(), - o_end = objects.end(); o != o_end; ++o) - { - int type = (*o)->getType(); - if (type != OBJECT_PLAYER && type != OBJECT_MONSTER && type != OBJECT_NPC) - { - continue; - } - MovingObject *obj = static_cast< MovingObject * >(o->get()); - - Point const &pos1 = obj->getOldPosition(), - &pos2 = obj->getPosition(); - int src = (pos1.x / zoneDiam) + (pos1.y / zoneDiam) * mapWidth, - dst = (pos2.x / zoneDiam) + (pos2.y / zoneDiam) * mapWidth; - if (src != dst) - { - addZone(zones[src].destinations, dst); - zones[src].remove(obj); - zones[dst].insert(obj); - } - } -} diff --git a/src/mapcomposite.h b/src/mapcomposite.h deleted file mode 100644 index 7961f4da..00000000 --- a/src/mapcomposite.h +++ /dev/null @@ -1,239 +0,0 @@ -/* - * The Mana World Server - * Copyright 2006 The Mana World Development Team - * - * This file is part of The Mana World. - * - * The Mana World 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 - * any later version. - * - * The Mana World 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 The Mana World; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - * - * $Id$ - */ - -#ifndef _TMW_SERVER_MAPCOMPOSITE_ -#define _TMW_SERVER_MAPCOMPOSITE_ - -#include "object.h" -#include "player.h" - -#include - -class Map; -class MapComposite; - -/** - * Ordered sets of zones of a map. - */ -typedef std::vector< unsigned > MapRegion; - -/** - * Part of the map. - */ -struct MapZone -{ - unsigned short nbPlayers, nbMovingObjects; - /** - * Objects present in this zone. - * Players are stored first, then the remaining MovingObjects, then the - * remaining Objects. - */ - std::vector< Object * > objects; - - /** - * Destinations of the objects that left this zone. - * This is necessary in order to have an accurate iterator around moving - * objects. - */ - MapRegion destinations; - - MapZone(): nbPlayers(0), nbMovingObjects(0) {} - void insert(Object *); - void remove(Object *); -}; - -/** - * Iterates through the zones of a region of the map. - */ -struct ZoneIterator -{ - MapRegion region; /**< Zones to visit. Empty means the entire map. */ - unsigned pos; - MapZone *current; - MapComposite const *map; - - ZoneIterator(MapRegion const &, MapComposite const *); - void operator++(); - MapZone *operator*() const { return current; } - operator bool() const { return current; } -}; - -/** - * Iterates through the Players of a region. - */ -struct PlayerIterator -{ - ZoneIterator iterator; - unsigned short pos; - Player *current; - - PlayerIterator(ZoneIterator const &); - void operator++(); - Player *operator*() const { return current; } - operator bool() const { return iterator; } -}; - -/** - * Iterates through the MovingObjects of a region. - */ -struct MovingObjectIterator -{ - ZoneIterator iterator; - unsigned short pos; - MovingObject *current; - - MovingObjectIterator(ZoneIterator const &); - void operator++(); - MovingObject *operator*() const { return current; } - operator bool() const { return iterator; } -}; - -/** - * Iterates through the Objects of a region. - */ -struct ObjectIterator -{ - ZoneIterator iterator; - unsigned short pos; - Object *current; - - ObjectIterator(ZoneIterator const &); - void operator++(); - Object *operator*() const { return current; } - operator bool() const { return iterator; } -}; - -/** - * Pool of public IDs for MovingObjects on a map. - */ -struct ObjectBucket -{ - static int const int_bitsize = sizeof(unsigned) * 8; - unsigned bitmap[256 / int_bitsize]; /**< Bitmap of free locations. */ - short free; /**< Number of empty places. */ - short next_object; /**< Next object to look at. */ - MovingObject *objects[256]; - - ObjectBucket(); - int allocate(); - void deallocate(int); -}; - -/** - * Combined map/entity structure. - */ -class MapComposite { - - public: - MapComposite(Map *); - ~MapComposite(); - - Map *getMap() const - { return map; } - - /** - * Inserts an object on the map and sets its public ID. - */ - bool insert(ObjectPtr); - - /** - * Removes an object from the map. - */ - void remove(ObjectPtr); - - /** - * Updates zones of every moving beings. - */ - void update(); - - /** - * Gets an object given its ID. - */ - MovingObject *getObjectByID(int) const; - - /** - * Gets an iterator on the objects of the whole map. - */ - ZoneIterator getWholeMapIterator() const - { return ZoneIterator(MapRegion(), this); } - - /** - * Gets an iterator on the objects around a given object. - */ - ZoneIterator getAroundObjectIterator(Object *) const; - - /** - * Gets all objects on a tile - */ - std::list getObjectsOnTile(Point const &) const; - - /** - * Gets an iterator on the objects around the old and new positions of - * a player (including the ones that were but are now elsewhere). - */ - ZoneIterator getAroundPlayerIterator(Player *) const; - - private: - MapComposite(MapComposite const &); - - /** - * Allocates a unique ID for a moving object on this map. - */ - bool allocate(MovingObject *); - - /** - * Deallocates an ID. - */ - void deallocate(MovingObject *); - - /** - * Fills a region of zones with the vision range around a point. - */ - void fillRegion(MapRegion &, Point const &) const; - - Map *map; /**< Actual map. */ - - /** - * Objects (items, players, monsters, etc) located on the map. - */ - Objects objects; - - /** - * Buckets of MovingObjects located on the map, referenced by ID. - */ - ObjectBucket *buckets[256]; - - int last_bucket; /**< Last bucket acted upon. */ - - /** - * Partition of the Objects, depending on their position on the map. - */ - MapZone *zones; - - unsigned short mapWidth; /**< Width with respect to zones. */ - unsigned short mapHeight; /**< Height with respect to zones. */ - - friend class ZoneIterator; -}; - -#endif diff --git a/src/object.h b/src/object.h index 23d97434..3e296d54 100644 --- a/src/object.h +++ b/src/object.h @@ -26,7 +26,6 @@ #include -#include "defines.h" #include "point.h" #include "utils/countedptr.h" @@ -135,21 +134,13 @@ class Object class MovingObject: public Object { public: - /** - * Directions, to be used as bitmask values - */ - static const char DOWN = 1; - static const char LEFT = 2; - static const char UP = 4; - static const char RIGHT = 8; - /** * Proxy constructor. */ MovingObject(int type, int id) : Object(type), mPublicID(id), - mDirection(DOWN), + mDirection(0), mActionTime(0) {} @@ -174,7 +165,7 @@ class MovingObject: public Object /** * Sete object direction */ - void setDirection(unsigned char direction) + void setDirection(int direction) { mDirection = direction; } /** diff --git a/src/player.cpp b/src/player.cpp index d91bfcab..e7d84d3e 100644 --- a/src/player.cpp +++ b/src/player.cpp @@ -23,7 +23,6 @@ #include #include "defines.h" -#include "mapcomposite.h" #include "player.h" /** -- cgit v1.2.3-70-g09d2