Forum

> > Projects > Stranded III Dev. Blog - Comments
Forums overviewProjects overviewLog in to reply

English Stranded III Dev. Blog - Comments

1,827 replies
Page
To the start Previous 1 284 85 8691 92 Next To the start

old Re: Stranded III Dev. Blog - Comments

HudaJan
Super User Off Offline

Quote
Hey DC, long time no see
Been catching up with Stranded 3 dev blog and stumbled across this one. Reminded me I was implementing something of that sort back in my Stranded modding days. Here's a little preview, excuse the horrible audio and video quality

That's all, just wanted to check it, keep up the great work and best of luck with all you're up to

old Re: Stranded III Dev. Blog - Comments

Hurri04
Super User Off Offline

Quote
Huh, for some reason I missed the update from last month...

The "beach_gradient_gone_wrong" certainly looks interesting, almost like terraces or dunes along the beach.
I implemented something similar to this for a university project years ago where I calculated the steepness of each terrain point towards the surrounding points and applied different ground textures at different strengths depending on the angle (and height layer) to add some accents (additionally to the base gradient which blends between layers).
So maybe this "mistake" could be turned into a feature?

The screenshot from the Unity editor is also interesting since it shows a bit of your setup. One thing I notice with this is that the selected chunk GameObject (so presumably all others as well?) does not have a Collider attached. Is this just because you haven't added one yet? Or are there other reasons, like maybe performance problems due to the amount of Meshes you create?
Or are you by chance planning to add a custom physics system? Replacing the MeshRenderer system with a custom one which which uses a single flat quad Mesh and draws it repeatedly via Graphics.DrawMesh (or one of the other variants) is rather simple. All that's needed then is a shader to do a bit of vertex displacement (additionally to the color and texture interpolation) and the (visible part of the) terrain will be created on the GPU. And enabling GPU Instancing then allows for massive performance boosts.
The part which may be a bit tricky would be collision detection and handling. But if you got that working it would allow bypassing the entire process of creating GameObjects for all those chunks, saving lots of overhead of creating, managing and deleting them, as well as baking the Meshes.

old Re: Stranded III Dev. Blog - Comments

Jawohl
User Off Offline

Quote
thanks for sharing @user HudaJan: i remember watching that a few years ago.

Honestly with that concept in mind, it would be rather awesome to see animated faces (other than blinking eyes and what not) while voice chat is active, the mouth widens based on audio volume, widest when maxed

just a thought, but it'd be a nice polish.

old Re: Stranded III Dev. Blog - Comments

Nova
User Off Offline

Quote
Sadly the solution has some huge biases. I have prepared some pictures to show the problem.
... and I wrote some long ass stuff about a solution. Let's hope you get something out of this, user DC, as I did put quite some time in writing and checking this.
I tried to write it in a way that most people can understand it.

Stranded 3 Dev Blog has written
• 1. start at a random point
• 2. Check if all requirements are met
• 3. if √ yes: cool, done!
• 4. go to next point (left to right, top to bottom order)
• 6. if reached bottom right point go to top left point
• 7. check if at random starting point
• 5. if √ yes: all points checked! failed to find spawn!
• 8. if × no: go to 2.


IMG:https://i.imgur.com/yHxVAyQ.png

Green island in a nice blue ocean.

IMG:https://i.imgur.com/FBz76wd.png

Red checkerboard denotes possible spawn area: on land, but near water.

IMG:https://i.imgur.com/w8Ep1qm.png

Violet checkerboard denotes all positions which will lead to the yellow mark at the top being the starting point. Whatever point on the checkerboard area the random algorith chooses it will lead to the mark according to the rules of the spawning algorithm.
For 20% of the possible random points, as the violet area fills ~20% of the picture / map, the spawnpoint will be this yellow mark. In general the left facing borderside of spawn area has a much higher chance to be chosen as a spawn point. (Imgur link for the pictures)

Solution
Your idea of having a list of every possible point and then shuffling them is pretty decent, except that (as you noted already) saving such a list is wasted memory. So, what is the solution? Not storing the list. How do we now get a random list of the points without storing them?
The keyword of what we want is Random permutation. To be more precise we want a way to get a random permutation without storing and shuffling our original list. One field where such things are needed / wanted is random number generation.
Let's take a look at one really simple random number generator, the linear congruential generator of the form
1
x[n+1] = (a*x[n] + c) mod m
You only need to save the last value for x to calculate the next one, and the generator will go through every value from 0 to m-1 in a semi-random order as long as the values for a, c and m have some simple properties.
Calculating example >

