Random Loc in Circular Range?

[AceHart]

> the distribution of points would not be uniform or even rotationally symmetrical.

If random fails to meet your expectations, it is random indeed.

It's not supposed to find every possible point exactly once if you run it often enough.
It's supposed to be random.
That's what it is.

The code is solid. So is the math used.

 

[TheDamien]

> the distribution of points would not be uniform or even rotationally symmetrical.

If random fails to meet your expectations, it is random indeed.

It's not supposed to find every possible point exactly once if you run it often enough.
It's supposed to be random.
That's what it is.

The code is solid. So is the math used.

I don't question that it will find a random point within a circle, but it seemed to me that Vex was implying that the distribution of random points would be uniform, which did not seem to be the case. Just thought I might be missing something.

 

[Vexorian]

I don't question that it will find a random point within a circle, but it seemed to me that Vex was implying that the distribution of random points would be uniform, which did not seem to be the case. Just thought I might be missing something.

I am not sure, what I know is that polar projection is really not uniform, mine probably isn't either, a way to test would be to run the function for a long period of time and see if there is a bigger density of points in a side, I think my function could have a bias on the external sides of the circle.


For a lot of time I thought my Pythagoras was a good alternative to polar projection but I wasn't sure after I made my first post in this thread, I went to http://mathworld.wolfram.com/DiskPointPicking.html and it certainly does not use pythagoras, I will get myself into SDL and a C++ and test my function, comeback later.

Edit: Just tested and it looks like there is an small bias towards the x axis extremes of the circle, it is smaller than the polar projection bias towards the center though.

Edit: It looks like the formula in that page is the only way to do it uniformly, the problem is that you would now require SquareRoot AND Cos AND Sin

function RandomPointCircle takes real x, real y, real d returns location
    local real a=GetRandomReal(0,2)*bj_PI
    set d=d*SquareRoot(GetRandomReal(0,1))
    return Location(x+d*Cos(a), y+d*Sin(a))
endfunction

If speed is more important than an uniform distribution then my pythagoras based one is not that bad, the bias is also not as terrible as with the polar projection-without-squareroot one.

I said 'arguably faster' because I don't really know, SquareRoot, sin and cos are all "slow", in theory a single SquareRoot should be better than sin + cos, but I have no benchmarks.

 

[AceHart]

For those interested, I made a couple quick screenies:
- rpd_polar, biased towards the center
- rpd_pythagoras, biased towards the x-extremes
- rpd_sqrt, the uniform method

Actually, the "error" in "pythagoras" is just as bad as for the polar projection method.
Only, it's less obvious, as the error isn't clumped together in the center.

Regardless though, for a random point used in some spell trigger... does it really matter?
Go with whatever works or is fastest to use...

 

[TheDamien]

Vexorian's still seems to be the best where speed is concerned. Though, if the map isn't too CPU intensive, it might be worth going for the uniform method.

 

[N-a-z-g-u-l]

seems to me like vexorians solution is the best just because it is made by vexorian imho the polar projection one is even better, because its consistent irregular... the chance for a point in the middle is higher, which does not have to be that bad for an aoe spell... nontheless the 3rd way is in every case the best... cos() is not slower than GetTriggerUnit(), you dont have to bother about it, at least you dont have if you use the spell less than about 200 times per second... but i'd still use the 3rd solution...

and heres another alternative, one SquareRoot()-call instead of Sin()

function RandomPointCircle takes real x, real y, real d returns location
    local real xadd
    set d=d*SquareRoot(GetRandomReal(0,1))
    set xadd=d*Cos(GetRandomReal(0,2)*bj_PI)
    return Location(x+xadd, y+SquareRoot(d*d-xadd*xadd))
endfunction

but i believe the other function is faster

if you need performance, the first step wouldnt be to remove one Sin()-call, it would be to inline that function and remove the location

 

[emjlr3]

im with ace

local real x = x + GetRandomReal(0,dist) * Cos(GetRandomReal(0,360) * bj_DEGTORAD)
local real y = y + GetRandomReal(0,dist) * Sin(GetRandomReal(0,360) * bj_DEGTORAD)
return Location(x, y)

is what I would use

easy and fast and simple

 

[N-a-z-g-u-l]

GetRandomReal is not faster than Sin()... and your coordinate could also be outside the circle oO

assuming dist = 100

local real x = x + GetRandomReal(0,dist) * Cos(GetRandomReal(0,360) * bj_DEGTORAD)
local real y = y + GetRandomReal(0,dist) * Sin(GetRandomReal(0,360) * bj_DEGTORAD)
return Location(x, y)

lets try it with that random values:

local real x = x + 100 * Cos(0 * bj_DEGTORAD)
local real y = y + 100 * Sin(90 * bj_DEGTORAD)
return Location(x, y)
// x = x + 100
// y = y + 100
// and thats definetely outside the circle...

 

