Need help with a recursive function
Author
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!
Author
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?
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?
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:
[edited by - andy_fish on July 3, 2003 1:01:16 PM]
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]
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.
To put it simple, I dont think there is an efficient algorithm. But since N is somewhat small, go with the naive solution.
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.
But of course all that is completely unnecessary for 10 bullets.
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 
.
.
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.
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.
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
[edited by - Extrarius on July 3, 2003 8:19:54 PM]
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 endifend for[edited by - Extrarius on July 3, 2003 8:19:54 PM]
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:
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:
[edited by - Dobbs on July 3, 2003 8:55:12 PM]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
