🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to Networking and Multiplayer

Client/Server Tile-Map Considerations

MatrixCubed · 2000-12-21T19:54:20

This really didn''t get a response in the Game Development section, maybe it will spark interest here... I came across a particular problem when designing the server portion of my game. On the client side, the player sees only one part of the map at one time; loading the map dynamically is not really a big thing. However, the server might need to keep track of a lot of different characters all over the place. With a map file of 4096*4096 at 6 bytes per tile, we''re looking at a 96mb file. I thought of a couple of resolutions: 1 - load the entire map into memory 2 - load portions ("regions") based on character occupancy 3 - split the map up into sections (groups of regions) and distribute server load across many machines Of course #1 requires an awful lot of resources for areas that mightn''t be accessed all at once. So we waste memory and CPU cycles maintaining the entire map. I figure #2 would be a good starting design choice, since it''s unlikely that a character will be at EVERY location that requires memory at once; this allows the server to allocate/deallocate dynamically, and avoid wasted resources. But in the event that characters DO overload the server (that means only 1024 characters online at once, ALL spread out over the map evenly to maximize server load) we''re looking at server crash, lost items and character advancement, and general playerbase upheaval. So what about a combo of #2 and #3... the final option lets many servers handle the game (in the event of a large player base), or one server handle the entire game (for a small player base). You''d have a multi-server configuration as below: Server 1 { NorthBoundary=0 WestBoundary=0 EastBoundary=4095 SouthBoundary=2047 IP=24.67.231.19 } Server 2 { NorthBoundary=2048 WestBoundary=0 EastBoundary=4096 SouthBoundary=4096 IP=24.67.231.36 } You could add different IPs, ports even, plus maybe a custom password authentication, per server (for total servers > 1) or just host the whole thing on one machine... and with #2 map handling in effect, you don''t have to worry about overloading the server (for total servers = 1). Comments? MatrixCubedhttp://MatrixCubed.org

Networking and Multiplayer Programming

Started by MatrixCubed December 07, 2000 07:09 PM

23 comments, last by MatrixCubed 23 years, 6 months ago

MatrixCubed

199

Author

December 09, 2000 06:53 PM

Ahh a fellow UO shardie! I did a little bit of scripting for POL... great idea, free UO is

I''m thinking of implementing 128x128 regions... I''ll try different numbers, but I will be using the same map, tile, and region classes for the client as the server, so I want it dynamic.

On another topic, how did you manage object lists? Were they sorted arrays based on (above) regions? Linked lists?

MatrixCubed
http://MatrixCubed.org

[ Odyssey Project ]

Anthracks

122

December 09, 2000 08:28 PM

I''ll have to admit here that I don''t know the nitty-gritty details of the implementation; I helped on the project in more of a support coder role, adding random features like auto-save, the GM paging system, some skills, etc. So most of the code dealing directly with the map was largely irrelevant to me, and I didn''t pick it all up

. I did get those fundamental things I posted though. I can give you my best guess though!

If memory serves me (I don''t even have the source on this computer anymore), this data was in dynamically allocated arrays. I don''t think there are any linked lists in UOX, although maybe that''s changed since I left the project.

Oh wait, *smacks head*, you were asking about OBJECTS. Uh...let''s see. Those were in dynamic arrays also...hmm. Near when I left was when all this region stuff was implemented, so I am not as up to date on it. Previously, everything was just in a huge array, which was massively inefficient. I think what happened is there was an array of as many indexes as there are blocks, and each element of this array had another array containing all the objects/players in that block. This could have been just as well and probably more efficiently with a linked list, like you said.

When an object, npc, etc. was created, it got put into the object list for the appropriate block, and if for whatever reason it wanted to move into a new block, a copy was simply placed in the list of the new block and the old object deleted.

As far as I can remember, these structures were entirely seperate from the actual map data my previous post talked about. That went into a different array; if it went into the same one as the objects, it would just be wasted memory cause the entire map would be in memory.

Did that make sense? I sometimes lack that ability

!

Anthracks

fprefect

122

December 10, 2000 01:28 AM

Here''s my quick-n-dirty suggestions:

1) Don''t bother loading the 96Meg terrain file and thrashing VM, memory map it instead. You will still have random access to the tiles, but you are hinting to the system that most of the data won''t be loaded at once.