The great part about this is that you can start at any point in this list, even a random one and just continue with it. Instead of choosing a random point on the map and then going right from it you just continue the random number generator and get another random point.
Requirements >


How to use this thing now?
Really easy. First we have to select some values.
Select m, a and c >

Now we can change the algorithm to fit our new way to handle it:
New Algorithm has written
• 1. start at a random point (using the normal random number generator everything else uses)
• 2. Check if all requirements are met
• 3. if √ yes: cool, done!
• 4. go to next point (use the custom linear congruential generator to generate the new position x[n+1] depending on the current x[n])
• 5. check if at original starting point from 1.
• 6. if √ yes: all points checked! failed to find spawn!
• 7. if × no: go to 2.

This will - as far as I think - lead to a semi-random order of checking all positions on the map without showing obvious bias.

Disadvantages >


If something isn't clear (or wrong) feel free to ask / correct.
edited 1×, last 04.11.19 04:36:52 am

old Re: Stranded III Dev. Blog - Comments

DC
Admin Off Offline

Quote
@user Nova: Oh wow, pretty interesting and cool solution. I would never come up with something like this because of the involved math magic

The disadvantage you mentioned isn't a real disadvantage in my opinion because the most relevant source of randomness is the starting point which can still be chosen with any RNG.

So thanks a lot for sharing that idea and for the very detailed description! Cool stuff!

I'm not sure if I will use this approach (because of the constraints) but iterating a list randomly is actually a very common task so this is super useful for many things!

@user Hurri04: I do use mesh colliders but you probably saw a LOD mesh. Only the highest detail LOD has colliders on it. All that GPU based stuff would be possible and amazing but I don't want to deal with it

old Re: Stranded III Dev. Blog - Comments

Nova
User Off Offline

Quote
Yeah, it's some nice math magic. I'm very interested in that field and therefore do know a bit about it.

The disadvantage of LCGs are a bit tricky. For games and something like spawn point calculation it's not important, especially if you still have some better RNG for the start value, but never use LCGs for anything important or security related. There are tons of problems in real life because people did use LCGs for stuff like medical studies, passwords, encryption and similar. Don't do that.

You don't have to care about the constraints of the rng at all as long as you just use the example values. They are already correct. (And even if you want to use different values, calculating correct ones is so easy most people without any deeper math knowledge can do it.)

Well, I did write some example pseudo code. Never did code in C#, so haven't tested it - I did convert it into C++ and did test that, through.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static ushort seed = 0;
public static ushort const rngA = 5;
public static ushort const rngC = 7;
public static ushort const rngM = 16;
// Values for 16 bit rng:
// public static ushort const rngA = 25173;
// public static ushort const rngC = 13849;
// public static int const rngM = 65536;

public void randomPoints()
{
	// seed = [random number of better rng];
	for (int i = 0; i < 17; i++) // 17 values
	{
		int point = nextSpawnpoint(seed);
		int pointX = point >> 2; // bitshift for half the bit size of the rng
		int pointY = point % 4; // power of two of half the bit size
		Console.WriteLine("x" + pointX + " y" + pointY);
	}
}
public ushort nextSpawnpoint(int x)
{
	seed = (ushort) ((rngA * seed + rngC) % rngM); // can remove % rngM if it is equal to 65536 and remove the cast
	return seed;
}

Output of this example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
x1 y3
x2 y2
x2 y1
x1 y0
x2 y3
x3 y2
x3 y1
x2 y0
x3 y3
x0 y2
x0 y1
x3 y0
x0 y3
x1 y2
x1 y1
x0 y0
x1 y3

(Because of the very small bit size of this example rng you see some really terrible "random" numbers for the y values (3, 2, 1, 0, 3, 2, 1, 0, 3, ...). That problem is "normal" for LCG and much less severe for bigger values of m. Should not be noticable for your map spawn algorithm. )
edited 1×, last 09.11.19 06:51:03 pm

old Re: Stranded III Dev. Blog - Comments

DC
Admin Off Offline

Quote
@user VADemon: Very cool links, thanks for sharing.

@user Nova: Thanks for the implementation. This is pretty close to C#
65536 doesn't fit into a ushort though (max is 65535)
edited 1×, last 09.11.19 02:25:48 pm

old Re: Stranded III Dev. Blog - Comments

Nova
User Off Offline

Quote
user DC has written
65536 doesn't fit into a ushort though (max is 65535)

You are right, I did fix it in my C++ implementation, but forgot to do it for the C# one. Will correct it in the example, just to make sure.

