| Re: Efficient Algorithm for Scanning planets/fleets/etc. |
Sun, 07 October 2007 16:38   |
|
 yartrebo |
 | Petty Officer 3rd Class |
Messages: 43
Registered: July 2006
Location: North America | |
|
There is great improvement that can be had with a better algorithm. Your algorithm is probably O(s, f) = s * f, where s is the number of scanners and f the number of fleets.
While the algorithm is simple, it can be very slow for a large dataset. While I don't have a better algorithm offhand, I can think of an approach to get one with a better big-O:
1: Partition universe into four equal quadrants (upper-left, upper-right, lower-left, lower-right).
2: Go through the list of fleets (or objects that are to be scanned) and place them in their respective quadrants.
3: Go though each scanner and place it into the quadrant(s) where it may have an effect.
4: Apply 1: recursively onto each quadrant until the problem is small enough to brute-force (1 scanner left is trivial, a 1x1 area of space is trivial, an nx1 or nx0 or 0x0 area of space is trivial).
5: You should now have a 1-1 mapping of fleets to the scanner that is most likely able to scan it. Just run through each fleet and compare to this scanner.
O(s, f) = ln(s+f) * (s + f), average case. Worst case is still s * f.
The hardest part will be calculating step 3. In particular, placing scanners in the proper bins. For a particular point, you can use (scanner[1].power * scanner[2].distance > scanner[2].power * scanner[1].distance), but I do not know how to do this for an area (to figure out if the comparison will always be <, always be >, or varies within a specified rectangle). Figure out how to do that without using too many computations or unnecessarily throwing too many scanners into extra bins and you'll have yourself a very fast algorithm.
Personally, I don't mind waiting 10 seconds for a game with 10,000 fleets and 10,000 scanners to process a turn (which is slightly greater than stock stars! limits), so I don't plan on working out the kinks, but if you so desire, feel free to do so.
Report message to a moderator
|
|
|
|
Members
Search
Help
Register
Login
Home
