hi hplus,

thanks a lot. i appreciate testing that out for me. you know, i hadn't even thought that the map might shift around my data and put it at different spots in memory (i know you were saying this the whole time, but i just didnt get it). i could only imagine the bugs that could cause if it didnt crash...

which reminds me, im going to have to go through my code and make sure i don't do that anywhere (with different containers that is) [grin]. i'm a little worried about what i will do when switching to boost multi index containers (if they don't support this). then i guess i will just store PlayerID's on the Map's, and have to do 2 lookups to find a player. hopefully that won't totally screw me later on.

thanks again.

hi again,

i have another concern [smile]. what about bullets and other projectiles? a projectile must track what map he is on, so that when a player enters a map he can be told about any projectiles currently flying in the air, and also when doing collision detection, i only want to check projectiles against characters who are on the same map.

so, should i do the same for projectiles as well? put a std::list<Projectile*> as a member of my Map class? when a bullet is born, i do an insert into this list, and remove when it dies..

i just have one big concern though. im really worried this might be too slow. i mean, thats possibly ALOT of inserts and deletes going on. each time an enemy or player fires their gun that is an insert / delete. with 30 players running around killing monsters and people, this could be hundreds of inserts and deletes constantly happening. with 100 players it could be thousands.

is this system too slow then? will it be faster to just compare maps when sending packets / doing collision detection? it would also be easier to code and maintain as well. and i want to be consistant, i don't want to have players grouped by map but not projectiles, that just seems sloppy...

lastly, its a good chance i will wind up using a std::hash_map instead of a std::map. do you think this is like the std::map, in that pointers / iterators are not invalidated? i looked at the SGI docs, but it doesnt mention this.. actually, ill just run that test you did then.

thanks again for any help!!

I suggest you keep a set of all entities, rather than separate lists of projectiles, monsters, players, etc. If you do that, you pretty much have to use pointers (to an abstract base class) rather than objects, though.

You could go both ways: derive all classes from Entity, and then have a factory for each class. The factory has a list of all objects of "its" class, which could be a map containing the actual object.

So you'd have something like:

class Interface {  public:    virtual char const * interfaceName() = 0;    // "query" in the COM sense, not just a dynamic_cast<>    virtual Interface * queryInterface( char const * name ) = 0;};class Entity : public Interface {  public:    virtual Pos pos() = 0;    virtual Vel vel() = 0;    virtual void addStateToNetworkPacket( NetworkPacket * p ) = 0;};class Player : public Entity {  public:    ...};class Bullet : public Entity {  public:    ...};class EntityFactory : public Interface {  public:    EntityFactory( char const * kind ) {      factories_[kind] = this;    }    static Entity * makeEntity( char const * kind ) {      if( factories_.find( kind ) != factories_.end() ) {        return factories_[kind].makeEntity();      }      return 0;    }  protected:    virtual Entity * makeEntity() = 0;    static std::map< std::string, EntityFactory * > factories_;};class PlayerFactory : public EntityFactory {  public:    PlayerFactory() : EntityFactory( "Player" ) {}    Entity * makeEntity() { ... }  private:    std::hash_map< PlayerID, Player > players_;};class BulletFactory {  public:    BulletFactory() : EntityFactory( "bullet" ) {}    Entity * makeEntity() { ... }  private:    std::hash_map< BulletID, Bullet > bullets_;};

This is getting pretty far from networking and deep into game engine design, tnough :-) Suffice to say that most games end up implementing something along this lines to have polymorphic entity management, dynamic class instantiation, and other such useful things. You may have parts of this already.


Regarding the cost of creating and destroying entities, I'd be more worried about the network cost than the CPU cost. Entity lifetime needs to be somewhat reliable, because you don't want bullets that stay alive forever on some machine that lost a single packet :-)

Further, if you run collision detection on the server, this happens every pulse, which is rather more often than just creating/deleting entities, so the overhead of the entity inserts/deletes themselves is likely to be relatively small.

Last, it's easy to optimize the case of entity ID and entity creation/insertion. Create an array of size (say) 1024; then keep a "next free" ID. When you need to allocate, keep incrementing the ID, and calculate the array index as ID&1023. When the indes shows a free slot, stuff the ID in there and mark it allocated. Mapping from ID to entity is really cheap -- again, just mask ID by 1023. Any other power of two works as well; it's just a maximum cap on the number of allocated objects you can have.

Just because I have some downtime, here's the pattern I usually use (not tested, but sketched out):

