256 Player Group Mapping Project

[QwazyWabbit]

Hey all ~

Ben2 now has the means to disable the Lights and the Elevators.  I'm working on the usable size of the Map, allowing negative XYZ coords and such.   

My question:  Do any of you know off-hand, the limits of the X,Y, and Z coords in the game?  I want Ben to be able to max this out...something I've always wanted to do anyhow, and it looks like a rather important item for this project..

~Yendor

From the q_shared.h for the game:
#define   MAX_STRING_CHARS   1024   // max length of a string passed to Cmd_TokenizeString
#define   MAX_STRING_TOKENS   80      // max tokens resulting from Cmd_TokenizeString
#define   MAX_TOKEN_CHARS      128      // max length of an individual token

#define   MAX_QPATH         64      // max length of a quake game pathname
#define   MAX_OSPATH         128      // max length of a filesystem pathname

//
// per-level limits
//
#define   MAX_CLIENTS         256      // absolute limit
#define   MAX_EDICTS         1024   // must change protocol to increase more
#define   MAX_LIGHTSTYLES      256
#define   MAX_MODELS         256      // these are sent over the net as bytes
#define   MAX_SOUNDS         256      // so they cannot be blindly increased
#define   MAX_IMAGES         256
#define   MAX_ITEMS         256
#define MAX_GENERAL         (MAX_CLIENTS*2)   // general config strings

//
// key / value info strings
//
#define   MAX_INFO_KEY      64
#define   MAX_INFO_VALUE      64
#define   MAX_INFO_STRING      512



From the engine code:

sv_world.c
#define MAX_TOTAL_ENT_LEAFS      128

q_files.h
// upper design bounds
// leaffaces, leafbrushes, planes, and verts are still bounded by
// 16 bit short limits
#define   MAX_MAP_MODELS      1024
#define   MAX_MAP_BRUSHES      8192
#define   MAX_MAP_ENTITIES   2048
#define   MAX_MAP_ENTSTRING   0x40000
#define   MAX_MAP_TEXINFO      8192

#define   MAX_MAP_AREAS      256
#define   MAX_MAP_AREAPORTALS   1024
#define   MAX_MAP_PLANES      65536
#define   MAX_MAP_NODES      65536
#define   MAX_MAP_BRUSHSIDES   65536
#define   MAX_MAP_LEAFS      65536
#define   MAX_MAP_VERTS      65536
#define   MAX_MAP_FACES      65536
#define   MAX_MAP_LEAFFACES   65536
#define   MAX_MAP_LEAFBRUSHES 65536
#define   MAX_MAP_PORTALS      65536
#define   MAX_MAP_EDGES      128000
#define   MAX_MAP_SURFEDGES   256000
#define   MAX_MAP_LIGHTING   0x200000
#define   MAX_MAP_VISIBILITY   0x100000


from the client:
cl_tent.c
#define   MAX_LASERS   64
#define   MAX_EXPLOSIONS   64
#define   MAX_BEAMS   64


I believe GL begins visibility clipping at 8192 Q units. Targets further than that won't be rendered.

The server will be limited by its bandwidth:

A server frame occurs 10 times per second for each player. The server frame size is variable, ranging anywhere from 100 bytes to a hard-coded maximum of 1400 bytes. So for a server with 10 players and a maximum sized set of frames to send to each player, the aggregate bandwidth would be 10 x 10 x 1400 = 140,000 Bytes per second or about 1.4 Mbps of downstream data rate. A T1 link is 1.5 Mbps so you can see that when server frames get larger, even a T1 can become overloaded and we start losing frames or they become delayed. This is a peak value, most of the time the downstream bandwidth of a server should hover around 450 bytes per frame and at 10 users it would be 45,000 kBps or about 450,000 bps at the server's ethernet port.

On a LAN you should probably have a 1000 Mbps server and switches to 100 or 1000 Mbps clients to clear traffic.

But...

So what's an overflow? This is related to the 1400 byte limit on outbound server frames, the 10FPS frame rate, and the server rate command. In the days of modem connections servers had to limit the rate they sent data to a client or the client's downstream bandwidth would be overloaded and they would lag. The rate command was designed to cap the rate the server would attempt to send data and when the rate was exceeded it would discard data destined for that client until the client could catch up. This is less of an issue these days with the majority of online gamers using wideband connections. Setting maxrate to 15000 or 25000 effectively disables rate limiting to clients and the server is free to max out the frame size and rate at 1400 bytes x 10 frames per sec = 14000 Bps. A Quake2 server is hard-coded for a maxrate of 15000, so putting anything larger in there doesn't buy you anything.  In the final analysis, since 10 server frames x 1400 max frame size x 10 bits per frame byte = 1.4Mbps a rate of 15000 will never be reached by any one user no matter what mod is being played.

Soo....

If we have 1.4Mbps per client max speed you will hit the bandwidth wall at 1000/1.4 = 714 clients per server.

But I doubt the server can do that many ClientThinks per second and still keep up with the state changes.

64 player maps already exist, city64.bsp comes to mind. You may want to load a server up with that map in a single map configuration and see if you can pile more than 64 players into it as proof of concept before you attempt to take it to 256.

[Jay Dolan]

You didn't answer what an overflow actually is, or why a 256 player scenario would be prone to them.

There are two classes of overflows: datagram and reliable, corresponding to the two outbound communication "channels" the server maintains to each client.  Entity state changes are sent over the datagram channel, and commands such as baselines, configstrings, precache and level change, chat messages, and other more critical things are sent over the reliable channel.  Basically an overflow occurs when a given frame's information does not fit into the corresponding channel.  The server will not send a partial frame; Quake's message serialization/deserialization doesn't work like that.  It's all or nothing.  So the message is dropped, and an overflow warning is printed out to the server console.  For datagram messages, the protocol can usually cope with this so long as the amount of activity over the next few frames decreases significantly.  For reliable messages, it's a deal breaker, and the client is dropped because the server has no mechanism to "catch them up" when activity subsides.

So.. during your 256 player game, let's say 30 players are all in your PVS, and there's a lot of fighting going on.  30 player entities changing angles, origins, and animations every frame.  30 players firing various weapons, some producing new entities (rockets, grenades, blaster/hyperblaster bolts, BFG balls, ..), some producing "temp entities" (explosions, bullet impacts, rail trails, blood, bubble trails, ..), and all producing muzzle flashes.  Plus player entity events like footstep sounds, falling sounds, pain sounds.  Then factor in some gibbing, some respawning, .. and lets not forget all of the non-player entities in the scene.  It's quite easy to imagine frames frequently reaching 1400 bytes in size.  You'll have packet loss on a LAN game, heh.  And if it happens for consecutive frames, things really break down and clients will be forced to reconnect.

And before someone suggests increasing the maximum message size to > 1400 bytes; you can't for UDP protocols.  Many routers and switches can't cope with large datagram packets, and/or fragmenting and reassembling them.  1400 is the largest safe UDP packet size for _most_ network environments.

[peewee_RotA]

//
// per-level limits
//
#define   MAX_EDICTS         1024   // must change protocol to increase more
#define   MAX_LIGHTSTYLES      256
#define   MAX_MODELS         256      // these are sent over the net as bytes
#define   MAX_SOUNDS         256      // so they cannot be blindly increased
#define   MAX_IMAGES         256
#define   MAX_ITEMS         256
#define MAX_GENERAL         (MAX_CLIENTS*2)   // general config strings

This is what worries me most. I think that this will be the first obvious limitation. I knew that there was one but I guess I was afraid to ask what the actual limit was, lol. Is this something that could be reasonably changed on the client to compensate for? Like you said, they are sent over the net as bytes. So would increasing the size be feasible?

[Jay Dolan]

MAX_MODELS worries you?  Why?  Of your 256 players, 220 of them are going to be using male/female/cyborg.  And no, the protocol is very much dependent on the fact that ent->s.modelindex[2,3,4] are each just one byte.  Increasing MAX_MODELS and allowing higher model indexes would require a protocol change.  Basically, increasing anything will require a protocol or engine change.

GLHF   

[QwazyWabbit]

JDolan is correct. Bytes means the indexes are limited to 256 values. Expanding the index to integer now means 32 bits or 4 bytes and a protocol change in client, server and all the mod code to accomodate the extended indexes where they expected a byte. Granting that going from byte to int might only change a few function definitions, it's not a small change. Even going short (16 bit) means a protocol change. This is one of the areas where they compromized extensibility for bandwidth efficiency in Q2's network protocol. When you see stuff like

      gi.WriteByte (svc_temp_entity);
      gi.WriteByte (TE_BLASTER);
      gi.WritePosition (p2);
      gi.multicast (p1, MULTICAST_ALL);

You are seeing the game dll que the network frames for updating those indexes to the clients. Break them and it's not Q2 anymore.

But all is not lost. The indexes are reused as entities are created and destroyed, so the game will usually run with less than the max most of the time.

I guess now would be a good time to introduce another ugly but necessary hack:
Put these functions in your g_main.c

// HACK
char modelSeen[256];

