Dev Blog
Hi, this is the Stranded III development blog (see also Forum Thread, Comment Thread).
Entry 90 - Random Spawning - November 3, 2019
More Icons
I recorded a video of me drawing new icons.
You can see that some of the icons are based on already existing items that I made earlier. I was forced to draw those again because I made the mistake to create them with only 32x32 pixels which is definitely not enough.
Drawing Icons.
More Trees
There are only palm tree models as of now. I want to have jungle biomes as well though.
Therefore I started working on some jungle trees.
Creating a tree model.
Aaand this is what it looks like when you add an unfinished and untextured tree model to the game and define a biome which only contains that object:
(click for larger version)
Beautiful. Somewhat looks like big mushrooms.
Finding A Random Spawn Position (attention: boring stuff!)
Time to explain some implementation details! Fun fun fun!
As you might have seen in my previous blog post there will be an option to define where the player will be spawned when creating a random map.
This option requires me to find a random position on the map which matches the configured conditions. How to do that?
The (probably) most naive approach would be the following:
1. Find a random spot (a random x and z coordinate generated with a random number generator)
2. Check if all requirements are met (e.g. is it sea, beach or land?)
3. if 
yes: cool, done!
4. if 
no: start over (1.)
This approach is cool because it's very simple. It's easy to implement and it just works most of the time.
Correctly. Only MOST of the time. We can't guarantee that it always works because we might have a map which does not have any landmass at all (for instance).
Did you ever try to spawn a player on a beach which doesn't exist? It's a bad idea.
If you know something about programming you might notice that what I explained above is a loop.
The exit condition is step 2. We can't guarantee that this will be true at some point for all possible maps. Therefore we end up with something which must be avoided at all cost: An infinite loop.
The game will just keep checking random points forever. Never finding a valid spawn point.
This will result in a "the application does not respond"-kind of "crash".
A straightforward hack to tackle this issue would be to count the attempts and to stop at some point:
1. Find a random spot
2. Check if all requirements are met
3. if yes: cool, done!
4. if no: increment a counter
5. If the counter exceeds a limit: Cancel (use a fallback position or show an error)
6. Otherwise: start over (1.)
This isn't a perfect solution though.
The points we pick are entirely random. Therefore it might happen that some points are never checked even with a high number of attempts. We might miss valid spawn positions!
Also we might do a lot of unnecessary work. Since the points are randomly chosen we may check the same points multiple times. That's bad and might make finding a valid spot slow (if step 2 is slow).
To optimize the algorithm we should try to check every point just exactly once:
1. start at the top left point
2. Check if all requirements are met
3. if yes: cool, done!
4. otherwise check if at bottom right point
5. if yes: all points checked! failed to find spawn!
6. if no: go to next point (left to right, top to bottom order) and go to 2.
Okay cool! Works! But this isn't random anymore. We will always get the leftmost and topmost point that matches the conditions.
I can think of two subpar ways to bring back the randomness to the above approach:
Shuffle before iterating:
We could store all the points in a list and shuffle it randomly.
Afterwards we can check the points and return the first one that matches.
Wastes memory because we have to store data we already have redundantly
A lot of additional work for shuffling the data
Store all valid points and pick a random one:
Instead of leaving the loop at step 3 we would just store all valid points in a list.
After iterating over all points we would just pick a random one from the list.
We would always have to check ALL points just to find one random point.
Both solutions do the job but they also do a lot of useless work which is not needed.
Therefore I came up with a better solution:
Why not just start at a random point instead!?
This way we can check all points in sequence but since the starting point is random the result will be random too.
Also we don't need to do any extra work and we don't have to save a lot of extra data.
Even better: As soon as we find a matching point we can stop searching!
So this is the approach I'm using in more detail:
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.
Hooray! That's it! Congratulations for reading all this stuff. I didn't expect that anyone would do that. Are you interested in programming and/or solving problems? What do you think about my approach? Do you have other ideas how to find a random spawn point efficiently?
I recorded a video of me drawing new icons.
You can see that some of the icons are based on already existing items that I made earlier. I was forced to draw those again because I made the mistake to create them with only 32x32 pixels which is definitely not enough.
Drawing Icons.More Trees
There are only palm tree models as of now. I want to have jungle biomes as well though.
Therefore I started working on some jungle trees.
Creating a tree model.Aaand this is what it looks like when you add an unfinished and untextured tree model to the game and define a biome which only contains that object:
(click for larger version)
Beautiful. Somewhat looks like big mushrooms.
Finding A Random Spawn Position (attention: boring stuff!)
Time to explain some implementation details! Fun fun fun!
As you might have seen in my previous blog post there will be an option to define where the player will be spawned when creating a random map.
This option requires me to find a random position on the map which matches the configured conditions. How to do that?
The (probably) most naive approach would be the following:
1. Find a random spot (a random x and z coordinate generated with a random number generator) 2. Check if all requirements are met (e.g. is it sea, beach or land?) 3. if yes: cool, done! 4. if no: start over (1.)This approach is cool because it's very simple. It's easy to implement and it just works most of the time.
Correctly. Only MOST of the time. We can't guarantee that it always works because we might have a map which does not have any landmass at all (for instance).
Did you ever try to spawn a player on a beach which doesn't exist? It's a bad idea.
If you know something about programming you might notice that what I explained above is a loop.
The exit condition is step 2. We can't guarantee that this will be true at some point for all possible maps. Therefore we end up with something which must be avoided at all cost: An infinite loop.
The game will just keep checking random points forever. Never finding a valid spawn point.
This will result in a "the application does not respond"-kind of "crash".
A straightforward hack to tackle this issue would be to count the attempts and to stop at some point:
1. Find a random spot 2. Check if all requirements are met 3. if yes: cool, done! 4. if no: increment a counter 5. If the counter exceeds a limit: Cancel (use a fallback position or show an error) 6. Otherwise: start over (1.)This isn't a perfect solution though.
The points we pick are entirely random. Therefore it might happen that some points are never checked even with a high number of attempts. We might miss valid spawn positions!
Also we might do a lot of unnecessary work. Since the points are randomly chosen we may check the same points multiple times. That's bad and might make finding a valid spot slow (if step 2 is slow).
To optimize the algorithm we should try to check every point just exactly once:
1. start at the top left point 2. Check if all requirements are met 3. if yes: cool, done! 4. otherwise check if at bottom right point 5. if yes: all points checked! failed to find spawn! 6. if no: go to next point (left to right, top to bottom order) and go to 2.Okay cool! Works! But this isn't random anymore. We will always get the leftmost and topmost point that matches the conditions.
I can think of two subpar ways to bring back the randomness to the above approach:
Shuffle before iterating:We could store all the points in a list and shuffle it randomly.
Afterwards we can check the points and return the first one that matches.
Wastes memory because we have to store data we already have redundantly A lot of additional work for shuffling the data Store all valid points and pick a random one:Instead of leaving the loop at step 3 we would just store all valid points in a list.
After iterating over all points we would just pick a random one from the list.
We would always have to check ALL points just to find one random point.Both solutions do the job but they also do a lot of useless work which is not needed.
Therefore I came up with a better solution:
Why not just start at a random point instead!?
This way we can check all points in sequence but since the starting point is random the result will be random too.
Also we don't need to do any extra work and we don't have to save a lot of extra data.
Even better: As soon as we find a matching point we can stop searching!
So this is the approach I'm using in more detail:
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.Hooray! That's it! Congratulations for reading all this stuff. I didn't expect that anyone would do that. Are you interested in programming and/or solving problems? What do you think about my approach? Do you have other ideas how to find a random spawn point efficiently?