template< class T, int N > FastFactory {  public:    FastFactory() {      assert( !(N & (N-1)) );      live_ = 0;      nextId_ = 1;      memset( items_, 0, sizeof( items_ ) );    }    ~FastFactory() {      assert( live_ == 0 );    }    int makeNew() {      // catch too small container in debug build      assert( live_ < N );      if( live_ == N ) return 0;      while( item( next_ )->id_ ) {        ++next_;      }      new( &(item( next_ )->t_) ) T;      item( next_ )->id_ = next_;      ++live_;      return next_;    }    void destroy( int id ) {      assert( live_ > 0 );      item( id )->t_.~T();      item( id )->id_ = 0;      --live_;    }  private:    Item * item( int id ) {      assert( id != 0 );      Item * r = (Item *)storage_[id & (N-1)];      assert( r->id_ == 0 || r->id_ == id );      return r;    }    struct Item {      int id_;      T t_;    };    char storage_[N][sizeof(Item)];};

hi hplus,

wow, what would i do without you? the words "mistake" and "refactor" come to mind [grin].

anyway, about the factory pattern you posted. that seems like a very nice idea. i have another idea though, which to me is simpler (because i have limited experiance with the factory pattern, but good experiance with the following). anyway, basically, it will work like this:



do you see what i do here? i make my 4 classes, and each class has a static list which tracks all instances of that class. first, i have a collection of ALL entities in the world. then i have seperate collections for players, projectiles, enemies. what i like about this is it is self-managing. i dont have to really do any maintenence on any of these. it is all done by the constructors and destructors.

now, for my Map class, i will do this:



here i do the same, track each object on the map AND have a copy of all entites.

theres a few concerns about this system:

1) thats ALOT of inserts and deletes going on [smile]. im not sure if this system is feasable or not

2) what happend to PlayerID's ? well, PlayerID's is how RakNet identifies a connection on the server. when i receive a packet, Packet::playerID tells me who this packet came from. PlayerID is just a struct with 2 members, unsigned long binaryAddress, and unsigned short port. now, i didn't want to have to send around 6 bytes for an ID each time i sent a packet. so, i make my own ID scheme which is seperate from RakNet. here you see im using Uint16's for ID's, however this will change to a typedef. especially since with this system all Entities have to be unique, so i might need a full unsigned integer for this. anyway, since Enemies and Projectiles dont have PlayerIDs, im going to have to store them by their network ID. which means i must make PlayerID a member of the Player class then. im a little worried this switch from PlayerIDs to regular network ID's as the key is going to confuse me or screw me somehow down the road, but i think it will be fine. (my main concern is double- lookups needed when i want to get a PlayerID, but im not sure if this is a real problem).

so, lets say i receive a movement packet from a player, and wanted to bounce this back to all clients on his map. it would look like this:

case MSGID_PLAYER_MOVING:{   --- build the packet here !! --   //this will send a packet to a list of PlayerID's   Broadcast_To_Players(packet,map_manager.Get_Player_List(packet->playerID););}

now, my Map Manager class looks like this:


well, i hope your still reading at this point [smile]. what do you think? is this system flawed in any way? is this too many inserts and deletes? if so, i would try out using your factory idea, i just wanted to do this because its a similar pattern i use all the time, so i am used to it.

lastly, about your "Fast Factory" template. i am trying to understand how it works and its purpose. (it doesnt help that i dont fully understand bitwise operations (&), im gunna google for it though). so, what is the purpose exactly? im un-sure about this. is its entire purpose just so that i don't have to constantly call new and delete? i actually planned on doing some sort of memory manager eventually, to avoid doing so many news and deletes. however im not sure how serious of a problem new and delete is.

thanks ALOT once again!

It's fine to keep a list of entities, and separately a list of each class instance, within each class.

Keeping a per-class list in your Map class seems a little unwieldy, though. Why do NPCs have to be different from Bullets? What's special about Player? It might be that you want the Map to have a collection of "Connections," and the Connections might have an associated Player, and the Player might even have an associated Connection, but a list of Players doesn't seem like something I would do -- I'd probably have a list of Entities, and then separate lists of things I actually need (typically, a list of deferred events, a list of connections, etc).


On the C++ topic: If you want to prevent specific constructors/destructors from getting called, you can let the linker tell you:

class Foo {public:  Foo( int i ) { printf( "%d\n", i ); }  ~Foo() {}private:  Foo(); // not implemented  Foo( Foo const & f ); // not implemented  Foo & operator=( Foo const & f ); // not implemented};int main() {  Foo f(1);#if CANT_MAKE_DEFAULT  Foo f2;#endif#if CANT_MAKE_COPY  Foo f3( f );#endif#if CANT_ASSIGN  Foo f4(2);  f4 = f;#endif}

You will note that if you turn on one of the CANT things, you will get a link error (in addition to likely getting a compile error because of the private access). That's because, when you declare a default function (constructor, copy constructor, assignment operator), the compiler will no longer emit it automatically for you, so if you never define it, the linker won't find it. This means you are told about problems sooner than with an assert().

hi again,

well, isn't a connection a player anyway? you're right, i dont need the list of projectiles or enemies, i dont think. i was just doing that just "in case". i mean, maybe one day i would need a list of all projectiles or all enemies on a map, no? i figured if i had all of the information up front, then later when writing code i could take advantage of that. i guess i figured theres no such thing as "too much information", except, well, there is such a thing [smile].

ok, so, the Map class will only have 2 hash maps then. a std::hash_map<Entity*> entities_on_map, and a std::hash_map<Player*> players_on_map. im really not sure how i could make "connections" though..

another concern is what about items? items are not implemented yet, but they will be. items will be able to be placed on maps, and users could pick them up. but, is an item an Entity? it cant be with my current defintion of Entity, since an Entity has a velocity, but an item will never have a velocity. what could i do about this then? simply just remove velocity from the Entity class? or possibly make some sort of Entity and Moving_Entity seperate classes, or something..

thanks again.

EDIT: now that i think about it more, i actually do need each map to know about the projectiles on it.

for example, when a player enters a map, he must be told about all the players on that map, and all projectiles. however, he would also have to be told about NPC's i suppose, so maybe i could just use the entities list? one problem i see is that some NPC's positions will be static, that is, they will always be standing in the exact position. the player will cache these NPC's in a similar way that he cache's players names (remember that?), so he wont have to be told about it. argh, im not sure if this is even a problem at all. its funny, i need to design this code before i write it, but its hard to see the logic without being in the IDE and punching in code [smile]. also, on a side note; i was thinking that i could get away with NOT sending a player the current projectiles flying in the air when he enters a map. this could help reduce bandwith by a good amount. the player would still get the result of the projectile though, if it hit someone for example (he would still see the blood spurt / miss message and the persons health reduced). what do you think?

[Edited by - graveyard filla on December 27, 2004 3:41:42 PM]

Is every connection a player? How about a "bodyless" God who logs in to run a campaign? How about some monitoring script that connects to make sure all is well in the map?

Quote:

i was just doing that just "in case"

Look up the "YAGNI" design principle :-) (Short for "You Ain't Gonna Need It").

Quote:

Static positions, etc

If you take this to the extreme, you notice that an RPG is just a big database of data, where some data changes often, and other data changes seldom or not at all. Some of the data can be seeded permanently (layout of levels, say), and other data is ephemereal (player location). In the end, you want to replicate the visible parts of this database to the client machine, with as low perceptible latency and as few discrepancies as possible. I believe something conceptually elegant could be developed based on the view of the game as a replicated database with special knowledge about kinds of data (and, in fact, our commercial offering makes good strides in that direction), but I think nothing I've seen is actually at the goal yet.

Um, yeah, that's philosophical. In practice, perhaps each entity attribute has a bit, which says whether it's been changed from the "template" for that level or not. Only attributes that are not the same as they were in the template get sent to users, for each entity -- this means that entities must be able to update only parts of themselves. However, you probably already do this, as the class of a character is unlikely to change when its position changes.

Last, I think Items may very well have velocity, if they're thrown for example. Or they're a special entity kind that overrides velocity to always be 0, and knows how to optimize transmission of this fact down to 0 bits. What we do, is have a special datatype called "position or delegate" which contains a position mode, as well as a union of real position, or pointer to position delegee. If the mode is "out in the world" then the union contains a real position. If the mode is "carried" then the union contains the system-wide unique ID of the carrier object. That object, in turn, might be a backpack, that has another carrier... Getting the position then returns this datatype, and there's a separate function that gets the position of the topmost delegee, so you always get a world-space position for something (which will be the same as the position of the carrier, for a carried item).

There's really no right or wrong way of doing this, though. We use entities for all our objects, which is a bit heavy-weight compared to something that can say "I have 25 of item 47 (+3 Flaming Arrow of Pulsation)" but allows us to totally avoid object duplication bugs, and have a log for anything that every happened to each object in the system. Typical RPGs will just send <count,archetype_id> pairs for your inventory, and items on the map.

Quote:

Original post by hplus0603 Is every connection a player? How about a "bodyless" God who logs in to run a campaign? How about some monitoring script that connects to make sure all is well in the map?

hmmm. you are referring to the server admin (me), correct? that is, some sort of "special" client (sometimes called a "GM", or Game Master) that could have super powers such as teleporting players around, silencing players, etc..

in this case, couldn't i just consider them as Players? really how they are stored on the server doesn't matter, no? as long as the "super" client can send special messages to the server "teleport this guy to this place", "silence this guy", etc...

also, i'm not sure about what you mean about a monitoring script. how would this work? what do you mean "make sure all is well" ?

are there any other situations i should look out for? as it looks now, i'm just going to make it a list of Players on each map. perhaps later i could add a "non player connections" system? if they needed to be partionioned into maps, i could either stuff them into the Map class or make a std::hash_map<Map_ID,std::hash_map<Uint16,NonPlayerConnection*>>.

also, its pretty interesting to look at a virtual world as just one big database . i can totally see what you mean, the world is just a database like any other, only in our case, we are presenting the data to the player through graphics (instead of say, an ordering form), and allowing him to make changes to the data dynamically using input. pretty cool way to look at it [smile].

What I'm saying, in suggesting to separate Connection from Player, is that you may wish to get a view of the world from something that is not a player. Or maybe that's a case where YAGNI applies. If it makes your game work, a list of Players in the Map is the way to go. There is no wrong way ;-)

Regarding what the scripts would be good for: Let me predict the future of your game servers:

Once your game is up and running, users will log in. Users who log in, cause load, create items, kill mobs, and try to game the system. Not to mention hardware might leak memory, run out of disk, become overloaded, or whatever. For the first month, you'll be so thrilled that you actually have users, that you'll just sit there, taking care of things yourself. Then you'll realize that you need to go to school/work/day center once in a while, and leave the world alone. Maybe you need to sleep sometime, too.

The first week of leaving the world alone, it'll run fine. On the eight day, however, someone will figure out how to dup the +3 Flaming Arrow of Pulsation, and suddenly all the shopkeeper inventories are full of it, and shopkeepers can't buy anything else, so player inventories fill up. Maybe you get an e-mail a day later with some complaints (if it makes it past the spam filter), but you probably want to know sooner.

Thus, it's a good idea to develop scripts that run reports of the world every so often, and compare to previous reports and a known baseline. If something is out of whack, it should e-mail your pager or whatever.


So the question is: where does the monitoring script get its data from? Is it a player? Does it use a totally separate connection to the servers? Does it scrape the database directly? If so, how can you monitor things like "the ability to log in" or "the average latency of chat commands"?

One possible solution is to support player-less connections, and let all data extraction take the same path out.

In our current world, we didn't take it this far -- we use something that looks like real players. Instead, special, mysterious players log into various places of the world. There's been quite a cult growing up around them, I hear, so maybe it's not all for the bad :-)

i see. couldn't i make some sort of "statistics and tracking" class, and everywhere in my code, i would record and log things, and periodically do things like loop through NPC and player inventories and mine the database? that is, i would have this directly on the server code?

im a little unsure on how you guys handle it. so you use a scripting language, and connect from a different PC to do this? that sounds more flexible to me, but if i did it directly on the server, it would save bandwith. also, for checking things in the database, i think i could just write MySQL scripts instead and do that from outside of my game.


now, about the design. i starting implementing this last night, then today at work i foresaw a problem arising.

i don't plan on sending "live" projectile data. that is, when a player steps on a map, he is told about all projectiles that are currently flying in the air. however, i don't want to do this. i feel i could cut this out to save on bandwith, and the effect would hardly be noticable.

so, when a player enters a new map, he is told about all other players, NPC's, and items on the map (all Entities except projectiles). but how do i do this? there are a few possible solutions..

1) have my map class only have 2 containers (like i planned): std::hash_map<ID,Player*> players on map, and std::hash_map<ID,Entity*> entities on map. then, use RTTI and give my Entity a Get_Type() member. then, when looping through entities, exclude projectiles from the packet. i really dont like this method at all...

2) do the same, have the same 2 containers as above, except simply just exclude from adding projectiles to the entities_on_map container. this would probably be the fastest and easiest solution, but it kind of worries me that im excluding projectiles from this list. i mean, its just not very obvious that projectiles wont be on the list. and what about the "master" list of ALL Entities in the game? this would still container all the projectiles, right? which just brings more confusion... also, what if one day i needed to get a list of all projectiles on a map?

3) instead of having 2 containers, do what i had originally planned (the YAGNI), and have multiple containers on the Map class:
std::hash_map<ID,Entity*> entities_on_map;
std::hash_map<ID,Character*> characters_on_map;
std::hash_map<ID,Player*> players_on_map;
std::hash_map<ID,Npc*> npcs_on_map
std::hash_map<ID,Enemy*> enemies_on_map
std::hash_map<ID,Projectile*> projectiles_on_map;

whoa, kind of bloated, no? notice: characters_on_map includes players,npcs,and enemies. entities includes everyone. also note, i have 2 classes, Enemy and Npc. why are these seperate? isn't and Enemy an NPC? well, perhaps it is named poorly, but an Enemy is a combat NPC, e.g. a monster, and NPC is a non-combat NPC, e.g. a vendor at a store. these are 2 seperate classes since an NPC would need scripting uses and an Enemy would need stats like health and stuff. anyway, this solution gives me full control over everything, which i like, however, this control comes at a cost. wont all those inserts and deletes be expensive?

anyway, what do you think is the best out of these solutions? so far im leaning towards 2, although its kind of un-intuative. 3 (could be) slow, and 1 is both ugly and slow [smile].

thanks again.