[AceHart]

> is what I would use

Obviously, you need the same angle for both sin and cos and the same random distance too.

 

[emjlr3]

meh

who cares?

 

[SerraAvenger]

seems to me like vexorians solution is the best just because it is made by vexorian imho the polar projection one is even better, because its consistent irregular... the chance for a point in the middle is higher, which does not have to be that bad for an aoe spell... nontheless the 3rd way is in every case the best... cos() is not slower than GetTriggerUnit(), you dont have to bother about it, at least you dont have if you use the spell less than about 200 times per second... but i'd still use the 3rd solution...

and heres another alternative, one SquareRoot()-call instead of Sin()

function RandomPointCircle takes real x, real y, real d returns location
    local real xadd
    set d=d*SquareRoot(GetRandomReal(0,1))
    set xadd=d*Cos(GetRandomReal(0,2)*bj_PI)
    return Location(x+xadd, y+SquareRoot(d*d-xadd*xadd))
endfunction

but i believe the other function is faster

if you need performance, the first step wouldnt be to remove one Sin()-call, it would be to inline that function and remove the location

If they are halfway good implemented, sin() and cos() will only return constants read from an array (y big array =S ), which won't be that slow. Sqrt, however, should be an iterative approximation to the root, and thus might ( or will ) be slower. Idk the exact implementations, but If I'ld created JASS my sqrt would be slower then cos or sin ; )
Greetings, Serra

 

[Vexorian]

im with ace

local real x = x + GetRandomReal(0,dist) * Cos(GetRandomReal(0,360) * bj_DEGTORAD)
local real y = y + GetRandomReal(0,dist) * Sin(GetRandomReal(0,360) * bj_DEGTORAD)
return Location(x, y)

is what I would use

easy and fast and simple

That one is neither easy, simple, fast nor correct.

Just use the uniform method unless you intend for bias on the center . If it looks complicated, just use it as the function it is, this is the reason people use functions.

In Jass number of native call is possibly slower than the C++ implementation of SquareRoot, sin or cos. So, the number of native calls counts more, but I hope someone actually does some benchmarks here.

--
If you ask me, the fact people are still making functions that return locations is reason of concern.

 

[Magentix]

function GetRandomLocInCircle takes real centerX, real centerY, real radius returns location
    local real angle = GetRandomReal(0,360)
    local real distance = GetRandomReal(0,radius)

    set centerX = centerX + distance * Cos(angle * bj_DEGTORAD)
    set centerY = centerY + distance * Sin(angle * bj_DEGTORAD)

    return Location(centerX,centerY)
endfunction

Would this do?

Edit: I get that using a sqrt will get the same result,
but I find it odd to believe that sqrt would get a more "spread out" result than this function

 

[N-a-z-g-u-l]

it would result in a focus of results in the center...

assuming your circle has a radius of 100, then, if you just use a random distance, the chance for your random distance to be higher than 50 is 50%, same for lower than 50...
but now, the area in that circle with a radius of 50 is much smaller than the outer part.

If you had divided your circle in 100 parts, the first ring would be 1 thick around the center point... now imagine the very outer ring, also 1 thick, but much longer, but both have the same probability to contain the random point

if you use squareroot, the probability for all points inside that circle will be the same

i personally leave out the squareroot often to focus the points in the center, but only because it fits to the ability...

 

[Searingdeath]

If you ask me, the fact people are still making functions that return locations is reason of concern.

Not really. The SquareRoot implementation works better if both values are calculated within the same function, and given that functions cannot return arrays in JASS, a Location is well suited.

Otherwise, you'd basically be calling the function twice - once for X and once for Y - except a small portion of the code would be omitted.

Also, when it comes to circles, you can't pick a random point x and a random point y separately and get a correct answer! One depends on the other. Otherwise, although the X value you get may have Y values that will place it in the circle, the Y value you get from a totally separate function call might not work.

This is exactly where Locations are supposed to be used . Either that or embed the function, but that's bad programming practice for complex functions like this.

One more thing - are you sure that trig functions take longer than square root? Unless I'm mistaken, they're all implemented as power series, so the only benefit would be that the square root only requires one call (in addition to the uniformity of the result).

 

[SerraAvenger]

Not really. The SquareRoot implementation works better if both values are calculated within the same function, and given that functions cannot return arrays in JASS, a Location is well suited.

Otherwise, you'd basically be calling the function twice - once for X and once for Y - except a small portion of the code would be omitted.

Also, when it comes to circles, you can't pick a random point x and a random point y separately and get a correct answer! One depends on the other. Otherwise, although the X value you get may have Y values that will place it in the circle, the Y value you get from a totally separate function call might not work.