int HACK_modelindex (char *name)
{
   int result;

   // First, get the result of gi.modelindex().
   result = oldmodelindex (name);

   // Log some "*Index: overflow" bugcatching info to the console, if
   // they're using the maplist feature on a dedicated DM server -

   //QW//
   // - and debugmodels is on.
   // The purpose of this hack is to allow debugging of the overflow bug of the 256 model
   // index limit in Q2. It starts the next level if we start to exceed the model limit.
   // I hacked the hack to allow the server configuration to control whether we see the
   // debug messages on the console or not.
   // The map city3.bsp hits the model limit every time even with a single player on a server.
   //QW//

   if (deathmatch->value && dedicated->value && maplist->value)
   {

      if (result >= MAX_MODELS - 1)
      {
         gi.bprintf (PRINT_HIGH, "Forced Timelimit. Model index = %d\n", result);
         EndDMLevel();
      }

      // If this model hasn't been seen before, report it & its number.
      if (!modelSeen[result])
      {
         modelSeen[result] = true;
         if (debugmodels->value)
            gi.dprintf ("modelindex %d allocated to %s\n", result, name);
      }
   }

   // Return the model index.
   return result;
}

void
HACK_SpawnEntities (char *mapname, char *entities, char *spawnpoint)
{
   // Clear modelSeen[]
   memset (modelSeen, 0, sizeof (modelSeen));

   // Proceed.
   TeamplaySpawnEntities (mapname, entities, spawnpoint);
}

And hack the game export table as follows:

game_export_t *GetGameAPI (game_import_t *import)
{
   gi = *import;

   // HACK
   oldmodelindex = gi.modelindex;
   gi.modelindex = HACK_modelindex;

   globals.apiversion = GAME_API_VERSION;
   globals.Init = InitGame;
   globals.Shutdown = ShutdownGame;
   globals.SpawnEntities = HACK_SpawnEntities;

....
}

And this at the top of g_main.c above the ShutdownGame function:

// HACK
int HACK_modelindex (char *name);
int (*oldmodelindex) (char *name);
void HACK_SpawnEntities (char *mapname, char *entities, char *spawnpoint);


This will keep the game from crashing hard due to modelindex overflow in all dedicated modes.

Don't forget to add the cvar debugmodels:

In g_main.c with all the other cvars
//QW//
cvar_t   *debugmodels;      // set for model messages in console

in g_local.h
extern   cvar_t   *debugmodels;      // 1 = print debug_models messages
and in g_save.c for initialization:
   debugmodels = gi.cvar ("debugmodels", "0", 0); //QW// server side runtime fix for debug models

It will print the modelindex values to the client consoles when switched on for debugging purposes and it will give you a good handle on how many model indexes are in use as the game progresses.

[peewee_RotA]

MAX_MODELS worries you?  Why?  Of your 256 players, 220 of them are going to be using male/female/cyborg.

Gmail has a feature that requires you to answer math questions if you try to send an e-mail after 11:00 at night... In this case it would have been a good things because I was confusing these two.

#define   MAX_EDICTS         1024   // must change protocol to increase more
#define   MAX_MODELS         256      // these are sent over the net as bytes

I was thinkings 256 total models, not 256 unique models. I guess it would have been a dead give away that I was horribly wrong if I wouldn't have deleted the line "in that case we can only have 255 players and 1 spawn pad before reaching the model limit" right before posting.

 

Thanks for the code snippet though QW. It should be a huge help.

My only question now is whether or not func_ ent's that are really just chained together brushes count in that model index.

