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, 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.
Green island in a nice blue ocean.
Red checkerboard denotes possible spawn area: on land, but near water.
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 Let's use an example with a = 5, c = 7 and m = 16. x denotes the list of random element, x[0] is the first element, x[1] the second, x[2] the third, x[3] the fourth, etc. We start with x[0] = 0. Let's calculate x[1] now:
x[1] = (a*x[0] + c) mod m
x[1] = (5*0 + 7) mod 16
x[1] = 7
Now let's do x[2]:
x[2] = (a*x[1] + c) mod m
x[2] = (5*7 + 7) mod 16
x[2] = (42) mod 16
x[2] = 10
If you continue this you will get the semi-random list
0, 7, 10, 9, 4, 11, 14, 13, 8, 15, 2, 1, 12, 3, 6, 5, 0, ... (repeats as soon as it reaches the starting point again.)
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 To guarantee that you really get every value between 0 and m-1, you need to make sure of three important requirements:
1. m and c have to be relatively prime. This is pretty easy if you make sure that m is a power of 2 (2, 4, 8, 16, 32, 64, ...) and that c is odd. Done
2. a-1 is divisible by all prime factors of m. If m is a power of 2, you just need to make sure that a is odd and not 0.
3. If m is divisible by 4, then a-1 also has to be divisible by 4. If m is a power of 2, then it is nearly always divisible by 2 so you have to make sure that a is some value of the list {5, 9, 13, 17, 21, 25, ...}
How to use this thing now?
Really easy. First we have to select some values.
Select m, a and c m has to be the size of your map relative to the resolution of the spawn point algorithm. Let's say the map is from -128 to +128 (distance ~256) on both coordinates and we want to be able to spawn the player on every whole number. That means there are 256*256 = 65536 = 2^16 locations we can check for spawning - no problem with today's computing power and most of the time we get a valid position much sooner than that. If you want to spawn the player on a bigger map just multiply the random number with a scale factor. Therefore m is 65536.
For a and c you should just google some good values. I got a = 25173 and c = 13849 which results in
x[n] = (25173*x[n-1] + 13849) mod 65536;
(Depending on how Unity / C# handles integer sizes you can maybe use unsigned short and remove the mod operation.)
(To get values for x and z coordinates, split the random number into two halves, for example the first 8 bits and the last 8 bits. This will guarantee that every possible location is available.)
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 No solution without disadvantages.
LCGs are not good random number generators. Take a look at the example numbers 0, 7, 10, 9, 4, 11, ... - even, odd, even, odd, even, odd, ... That is the most glaring weakness of LCGs, but I think it is no problem for using them in this algorithm. The numbers always swap between even and odd for every check, but that only means the next position check can't be exactly next to the current one. It will still check every position Doesn't matter, right?
If something isn't clear (or wrong) feel free to ask / correct. edited 1×, last 04.11.19 04:36:52 am