Oh fun, just saw this thread! I’ve been busy as of late, but I wouldn’t miss the opportunity to post on a thread like this!
Since there are some good approximations posted, I’ll try posting a more precise method. This is what we’ll do:
- For each biome (we could only use the nearest biomes or those within a range to trade precision for speed) we’ll find all the points on its boundary.
- We’ll take each of these points and determine their distance from the player.
- We’ll then arrange these points into ordered sets defined by how far they are from the player. Points closer than their neighbors to the player (minimums) will be the first points in these sets. Sets will be separated by maximum points, which belong to both of the sets they are a boundary for.
- For the most complicated step, we’ll use these sets to and a special mathematical function to determine the weighted area of the biome. Because we want the area of a biome to matter less the further it is from the player, but can’t just multiple the entire area by a weight because not all of it is equidistant from the player, we’ll use calculus to find a precise function to determine the weighted area. Since the biome boundary isn’t defined by a smooth mathematical function, we’ll use the sets to incrementally add up strips of the biome until we have found the weighted area of the entire biome.
- Once all the weighted areas of a biome are added together, we’ll add the total weighted area to the biome type’s total. The end result we are looking for is the ratio between these totals. If we want to know what % a biome is at a point, we’ll divide the biome type total by the sum of all the different biome types’ totals.
This is quite an operation… in fact, I think one could write an academic paper on this question alone! I’ll leave out lots of details for the sake of brevity, but let me know if you have any questions.
To accomplish the first operation you will need to have all the biomes in some format that they can be enumerated. In addition, the points in each biome should be enumerable. If the boundaries are defined by parts, then I’d find the center points of the surfaces between the parts. If adjacent surfaces’ midpoints are not equal (they’ll be more than likely slightly off) then you can find the midpoint of them. Finally, store all these points in an array or circular linked list so that they are easy for enumeration and can be saved between runs of our biome detecting algorithm.
The second and third operations are where our runtime operations start. We enumerate through each biome, and each point. We need two dictionaries of sets stored at the biome enumeration scope (I’ll explain why later) as well as the current set we are constructing. Each set is a minimum first ordered queue. We start at any point, find its distance, and add it to the current set we are constructing. We’ll then continue to the next adjacent point and add it to the set. At this point we need to determine if we are walking further from or closer towards the player. We’ll continue adding points to the set until we reach a point were we were walking away from the player and we find a point that is closer. We don’t add the point that is closer to the player, but add the set of points we were building to the list of scopes. While there are multiple ways to store the dictionary of sets, I’d index it with the two maximum points in the set (making later operations much easier). To do this, we’ll add the set of points we were building to the first dictionary of sets indexed by the last point we added. Then we’ll make a new set, store it in the second dictionary of sets with the same index (the last maximum point added), then add the last maximum point and closer point to the new set. We’ll then continue our walk over the rest of the points until we come across another maximum. At which point we’ll repeat the process by adding the last set we made to the first dictionary of sets with the new maximum found as the index, and create a new set and add it to the second dictionary of sets with an index of the same maximum. The idea is that the first and second dictionaries of points determine which sets the maximum points belong to (since we add them to both sets). The last thing that needs to be noted for this operation is that when you reach the end, loop back around to the starting point. If it is a maximum, then keep the final and starting set separate and make sure the starting set can be found in the second dictionary using the starting point. If the starting point isn’t a maximum, merge the final and starting set, making sure that the starting point wasn’t added to the last set (causing it to appear twice in the resulting merged set).
For the fourth operation we’ll start with any set in the biome. We’ll then use a mathematical function to determine the weighted area from the minimum point to the next point in the set (the neighbor with the smallest distance to the player). Note that we are finding an area of a slice of pie with the radius of the neighbor of the minimum point’s distance to the player, centered at the player, but the edges of the slice converge to the minimum point. The third point to the slice is found at the intersection of the radius and the line from the minimum point to the neighbor on the other side (note that it may not be the third point in the set). This is a simple find a point on a line whose distance is x from a given point. Where it gets complicated is when we decide that we need the weighted area of the pie slice. This means that from the radius of the distance from the minimum point to the radius of the other points, we need to add up infinitesimally small chords, each weighted on their distance from the player, to add up to the weighted area of the pie slice. I’m working on a function to do this now, but after three blank white sheets of paper and a couple hours I decided to post before this thread gets too old.
Once we have our first pie slice, we have a five possibilities. First, the closest neighbor was not a maximum or minimum point. If this is the case, then we have a ring (from the point and the corresponding point we found on the pie slice, to the next point in the set and its corresponding point on the other side of the minimum point). We need to find the weighted area of this ring. I’m also working on a function to do this. Once this area is found, the two furthest points on the ring become the new points and we continue this recursive portion of the algorithm. The second possibility is that the closest neighbor/last point used was a maximum point. If this is the case, then there is an adjacent set that we need to compute the area up to that point. You can go about this any way you would like, but the way I thought of was to combine the sets. Make sure that the maximum point is not duplicated in the resulting set since it was in both sets. Also, make sure to add the corresponding point you found form the last operation so that we can keep track of the boundary of the weighted area we have computed. We’ll start at the resulting merged set’s minimum and repeat the process from the top. The third possibility is that the next point we are going to be doing calculations up to is farther from the player than the minimum point in another set. (To make this determination faster, we may choose to store the minimum points of sets in a minimum first queue, so we only need to do one comparison.) If this is the case then we have to compute the weighted area (either as a pie slice or ring) up to that minimum’s distance from the player. We’ll then split our set into two sets, one for each side of the minimum point. The minimum point will be in both sets temporarily. The boundaries from the last area computation will become the new minimum points in each set, with the minimum point as the second in each set (since it is equidistant with the points). From there both sets will eventually need to be computed. Unless the biome has holes in it (which this algorithm would handle fine), they will not be merging back together. This means that whatever set we don’t immediately continue with will need to be added to a list of sets to finish up. Note that this check does need to be performed every time before area is computed, even when starting with a minimum point and computed a weighted pie slice’s area. You always need too check if there is a ‘stalactite’ hanging down into the area that you would be computing. The penultimate possibility is that there is only one more point in the set. This is closes a set and means that it is finished. The shape formed will be a triangle with a semicircle cut out of it (kinda like an inverted pie slice). I believe that the same mathematical function as for the pie slice can be used, but I’ll verify that once it is complete. The final option is like an edge case of the previous possibility. If the set ends up with two points equidistant from the player, then we can find the closest point on the line between them (the midpoint, I believe) to the player. This will leave us with one more weighted ring operation and then two inverted pie slice weighted area operations. Make sure to complete/finish computing all sets before moving onto the next step. And that’s all we need to do to compute the weighted area! Yay, the hard part is over!
Finally, we’ll need to keep track of the weighted area of each biome type computed so far. Many different weights can be used in the mathematical functions but I’m working on using an exponential decay (1/x^n where n >= 0) as the weight. This will allow by inputting different values for n, the area to be unweighted (n = 0) and the biome with the greatest area always wins) to pretty much only the closest biome gets considered (n = math.huge). The ratio of a biome type where a player is located at is represented as the weighted area of biome type to the total weighted area of all biomes found. If you multiply this ratio as a decimal by 100 and round, then you have your percentage for a given biome type.
Well, I’ll tell you what. This is probably the longest post I’ve made in my time on this forum and on the old scripting helpers forum. I was going to add pictures and what not, but that would take forever and I assume this is going to be a TLDR post for most unless they are interested in this topic, and hopefully those interested will have enough background in the area to decipher my gibberish. Really, an academic paper could be written on this topic. If I was to do so I’d clean up the logic, add diagrams, and make sure to post the mathematical functions with some pseudo code. I might not even include the proof of the mathematical functions to save space… but forums aren’t the place to post academic papers! So here is my gibberish! Let me know if you have any questions. I’ll get to work on those promised mathematical functions.
