Jump to content

  • Log In with Google      Sign In   
  • Create Account


Voxel based world, best practice for sending information


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 riuthamus   Crossbones+   -  Reputation: 4333

Like
2Likes
Like

Posted 14 October 2012 - 07:11 PM

So, to give you some background.

I have a game that we are making. ( the core elements of the game are already in place and we were working from a Single player perspective only ) Unfortunately, we found that to get the multiplayer to work properly we would need to redesign most or all of the information. We have completed that process of handling how the server sends information to the client the question is now "What data to send the to client? and how often?"

We have a very massive world that is created with a perlin noise algorithm. The map is created in 16x16x255 regions know as "chunks". We want to figure out the best possible method for sending this information from the server to the client application. We would like to avoid the pitfalls that minecraft had with loading chunks outside of the players immediate zone, or having chunks missing all together for an extended period of time. What, if any, methods can we use?

Things of interest:
  • We dont want to spam the client with redundant regions
  • We want to prioritize regions closer to the client so they load first
  • We want to limit how much information is sent and optimize that with the premise that the player cant and doesnt need to see everything.
  • Possible use of super regions ( regions grouped together that have not been modified since last seen )
  • Storing the data, once sent, best possible option for storing it.
We have tried a few methods but wanted to see what people thought was the best route. Also, i am not sure if this post belongs here, it tech falls under game development as well as Networking/Multiplayer. If this needs to be moved please do so as we have no problem with that.

Sponsor:

#2 KnolanCross   Members   -  Reputation: 1228

Like
0Likes
Like

Posted 14 October 2012 - 09:53 PM

On login information:
If I got it right, the world is randomly generated by the server, the client player will appear at some starting position and you need to send the world information to it?
Is it a 2d game? If it is, I would define a character vision radius and send the information of character vision radius only (probably a little more), then as it moves I would send the information of the region of the direction it is moving.
On update:
In my own hobby project I had a zones approach, the zones were as big as the character vision radius.
In short, I would check the position of the character, then use its vision radius to check what regions it needed information.
At those regions I would check every monster and character in it and see it they were visible and inside the vision radius, then send the information update.
I didn't have any filter on monsters/players that hadn't change, but if I had to implement it, I would use a timestamp (seconds/useconds) of the last change.
My update rate was 20 messages/second, which was pretty smooth for my needs (in my tests, less than 18 started getting bad). But this will depend a lot on how is the player iteraction and how if you use any prediction algorithm in your game.
As of data storing, I used the same objects in the server/client and created/changed then by messages.

Edited by KnolanCross, 14 October 2012 - 09:55 PM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#3 hplus0603   Moderators   -  Reputation: 4986

Like
3Likes
Like

Posted 14 October 2012 - 10:14 PM

First: Is the algorithm deterministic? If so, could you generate the chunks on the client as well, without sending data, and only send deltas for things that are changed?

Second, quote:

We would like to avoid the pitfalls that minecraft had with loading chunks outside of the players immediate zone, or having chunks missing all together for an extended period of time.


Why do you think that is? And, given what you know about it, what, if anything could be done differently?

enum Bool { True, False, FileNotFound };

#4 riuthamus   Crossbones+   -  Reputation: 4333

Like
0Likes
Like

Posted 14 October 2012 - 11:04 PM

On login information:
If I got it right, the world is randomly generated by the server, the client player will appear at some starting position and you need to send the world information to it?
Is it a 2d game? If it is, I would define a character vision radius and send the information of character vision radius only (probably a little more), then as it moves I would send the information of the region of the direction it is moving.
On update:
In my own hobby project I had a zones approach, the zones were as big as the character vision radius.
In short, I would check the position of the character, then use its vision radius to check what regions it needed information.
At those regions I would check every monster and character in it and see it they were visible and inside the vision radius, then send the information update.
I didn't have any filter on monsters/players that hadn't change, but if I had to implement it, I would use a timestamp (seconds/useconds) of the last change.
My update rate was 20 messages/second, which was pretty smooth for my needs (in my tests, less than 18 started getting bad). But this will depend a lot on how is the player iteraction and how if you use any prediction algorithm in your game.
As of data storing, I used the same objects in the server/client and created/changed then by messages.


This is a 3d game,

We have tested out several methods so far, but we need to figure out the best option. None of us are network coders so messing with this and being optimized it our main concern. Should we create everything on the server, or should we have the clients do some of the leg work and only pass updates to the client? security is also an issue as we dont want to make it easy to hack things.

#5 riuthamus   Crossbones+   -  Reputation: 4333

