# Biome detection algorithm?

Hey guys, I’m struggling with a sort of logic problem and seeking some help in solving it.

So, this is the problem. These arbitrary black shapes are biomes in the world. They’ll each have their own lighting settings. Lets say the bottom has a green tint, and the left has an orange tint, to make things easy.

Now, the red dot is the player.
I’m needing an algorithm that can detect what % of the closest biomes you’re in(closest being determined by a distance threshold, so it’d likely ignore the top and right biomes since they’re significantly farther)

I’m needing to determine the percentages because I’m wanting to blend the lighting settings accordingly. So theoretically , if you were exactly 20% “in” the bottom and 20% “in” the left , your color tint would have a 20% green and 20% orange color.

The problem is, I can’t just use a simple point for the biome centers to check distance, because it doesn’t actually respect the shape.

Any thoughts or advice would be appreciated

3 Likes

Perhaps sampling from various points? like so:

The more points it detects in range, the more percentage from that biome.

1 Like

Yeah, I’m considering this. It may be the best solution

Various points works ok, but might have some issues. Another possible solution is to draw a ray between each of your points and use the ClosestPoint method, then use those points instead.

The only caveat with that is that you will have to check the distance of the point to make sure it actually exists on the line between the two points (because by nature a ray is infinite in 1 direction).

3 Likes

we’re currently drawing their borders with actual parts

so I may try simply raycasting from the player to the center of the biome and using the distance from the ray hit point

1 Like

You could try raycasting down in a circular array around the player on a fixed radius, and checking what biome each ray strikes, then doing percentage calculations based on the number of rays that strike each biome. This would give you more of an estimate than a concrete number though.

2 Likes

If you know both points, why raycast? I may be missing something, but can’t you just subtract one Vector3 from the other and use the magnitude of the result?

That would only tell the distance from the centre. This could cause cases where you’re right at the edge of a biome, but the centre is farther than another biome, causing it to do the wrong lighting effects.

2 Likes

Seems pretty clever to me, but you’d have to fire a lot of rays in order to get a decent resolution

How high of a resolution would you realistically need? If biomes are large, then I don’t imagine you’d need a high resolution.

There’s also a size bias on that solution.

More rays would hit the one below, doesn’t necessarily mean it’s closer

Or if you cast straight down in this case and not to the point on the circle, it wouldn’t hit that island at all

1 Like

Good point. It’s pretty influenced by how variable your biomes are in size. What if you fired more rays closer to the center of the circle? That would weigh closer biomes more heavily than farther ones.

One way of doing it might be to draw out the biome boundaries in parts, like you’ve done, and put those drawn boundaries at an elevation where you won’t see them (i.e. underground) or make them invisible. Then draw a ray for each biome from the character’s XZ and the drawn boundary Y towards each biome’s centre, and how far the ray gets before it hits a boundary would be how far you are from that biome.

Sorry if I explained this in a convoluted way, I’ll try and get a couple of diagrams together if I can.

The advantage of this would be it’s relatively lightweight, and should scale well should you add more biomes.

1 Like

If you split your biome borders into convex polygons, you can test whether or not a point is inside by checking if it lies on the same side of a line that passes through pairs of vertices of the polygon in order. The side to check for depends on the ordering of your vertices.

2 Likes

I think they’re also trying to get the distance from a biome’s border, because they want to tween lighting settings based on proximity to each one.

1 Like

That should be fairly trivial for a decent approximation, then. Just choose the shortest distance to an edge that isn’t shared between two convex hulls in the same biome.

3 Likes

convexPolygonTest.rbxl (13.8 KB)

I put together a quick test of what I’m talking about. See the script in ServerScriptService. Convex decomposition is up to you, sorry! I would just do it manually myself…

EDIT: Oh, I should probably explain how it works. Try running it and dragging the part called Test in and out of the pentagon formed by the other parts.

EDIT 2: I’ll also give you a hint for convex decomposition: Delaunay triangulation.

EDIT 3: I updated the rbxl to have a really janky visualization drawn.

8 Likes

This is really neat! Thanks

1 Like

This isn’t true for convex polygons, and certainly not concave.

One option, since the areas are nicely defined by a small number of parts, is to pre-calculate the vertices of the resulting polygons. The nearest vertex to the player (in the XZ plane) isn’t necessarily the nearest point on the polygon to the player, but it will an endpoint of one of the sides that does contain the nearest point. For mostly-convex biomes, the nearest vertex may be a good enough approximation, and you can find it with a simple loop over all the vertices. If not, you only need examine the two sides that have it as an endpoint and check the distance from player to nearest point on those 2 line segments.

2 Likes

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:

1. 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.
2. We’ll take each of these points and determine their distance from the player.
3. 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.
4. 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.
5. 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.