void SP_func_door (edict_t *ent)
{
   vec3_t   abs_movedir;

   if (ent->sounds != 1)
   {
      ent->moveinfo.sound_start = gi.soundindex  ("doors/dr1_strt.wav");
      ent->moveinfo.sound_middle = gi.soundindex  ("doors/dr1_mid.wav");
      ent->moveinfo.sound_end = gi.soundindex  ("doors/dr1_end.wav");
   }

   G_SetMovedir (ent->s.angles, ent->movedir);
   ent->movetype = MOVETYPE_PUSH;
   ent->solid = SOLID_BSP;
   gi.setmodel (ent, ent->model);

        ...

[Jay Dolan]

Of course.  The server has no other mechanism for associating models to entities.  You can see where these are initialized in sv_init.c, SV_SpawnServer.  The model names for "inline" world models are "*1", "*2", "*3", ..

[QwazyWabbit]

Yes. Any time you are calling gi.setmodel you are creating another model and the associated entity, if the model has been spawned before it won't count against the model limit (it was already indexed) but it will count against the entity limit (as a new ent). If it has an associated Think function (ent->think = ...) then it has physics or touch properties that can also create network traffic for all players in view when it moves. (a potential lag problem)

In OO terms, you are creating an ent object and changing its attributes by filling the struct for it, the gi.* functions are the public interface to that object that is managed by the engine. Think of Spawn_Something funcs as being operator new for an object of class Something derived from class Entity and you pretty much have a handle on it. The engine is then acting as the memory manager for your objects and it has those limits on how many objects you can create.

[peewee_RotA]

Yes. Any time you are calling gi.setmodel you are creating another model and the associated entity, if the model has been spawned before it won't count against the model limit (it was already indexed) but it will count against the entity limit (as a new ent). If it has an associated Think function (ent->think = ...) then it has physics or touch properties that can also create network traffic for all players in view when it moves. (a potential lag problem)

In OO terms, you are creating an ent object and changing its attributes by filling the struct for it, the gi.* functions are the public interface to that object that is managed by the engine. Think of Spawn_Something funcs as being operator new for an object of class Something derived from class Entity and you pretty much have a handle on it. The engine is then acting as the memory manager for your objects and it has those limits on how many objects you can create.

In light of this, I think that it's safe to say that speakers and platforms are out of the question. They should be only added in as a final pass of the map. Everything else should be accessible by ladder, stairs, and teleporters. I would leave jumppad's out of the mix as well since I've seen corruption of trigger_push entities when passed in between mapping programs. We can leave trigger push's for last.

Area portals and doors are another issue. It may be possible to overcome these obstacles by creating generic .md2 door and .md2 elevator models that are used for all non-area portal doors and all elevators.

[Yendor]

Yayy! At long last I have updated our friend Ben2.  The EXE is attached.  Any new-comers who want to try this thing out let me know and I'll send a package with all the goodies.   For now, this update is for PeeWee, with changes that he asked for several days ago:

1.  Ben2 can now use the entire available game area, which is +/-4095 "Q" units.
2.  Cell-space area in Ben2 can now be initialized up to 50x50x20 cells.
3.  You can now "draw" hallways directly on the Map view.  Just click-and-drag!  This is way cool - just remember that there is no Undo functionality! 
4.  Mouse Wheel now scrolls through the vertical levels of the Map space.   If you hold down your left button while wheeling, you will carve vertical hallways.
5.  You can turn off the generation of Light entities and elevators.  This was on PeeWee's request.  The check boxes are in the Play Map Settings window.  The Add Light Entities to Map checkbox prevents "light"s from being added to the Map file, and is independent of Use Lighting Effects, which simply turns on or off using QVIS and QRAD.  Turning off Elevators will result in an un-playable map!
6.  As spiffy new icon!  Actually it's pretty crappy, but it's supposed to be a mouse superimposed over a maze, in honor of the movie after which this program is named.

Known Bugs:
I sometimes get a leaky map at larger Cell-Area sizes.  Also sometimes get a dark map, despite lights and lighting effects being turned on.
There is a warning that comes up when you click Play Map that warns you if some boundries exceed the limits...sometimes if you ignore this the map is OK anyhow.  There's something fishy in there still that results in leaky maps, but for the most part it works a charm!

This thing is almost to the point of being the world's fastest map editor

I await the barrage of questions!
~Yendor

[SquiSHeR]

The biggest map i know so far is base100, check it out: http://www.deaconstomb.org/pub/q2/maps/base100.zip

Why not make your 256 map "outdoor" like the massive CTF maps in Q3 Team Arena, just a few stand alone buildings or maybe caves.

[peewee_RotA]

checking out base100 now..

I'm expecting some outdoor areas from people working on the top levels, but overall caves and outdoor areas are going to be way too detailed. This is going to be more like square pillars and boxes in giant warehouse style rooms.

*EDIT*

That base100 is the same as base64. There may be a single room that's different because I simply don't remember the mega/rail room in between the base3 exit and base2 switch doors.

I'm pretty sure that City64 is bigger than that.

[Yendor]

I'm expecting some outdoor areas from people working on the top levels, but overall caves and outdoor areas are going to be way too detailed. This is going to be more like square pillars and boxes in giant warehouse style rooms.

Yeah, when you go for natural looking rocks and such, it makes compile times horrific.  I made a map called Phang, which is not terribly large (about a good 4-5 person map), which is all open areas and "natural" rocks and such.  It took 14 HOURS to compile!!!  And that's on a dual P4 x64 at 3.2MHz!  Most maps I make, including the hated Fours2d.bsp on Mutant, which is all simple angles) take about 10 minutes to compile...  I would definitely keep the polygon count down, as well as keeping angles right!  After reading up on what QBSP actually does, I can see how these things end up as a severe clusterfrak!

Edit:  Attached Phang for anyone interested...

[quadz]

It took 14 HOURS to compile!!!  And that's on a dual P4 x64 at 3.2MHz!

Well, no wonder!! 

[Yendor]

It took 14 HOURS to compile!!!  And that's on a dual P4 x64 at 3.2MHz!

Well, no wonder!! 

Heh heh... Yeah, my arm got really tired banging that toggle switch up and down to generate all those clock pulses!