finding a random spot in circle

[evildaddy911]

What is it you are trying to achieve?
first-person shooter rpg (using a bow)


What is the problem you are having?
I am trying to determine a random spot in a circle for the arrow to hit, but it keeps putting a negative value through the square root function


Describe what you have tried to solve this problem
I have no idea why it keeps happening to fix it, ive rechecked the math at least 10 times...


Post any relevant code (You may choose to attach the file instead of posting the code if it is too long)
the rx and ry variables are where the arrow is hitting, im drawing a small circle there at the moment

Please specify what version of Turing you are using
open turing

[Raknarg]

I recall trying to accomplish a similar task using this method, and it didn't ever work quite the way I would've liked; I would recommend using trigonometry instead. It's much easier to use.

[Dreadnought]

You have the right idea but there's a little something you overlooked.

Turing:

rx := Rand.Int (x - rad, x + rad) ry := Rand.Int (round (y - sqrt (rad ** 2 - (rx) ** 2)), round (y + sqrt (rad ** 2 - (rx) ** 2)))

rx is given a value that can be within the circle (or at its edge). This is fine.
Remember that rx is a coordinate measured from the rightmost side of the Turing window.

Now, lets look at ry. we want it to be within the circle at this particular x coordinate. You have the right idea here, the sum of the squares of the x and y distances must be equal to or smaller than the square of the radius. But should these x and y distances (x in particular) measured from the rightmost side of the Turing window?


As a remark, your method generates points distributed evenly over the x axis but not over the area of the circle since there are more possible points near the center than near the edges. As a consequence, you might find that you more frequently get points near the edge of the circle than you might expect for a random generation over the area. If this bothers you, consider simply randomly generating x and y values and then checking if they are within the circle. If they are, good, if not, regenerate them and try again. Since you aren't doing this too often it shouldn't impact performance.

Another method could be randomly generating a radius (similar to how you generate rx) then randomly generating a point along a circle of that radius centered where the mouse was clicked.

[RandomLetters]

Equation of a circle is

x2 + y2 = r2

thus, generate random r value from 0 to max, and then x from -r to r, for the point on the new (smaller) circle, and calculate y using y = root(r2 - x2)

since x <= r and both are squared, there will not be negatives.

then randomly choose the sign for y.

r = rand(0, maxr)
x = rand(-r, r)
y = root(r^2 - x^2)

if(rand(0, 1) >= 0.5) then
y = -y

[evildaddy911]

Raknarg @ Fri Dec 30, 2011 9:08 pm wrote:

I recall trying to accomplish a similar task using this method, and it didn't ever work quite the way I would've liked; I would recommend using trigonometry instead. It's much easier to use.

the trig way would be choosing a distance from the middle, then choosing the degree from the center right?

Turing:

dist:=Rand.Iny(0,rad) angle:=Rand.Int(0,359) tand(angle)

m lost after this...

dreadnought: so what you are saying is to use the equation to determine a spot as if the circle was on (0,0), then shifting it up to (x,y)

Turing:

rx:=Rand.Int(-rad,rad) ry:=Rand.Int( -round( sqrt( rad**2-rx**2 ) ), round( sqrt( rad**2-rx**2 ) ) ) if whatdotcolor(rx+x,ry+y)=black then     % checking if the arrow hit the target - - - end if

and i was considering using the generate, check, regenerate method if i couldnt figure it out soon

[RandomLetters]

Quote:

and i was considering using the generate, check, regenerate method if i couldnt figure it out soon

This works fine and is actually faster than using trig.

[Raknarg]

@evildaddy thats fairly close. However, there's a couple more steps with trig:

Turing:

var angle : int := Rand.Int (0, 359) var rad : int := 10 var dis : int := Rand.Int (0, rad) var x, y : real := 100 var newX : real := (cosd (angle) * dis) + x var newY : real := (sind (angle) * dis) + y

The newX and newY will give you the position of the point in the target you're aiming at, relative to the origin (100, 100 in this case), the distance from the origin, and the angle from the origin. Notice the simplicity.

@randomletters it is faster. I just prefer trig, its another alternative

[evildaddy911]

The problem with the trig is if you use int values for angle, then it can only have 360 points around the circumference, if the circles circumference is more than 360 ( ~115 radius) then it cant get all the possible points... Youd have to

Angle:=Rand.Int(0,35999)/100