This is exactly where Locations are supposed to be used . Either that or embed the function, but that's bad programming practice for complex functions like this.

One more thing - are you sure that trig functions take longer than square root? Unless I'm mistaken, they're all implemented as power series, so the only benefit would be that the square root only requires one call (in addition to the uniformity of the result).

Why not just use more interesting location implementations like this one:

struct point
    real x
    real y
    real z
    static method create takes real x, real y, real z returns point
        local point new = point.allocate()
        
            set new.x = x
            set new.y = y
            set new.z = z 
 
        return new
    endmethod
            
    method rotate takes point fixpoint, real zenith, real azimuth returns real
        local real deltaX = .x - fixpoint.x
        local real deltaY = .y - fixpoint.y
        local real deltaZ = .z - fixpoint.z
        local real euclideanDist = SquareRoot( deltaX * deltaX + deltaY * deltaY + deltaZ * deltaZ )
        local real d2Distance    = SquareRoot( deltaX * deltaX + deltaY * deltaY )
        local real newZenith
        local real newAzimuth
       
        // new Zenith    
        set newZenith = Atan2( d2Distance, deltaZ ) + zenith * bj_DEGTORAD

        // new Azimuth
        if deltaX == 0 and deltaY == 0 then        
            set newAzimuth = 0             
        else
            set newAzimuth = Atan2( deltaY , deltaX ) + azimuth * bj_DEGTORAD
        endif
       
        set .x   = euclideanDist * Sin( newZenith ) * Cos( newAzimuth )
        set .y   = euclideanDist * Sin( newZenith ) * Sin( newAzimuth )
        set .z   = euclideanDist * Cos( newZenith )
        
        if newZenith > bj_PI or newZenith < 0 then
            return -zenith
        else
            return zenith
        endif
        
    endmethod

endstruct

 

[Searingdeath]

Why not just use more interesting location implementations like this one:

// struct point {...}

While I admit that vJass is amazing when it comes to speed with structs, it's still better programming practice to keep things simple first and optimize later. If the speed of extracting values from Locations causes serious lag, which is doubtful since this function is likely to be called as an effect of some ability. Either way, you should really only optimize code when it must be done - when it has an impact on performance - which it most likely won't with a function with applications like this one.

 

[TheDamien]

I can't imagine how a point struct could be better than a location.

 

[SerraAvenger]

While I admit that vJass is amazing when it comes to speed with structs, it's still better programming practice to keep things simple first and optimize later. If the speed of extracting values from Locations causes serious lag, which is doubtful since this function is likely to be called as an effect of some ability. Either way, you should really only optimize code when it must be done - when it has an impact on performance - which it most likely won't with a function with applications like this one.

I absolutely agree to that. That is why I use this code. For me it is much clearer to say

SetUnitX( unit, point.x)

than doing
SetUnitX( unit, GetLocationX( point ) )

I allways optimize my code if possible easily, and know what? It starts getting cleaner and more maintainable the more I optimize it. Interesting, right?

Another thing one needs to keep in mind is that these locations need to be optimized in a slide trigger.

Note that ugly programming languages should be absolutely redundant if ones goal would always need to be cleanness. We could all use python or ruby then, and the world was a nicer place.

I can't imagine how a point struct could be better than a location.

As stated above, I think it is easier and more intuitively to use such a point implementation than the prebuilt JASS location. It might be a matter of taste. Also it seems a bit faster when working with high frequency code, just like a slide trigger. Doing

s_point__x[ this ] = s_point__x[ fixpoint ] * Cos( ZAngle )

is a lot faster than

set newLocation = CreateLocation( GetLocationX( fixpoint ) * Cos( ZAngle), GetLocationY( thispoint ) )

And in the standart vJASS view it is shorter than the location stuff, which also makes it more readable. Introducing variables for every of these values doesn't seem the right choice either, it just lengthens the code and builds up a huge stack.
Another point might be that with complex calculations, it might be interesting to have a four dimensional point model, or at least a 3 dimensional one which does not seem to be supported by the traditional location system either. I did not even see any setters for the location's x,y and z values.
Turning point one arround point two would be absolutely impossible withouth creating and destroying at least 1 location. All this can be prevented by just using reals.

greetings, Davey

 

[TheDamien]

MoveLocation enables you to move a location. X and Y are always stored in locals, usually because they are used multiple times; and honestly, the speed difference between locations and structs is going to be completely negligible by comparison to the rest of the function.

In practice, you're usually making something like a projectile system or a physics engine (both of which will need to use locations to make proper height adjustments, anyway) where it is sensible to add the x, y and z values to the struct. Really though, we don't need to reinvent the wheel for a code snippet.

Recently, "good practice" has come to mean excessively verbose code where lots is written, little is done, and something as simple as a message loop needs an accompanying class hierarchy, hash table and 2 pages of comments.