diff options
| -rw-r--r-- | ChangeLog | 2 | ||||
| -rw-r--r-- | src/mapcomposite.cpp | 352 | ||||
| -rw-r--r-- | src/mapcomposite.h | 162 | ||||
| -rw-r--r-- | src/state.cpp | 72 |
4 files changed, 519 insertions, 69 deletions
@@ -5,6 +5,8 @@ Object class; added update flags instead. Reduced size of Object fields. Moved sayAround from GameHandler to State class. Improved handling of flags for move messages. + * src/mapcomposite.h, src/state.cpp, src/mapcomposite.cpp: Added map + partitioning to reduce quadratic behavior when checking object ranges. 2006-09-02 Bjørn Lindeijer <bjorn@lindeijer.nl> diff --git a/src/mapcomposite.cpp b/src/mapcomposite.cpp index dfbbc052..a7eae6bf 100644 --- a/src/mapcomposite.cpp +++ b/src/mapcomposite.cpp @@ -23,6 +23,233 @@ #include "mapcomposite.h" +#include <algorithm> +#include <cassert> + +#include "defines.h" +#include "map.h" + +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_end = objects.begin() + nbPlayers; + i = std::find(i_beg, i_end, obj); + assert(i != i_end); + int pos = i - i_beg; + if (pos != nbPlayers - 1) + { + objects[pos] = objects[nbPlayers - 1]; + } + if (nbPlayers != nbMovingObjects) + { + objects[nbPlayers - 1] = objects[nbMovingObjects - 1]; + } + --nbPlayers; + if (nbMovingObjects != objects.size()) + { + objects[nbMovingObjects - 1] = objects[objects.size() - 1]; + } + --nbMovingObjects; + objects.pop_back(); + } break; + case OBJECT_MONSTER: + case OBJECT_NPC: + { + i_end = objects.begin() + nbMovingObjects; + i = std::find(objects.begin() + nbPlayers, i_end, obj); + assert(i != i_end); + int pos = i - i_beg; + if (pos != nbMovingObjects - 1) + { + objects[pos] = objects[nbMovingObjects - 1]; + } + if (nbMovingObjects != objects.size()) + { + objects[nbMovingObjects - 1] = objects[objects.size() - 1]; + } + --nbMovingObjects; + objects.pop_back(); + } break; + default: + { + i_end = objects.end(); + i = std::find(objects.begin() + nbMovingObjects, i_end, obj); + assert(i != i_end); + unsigned pos = i - i_beg; + if (pos != objects.size() - 1) + { + 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) + { + r.push_back(z); + } + else if (*i != z) + { + r.insert(i, 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) { @@ -75,14 +302,17 @@ void ObjectBucket::deallocate(int i) ++free; } -MapComposite::MapComposite() - : map(NULL), last_bucket(0) +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() @@ -91,6 +321,8 @@ MapComposite::~MapComposite() { delete buckets[i]; } + delete[] zones; + delete map; } void MapComposite::allocate(MovingObject *obj) @@ -136,3 +368,119 @@ void MapComposite::deallocate(MovingObject *obj) obj->setPublicID(65535); 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; + 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); +} + +void 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) + { + allocate(static_cast< MovingObject * >(obj.get())); + } + + objects.push_back(obj); +} + +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 index a6b8b40b..43f5d366 100644 --- a/src/mapcomposite.h +++ b/src/mapcomposite.h @@ -25,12 +25,104 @@ #define _TMW_SERVER_MAPCOMPOSITE_ #include "object.h" +#include "player.h" -class Player; class Map; +class MapComposite; /** - * Pool of MovingObject. + * 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 { @@ -50,23 +142,51 @@ struct ObjectBucket class MapComposite { public: - MapComposite(); + MapComposite(Map *); ~MapComposite(); + Map *getMap() const + { return map; } + /** - * Actual map. + * Inserts an object on the map and sets a public ID. */ - Map *map; + void insert(ObjectPtr); /** - * Objects (items, players, monsters, etc) located on the map. + * Removes an object from the map. */ - Objects objects; + void remove(ObjectPtr); /** - * Players located on the map. Already owned by the objects field. + * Updates zones of every moving beings. */ - std::vector< Player * > players; + 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 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. @@ -79,19 +199,33 @@ class MapComposite { void deallocate(MovingObject *); /** - * Gets an object given its ID. + * Fills a region of zones with the vision range around a point. */ - MovingObject *getObjectByID(int) const; + void fillRegion(MapRegion &, Point const &) const; - private: - MapComposite(MapComposite const &); + Map *map; /**< Actual map. */ /** - * Buckets of MovingObject located on the map, referenced by ID. + * 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/state.cpp b/src/state.cpp index d959876a..789675a7 100644 --- a/src/state.cpp +++ b/src/state.cpp @@ -57,7 +57,6 @@ State::~State() for (std::map< unsigned, MapComposite * >::iterator i = maps.begin(), i_end = maps.end(); i != i_end; ++i) { - delete i->second->map; delete i->second; } } @@ -71,28 +70,23 @@ State::update() { MapComposite *map = m->second; - typedef std::vector< MovingObject * > Movings; - Movings movings; - - for (Objects::iterator o = map->objects.begin(), - o_end = map->objects.end(); o != o_end; ++o) + for (ObjectIterator o(map->getWholeMapIterator()); o; ++o) { (*o)->update(); - int t = (*o)->getType(); - if (t == OBJECT_NPC || t == OBJECT_PLAYER || t == OBJECT_MONSTER) { - MovingObject *ptr = static_cast< MovingObject * >(o->get()); - ptr->move(); - movings.push_back(ptr); - } } - for (std::vector< Player * >::iterator p = map->players.begin(), - p_end = map->players.end(); p != p_end; ++p) + for (MovingObjectIterator o(map->getWholeMapIterator()); o; ++o) + { + (*o)->move(); + } + + map->update(); + + for (PlayerIterator p(map->getWholeMapIterator()); p; ++p) { MessageOut msg(GPMSG_BEINGS_MOVE); - for (Movings::iterator o = movings.begin(), - o_end = movings.end(); o != o_end; ++o) + for (MovingObjectIterator o(map->getAroundPlayerIterator(*p)); o; ++o) { Point os = (*o)->getOldPosition(); Point on = (*o)->getPosition(); @@ -188,8 +182,7 @@ State::update() gameHandler->sendTo(*p, msg); } - for (Movings::iterator o = movings.begin(), - o_end = movings.end(); o != o_end; ++o) + for (ObjectIterator o(map->getWholeMapIterator()); o; ++o) { (*o)->clearUpdateFlags(); } @@ -202,14 +195,10 @@ State::addObject(ObjectPtr objectPtr) unsigned mapId = objectPtr->getMapId(); MapComposite *map = loadMap(mapId); if (!map) return; - map->objects.push_back(objectPtr); + map->insert(objectPtr); objectPtr->raiseUpdateFlags(NEW_ON_MAP); - int type = objectPtr->getType(); - if (type != OBJECT_MONSTER && type != OBJECT_PLAYER && type != OBJECT_NPC) return; - map->allocate(static_cast< MovingObject * >(objectPtr.get())); - if (type != OBJECT_PLAYER) return; + if (objectPtr->getType() != OBJECT_PLAYER) return; Player *playerPtr = static_cast< Player * >(objectPtr.get()); - map->players.push_back(playerPtr); /* Since the player doesn't know yet where on the world he is after * connecting to the map server, we send him an initial change map message. @@ -238,39 +227,18 @@ State::removeObject(ObjectPtr objectPtr) MovingObject *obj = static_cast< MovingObject * >(objectPtr.get()); MessageOut msg(GPMSG_BEING_LEAVE); msg.writeShort(obj->getPublicID()); - Point objectPos = obj->getPosition(); - typedef std::vector< Player * > Players; - Players &players = map->players; - Players::iterator p_end = players.end(), j = p_end; - for (Players::iterator p = players.begin(); p != p_end; ++p) + + for (PlayerIterator p(map->getAroundObjectIterator(obj)); p; ++p) { - if (*p == obj) - { - j = p; - } - else if (objectPos.inRangeOf((*p)->getPosition())) + if (*p != obj && objectPos.inRangeOf((*p)->getPosition())) { gameHandler->sendTo(*p, msg); } } - - if (j != p_end) - { - players.erase(j); - } - - map->deallocate(obj); } - for (Objects::iterator o = map->objects.begin(), - o_end = map->objects.end(); o != o_end; ++o) - { - if (o->get() == objectPtr.get()) { - map->objects.erase(o); - break; - } - } + map->remove(objectPtr); } MapComposite *State::loadMap(unsigned mapId) @@ -279,8 +247,7 @@ MapComposite *State::loadMap(unsigned mapId) if (m != maps.end()) return m->second; Map *map = MapManager::instance().loadMap(mapId); if (!map) return NULL; - MapComposite *tmp = new MapComposite; - tmp->map = map; + MapComposite *tmp = new MapComposite(map); maps[mapId] = tmp; // will need to load extra map related resources here also @@ -305,8 +272,7 @@ void State::sayAround(Object *obj, std::string text) MapComposite *map = m->second; Point speakerPosition = obj->getPosition(); - for (std::vector< Player * >::iterator i = map->players.begin(), - i_end = map->players.end(); i != i_end; ++i) + for (PlayerIterator i(map->getAroundObjectIterator(obj)); i; ++i) { if (speakerPosition.inRangeOf((*i)->getPosition())) { |