2) Instead of 1 file of 4096x4096 tiles, create 64x64 chunks of 64x64 tiles each, so that moving vertically on the map doesn''t jump 4096 * 6 bytes in the file/array (and thrash the cache).

3) Don''t let the players modify the terrain, it''ll make coordination between client and server much better.

4) Track objects and structures independently of terrain.

Matt Slot / Bitwise Operator / Ambrosia Software, Inc.

Shannon Barber

1,684

December 10, 2000 04:09 PM

Are not most of those 16,777,216 tiles, passible?
Create a sparse array, and only stick the blocked tiles in it.

If you want the server to do CD, and have higher accuracy than the clients doing it, then I think you need to lock frames. There''s lag both ways, both from and to the server, you don''t eliminate that by having the server do CD.
In order for Server CD to work, would you not have to send movement request to the server and wait for a response?

Those seem like unacceptable consequences.... the client side CD with a low-accuracy server policing seems like the best method...

Magmai Kai Holmlor
- The disgruntled & disillusioned

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

Sly

128

December 10, 2000 04:19 PM

quote: Original post by MatrixCubed

Make that 5 bytes... I made a couple changes. They''re as follows:
typedef struct _TILE{	unsigned char	m_cHeight;	unsigned short	m_iType;	short		m_iZLevel;} TILE, *LPTILE;
This lets me devise up to 65,536 types of tile images, heights up to 255, and Z levels ranging in -32,768 to +32,767.

Your five byte struct would get expanded to twelve bytes by the compiler by default. This to allow more efficient access to the fields. Your struct would look like this in memory:

unsigned char m_cHeight;
char padding;
char padding;
char padding;
unsigned short m_iType;
char padding;
char padding;
short m_iZLevel;
char padding;
char padding;

Each field is aligned to a four-byte boundary. You could pack the structs, in which case your struct would only take five bytes, but it will not be as fast to access by the processor because it will have to access multiple DWORDs and do byte shifting to get the field it wants.

Steve ''Sly'' Williams
Tools Developer
Krome Studios

Steve 'Sly' Williams Monkey Wrangler Krome Studios
turbo game development with Borland compilers

MatrixCubed

199

Author

December 10, 2000 07:17 PM

quote: Original post by Magmai Kai Holmlor

Are not most of those 16,777,216 tiles, passible?
Create a sparse array, and only stick the blocked tiles in it.

If you want the server to do CD, and have higher accuracy than the clients doing it, then I think you need to lock frames. There''s lag both ways, both from and to the server, you don''t eliminate that by having the server do CD.
In order for Server CD to work, would you not have to send movement request to the server and wait for a response?

Those seem like unacceptable consequences.... the client side CD with a low-accuracy server policing seems like the best method...

Magmai Kai Holmlor
- The disgruntled & disillusioned

What about if the client sends all movement requests to the server, and the server checks them at leisure ... if the server finds any discrepancy, it sends a "here''s your REAL position" message? That way, the server is still tracking all client movement, but not necessarily giving feedback on good messages.

As an alternative to per-tile movement collision checks, I could use a sort of tile-based dead-reckoning system. The client walks forward, so sends new "increase velocity" data to the server. Server only responds if the client collides with something. I guess the server would have to keep the client connection alive as long as messages are being sent or (I suppose) a "ping" packet is received from the client in this case.

quote: Original post by Sly

Your five byte struct would get expanded to twelve bytes by the compiler by default. This to allow more efficient access to the fields. Your struct would look like this in memory
(snip)

Well that throws a small wrench into things, doesn''t it! A 200mb memory chunk certainly isn''t wanted, because there are also things like item lists and NPCs that will have to be tracked. I think I''ll work more on that multi-server layout... then it won''t be such a big issue.

This is turning into quite an interesting thread... keep it up, fellows

MatrixCubed
http://MatrixCubed.org

[ Odyssey Project ]

fprefect

122

December 10, 2000 09:59 PM

quote:
Your five byte struct would get expanded to twelve bytes by the compiler by default. Each field is aligned to a four-byte boundary.

Actually, the original 5 byte structure would be padded out to 8 bytes as follows:

unsigned char m_cHeight;
char padding;
char padding;
char padding;
unsigned short m_iType;
short m_iZLevel;

You can shuffle the data around, but you can''t beat the 8 byte size for these 3 fields. Another option would be to separate the 1byte Height from the 2+2 bytes for Type+ZLevel, so that they would pack better.

The best path would be squeeze the data down to 4 bytes (using bitfields perhaps), so that it packs nicely.

quote:
This to allow more efficient access to the fields.

Actually, compilers try to pad structures so that fields fall on natural bounds for the data type.

Long: padded to start on 4 byte boundary
Short: padded to start on 2 byte boundary
Char: no padding
Array: padded to start/end on 4 byte boundary
Struct: padded to start/end on 4 byte boundary

It''s often faster to read a 2 or 4 byte word when it falls on a 2 or 4 byte boundary, respectively. In addition, reading 2 or 4 byte words from an odd address can cause a hardware exception on certain processors.

Note that the actual padding is compiler dependent, since the ANSI C standard doesn''t specify if or how it should be implemented, but the behavior above is standard in all of the compilers I''ve examined.

quote:
You could pack the structs, in which case your struct would only take five bytes, but it will not be as fast to access by the processor because it will have to access multiple DWORDs and do byte shifting to get the field it wants.

For data stored on disk, packing is a practical balance between speed and footprint. At worst, read the file into memory as a single chunk, then expand the tiles to a (padded) data structure.

As far as speed, you are only talking 1 extra cycle for a read or write misaligned data. Since we are using tiles that will be accessed sparsely and infrequently (as opposed to pixels in an offscreen buffer), the overhead would be negligible compared to the simplicity of design.

Matt Slot / Bitwise Operator / Ambrosia Software, Inc.

Shannon Barber

1,684

December 11, 2000 12:45 AM

Array of packed 1bit booleans on the server - one bit for each tile, blocked or unblocked.
2Megs. A dereference & a mask & store to access or twiddle.

Load a screen & a half on the client, or whatever''s efficient. Each time the player moves into a new tile, load the next row, rip through mobj tree and add appro. players/monsters to screen.

No good reason why a tiled based game can''t run on a dx66

...
You wanted to be able to have the players alter the terrian? Is the world persistent, or does it reset each time you play?
If it''s persistent.... it''s going to get hard.

Magmai Kai Holmlor
- The disgruntled & disillusioned

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

MatrixCubed

199

Author

December 11, 2000 06:58 AM

quote: Original post by Magmai Kai Holmlor
Array of packed 1bit booleans on the server - one bit for each tile, blocked or unblocked.
2Megs. A dereference & a mask & store to access or twiddle.

Load a screen & a half on the client, or whatever''s efficient. Each time the player moves into a new tile, load the next row, rip through mobj tree and add appro. players/monsters to screen.

Hmm. I could do that, and still use the client''s data file (just require the server to do a little more dirty work parsing upon launch).

quote:
No good reason why a tiled based game can''t run on a dx66

One reason: my sprite engine uses the 3D accelerator for rendering and effects. I could devise a basic blitter (for the low-end settings) but that will come later for certain.

quote:
You wanted to be able to have the players alter the terrain? Is the world persistent, or does it reset each time you play?
If it''s persistent.... it''s going to get hard.

The game is persistent (a la EQ/UO/AC/etc), and I want to be able to edit the game world using the client application (we did a lot of this in my old UO shard, which made things very easy to manage when you could see the results realtime). Though we didn''t have map-file editing capabilities then (just world-object editing) I would like to add on to that possibility.

MatrixCubed
http://MatrixCubed.org

[ Odyssey Project ]

Shannon Barber

1,684

December 14, 2000 07:57 PM

This a persistent mutable world, I don''t know how you can quickly determine what information the client needs to downloaded.

You could keep a list of all the changes made from the 0 state, and send it each time a client logs in... maybe only download it when its changed...

Its gonna suck when you to download a significant portion of that 16megs.

Magmai Kai Holmlor
- The disgruntled & disillusioned

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

🎉 Celebrating 25 Years of GameDev.net! 🎉

Client/Server Tile-Map Considerations

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

🎉 Celebrating 25 Years of GameDev.net! 🎉

Client/Server Tile-Map Considerations

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines