Advertisement

Ore Generation Algorithm

Started by June 23, 2021 05:26 PM
8 comments, last by LorenzoGatti 3 years, 2 months ago

I'm currently developing a game that is meant to be very similar to mining games such as Motherload and Miner Disturbance. If you haven't heard of them before, the main goal of the games is to dig down underground to gather ores that gives the player points that can be used to upgrade their gear, or just achieve a higher score. The ores you find change as you get further down, with rarer ores becoming more common the further you progress.

My game involves the same system, though I am struggling on coming up with an algorithm to achieve it. I have never implemented something like this before so I am unaware if there is actually an optimal way to implement this type of system. My current attempt of it has specific ores having a Common Depth variable that is used to say at which depth the ores are the most common. So at their specific common depth, the ore will have a 100% chance to spawn, which will decrease as the player is further away (Either being at a higher or lower depth). This from what I can understand should be fine, though It's checking the distance between the current achieved depth and that common depth which is where I'm really struggling.

Currently I get the distance between the depth of the block the ore will be placed within and the common depth by simply Common Depth - Depth. I then use this offset/distance to get a percentage away from that Common Depth by (DepthOffset / Common Depth) * 100 to see if that type of ore should spawn. The main issue comes when we start getting to much larger distances. For example: I have a Copper ore that has a Common Depth of 1. I want it to be the first ore the player encounters and something that while get rarer as they get deeper, is still present in much smaller amounts. At a depth of 1632, the percentage chance to encounter the copper ore becomes 163200%. Obviously I can understand why, dividing 1632 by 1 (The Common Depth) * 100 isn't going to give anything ideal but I'm honestly just not sure how to handle these depths with much higher distances. At this point I am basically asking for maths help as I'm unsure about how to change the algorithm to solve this problem. I have tried several things such as capping the percentage but that doesn't help either.

I'd really appreciate any maths help, but also any possible recommendations for other algorithms to use would be amazing. While I don't see an issue with the system I've implemented (Aside the maths), I strangely feel that it isn't ideal.

Never done anything like it, but after reading your description, I would start with defining a minimal and a maximal depth of an ore. Outside this range you will not find the ore obviously. Within the range you could derive the middle depth to have the highest concentration, but this isn't required. You could move that point very much upward or very much downward within the range, to get loads of the stuff very early, or a little bit only for a long time. You could also randomize it, and then depending on the spot where you dig you get different results.

The overall shape of the concentration along the depth can be changed too, but for starters, just linear from minimal to maximal and back to minimal along the vertical depth is likely sufficient. (You could for example also have the same concentration for much of the depth range, and only reduce very fast near both ends. Many other shapes are possible.)

As for math, assuming you know highest, maximal, and lowest depths (let's call these H, M, and L) and your current depth D, the first thing to do is decide whether D is above or below M. Let's assume it's above, so D is between H and M (written H ≤ D ≤ M). The other case (D ≥ M) is symmetrical and works the same except you use L instead of H. Also, since L is below M, the sign of the subtraction swaps which you may want to compensate for.

What you want is a normalized depth ‘d’, which is 0 at either end, and 1 at M. In that way, it doesn't matter how far the depths H, M, and L are away from each other. The simplest is d = (D-L) / (M-L). If D==L then d = (L-L)/(M-L) = 0. If D==M then d = (M-L)/(M-L) = 1. If D is in the middle between M and L at (M+L)/2 == (M/2+L/2), then d = ((M/2+L/2)-L)/(M-L) = (M/2-L/2)/(M-L) = ½ * (M-L)/(M-L) = ½ .

You can try some numbers and compute d for various D if that is simpler for you.

Now 'd' runs from 0 to 1 at depth M and symmetrically from 1 back to 0 as you go further down. If that is sufficient, we're done. Otherwise you need apply a linear transformation from d to whatever destination range you want to have. In the latter case, you can of course fold both computations into one if you want.

BTW: What I have done is linear interpolation what you can read about at https://en.wikipedia.org/wiki/Linear_interpolation

Advertisement

Alberth said:

Never done anything like it, but after reading your description, I would start with defining a minimal and a maximal depth of an ore. Outside this range you will not find the ore obviously. Within the range you could derive the middle depth to have the highest concentration, but this isn't required. You could move that point very much upward or very much downward within the range, to get loads of the stuff very early, or a little bit only for a long time. You could also randomize it, and then depending on the spot where you dig you get different results.

The overall shape of the concentration along the depth can be changed too, but for starters, just linear from minimal to maximal and back to minimal along the vertical depth is likely sufficient. (You could for example also have the same concentration for much of the depth range, and only reduce very fast near both ends. Many other shapes are possible.)

As for math, assuming you know highest, maximal, and lowest depths (let's call these H, M, and L) and your current depth D, the first thing to do is decide whether D is above or below M. Let's assume it's above, so D is between H and M (written H ≤ D ≤ M). The other case (D ≥ M) is symmetrical and works the same except you use L instead of H. Also, since L is below M, the sign of the subtraction swaps which you may want to compensate for.

What you want is a normalized depth ‘d’, which is 0 at either end, and 1 at M. In that way, it doesn't matter how far the depths H, M, and L are away from each other. The simplest is d = (D-L) / (M-L). If D==L then d = (L-L)/(M-L) = 0. If D==M then d = (M-L)/(M-L) = 1. If D is in the middle between M and L at (M+L)/2 == (M/2+L/2), then d = ((M/2+L/2)-L)/(M-L) = (M/2-L/2)/(M-L) = ½ * (M-L)/(M-L) = ½ .

You can try some numbers and compute d for various D if that is simpler for you.

Now 'd' runs from 0 to 1 at depth M and symmetrically from 1 back to 0 as you go further down. If that is sufficient, we're done. Otherwise you need apply a linear transformation from d to whatever destination range you want to have. In the latter case, you can of course fold both computations into one if you want.

BTW: What I have done is linear interpolation what you can read about at https://en.wikipedia.org/wiki/Linear_interpolation

I may just be being stupid but just for clarity, what do you mean by the highest, maximal, and lowest depths which you labelled H, M, and L? I'm assuming M is the maximum depth that the ore can appear, though is the highest and lowest depths referring to the highest depth and the lowest depth the player can reach respectively? Completely unrelated to the ores themselves. If that is the case, would the minimum depth of the ore matter?

I may have swapped Highest and Lowest, I think, sorry

Alberth said:

Ah, Middle! ahaha. I see now, I was just being a little stupid!

I'll have a go at implementing that now. From what I understand, that should work ideally! I'll let you know how it goes once I've implemented it. Thank you a bunch

Advertisement

Alberth said:

Never done anything like it, but after reading your description, I would start with defining a minimal and a maximal depth of an ore. Outside this range you will not find the ore obviously. Within the range you could derive the middle depth to have the highest concentration, but this isn't required. You could move that point very much upward or very much downward within the range, to get loads of the stuff very early, or a little bit only for a long time. You could also randomize it, and then depending on the spot where you dig you get different results.

The overall shape of the concentration along the depth can be changed too, but for starters, just linear from minimal to maximal and back to minimal along the vertical depth is likely sufficient. (You could for example also have the same concentration for much of the depth range, and only reduce very fast near both ends. Many other shapes are possible.)

As for math, assuming you know highest, maximal, and lowest depths (let's call these H, M, and L) and your current depth D, the first thing to do is decide whether D is above or below M. Let's assume it's above, so D is between H and M (written H ≤ D ≤ M). The other case (D ≥ M) is symmetrical and works the same except you use L instead of H. Also, since L is below M, the sign of the subtraction swaps which you may want to compensate for.

What you want is a normalized depth ‘d’, which is 0 at either end, and 1 at M. In that way, it doesn't matter how far the depths H, M, and L are away from each other. The simplest is d = (D-L) / (M-L). If D==L then d = (L-L)/(M-L) = 0. If D==M then d = (M-L)/(M-L) = 1. If D is in the middle between M and L at (M+L)/2 == (M/2+L/2), then d = ((M/2+L/2)-L)/(M-L) = (M/2-L/2)/(M-L) = ½ * (M-L)/(M-L) = ½ .

You can try some numbers and compute d for various D if that is simpler for you.

Now 'd' runs from 0 to 1 at depth M and symmetrically from 1 back to 0 as you go further down. If that is sufficient, we're done. Otherwise you need apply a linear transformation from d to whatever destination range you want to have. In the latter case, you can of course fold both computations into one if you want.

BTW: What I have done is linear interpolation what you can read about at https://en.wikipedia.org/wiki/Linear_interpolation

So that works quite well, Thank you! The only issue I've found is for a ore such as Copper, I want it to appear throughout the entire game, at even the lowest of depths but with just a super super low chance to spawn. With the way Linear Interpolation works, it doesn't seem like I can do this since if I have a very high maximum depth value for the ore cause I want it to appear at all depths, It will take a lot longer to go from 1 to 0 when interpolating from the middle to the maximum, meaning that the ore still has much higher chances of spawning for much longer then it ideally should. I kinda hope that makes sense.

So what you're saying is that the chance of finding ore is too high? Assuming you use ‘d’ for chance, that thus means ‘d’ is too high? So, linear interpolation grows too fast? The question is thus, what curve do you want for chance as d runs from 0 to 1?

See it as a graph, horizontally d from 0 to 1, vertically chance from 0 to 1, current graph is a straight line from (0, 0) to (1, 1). This is too much, so how should it run instead?

There are 2 parts to this. You found the speed of growth, but there is also scale. At the optimal depth (d==1), should you dig up ore every single time (ie 100% chance), or should that be less? The point here is, if you want the optimal depth give less ore, the entire curve is scaled down. A change at optimal depth thus also affects all other depths.

For example, assume that you want 1 in 4 attempts to succeed at optimal depth. With linear interpolation you would then draw a line from (0, 0) to (1, ¼). You can clearly see all depths are affected, including the depths you currently have a problem with.

So, decide chance at d=0 and at d=1 giving you the desired values at both endpoints of the graph. Then think what the curve between them should be.

For changing the curve itself, if you want the chance to 'stick' closer to the chance==0 line, a simple way is to take a power of d. Eg d*d grows quadratically from 0 to 1, higher powers have even stronger curves.

I guess what you also need is not just the rarity of the ore but also some randomizer which chooses from probability of all ores possibly found on a certain depth to select one which is then finally placed. So lets say you collect all ores that have a chance to appear at certain depth, add all their probability values together and take the comulated value as 100%, then you can calculate for each ore the final probability of appearance.

Lets say you have Copper at a constant 10% probability, Iron at 40% and Gold at 5%, then you have a 55% chance to find an ore. This means Copper at 18% Iron at 72% and Gold at 9% chance as final probability values when you gather an ore

You could also try a point system with the ores. It would work very similar to what Shaarigan suggested. For example: At level 1, copper would have 100 points, silver maybe 10 points, gold 1 point, and platinum 0 points. As you generate each layer deeper, copper might lose 1 point until it reaches 1, but it will always have at least 1 point. Silver could gain 1 point until it reaches it's maximum of 100, then slowly lose a point every 2 or 3 levels until it bottoms out at 2 points. That way there's always a small chance of copper, and a slightly greater chance of silver.

The nice thing about a system like this is you can make it as complicated as you want and you're not stuck on a line or a curve. For example: Gold could become increasingly more common until it reaches it's max at 100 points, then dwindle off to 20 or 30 points, then go up to a new max at 150 points as the player goes deeper and deeper. In fact golds chances of showing could be constantly changing deeper and deeper.

To add more variance to the game, you could also randomly change the max point values of each ore as well. One game the player plays might have gold everywhere, but in the next game gold might be rare (but the game makes up for it by adding more of the other ores).

However, to make a system like this work, you have to remember that 100 is not the maximum point value. At each level you would have to add up the point values for all the ores, then choose a random number between 1 and the total point value at that level in order to figure out which ore to place. At level 1 for example, copper 100, silver 10, gold 1, totals 111 points. So you would choose a random number between 1 and 111. You'll have to do some serious experimenting to figure out what kind of percentages you want at certain levels.

I liked Motherload BTW. I have to admit I didn't like Super Motherload as much though. Something about trying to get points rather than just trading in the ore for cold-hard cash kind of irked me a little. But that's probably just me. Good luck with the project! I once thought about doing the same thing, but if I'm honest with myself, I'll never get around to doing it. One thing I thought about adding was sand blocks. If the player digs under a sand block, it dumps on their digger. Doesn't kill them, but they're stuck and it takes a bunch of fuel to get out.

Good Luck!

This topic is closed to new replies.

Advertisement