The links by user VADemon are pretty much the same as my explanation, just with a LFSR instead of a LCG. The latter works with math magic, the first with bit magic... which is also some kind of math magic. Both are usable for this algorithm. Both have advantages and weaknesses.

old Re: Stranded III Dev. Blog - Comments

Uglynator
User Off Offline

Quote
Yay! Another dev blog entry! There is just one thing I am worrying about, and with every new post my worries get bigger:

There is no gameplay yet. Don't get me wrong, a lot of things that have been done so far are integral parts of Stranded, however as of right now, there is no core gameplay loop. (Unless I'm a dunce and just can't recall a blog post where you showed anything like this )
I don't know what exactly your plans are, DC, I'm sure you have a well thought out strategy, and laying good foundations will save a lot of time in the long run. Yet I still can't help but wonder how much longer it will take for Mr. Stranded to learn how to make the hammer.

Don't let that discourage you though! The progress you have been making is steady and at a good pace, especially in the last few months. There have been more than enough times where the dev blog was updated once a month, which is terrific! I hope you still have lots of fun making this game, and I wish you the best of luck.

old Re: Stranded III Dev. Blog - Comments

Sabowulf
User Off Offline

Quote
I just realized it's been 8 years since you started this. 2 years ago you "threatened" to end the project should you not be able to develop a playable alpha.

old Re: Stranded III Dev. Blog - Comments

GeoB99
Moderator Off Offline

Quote
Have you thought of how the Lua infrastructure of Stranded III will be anyhow? Will it use hooks like the same way in CS2D to trigger certain events in the game or you'll base upon a different approach?

old Re: Stranded III Dev. Blog - Comments

Spark Fountain
User Off Offline

Quote
@user DC: Just a picky question: In your blog you wrote at one place that map chunks will be stored with 64x64 meters, but later you mentioned it would be 64m² (which would technically be only 8 x 8 m). Which of these two values fits?

old Re: Stranded III Dev. Blog - Comments

DC
Admin Off Offline

Quote
Oh my... that mistake again. Math... Thanks for pointing that out!
It's 64x64 meters (4096m²). And 4m² was nonsense as well. It's 16m² (4x4 meters). Corrected it.

old Re: Stranded III Dev. Blog - Comments

VADemon
User Off Offline

Quote
Why use gzip/zlib if you can have both better compression and speed with zstd? https://github.com/PaperMC/Paper/pull/2814 relevant comparison and implementation benchmarks in first comment.

Why so much hassle with sub-chunks? From what I understand you store absolute values and don't make use of locality. Suggestion: always store tbe first (XZ = 0,0 = topleft) the first height as an int and all the following will be a single byte (diff) value by which it is smaller or bigger than the previous one:
0,0=465 -> 1,0 (+123) = 588 etc...
0,1 (-15) = 450 etc...

If you don't want to limit yourself to small diffs (this would allow a max diff of 8km across a whole chunk, axis-aligned, if I understand your math right) because it won't be enough for steep hang cliffs:

Add a bitmap. Each bit controls the size of the next diff type. If bit=0, the difference is stored as a byte. If 1, it is 4-byte int. The first bit of this bitmap is unused because the first value at 0,0 is always stored as an absolute 4-byte value.
With this approach there are virtually 0 cases when you'd need two ints in a row to describe height. Imagine a cliff, after a 4-byte fall the terrain becomes plain again and only needs 1-byte diff values from there on.

PS: You can combine your sorting approach to half the required storage if all diffs in a chunk are small. If possible (bitmask's first (unused) bit=0) use 4-bits for height diff (fix: 4bits is +7 and -8), otherwise 1-byte for height diff (+127 to -127)

Hm, do you currently store 6400cm*6400cm for height map? That's at least 40MB then? The 1:1 bitmap would be 5MB but eliminate all need for the current 1/2/4-byte and sub-chunks logic.
360MB just for height maps if the players needs to keep 9 chunks loaded around him? And what's with the server?
edited 2×, last 02.05.20 12:42:14 pm

old Re: Stranded III Dev. Blog - Comments

DC
Admin Off Offline

Quote
I used gzip because it's part of the .NET framework and quite fast. I can give lz4 a try!

Pretty fancy ideas for better optimization. Sounds practical! I will evaluate that. Thank you

Regarding your precision question: No, I only store Y (height) with a 1 cm precision. X and Z are only stored with a 1 m precision. It would be way too much data otherwise as you already pointed out.
edited 1×, last 02.05.20 12:54:51 pm
To the start Previous 1 284 85 8691 92 Next To the start
Log in to replyProjects overviewForums overview