[Trigger] Intersecting Donut Point Search

[Damage]

Hello All,

I'm trying to make a spawn system for a kind of swarm survival game, and the spawning trigger spawns enemies in a "donut" shape around each hero, like this:

This means monsters spawn within 1800 and 2400 distance of your hero. (out of your line of sight, but not so far away as to take a long time to reach you.)

However, I want each player to have his own spawning ring, so as the players run around, they may have their ring intersect with another players. If so, this would cause double spawning in the areas they intersect. This is okay though! I want this behaviour.

However, the problems appear when a player moves close enough to another hero that their spawn donut gets extremely close (or on top) of another player. I don't want units to spawn inside the donut of another player. Like this:

There's also one final problem. It's possible to arrange the players in such a way that one player has a fully teal / cyan area, like this:

In the case where a player is totally surrounded, and no valid location can be found, I want it to pick one of the other player's spawn positions and add it to their donut instead.


So far, this is the code I've made.

• Spawn
  • Events
    • Time - Every 0.10 seconds of game time
  • Conditions
  • Actions
    • Set temp_group = (Units of type Mercenary)
    • Unit Group - Pick every unit in temp_group and do (Actions)
      • Loop - Actions
        • Set SpawnOrigin = (Position of (Picked unit))
        • Set temp_group2 = (Units within 2600.00 of SpawnOrigin matching (((Owner of (Matching unit)) Equal to Player 23 ($$Dark Green)) and (((Custom value of (Matching unit)) Equal to (Player number of (Owner of (Picked unit)))) and (((Matching unit) is alive) Equal to True))))
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
            • (Number of units in temp_group2) Greater than or equal to 40
          • Then - Actions
          • Else - Actions
            • Set SpawnFailureCount = 0
            • -------- Find Spawn Location --------
            • Trigger - Run Spawn Location Finder <gen> (ignoring conditions)
            • -------- Define New Intervals --------
            • Unit - DO THE SPAWN STUFF (LOTS OF CODE HERE - ALREADY FINISHED)
            • Custom script: call RemoveLocation(udg_SpawnPoint)
        • Custom script: call DestroyGroup(udg_temp_group2)
        • Custom script: call RemoveLocation(udg_SpawnOrigin)
    • Custom script: call DestroyGroup(udg_temp_group)

And

• Spawn Location Finder
  • Events
  • Conditions
  • Actions
    • Set temp_point = (SpawnOrigin offset by (Random real number between 1800.00 and 2400.00) towards (Random angle) degrees)
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • (Terrain pathing at temp_point of type Walkability is off) Equal to True
      • Then - Actions
        • Set SpawnFailureCount = (SpawnFailureCount + 1)
        • Custom script: call RemoveLocation(udg_temp_point)
        • Trigger - Run (This trigger) (ignoring conditions)
        • Skip remaining actions
      • Else - Actions
    • Set SpawnPoint = (temp_point offset by 0.00 towards 0.00 degrees)
    • Custom script: call RemoveLocation(udg_temp_point)

This currently only replicates the behaviour of pictures 1 and 2 (donut shape, and increased spawning of overlapping donuts) but it doesn't prevent spawning when too close to another player's safety zone, and there's no failsafe for when no location is valid.


tl;dr
How do I make spawns in a donut shape around a unit / hero without spawning too close to another unit who also has its own donut, and secondly how do I move the spawn to a nearby other donut if that player is completely surrounded by the "safe zone" of other units.

 

[Damage]

And before all you script-elitists kick in, I know it's in GUI because that's all I'm good at - and running a trigger in the middle of another trigger to define global variables is the only way I can do a "function call" so to speak.

If you can write this better in JASS, be my guest but know that I need to be able to import it to the normal (PTR) World Editor or it's not helping me.

 

[~El]

This is a really interesting problem. It'll probably involve quite a bit of trigonometry to figure out properly, so let's dive in!

Let's break it down into some digestible sub-problems.

Problem #1: How to figure out when a player's "donut", or spawning ring (I'll use that phrase from now on) overlaps with another player?

