Where am I in the world?

[Mr Baggins]

I'm toying with making an MMORPG (Another one of the brilliant waste of lives for teenage nerds everywhere) and one of the main fundamentals I can't get my head around is working out where everyone (and everything) is.

Obviously, you only want the player to know about the stuff in the immediate vicinity. Knowing that there is a strawberry in a bush on the other continent is not only a waste of the server processor, but ever so precious bandwidth.

I've tryed to work out ways to breach this issue. Without any coding, just concepts, I've toyed with Cells (Like cell phone network), Coordinate ranges (Radius around char sent to client) and a few other obvious failures.

Ranges seems like I would be doing a lot of loops (Bad processor utilisation) for every char in the game. There would end up being at least 2 nested loops, which is V.Bad.

Cells seemed like it would work, but the end result is either a shiteload of cells, or the cells being huge, and I am not sure on how one would transition/move between cells.

A sort of in between a friend came up with was cell lists, (mainly for near chars, not things or terrain) where you only need to check the range for a list in the nearby cell. This shortens the loops, knocking a lot of processing off. When the user moves from one cell to another, they change lists, a relatively easy process.

Any ideas? The end result is hopefully going to be semi 3D or full3D. Sort of view as in Warcraft 3, Tiberian sun, Civ III etc, but zoomed in slightly. Also, movement is akin to Warcraft 3, not strictly tile based as in Civ III. More than likely C++ with OpenGL.

Other thing, more than likely should be in another thread, not sure whether to keep the map on the server (Like Tibia) or the client (Like WoW). Ideas, pros and cons?

[Mr Baggins]

Oh, and Hi. I'm new here. Aussie, Uni Student, wants to make an MMOG

[m4x0r]

This issue is not really unique to MMOs -- pretty much every game that takes place in a non-trivial world will have to solve these sorts of problem.

For example, when you're rendering or updating objects in a single player game, you still won't want to consider that strawberry all the way across the world. For many applications this simply means partitioning the world somehow so that you can easily examine only the areas near the player. These seems conceptually similar to what you are describing as cells, so I'm not really clear on why you are dismissing this option.

MMOs (or client-server network games in general) have the extra complexity that the full world only state only exists on the server. However, this doesn't mean that similar approaches are not applicable. For example, if you consider the hard disk is be similar to the server, then you may gain some insight from the method they used to move the world state from disk to memory in in Dungeon Siege (http://www.drizzle.com/~scottb/gdc/continuous-world.htm).

I have no MMO experience, so perhaps I'm misunderstanding your question.

Max

[corey]

What happens when two lists are adjacent then? Will you consider all neighboring lists and if you do, what happens when multiple lists connect at or near a point?

corey

[NeZbiE]

Well, I havn't programmed any games quite up to that scale, but I'll give my 2 cents anyways.

A lot of the world data (maps, models, textures, pretty much everything except dynamic stuff like other players) is stored on the client side. Therefore, if the maps were subdivided (a la Octrees), all the calculations required to determine which "nodes" are needed would be client side, no? That means, that once the client has determined which nodes are relevant to the current player, then it requests updates concerning those nodes, from the game server. The server would only have to keep track of which nodes players are in, and I think this scheme would help minimize server-side stress.

Of course, to tell the truth, I don't know how it is really done on modern MMOs, but logically I don't think this is too far off the mark :-)

[Goober]

First up, don't let the client decide on the information it gets from the server, you will get people hacking the client and request more information that they wouldn't otherwise get in order to get some sort of advantage in the game (this should probably be Rule #1: Don't trust the client, ever).

For spatial subdivision (a good Google term right there), some form of quadtree or octree (depending on the dimensionality of your game) would suit pretty well. Alternatively, you could look into sphere trees. IIRC there's a pretty good article in one of the Game Programming Gems books on that (although I can't remember which book at the moment, sorry).

HTH.

[Polar Sleuth]

The answer to your question depends on the size of world you want. The larger the world, the simpler the base data structure needs to be and the faster the initial cull needs to be. For standard FPS, game levels are loaded in from individual files; either a portal engine or bsp tree is used to do the culling against the visibility cone. Since it wasn't mention previously, portal engines use rooms with a finite number of doors (portals) leading into other rooms. Visibility tests are done against the portals to determine what rooms are possibly in the visibility cone. As the player crosses the threshold into a new room, the player data structure is passed the pointer or id to the new room.

Large level games use regions to provide a container for action areas (and there are a few portal engines that call their rooms regions just to confuse). Regions like rooms have a finite number of exits into surrounding regions. It is accepted practice that visibility cone will reach only into the next region - as each region will contain geometry that will block line of sight between its exit portals. Again as the player crosses the threshold into a new region, the player data structure is passed the pointer or id to the new region.

For wide open exterior spaces, few structures beat a 2D array of tiles. These are regular regions that have four exits. Visibility is limited to a certain number of tiles in each axis. A square of tiles is then dumped into the next layer of culling.

The trick with each of these types, rooms, regions, and tiles, is to use them as containers for action areas. A BSP tree is the best for visibility culling, but the larger the tree, the more memory it consumes; the more efficient it is at culling, the slower it is to generate. Rooms can hold BSP tree fragments that can be added to the current tree (although this requires a lot of forethought and planning). Tiles and regions can be pointers to files stored not in memory but on disk. As the player moves toward a new tile or region the new data can be loaded. Even for a MMORPG, this allows the minimum amount of data to be in server memory at any given time.

Good luck.
I hope this helps.