Get every point X units away from another point

[sethmachine]

Hi,

How do I get a (random) point that is X units of distance away from another point.

e.g.

function getRandomPoint takes location origin, real distance returns location
  ...
  return randomLoc
endfunction

This function takes an origin, a distance, and returns a random point which is distance units away from the origin. How would I make it?

 

[Dr Super Good]

Using basic geometry? It is as simple as generating a location which is offset by distance units from origin at a fully random angle (between -pi and pi or 0 and 2pi radians).

In case you were a tad too busy to pay attention to your high school mathematics teacher when you were 13 or are confused about what a radian is I will give a quick explanation here. By defining a right angled triangle such that the right angle forms 2 lines, one parallel to the x axis and the other the y axis you can name each side relative to one of the other corners. This corner is then centred at the origin and usually is the one which shares a side parallel to the x axis. This defines the hypotenuse (the longest side) as the distance to a point from the origin and the angle of chosen side as the angle needed to reach a point. This means that angle of 0 results in a point at x = distance and y = 0 while an angle of 90 degrees (pi/2 radian) results in a point at x = 0 and y = distance. The side that is parallel to the x axis is defined as being adjacent to the angle and the side parallel to the y axis is defined as being opposite to the angle.

There exists a function that takes an angle and returns the length of the adjacent side required to make a unit circle. This function is cos(a) where a is the angle. Since the opposite side behaves identically to the adjacent side offset by 90 degrees, sin(a) is defined such that sin(a) = cos(a - 90degrees). Finally there is the tan(a) which is a ratio between opposite and adjacent but this is not helpful for what you are doing. However sin and cos can also be defined as ratios with respect to the hypotenuse and as such generate sides for non-unit circles.

Cos(a) = adjacent / hypotenuse
Sin(a) = opposite / hypotenuse

Since opposite and adjacent are parallel to axis, you can convert them to coordinates such at adjacent = x and opposite = y. Your distance is the length of the hypotenuse. Arrange to get...

x = Cos(a) * distance
y = Sin(a) * distance

This then is an offset added to origin to produce your final location. For a random point on the circle simply define a as a random angle. When using JASS you will need to define it in radians where pi radians = 180 degrees and in GUI you will need to use degrees (if I recall). Either a random real between 0 and 2pi or -pi and pi will work.

Oh but there are other ways that do not involve sin/cos. As you know a circle around the origin is...
radius^2 = x^2 + y^2
Since radius is distance and you know that the magnitude of either x or y must be less than radius you can define a random point on the circle by choosing a random x or y between 0 and distance and then using the above formula to calculate the magnitude of the missing variable. Since you have 2 magnitudes for x and y you can use a further random process to decide their sign to produce a fully random result. You can then apply this x/y as an offset to the origin location to get your desired result.

So which is better? The first approach is probably faster as it will require less operations. The second approach avoids the use of sin/cos by using power operations so could be faster if sin/cos are more expensive than power.

 

[sethmachine]

I'd rather just avoid as much (mathematical) overhead as possible, and stick with r^2 = x^2 + y^2 (I am assuming I can just use d(iameter) = x^2 + y^2 though, which is the distance...).

When you say magnitude, you mean it does not matter what signs I choose for x, y correct?

So to summarize if I have

d = x^2 + y ^ 2

I will arbitrarily decide to assign the x value and solve for the y.

I choose a value for x that is less than sqrt(d) and then I solve for y. I can then randomize the signs of the final (x,y) pair and that is my location, correct?

 

[Dr Super Good]

I'd rather just avoid as much (mathematical) overhead as possible, and stick with r^2 = x^2 + y^2 (I am assuming I can just use d(iameter) = x^2 + y^2 though, which is the distance...).

Yeh um that technically will be slower due to how slow JASS is. Most people go with the first method due to how much simpler and shorter the code is.

Anyway for such method you do the following (these are not real functions, but just to give you the idea)...
x = randomreal(0, distance) // random within right side of origin
y = (distance^2 - x^2)^0.5 // corresponding point above origin
if randomint(0, 1) == 1 then x = -x // randomly reflect x around origin so left side is covered
if randomint(0, 1) == 1 then y = -y // randomly reflect y around origin so bottom is covered
return offsetpoint(origin, x, y) // offset origin by x and y

As you can see it needs quite of lot of powers and at least 3 random calls.

The usual approach is.
a = randomreal(0, 2pi) // random angle
x = distance * Cos(a) // x offset
y = distance * Sin(a) // y offset
return offsetpoint(origin, x, y) // offset origin by x and y

Which needs no powers, only 1 random call but performs a Cos and Sin call. Since Cos and Sin solve virtually instantly compared with the JASS interpreter it is highly likely to be faster than the first approach. I only mentioned the first approach as an alternative to show that it can be solved without using Cos/Sin.

How do the two relate? It all comes down to how powers work, specifically complex powers. By mapping x as real and y as imaginary you can convert any point in this complex plain to a complex number such that the real part represents magnitude from the origin and the complex part represents angle by using the ln function. In fact this is how all powers work and how one can easily solve problems such as (-3)^1.5.

where j is the imaginary unit.
-3 = e^(ln(3) + jpi)
Substitute back.
e^(ln(3) + jpi)^1.5 = e^(1.5*ln(3) + j1.5*pi)

j1.5*pi means the output is negative imaginary (at 270 degrees in the complex plain)
1.5*ln(3) = ln(3^1.5) through the properties on log natural.
Solve magnitude
e^ln(3^1.5) = 3^1.5

This means (-3)^1.5 = -5.1961524227066318805823390245176j

 

[sethmachine]

How do I get the offset point?

Also what is the name for pi in JASS?

 

[Chaosy]

constant real bj_PI=3.14159

 

[Dr Super Good]

How do I get the offset point?

Using arithmetic? I mean its literally...
output.x = origin.x + x
output.y = origin.y + y

 

[sethmachine]

Using arithmetic? I mean its literally...
output.x = origin.x + x
output.y = origin.y + y

Do they both have to be positive or will the signs matter at all?

 

[Acutesharpness]

Use point with polar offset in the UI editor


X point offset by 300 distance offset by random angle.

 

[sethmachine]

Alright it looks like it works, but a big problem.

How do I filter out "bad" points, i.e. points which are actually in spots that units can't spawn, or possibly outside the bounds of the maps (= crash), but still on the particular circle I decide to make?

What is the diagnostic for taking a given point and deciding if it's "valid?"

And even if I have that, what do I do? Keep generating a new random point until I eventually get a good one? (sounds like a really really bad way to do a search...).

 

[Cokemonkey11]

In your other thread, DSG suggested you do something like this

private function getRandomPoint takes real xC, real yC, real radius returns boolean
    //modifies globals X, Y for output
    local integer count=0
    loop
        exitwhen count>MAX_CHECKS //just do 5 checks per frame, else return false

        //do math logic to get a point (use trigonometry eg sin/cos. If you don't know how, you must learn this - it's extremely important in JASS

        if isPointMatch(X,Y) then // build a new function that check the viability of the point. You must decide for yourself what your conditions are.
            return true
        endif
        set count=count+1
     endloop
     return false
endfunction

 

[Acutesharpness]

If (Check point if flyability is true)

Map is not out of bounce

Else

Fuck this shit I am out

 

[sethmachine]

cokemonkey that is the problem, how do I check arbitrary conditions on a given point?

Here's a high level function

//returns true iff
//1) the point is not out of bounds (prevent crash)
//2) the point is in a spot where a ground unit can spawn
function isPointValid takes location whichLoc returns boolean
  ...
endfunction

I have some idea about checking condition 1) (I have to do some maths with knowing what values of (x,y) are out of bounds and comparing this to the randomly generated point).

But what about 2)? Do I just attempt to make a dummy unit there, and if it gets made, then it's a go ahead?

This is a bottom-up approach--I'm trying to a make a valid string in the language of all points which I define valid and hopefully my derivation doesn't fail (I end up at the start symbol).

But is there no way I can do a top-down approach (I am guaranteed to find such a point in a single pass, even if it's computationally more expensive)?

 

[Cokemonkey11]

I suggest IsTerrainWalkable (library), but you can use IsTerrainPathable() as well (note: the return values for IsTerrainPathable are the opposite of what you'd expect)

Sorry for the short answer but I need to run. Hopefully someone else can offer more guidance.

 

[BPower]

For SetUnitX/Y you can use BoundSentinel by Vexorian. It checks if a unit is leaving the map and puts it back in.
Somehow the game doesn't crash instantly and the trigger solves the problem before the wc3 engine crashes.

You could also use SetUnitPosition. It will check for pathability, mapbounds and also takes collision into account.
It is about ~90% slower than SetUnitX/Y. SetUnitPosition will put the unit to closest possible spot, but as I already mentioned it is a slow operation.

Why are you so eager to use locations? Use coordinates instead.

 

[sethmachine]

Why are locations so much slower? Aren't they just a wrapper around coordinates (x,y), e.g.

struct loc
  real x
  real y
...
endstruct

Where do I create the unit then before setting its position (it sounds like it takes care of most things...)? Some dummy area?

 

[Cokemonkey11]

Why are locations so much slower? Aren't they just a wrapper around coordinates (x,y), e.g.

struct loc
  real x
  real y
...
endstruct

Well locations are handled in machine code, so in theory they should be faster than a struct that emulates a location. The issue is that creating and destroying a location has (at least) twice as much overhead as just using their x,y values. The difference is negligible in practice of course, but really, JASS just supports coordinates better anyway.

Where do I create the unit then before setting its position (it sounds like it takes care of most things...)? Some dummy area?

If you immediately move a unit after creating it, it won't be visible at its initial location. I use 0.,0. usually but there are times when a "safe" location (like in the map boundary) has its uses.