Archived

This topic is now archived and is closed to further replies.

Teric

Need help with a recursive function

Recommended Posts

Ok here''s something to mull over: I''m building a game where a shooter is putting up to 10 shots into a bulls-eye target. I need to be able to figure out if a given number of them are grouped close enough together, to see if the shooter passes. For example--the shooter puts 5 shots into a target, 3 of which will count toward the final grouping. The group is required to be within one inch. If any 3 of the five shots shots are within a one-inch diameter circle, the shooter passes. (The grouping doesn''t necessarily need to be at or near the center of the bulls-eye.) I can track the location of each shot no problem, and I can convert inches to pixels no problem. I know how to check the distance between two different shots. My problem is that when I try to check if multiple shots are all within a given distance, the only algorithm I can think of seems very inefficient and clunky. I''m sure there''s a way to do this using a recursive function, but I can''t figure out how to do it. Can someone give me a push in the right direction? Thanks in advance!

Share this post


Link to post
Share on other sites
Just spoke with a co-worker, and he said that a recursive function probably wouldn''t work. Hm....

I could simply brute-force this check by going to every pixel on the target and checking to see how many shots landed within a given radius of that pixel. But that just seems like a clunky way to do it--anyone else have a better suggestion?

Share this post


Link to post
Share on other sites
I can think of a recursive algorithm that would work, but it would only work if the grouping is 3 bullets big (ie, if you wanted a bigger grouping later, you would have to rewrite the algorithm). So for this reason I would say its a bad idea.

Also, recursive functions are bad in general. Sure they look pretty, but they are memory inefficient (unless your compiler allows tail-recursive functions).

You don't need to check every single pixel. Here's a way you could do it:


For every shot
Create an empty list, we'll call 'nearby'
Loop through every other shot, and add that shot to 'nearby' if its within an inch of the first shot
For every element in 'nearby'
Loop through every other element of 'nearby'
Check if those two elements are within an inch of each other
If they are, then those three shots are a grouping


[edited by - andy_fish on July 3, 2003 1:01:16 PM]

Share this post


Link to post
Share on other sites
I may be wrong, but at base the problem is to find a specific group of K element out of N total element. So in worst case you will always have to check every possible group of K. It makes every solution at least N^K.

To put it simple, I dont think there is an efficient algorithm. But since N is somewhat small, go with the naive solution.

Share this post


Link to post
Share on other sites
I think there are some algorithms that are more efficient than the one I gave. Like, you could create a 2-dim array, where every element in the array represents an inch by inch block of the target. Then sort every shot into the array, and when you look for groupings, you only need to compare the shots that are within a given 2-inch by 2-inch block. I believe this would get you a running time of O(N*K)

But of course all that is completely unnecessary for 10 bullets.

Share this post


Link to post
Share on other sites
Im not sure if I understand what you mean, andy_fish. But even if you reduce the number of bullets compared together, you dont reduce the polynomial time, plus putting the "bullets" in the array takes linear time, thus making the solution worst, at least in theory .

Share this post


Link to post
Share on other sites
Yeah I guess you''re right that it would still take exponential (not poly, my mistake) time. But even though you spend a little extra time setting up the array, I think it would drastically speed up the algorithm for large N. Linear time is OK but exponential time is baaad.

Share this post


Link to post
Share on other sites
I think the quick and dirty solution is the best here, since you''re limited to 10 shots. For each shot, count how many of the other 9 are within the desired radius. This is 90 distance checks, and since it sounds like the function is not going to be needed in real time (i.e. it''s after all the shots have been taken), you should be just fine.

Share this post


Link to post
Share on other sites
You can't just check how many are in the desired radius of a shot because 3 shots could be within a 1 inch circle without 3 being within a 1 inch circle centered on one of them. If 3 shots form a triangle where each side is 0.99 inch, they are in a 1 inch circle centered on the median position of the 3 but not in a 1 inch circle centered on any one of them.

I THINK you could just do something like
center = [position of bullet 1]
for each bullet ii
counter = 1
for each bullet jj
if ii isn't jj, and jj is within 1 inch of center
counter = counter + 1
center = center * (counter-1)/counter) + [position of bullet jj] / counter
end if
end for
if counter >= number of bullets required to be in group
win = true
break out of loop
endif
end for


[edited by - Extrarius on July 3, 2003 8:19:54 PM]

Share this post


Link to post
Share on other sites
I'm pretty sure this algorithm will work. Haven't proved it, but it makes sense to me. If you have 3 points A,B,C and want to determine if they lie within a circle of radius R:


For each pair of points p1 p2:
Find the intersection of the circles centred at p1 and p2 with radius R
If the remaining point p3 is within a distance R of either intersection point:
You've got a match
Else:
Try again with the next pair of points


Repeat this with each triplet of bullet holes until you get a match. If you get no matches, the player has bad aim.

Here's some pseudocode:


function areClose(Point A, Point B, Point C, radius R)
{
circle1 = circle centred at A with radius R
circle2 = circle centred at B with radius R
X,Y = intersection points of circle1 and circle2
if distance(C,X) <= R or distance(C,Y) <= R
return true

circle1 = circle centred at A with radius R
circle2 = circle centred at C with radius R
X,Y = intersection points of circle1 and circle2
if distance(B,X) <= R or distance(B,Y) <= R
return true

circle1 = circle centred at B with radius R
circle2 = circle centred at C with radius R
X,Y = intersection points of circle1 and circle2
if distance(A,X) <= R or distance(A,Y) <= R
return true

return false
}


[edited by - Dobbs on July 3, 2003 8:55:12 PM]

Share this post


Link to post
Share on other sites
That would work for three shots, yes. But the game needs to be able to count up to all 10 shots in a circle--there is a game option where the user can choose how many shots count toward the final score.

So an algorithm that only checks three shots wouldn''t be quite good enough for all 10 shots.

Would this algorithm work for more than three?

Share this post


Link to post
Share on other sites