Figuring out whether there is an overlap is simple: just check if the distance between 2 players is less than the inner radius of the spawning ring, in this case, 1800. If it is less, then there's an intersection (i.e. one ring goes inside the other). If it is bigger than 1800, but smaller than 2400 (the outer radius), then that means there's an overlap, but it doesn't intersect.

But, that doesn't really tell us where it overlaps. So:

Problem #2: How to figure out -where- the spawning rings intersect?

Now, this is where it gets a bit complicated. This would require a bit of trigonometry and, to be honest, is probably not really that convenient to implement in GUI. It would require keeping track of multiple angles, intersecting arcs, and so on.

I'm also very rusty with trig right now, so let's try working around that problem by changing the approach.

Suppose this is the routine for spawning a mob:
1. Pick a random angle on the ring around the player. It basically works out to Point = (Cos(angle) * Random(dist), Sin(angle) * Random(dist))
2. Spawn a unit there

What we can do is add a check to see if the point we've picked is in another player's circle. So let's add that.
1. Pick a random point around the player.
2. Loop through all players, check if the distance to the player is less than 1800. If it is, try finding another point. Repeat until we found a suitable point.
3. Spawn a unit there.

There's an obvious problem there - if a player is completely surrounded by other players, we'll never find a suitable point. Instead of choosing a completely random angle, let's pick a random angle from 12 possible directions. That way, our "search" is limited to only 12 steps, and if it fails, we can resort to spawning the unit in another player's circle. Tip: You can choose a random number from 0 to 11 as your starting value, and then loop 12 times incrementing it, until you find a suitable point. E.g.:

// kind of pseudocode
local pointX = 0
local pointY = 0
local foundPoint = false

local start = Random(0, 11)
local i = start
local dist = Random(1800, 2400)
loop
  exitwhen i > start + 12 or foundPoint
  pointX = Cos(360 * i / (i - start)) * dist
  pointY = Sin(360 * i / (i - start)) * dist
  // this should check whether the point is not in another player's inner radius
  if isSuitablePoint(pointX, pointY) then
    foundPoint = true
  endif
endloop

if foundPoint == false then
  // this tries to find a point from another player
  pointX, pointY = findAnotherPlayer(...)
endif

Something like this. Obviously this isn't a working example, it just serves to illustrate the general logic.
Unfortunately, that way you're restricted to only 12 possible directions, but you can randomize it a bit by adding some random skew factor to your point on both axi.
You can also use player/unit groups to keep track of each player "congregation" and spawn a unit not for each player individually, but for every group. The above logic for finding a suitable point would still apply, however. If you're spawning a lot of units, it shouldn't make much of a difference in terms of which player gets most creeps.

Of course, you could try and go full math mode on this, but personally, I don't think it's worth it. The above solution should work just fine, IMO.

 

[Damage]

Yeah I was thinking along your lines, but the unfortunate side effect of spawning in only 12 (or however many) directions is that it makes the spawns sort of cluster in particular locations which I'd like to avoid if possible.

So the way I thought of implementing this is to:

1) Pick a random point between 1800 and 2400 of the player.
2) Check if it's pathable. If not, go to step 1.
3) Check all other players. Is the point within 1600 of them? If it is, go back to step 1.
4) How many failures have happened? If it's over 100 or so, it's likely that no locations are valid. Choose the nearest other player, and go back to Step 1 again.
5) If all the above checks are passed, the location is found.

Then this function would pass that location back to the main trigger, which would handle the spawning.

The problem with this is that it involves quite a few nested functions (check if pathable is easy, but check other players, followed by re-running itself on failure etc..), which I don't really think is feasible with GUI. If anyone would adapt this to Jass, that'd be fantastic.

 

[nedio95]

I'd say, just force it...

@Damage just as you have described it, although, do it a bit less random, Pick a random angle at the beginning of the whole process like:

Step 0 Pick random angle
Step 1 Pick a random point between 1800 and 2400 of the player towards Angle.
Step 2 Do checks, Anything goes wrong, increase Angle by 1-5 degree, back to step 1, terminate when a full circle has been done

 

[Nowow]

The second problem is a bit ahead of the way for now, so I'll only addres the first one:

A geometric solution will probably require much less calculation then the idea of choosing random sample points. The idea is based on the fact that two players and their respective"donuts" create a rhombus, whose oppsing vertices have the same degree as the section of the donut where you don't want to spawn things.

We'll break the process to more steps:

1. You have 2 players with overlapping donuts, which create a rhombus. As an interesting aside of that, the rhombus can be split into 4 identical right triangle, each with a hypotenuse of 1800, the radius of the lower bound circle creating your donut.
2. What we want to do is find out what section of your donut's loser bound is inside the other player's lower bound circle.
3. To do that, divide the distance between your player and the other player by two, then divide it again by the radius of the lower bound (which is 1800). Then, use the Acos function on it to find half the angle of the section you want to cut (we'll call that one x).
4. Find out the angle between your player and the other player, we'll call that one z, then you want to be able to spawn in any angle from your player to the other, except anywhere between x + z and x - z.

This should give you the blue sections in your example with relatively few computations to make.

 

[Damage]

@nedio95
Unfortunately, if the player is in the top left corner of the map for example, that means doing a rotational method will cause some unintended behaviour. In the top left corner, angles between 0 and 270 are not allowed, and so 75% of the circle is invalid. This means that when it picks a random angle, 75% of the time it will pick these disallowed regions, and recursively track to the edges of the disallowed region, causing the spawns to get clustered in those locations instead of spreading evenly.

@Nowow
This sounds great, but I'm not sure how it would be scalable to more than 2 players. Mathematically it checks out to discover the range of disallowed angles in a 2 person scenario, but unfortunately it would need to be more modular to work with an undetermined number of players.

For both of the above reasons, this is why I decided to go with random points and assess and retry. Rotating causes unintended behaviours (like clustering when near corners or unwalkable terrain) and an angular approach becomes almost impossible to resolve when multiple players come into place.

 

[pick-a-chew]

The problem with this is that it involves quite a few nested functions (check if pathable is easy, but check other players, followed by re-running itself on failure etc..), which I don't really think is feasible with GUI. If anyone would adapt this to Jass, that'd be fantastic.

I don't see why this wouldn't be feasible on GUI, GUI is more robust than people think it is. The only inefficiency i can foresee is if upon failing to find a suitable point, and the trigger fires 100+ times again without actually finding a point (e.g. a player's donut completely surrounded by other donuts), you could run into performance problems, especially if multiple incidences of this happen at once. The key word is could, you'd have to try it and find out.

Games that use similar systems will teleport enemies right on top of you if they were to be spawned in a bugged place, or if their spawn locations are invalid they spawn at random points in an area that are not within range of players. Team-based maps that use a similar system seem (i am just guessing now) to just reallocate a player's spawn to another player's ring if it fails. Another one that comes to mind lets things spawn "outside" of the playable area (where the outside is inaccessible to players but accessible for NPCs) to stop corner camping from being a thing.

 

[Nowow]

This sounds great, but I'm not sure how it would be scalable to more than 2 players.

Why would it not be scalable? You can find all player units distance of 1800 from your target, then get a range of invalid angles for each one. This is far better than the idea of random sampling. Imagine your target is very close to another unit, it can make nearly half of the donut an invalid spawn point. Instead of going over invalid sample points 30-36 times, you get the whole range of invalid points immediately.

 

[Damage]

Hmm, sounds feasible then.

I think with some kind of map of the nested functions and "go to" steps, I could work my way through this. Could you throw some mock / pseudo-code for a general layout for that solution?

Also, it's been a while since I did mathematics, could you give a rough formula for your angle calculation?

 

[Nowow]

Sure thing. I added a "visual aid", it's only partial because apache open office sucks and I can't use it for more than 5 minutes straight.

Anyways, the basic idea when calculating the angle is that diagonals in a rhombus cut it into 4 indentical right triangles (see aid). So, in order to calculate the sector (i.e. the part of the circle that is invalid) we need to know angle indicated in the visual aid. We can achieve that using the arccosine function (Acos in JASS, dunno if it has a GUI counterpart), which needs the ratio between the hypotenuse and the edge close to said angle. We already have the hypotenuse - it's the radius of the lower bound circle (in red), and we can find the length of the close edge by getting the distance between the target unit and it's surrounding unit. This gives us the angle (we'll call that deviation_angle).
Now, notice this is not enough, because we are in a certain coordinate system - the one of the game engine, so we will get the angle between the distance of the two units and the game's X-axis, also with the Acos function (we'll call that start_angle), then our invalid sector starts and (start_angle - deviation_angle) and ends at (start_angle + deviation_angle).

There is a problem with the world editor as it does't really allow number ranges, so as a suggested workaround, I created a boolean array size 360, and for every such range we find, we will "cross off" a certain sector of integers between 1 and 360.

TL;DR here's the pseudo-code

// This code emulates spawning around a single "target"
global RADIUS = 1800
local target_unit
local array valid_array

for index in range(0,359):
    if PointWithOffset(target_unit, RADIUS, index) is pathable:
        valid_array[index] = true
    else:
        valid_array[index] = false

for surrounding_unit in GetUnitsInRange(player_units, range=RADIUS):
    distance = GetDistance(target_unit, surrounding_unit)
    deviation_angle = Acos( (distance / 2) / RADIUS )
    start_angle = Acos( GetDistanceX(target_unit, surrounding_unit) / distance)

    if deviation_angle < 0:
        deviation_angle = deviation_angle + 360
    if start_angle < 0:
        start_angle = start_angle + 360

    for index in range( RoundDown(start_angle - deviation_angle), RoundUp(start_angle + deviation_angle) ):
        valid_array[index] = false

Now you can iterate over valid_array and spawn a unit whenever the angle is "valid".

There is one small caveat with this method: If you look at the intersection between the donuts, you'll find that there is a small area which technically has a valid angle, but is too close to the surrounding unit. But this should be insignificant and shouldn't cause any problem.

This was actually very interesting. I might try to do it in JASS (no promises).

EDIT:
Added a line to filter out unpathable terrain.

 

[~El]

4) How many failures have happened? If it's over 100 or so, it's likely that no locations are valid. Choose the nearest other player, and go back to Step 1 again.

TBH, this isn't much different from using fixed angles. If you're going to limit it to a 100 checks, might as well make it 100 directions instead of 12, or some other number.

For example, if you choose 64 directions, then the arc length between each checked spawn position is 235 units, which is actually not that much, and shouldn't cause units to cluster.

Either way, interesting problem. Let us know which solution you settle with at the end of the day!

 

[~El]

Another solution just popped into my mind as well.

Instead of trying to find which positions are suitable or not, let's instead:

1) Track all player "groups". So if 2 players are close enough, count them as one group.
2) Pick a random point around the player group (using a circle that surrounds both their inner circles).
3) Trace a ray from that outer point to one of the player's circles.
4) The intersection point will be our spawning position for that player "group".

Here's a visual aid:

The black circles are the circles of each individual player.
The yellow circle is the circle that encompasses all of the players.
The green dots are the random points on that circles.
The green lines are ray-traces from that point to one of the players.
The brown dots are the points of intersection of those rays with one of the inner circles, and, the spawn position.

You can pretty easily google how to find an intersection of a ray and a circle. It should be a fairly cheap and easy operation.
If you want to add a random factor to where the unit spawns, you can pick a random number and "extend" the ray by that amount after an intersection happened.

 

[Damage]

Hey all.

So after discussing this with my computer-science friend, he was pretty amused by various things here.

Firstly, the method described by @Nowow actually greatly (as in, incredibly) increases the amount of computational power required. The method of checking off 360 different numbered angles, for each player, and calculating the zone (which you then STILL need to pick a random location in) for up to 22 players, actually takes more computing power than a randomised algorithm. He said this is a classic case where a deterministic algorithm actually underperforms against a trial-and-error method.

@Sir Moriarty
This is similar too - actually ray-tracing like that, while elegant and correct, will actually increase the computational power required.

So basically, it seems that these deterministic approaches will produce perfect results, but will actually not benefit the game engine whatsoever.


I think in the end, I'll go with a more simplified "trial and error" method. Doing some preliminary tests of placing terrain around a player and standing near corners, it's pretty likely to find a valid location in only 15 - 20 steps in the worst, realistic (in terms of the game play) cases.

So what I'll likely do is make the system check for a valid location at random in the donut, checking for nearby players. If it's too close to someone, check another random point. Repeat this process until either a good point is found or 25 attempts have been made. If after 25 attempts, no point is found - just don't spawn it.

Now I know this doesn't solve the true final problem, but given the way this map will play, I highly doubt it that the players will cluster in such a way that they can prevent all the spawns of one of the players - particularly seeing as this will not be a co-op survival.

Thanks all for your contributions though, so I've given rep out to those attempts.
Cheers.

 

[~El]

Hey all.

So after discussing this with my computer-science friend, he was pretty amused by various things here.

Firstly, the method described by @Nowow actually greatly (as in, incredibly) increases the amount of computational power required. The method of checking off 360 different numbered angles, for each player, and calculating the zone (which you then STILL need to pick a random location in) for up to 22 players, actually takes more computing power than a randomised algorithm. He said this is a classic case where a deterministic algorithm actually underperforms against a trial-and-error method.

@Sir Moriarty
This is similar too - actually ray-tracing like that, while elegant and correct, will actually increase the computational power required.

So basically, it seems that these deterministic approaches will produce perfect results, but will actually not benefit the game engine whatsoever.


I think in the end, I'll go with a more simplified "trial and error" method. Doing some preliminary tests of placing terrain around a player and standing near corners, it's pretty likely to find a valid location in only 15 - 20 steps in the worst, realistic (in terms of the game play) cases.

So what I'll likely do is make the system check for a valid location at random in the donut, checking for nearby players. If it's too close to someone, check another random point. Repeat this process until either a good point is found or 25 attempts have been made. If after 25 attempts, no point is found - just don't spawn it.

Now I know this doesn't solve the true final problem, but given the way this map will play, I highly doubt it that the players will cluster in such a way that they can prevent all the spawns of one of the players - particularly seeing as this will not be a co-op survival.

Thanks all for your contributions though, so I've given rep out to those attempts.
Cheers.

This is fair. However, it's also falling into a rather common trap in programming overall - premature optimization.

In truth, while some of these methods are definitely more computationally expensive than others, in practice, it is unlikely to matter. While JASS (and by extension, GUI) is a very slow language (by most modern standards), it actually is still faster than most people tend to realize.

I've written quite a handful of rather resource-intensive systems for WC3 in the past, and it actually takes quite a lot of effort to force WC3 to start lagging with just triggers, and doubly so with just math.

I guess the point I'm trying to make is with a periodic event like that (even if it runs a few times per second, though likely, far less frequently), you won't feel the impact of doing a few hundred calculations, like, at all. In fact, spawning a unit is probably slower than finding a location to spawn it in, using most of these methods.

So, unless you're literally spawning dozens of units every second, it won't make a difference. And even then, it's probably going to start lagging anyway just because of the sheer volume of units.

I'm not trying to sway you one way or another, it's just that a lot of people try to optimize prematurely, often to their own detriment. Profile first, optimize second!

Either way, happy triggering!

 

[Nowow]

Firstly, the method described by @Nowow actually greatly (as in, incredibly) increases the amount of computational power required. The method of checking off 360 different numbered angles, for each player, and calculating the zone (which you then STILL need to pick a random location in) for up to 22 players, actually takes more computing power than a randomised algorithm. He said this is a classic case where a deterministic algorithm actually underperforms against a trial-and-error method.

This is not entirely correct. My method performs the check on any player, rather than 360 numbered angles, meaning it will iterate only 22 in the worst case, in comparison to 100 or whatever chosen limit of times for a trial and error method. Iterating on all numbers between 1 and 360 is done only to assign a boolean variable, which is a very light process for the CPU, especially next to distance calculations.

But I digress, if you want to use a trial and error method just to avoid the workarounds required to use number ranges in JASS\GUI (which can actually be a smart choice), I suggest checking points in the middle of the spawn donut (distance 2000-2200 from target for example), just so you don't fall on a marginal case of unpathable terrain, or accidentally calculating another player as closer to you than he actually is.

I'd really like to see how this trigger looks at the end, this is an interesting problem. Good luck!

 

[Dr Super Good]

The solution...

Each player/unit has a spawn queue. This queue is the number of monsters that need to be spawned for that player/unit. It persists with respect to time, incrementing when new monsters are to be spawned and decrementing when monsters are spawned. This is needed to achieve the desired behaviour of spawn sharing.

For each player/unit you then pick a random location in their spawn field. You then check if that random location is in the safe zone of any other player/unit, a simple O(n) style distance test. If there are a lot of player/unit then one could use an area unit search (units in range) to reduce the size of n to be more reasonable, but this would only be needed if n is a large number like 30 or 50 I would imagine.

If this point passed all the safety checks, then you spawn a unit at that location, order it towards the player/unit and decrement the spawn counter for that player/unit. If it failed you do nothing, it will be spawned later.

These checks are repeated every 0.1 or so seconds for every player/unit that has monsters in its spawn queue. If there are few players/units to check one can perform multiple such checks per tick. If there are a lot of players/units to check one can perform the checks on a subset of the players/units, staging the full set them over several ticks. This gives this approach huge scalability without impacting performance.

When issuing monsters to spawn to a player/unit you increment their spawn queue count. However once the spawn queue count exceeds some maximum, say 3 monsters, then instead of incrementing the spawn queue count of that player/unit, it increments it for another player/unit that has a queue less than the maximum. This covers the spawn roll over in the case of player 1 in your second example. Up to maximum queue length monsters will remain unspawned for a player but these will eventually spawn if the player moves to an area where they statistically can. If all players/unit have maximum sized queues then you increment a dedicated counter which can be used to place extra spawns on players/units in the future when they have queue space, this covers the case of excessive bad luck finding a spawn location.

If you are worried about the queued monsters not spawning then another approach would be to scrap the queue maximum and that that after too many failed spawn attempts, eg 10, a spawn count is transferred to a random player/unit. Eventually this spawn count will make it onto someone which has a high statistical chance of getting a valid spawn location and hence will eventually spawn. It also keeps the number of monsters exact without potentially permanently locking down some on players they cannot spawn. It also removes the need for an overflow counter.

This works on statistical chance. In theory it is possible for no monsters to ever spawn if every player has at least part of their spawn point overlapping a safe zone. In reality this will never happen as the chance of it occurring for extended periods quickly starts to boarder the impossible and it may even be technically impossible due to how pseudo RNGs work. Assuming your second example becomes a reality, one would see approximately equal monster spawns for Players 2, 3, 4 and 5 distributed across the appropriate areas with none spawning for Player 1.

 

[Arxos]

This is not entirely correct. My method performs the check on any player, rather than 360 numbered angles, meaning it will iterate only 22 in the worst case, in comparison to 100 or whatever chosen limit of times for a trial and error method. Iterating on all numbers between 1 and 360 is done only to assign a boolean variable, which is a very light process for the CPU, especially next to distance calculations.

(Friend here) Yeah I actually misunderstood the method at first, it's more elegant than I thought at a glance. The biggest problem I have with it right now is that it doesn't cleanly solve the problem of finding a random point, as you're still stuck getting random numbers between 0 and 359 until you find a true. Finding a valid point in that array is still a lot faster than getting the distance between up to 23 other players, but I doubt a trial-and-error approach will fail that often on average anyway. If you assume it needs to try 2-3 times on average, then that's only ~50 distance checks, where as this code has at least 22 distance checks, twice as many acos and a lot of boolean writes. I'm guessing your approach is probably better if on average it fails something like 5+ times. I'll definitely keep the option in mind, perhaps even if a randomized approach is more efficient on average, it may turn out that your deterministic approach is better because the worst-case scenario isn't as bad.

In regards to the ray trace approach, I see primarily two problems with that approach. First, you'd have to find the intersection point of the line and all players in that group, and then figure out which is one is 'earliest'.
Secondly, I fear it may result in all players being considered as a single group. If two players are close to each other, their bubble expands, and then someone else is close too... so the bubble expands again.

The solution...

Each player/unit has a spawn queue...

This is quite the elegant approach actually, as it spreads the failures out over time. It's definitely a good improvement over the basic trial-and-error approach. I'll need to discuss some details with Damage but this one is definitely my favourite so far.

 

[~El]

In regards to the ray trace approach, I see primarily two problems with that approach. First, you'd have to find the intersection point of the line and all players in that group, and then figure out which is one is 'earliest'.
Secondly, I fear it may result in all players being considered as a single group. If two players are close to each other, their bubble expands, and then someone else is close too... so the bubble expands again.

You can find the earliest intersection point by comparing their distances to the original point. Whichever is closest to the edge is pretty much guaranteed to be the real intersection.
For figuring out player groups, I'd personally just use their inner radii instead of the outer "total" radius to test whether or not a player is in a group. Basically, a player "joins" a player group only if his 'bubble' intersects with another player's bubble in that group.

 

[Dr Super Good]

Oh just to warn people, the following does not result in uniformly distributed random locations in a donut shape.

Set temp_point = (SpawnOrigin offset by (Random real number between 1800.00 and 2400.00) towards (Random angle) degrees)

Points will be more likely to spawn per unit area at the inner circle of the donut than at the outer circle of the donut.

To generate points uniformly in a circle you need to use the following polar radius...
radius * random(0.0, 1.0)^0.5
This will result in even area distribution. Obviously the low bound of the random could be adjusted as appropriate to generate uniformly in a donut shape. So for the quoted example it would be...
2400.00 * SquareRoot(random(0.5625, 1.0))
Where 0.5625 = (1800.00 / 2400.0)^2

 

[Damage]

Huh, I never even considered that that function wouldn't create an evenly distributed donut. I suppose with infinitely many decimals for the random angle, it would, but we know that's not the case.

Once we've got a working trigger of this, I'll be sure to post it here. Arxos is going to be doing the leg work on this one though I'm afraid, as Dr Super Good's method is a little beyond my abilities I think.

 

[Dr Super Good]

Huh, I never even considered that that function wouldn't create an evenly distributed donut. I suppose with infinitely many decimals for the random angle, it would, but we know that's not the case.

No it is because area is radius squared and not radius. Hence if you use just a random radius it is less dense towards the edges than the middle. This is why one googles this sort of problem instead of trying to solve it yourself because chances are you will get it wrong unless you are an expert in the field.

 

[Damage]

Circumference is radius squared? Not sure I follow.

I kind of visualised it in my head though as being a random angle chosen first, then the distance from the center in that direction chosen next. There's more ways to get close to the center than to get close to an edge due to how 2 angles chosen facing away from each other could still result in 2 points very close to one another if the chosen distance is small. But if the chosen distance is large, they get much further apart. ergo, there's more ways to get close points in the center than further out, creating that gradient of density as you move out.

So yeah, makes sense.

Also, I'm pretty sure nobody googles every step of a mathematical procedure before at least attempting to solve it. I used to be a science teacher, so I kind of assumed I was pretty solid on the basics here. I wasn't, as it turned out.

Anyway, in this example it's unlikely to even matter. The difference between the inner limit (1800) and the outer limit (2400) in terms of the game will hardly be noticeable anyway.

 

[Dr Super Good]

Circumference is radius squared? Not sure I follow.

Meant area, sorry.

Basically because circumference is linear with radius, the larger the radius the larger the circumference. This means the random distribution is stretched out with the circumference the further away from the centre.

To compensate one has to squash the random radius distribution so it is more likely to be towards the edge of the circle than the middle. This is done by taking the square root of normalised random radius, as that is more likely to be towards 1.0 than 0.0. I am sure one can derive this correction mathematically.