[Dreadnought]

evildaddy911 wrote:

dreadnought: so what you are saying is to use the equation to determine a spot as if the circle was on (0,0), then shifting it up to (x,y)

Yes, that's the idea.

But now we have this question of "Which method is best?" floating around.

We have discussed 3 main methods of generating points within a circle.
1 - Choosing an x at random then choosing an appropriate y at random. (What you are using)
2 - Choosing both x and y randomly and checking them to ensure they are legal. (generate, check, regenerate method)
3 - Choosing a radius and an angle at random. (the "trig method")

We could attempt to examine run times but as my professor says "a common mistake we make early on is to worry too much about efficiency". Here's an article talking about this. Basically, it says that compilers are made to optimize your code in ways you wouldn't think of.

So let's not talk about about speed yet (I will in a bit), and to be fair, speed will not be an issue for what you're trying to do.

Instead let's examine the distribution of the points over the circle. One might be tempted to say they are all identical but this is not so (I mentioned this earlier).
I wrote some simple code that draws points inside a circle of radius 100 pixels. I chose to draw ~1 points per pixels in the circle (pi * 100^2 = ~31415 points).

1 -

Turing:

var x, y : int Draw.Oval (200, 200, 100, 100, 7) for i : 1 .. 31415     x := Rand.Int (100, 300)     y := Rand.Int (round (200 - sqrt (100 ** 2 - (x - 200) ** 2)), round (200 + sqrt (100 ** 2 - (x - 200) ** 2)))     Draw.Dot (x, y, 7) end for

We see that points are evenly distributed horizontally, since there are fewer possibilities for y coordinates near the left and right edges we have higher concentrations of points there.

2 -

Turing:

var x, y : int Draw.Oval (200, 200, 100, 100, 7) for i : 1 .. 31415     loop         x := Rand.Int (100, 300)         y := Rand.Int (100, 300)         exit when Math.Distance (x, y, 200, 200) < 100     end loop     Draw.Dot (x, y, 7) end for

We see that points are evenly distributed over the area of the circle.

3 -

Turing:

var x, y, rad : int var angle : real % I'm using radians, but degrees are basically equivalent Draw.Oval (200, 200, 100, 100, 7) for i : 1 .. 31415     rad := Rand.Int (0, 100)     angle := Rand.Int (0, round (2000000 * Math.PI)) / 1000000 % 0 - 2pi with a bunch of decimal places     x := 200 + round (cos (angle) * rad)     y := 200 + round (sin (angle) * rad)     Draw.Dot (x, y, 7) end for

We see that points are more concentrated near the center, that is they are distributed radially. This makes sense if you think about it since we pick a radius at random but there are more points on circles of larger radius. You more or less pointed this out in your last post.


If you are debating which method to choose this might help. Perhaps you want more chances of hitting near the center (method 3), maybe not (method 2). Personally, I don't like the method 1's distribution since it doesn't fit with a circle (but it's your choice).



Just for fun, let's look at run times. I added "put Time.Elapsed" at the end of each code and ran each a few times. So how much worst is trig? Sorry RandomLetters, its not actually slower. (this actually surprised me, that's why I'm talking about this)

Here are my average run times for 5 runs of each code (using turing 4.1.1, probably wouldn't be very different in open turing).
1 - 1144.8 ms
2 - 1196.2 ms
3 - 1119.6 ms

These run times are relatively close, but do seems to indicate that trig is in fact faster (remember this is for over 30,000 points). Our generate, check, regenerate (if needed) method placed last, but it should be noted that although we need to regenerate a little over 20% of points, we don't have 20% longer run time (maybe drawing points is longer than generating coordinates). Overall, this shows that efficiency in computing is not as easy to determine as we may think it to be.

EDIT: Just a fun thing to note. I removed the "Draw.Dot (x, y, 7)" line, the run times were about 10-15% the length they were originally (we're talking ~150 ms) so it would seem that drawing all the points is many times slower than generating coordinates. Also the generate, check, regenerate (if needed) method runs in ~200 ms which is approximately what we would expect.

Good luck with your program.

[Raknarg]

@evildaddy yeah, thats the general idea if you really want to get smaller values. However, there isn't really any point in having values inbetween degrees, because the difference is too small to matter. For instance, compare 1 degree and 1.5 degrees. On a small scale like this, you can even tell the difference.