Like
0Likes
Like

Posted 14 October 2012 - 11:08 PM

First: Is the algorithm deterministic? If so, could you generate the chunks on the client as well, without sending data, and only send deltas for things that are changed?

Second, quote:

We would like to avoid the pitfalls that minecraft had with loading chunks outside of the players immediate zone, or having chunks missing all together for an extended period of time.


Why do you think that is? And, given what you know about it, what, if anything could be done differently?


Yes it is, and yes we have thought of making seeds on the main server, sending that seed to the client on first initial login, having them generate the world ( or at least a decent size from where their location is ) and then having them update the client as they walk around.

As for the pitfalls of minecraft, they randomly would choose chunks to load, didnt have any priority to them ( they do now ), and the overall chunk loading seemed slow. On our single player version we could update a chunk in less than 5ms so we want to try and keep that as close as possible while going over a network. ( i know that speed of internet has an issue with this ) So the goal is to try to come up with the best possible choice for what the client should handle to what the server should, and how best to pass between the two. Are there any methods to this that are normally used? a library we could look at to understand? That is all we are trying to do is find some form of direction. So many possible avenues and choices! :)

Edited by riuthamus, 14 October 2012 - 11:09 PM.


#6 Runesabre   Members   -  Reputation: 157

Like
2Likes
Like

Posted 14 October 2012 - 11:56 PM

If the world generation is deterministic, the first optimization is to have the server share the generation seed with the client and have client and server generate the base map identically.

From that point, think about how often a "chunk" or "object changes.

If you have a world where objects/chunks rarely change once generated, then you can leverage a hybrid update range system where the player has an update range established in which change objects will be sent and then "remembered" on the server so they don't ever need resent BUT can be updated to the player in the event that object or chunk happens to change (so when the player comes wandering back they see the updated chunk even if they were miles away when the chunk changed.). This means chunks have to know who knows about them in order to update all players accordingly. This optimizes the initial loading of dynamic chunks that changed from the base generation since players are only sent info about chunks as they first come across them. Assuming these chunks don't change often, then, you never have to send the info for that chunk again once it's sent the first time.

If you have objects or chunks that change frequently, then you want to go with a standard update radius approach where dynamic objects are sent to the client when the player comes in range and then "forgotten" about when the player leaves range and resent when they come back in range. This strategy works well for objects that change a lot (like other players running around for instance) on large maps.

Kirk "Runesabre" Black
Enspira Online


#7 riuthamus   Crossbones+   -  Reputation: 4333

Like
0Likes
Like

Posted 15 October 2012 - 12:12 AM

Well, some chunks may never change, others will change often. The places that the players live and grow will be the most changed chunks in all of the world. Where chunks that you might mine or travel for quests would be less likely to change.

#8 Runesabre   Members   -  Reputation: 157

Like
1Likes
Like

Posted 15 October 2012 - 12:25 AM

I generally break my chunks/objects down into 3 basic categories:

1. Chunks that the client and server can generate identically with little to no shared information. (static chunks).
2. Chunks that are dynamic but don't tend to change much or at all once they are created at runtime. For instance, a terrain block that is created and never moves or changes state.
3. Chunks that are dynamic and change a lot (state info updates, position updates, etc). Player objects as an example. They change state a lot and move around a lot.

Then I build a system that can tackle these three major areas.

Edited by Runesabre, 15 October 2012 - 12:27 AM.

Kirk "Runesabre" Black
Enspira Online


#9 noizex   Members   -  Reputation: 846

Like
2Likes
Like

Posted 15 October 2012 - 01:53 AM

Problem with shared seed approach is that if you let client be able to generate and cache full terrain data, players will be able to easily check the map for resources (if your game is going to be based on finding them). Usually you generate a lot more than can be seen because without generating its hard to determine which chunks are completly surrounded by others. There is no easy algorithm to categorize chunks as being seen or not seen because it depends on camera, terrain shape etc, so usually you generate full square area around player and only generate smooth mesh / cubes where there is surface border.

Otherwise having seed and sharing only deltas is very tempting. I'm actually interested in any ideas that could prevent players from accessing information about the map easily - think of Minecraft and how players can load map in world viewer and look for resources. If only server knows this information and player receives only visible portion (so the one on the surface) there is no such possibility.

That depends on the game of course, if you don't care about players having advantage because they were able to access world information thats not visible for normal player, then its probably the best route.

#10 Waterlimon   Crossbones+   -  Reputation: 2384

Like
2Likes
Like

Posted 15 October 2012 - 05:01 AM

You could use a separate seed for placing resources, so you send the normal terrain seed, and then send the visible resources individually (not by sending the seed)


Waterlimon (imagine this is handwritten please)


#11 riuthamus   Crossbones+   -  Reputation: 4333

Like
1Likes
Like

Posted 15 October 2012 - 08:56 AM

You could use a separate seed for placing resources, so you send the normal terrain seed, and then send the visible resources individually (not by sending the seed)


That is a very interesting concept... separate them out and never share that seed with the client. Send resources to the client as they get near the chunk... very interesting indeed.

#12 tanzanite7   Members   -  Reputation: 1154

Like
0Likes
Like

Posted 15 October 2012 - 03:23 PM

We have a very massive world that is created with a perlin noise algorithm.

First: Is the algorithm deterministic?

No. Floating point arithmetic is not really deterministic. It is highly dependent on compiler settings, compiler mood (storing an intermediary value in memory causes a rounding while no rounding is done if compiler choosed/managed to use/reuse a register instead) and current FPU state. If you have any code in form of "if(noise_float < 0.5) spawn_block()" then sooner or later it will give different results if not the exact same binary is running.

Playing with fire.

#13 hplus0603   Moderators   -  Reputation: 4986

Like
1Likes
Like

Posted 15 October 2012 - 03:58 PM

No. Floating point arithmetic is not really deterministic.


I'd like to correct this statement on two parts:

First, not all algorithms need floating point.

Second, floating point is fully deterministic within the restrictions of a particular instruction set architecture.
If all CPUs run the same code, they will all come to the EXACT same result.

If some CPUs run an SSE2 path, and others run a x87 path, then no, they will not be deterministic. So don't do that.
If some CPUs run an x86 path, and others run a x86_64 version, then no, they will not be deterministic. So don't do that, either.
If some CPUs run with 80 bits internal precision, and others run with 64 bits internal precision, then on, they will not be deterministic. You have to avoid that, too. Set the floating point control word (rounding, precision) to a known value before you start computation to control for this.

Once all that's done, you can use floating point just as deterministically as any other user-level instruction set architecture feature.

enum Bool { True, False, FileNotFound };

#14 riuthamus   Crossbones+   -  Reputation: 4333

Like
0Likes
Like

Posted 15 October 2012 - 04:20 PM

No. Floating point arithmetic is not really deterministic.


I'd like to correct this statement on two parts:

First, not all algorithms need floating point.

Second, floating point is fully deterministic within the restrictions of a particular instruction set architecture.
If all CPUs run the same code, they will all come to the EXACT same result.

If some CPUs run an SSE2 path, and others run a x87 path, then no, they will not be deterministic. So don't do that.
If some CPUs run an x86 path, and others run a x86_64 version, then no, they will not be deterministic. So don't do that, either.
If some CPUs run with 80 bits internal precision, and others run with 64 bits internal precision, then on, they will not be deterministic. You have to avoid that, too. Set the floating point control word (rounding, precision) to a known value before you start computation to control for this.

Once all that's done, you can use floating point just as deterministically as any other user-level instruction set architecture feature.


um, would floats be deterministic in a C# program compiled for "any cpu"?

#15 hplus0603   Moderators   -  Reputation: 4986

Like
1Likes
Like

Posted 15 October 2012 - 07:11 PM

would floats be deterministic in a C# program compiled for "any cpu"?


I don't know; you have to check what guarantees the CLR makes regarding that. My guess would be "no."

My point is that the CPU itself and instruction set architecture is deterministic. The only non-deterministic parts come in simplifying assumptions sometimes made by software developers, but you don't *have* to make those assumptions, and those the CPUs (with floating point) *can* be deterministic.


enum Bool { True, False, FileNotFound };

#16 tanzanite7   Members   -  Reputation: 1154

Like
0Likes
Like

Posted 16 October 2012 - 08:23 AM

No. Floating point arithmetic is not really deterministic.

I'd like to correct this statement on two parts:

First, not all algorithms need floating point.

Erm, if it is not using floating point then it is not floating point arithmetic. What on earth are you correcting? Some form of straw-man?

PS. OP specifically mentioned Perlin noise, whose implementations almost exclusively use floating point as fixed point is just too slow there (coincidentally, some time ago i explored options to drop floating point in regards with simplex/perlin noise, but gave it up as it is just way too slow). Of course, whether or not OP uses floating point does not invalidate what i said either way.

Second, floating point is fully deterministic within the restrictions of a particular instruction set architecture.
If all CPUs run the same code, they will all come to the EXACT same result.

... then sooner or later it will give different results if not the exact same binary is running.

Which is what i said :/. So, no complaints here either.

Once all that's done, you can use floating point just as deterministically as any other user-level instruction set architecture feature.

Your list omitted the primary source of inconsistencies (which is odd as i specifically mentioned it in my post): stack vs register usage. Compiler decides when and where stack is used when it runs out of full precision registers. Even with VC "precise" compiler flag - platform / OS limitations remain:
* Different OS's have different FPU precision defaults (Win x86 - varying, Win x64 - 64bit, Unix/linux usually - 80bit). Also, VC "precise" allows compiler to ignore _controlfp.
* Even with VC "precise" (which requires extra rounding code to enforce specific precision in addition to other more restrictive/slower semantics) - rounding behavior is CPU architecture specific and differs between x86, ia64 and amd64 (Where x86 and amd64 are specifically mentioned as "This particular semantic is subject to change." Ie. you are essentially in the "unspecified" land).

Playing with fire. Might help roast beef - or roast you. I am not stopping anyone - just warning "if exact repeatability is required - stay away from floating point".

Edited by tanzanite7, 16 October 2012 - 08:25 AM.


#17 japro   Members   -  Reputation: 887

Like
1Likes
Like

Posted 16 October 2012 - 09:29 AM

To avoid unnecessary updates one could also cache chunk data on the client side and essentially version the chunks. So before resending a whole new chunk (after the player walked away and back) you can first check if the "version" on the server has changed. Most of the other things like only sending deltas etc has already been said.

#18 hplus0603   Moderators   -  Reputation: 4986

Like
0Likes
Like

Posted 16 October 2012 - 12:39 PM

Erm, if it is not using floating point then it is not floating point arithmetic. What on earth are you correcting? Some form of straw-man?


My answer was:

First: Is the algorithm deterministic?


To which you answered:

No. Floating point arithmetic is not really deterministic.


So, it seemed to me that you were jumping to conclusions, and/or attacking a straw man, hence I aclled that out.
Also, the statement you made as quoted right here is clearly not factual.

PS. OP specifically mentioned Perlin noise, whose implementations almost exclusively use floating point as fixed point is just too slow there


That's funny, given that the original Perlin noise was specified in terms of byte-size integer values, and it has been implemented on GPUs with 8 bits per component fixed-point colors. It can also be implemented with MMX or plain integer registers in fixed point with good performance. Thus, I have to also say that I don't agree that fixed-point implementations of Perlin noise are slower than floating point.

Your list omitted the primary source of inconsistencies (which is odd as i specifically mentioned it in my post): stack vs register usage.


No, I explicitly included it:

If some CPUs run with 80 bits internal precision, and others run with 64 bits internal precision, then on, they will not be deterministic. You have to avoid that, too. Set the floating point control word (rounding, precision) to a known value before you start computation to control for this.


I am not stopping anyone - just warning "if exact repeatability is required - stay away from floating point".


You were saying that floating point arithmetic is not deterministic, and I disagree, and I think I have literature and facts to back me up. If you do it right, it is totally deterministic. Many shipping games rely on this fact, including some I've worked on.

I think we can both agree that it's not for beginners. It seems like riuthamus is not a beginner, though, and thus may benefit from the actual facts to make an informed decision.
enum Bool { True, False, FileNotFound };

#19 riuthamus   Crossbones+   -  Reputation: 4333

Like
0Likes
Like

Posted 16 October 2012 - 05:22 PM

Thank you all, what you have provided is some very valuable insight. It has, at the very least, helped to affirm some of the methods we have chosen to take. I will update you guys with any further questions and progress we obtain. This should help us to get the multiplayer alpha test started.

#20 0BZEN   Crossbones+   -  Reputation: 2005

Like
0Likes
Like

Posted 17 October 2012 - 06:34 AM

In general it's best to stay away from floating points if you need determinism, although it can be made deterministic. Some algorithms can work fine off fixed point maths, which will be deterministic, but limited in precision. You can certainly use pseudo-random generators to build your world that way.

I've used two deterministic system based on floating point vector maths. One for a replay system, one for a network FPS. Both involved rather complex collision systems, one rigid body physics, so it is possible. None were cross platform, one was on PC supporting AMD and Intel architectures.

Once you start relying on determinism, you need to be very careful and provide debugging tools to detect determinism breaking up as soon as possible. Once it goes wrong, it stays wrong.

Everything is better with Metal.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS