Home » Stars! Clones, Extensions, Modding » FreeStars » Efficient Algorithm for Scanning planets/fleets/etc.
|
Re: Efficient Algorithm for Scanning planets/fleets/etc. |
Wed, 07 February 2007 17:33 |
|
m.a@stars | | Commander | Messages: 2765
Registered: October 2004 Location: Third star to the left | |
|
sirgwain wrote on Wed, 07 February 2007 22:36 | Each turn each player's knowledge set must be updated based on what universe objects are within scan range of his fleets. On a Huge/Packed universe with 15 AI players creating scanner ships and sending them out, it's taking 12 seconds to update scan knowledge. There are 1257 universe objects (with 312 of those being fleets) at this point.
The way my current algorithm works is like so:
Each fleet checks every universe object to see if it's within distance of its non pen scanners followed by a check for the pen scanners. This means I have 312 * 1257 = 392,184 distance calculations for a turn generation.
|
Tagging comes to mind. If an object has already been scanned, remove it from the list for subsecuent scanners.
Also, if you do the penscans 1st, the objects tagged by them can be ignored by the "openspace" scanners. Or perhaps do it the other way around.
I'd directly exclude planets from "openspace" scanning...
Cloaked fleets/starbases still pose some challenge, tho, as they cannot be "tagged out" until a satisfactory scan has been obtained.
Perhaps your distance check could be improved too...
So many Stars, so few Missiles!
In space no one can hear you scheme! Report message to a moderator
|
|
|
Re: Efficient Algorithm for Scanning planets/fleets/etc. |
Wed, 07 February 2007 19:20 |
|
NingunOtro | | Master Chief Petty Officer | Messages: 105
Registered: September 2005 Location: Brussels, Belgium | |
|
That is a very basic algorithm without any kind of optimisation, I would not call it an algorithm at all.
Why not try something like this:
1. Set visibility status of each object to none for all races
2. For objects = 1 to z
3. For races n still present = 1 to n
4. if object property of race n then set visibility for that object to perfect and jump to next race in 3.
5. For observing token a of race n having the biggest penscan diameter to a having the lowest diameter
6. if object within range of observing token a then set visibility for that object to perfect and jump to next race in 3.
Next observing token with penscan 5.
7. if visibility of object not perfect then
8. For observing token a of race n having the biggest non-penscan diameter to a having the lowest diameter
9. if object within range of observing token a then set visibility for that object to partial and jump to next race in 3.
Next observing token with non-penscan 8.
endif 7.
Next race 3.
Next object 2.
This way you schedule the evaluations for every object in a way that you handle the most significant and the most probable first, and you discard every object from further evaluations as soon as the first match is found, as subsecuent matches with other observing tokens will add no additional information.
Effectively, once an object has been penscanned, no additional penscan or non-penscan is going to add any more info, so we try to tag as many as possible as soon as possible by evaluating the observing tokens with the biggest scanners first.
As soon as we run out of observing tokens any non spotted object remains with visibility=none.
As soon as we run out of objects any remaining observing tokens can remain unevaluated as they will add nothing to what is aleady known.
This should keep your calculations well below 392.184.
[Edit: Of course range modifiers should be taken into account, either inherent to the observing tokens, the objects or dependent on location as when orbiting a star]
[Updated on: Wed, 07 February 2007 19:33]
If we were esteemed intelligent 'enough', they would have contacted us.
If we can not find them, either we are not smart enough, or they are smarter at hiding.Report message to a moderator
|
|
| | | |
Re: Efficient Algorithm for Scanning planets/fleets/etc. |
Thu, 08 February 2007 17:20 |
|
sirgwain | | Senior Chief Petty Officer | Messages: 86
Registered: March 2004 Location: Tucson | |
|
Kotk wrote on Thu, 08 February 2007 15:16 | there are basically 3 different scanning types
point blank scanning, non-penetrating scanning, penetrating scanning.
First one is important since scannerless ships see opponent ships and orbitals at same location. Also SS special scanners have improved abilities at same location.
|
Good to know. For some reason I was under the impression that ships without scanners didn't see any ships unless they engage in battle with them.
Quote: | Do not use squre root in range/distance calculations (its slow), instead compare the square of range with square of distance. Do not forget to apply squares of cloak/tachylon modifiers too.
|
Well my philosophy of coding has always been readability over efficiency, within reason. I don't tend to implement things that execute but are confusing to code browsers. Especially in a future open source project.
Quote: |
Algorithm i would use would consist roughly of those steps:
1) Make 3 lists of scanners. Note that if JOAT did split out 100 chaff in some location, then it is bad idea to have 100 equal scanners there, have just one.
2) Make a list of all objects that do not belong to player. QSort that list by coordinates (by x if x is same then by y). That way you get the same location effect that Leit described.
3) apply point-blank scanners first to the list (because these involve no ranges or cloaks). Everything that was scanned move to scanned objects list.
4) split the remaining list into two lists, orbiting objects and deep space objects.
5) apply non-pen scanners to deep space objects. Everything that is scanned move to scanned objects list.
|
For step 5, don't pen scanners scan hull designs, but non pen scanners don't scan hull designs (or planets, for that matter). I can't really move an object into the scanned list unless it's been pen scanned. I could keep two lists of scanned objects, penned and non penned...
Quote: |
6) apply pen scanners to orbiting objects. Everything that is scanned move to scanned objects list.
7) do what you want with scanned objects.
|
Quote: |
If it is still slow then switch to C++ or something.
|
Ooooh a little C# jab there. C# has been tested to be about 95% as speedy as C++. However, C# does not make a crappy programmer a good one, which is something that constantly jabs me. heh heh.
I have done enough C++ in my life. C# is like a angelic light warming my soul and making me happy. Ok, maybe not that nice, but it sure is more fun than clunking around in C.
Report message to a moderator
|
|
| |
Re: Efficient Algorithm for Scanning planets/fleets/etc. |
Fri, 09 February 2007 05:16 |
|
Kotk | | Commander | Messages: 1227
Registered: May 2003 | |
|
sirgwain wrote on Fri, 09 February 2007 00:20 | Good to know. For some reason I was under the impression that ships without scanners didn't see any ships unless they engage in battle with them.
|
They do not see the design (unless they are warmongers). Hulls are scanned like by usual scanners.
Quote: | Well my philosophy of coding has always been readability over efficiency, within reason. I don't tend to implement things that execute but are confusing to code browsers. Especially in a future open source project.
|
Common philosophy, however if you name square of range "range_squared" and not "range" then i dont get what is that unreadable about it?
Quote: |
Quote: |
5) apply non-pen scanners to deep space objects. Everything that is scanned move to scanned objects list.
|
For step 5, don't pen scanners scan hull designs, but non pen scanners don't scan hull designs (or planets, for that matter). I can't really move an object into the scanned list unless it's been pen scanned. I could keep two lists of scanned objects, penned and non penned...
|
Non-pen scanners see deep space objects as good as pen scanners see. Design can be scanned only by warmongers and no difference then if by penscanner or usual scanner or by having scannerless ship in the same location.
Planets and orbitals i was considering to be worth put into "orbiting" list.
Quote: | I have done enough C++ in my life. C# is like a angelic light warming my soul and making me happy. Ok, maybe not that nice, but it sure is more fun than clunking around in C.
|
Uhh... i did not say that switch to C. C++ is similar enough with C# and whatever they say ... C++ does calculations about 5 times quicker than C#.
m.a@stars wrote on Fri, 09 February 2007 00:30 | I was under the impression that "scannerless scan" yielded too poor info to happily discard a better scanning of the same target...
|
Yes i forgot to say that scannerless scan may be mostly ignored with planets.
Orbitals and fleets however are discovered by scannerless scan as good as with any other scan.
Range zero scanning has actually 4 different levels:
1) Scan presence of aliens (for WM it also scans orbital and hull designs)
2) Scan planetary values, terraforming, mineral conc, rough pop count and defenses (for CA it also scans exact HAB of opponent)
3) Scan minerals in fleets
4) Scan minerals on planet ground (Robber baron or by remote miners that mined the planet this turn)
That range 0 scan part works clunky in current stars! too so indeed should be thought deeper. Maybe scan planets entirely separately from all other objects.
[Updated on: Fri, 09 February 2007 05:46] Report message to a moderator
|
|
| | |
Re: Efficient Algorithm for Scanning planets/fleets/etc. |
Fri, 09 February 2007 16:49 |
|
sirgwain | | Senior Chief Petty Officer | Messages: 86
Registered: March 2004 Location: Tucson | |
|
Kotk wrote on Fri, 09 February 2007 15:42 | C++ compilers tend to optimize the code like you posted entirely out so i somewhat modified it to give any usage to the variables there... and also to measure the time directly in code. Somehow i get here different results than you. Maybe i just know C# not well enough and do something wrong with it. Other possibilities are that you run not "C++" but "managed C++" or that you run "Debug" version of C++. On that case your computer seems about 4 times better than mine.
|
Well I'm confused. I must have run into some compiler optimization thing. If I take out the:
Console.WriteLine("{0};{1};{2};{3}", span, d1, d2, d3);
statement it runs lickety split, but if I do anything with those d1,d2,d3 values (like pass them to a function), it takes 2400 ms. How very strange. I've never messed around with compilers so I don't know much about how they optimize.
Quote: |
C++ runs bit less than 4 times quicker but not much.
Both examples were compiled with very same Visual Studio 2005 Professional.
|
Apparently it does!
Off subject of the C# computation speed issue, I figured out what a major flaw in my algorithm was. I was computing the scan range of every component for every check (because it changes based on the race's electronics values for JOATs). If I cache that out it takes .02 seconds to calculate the scanners using a more efficient mark-as-scanned algorithm.
Anyway, thanks for the code postings. They were educational.
Report message to a moderator
|
|
|
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
|
|
| |
Re: Efficient Algorithm for Scanning planets/fleets/etc. |
Thu, 25 October 2007 07:01 |
|
PaulCr | | Chief Warrant Officer 3 Stars! V.I.P
| Messages: 187
Registered: February 2007 Location: An Island that kinda look... | |
|
I've not tried this but how about drawing the scanned area, should work but I don't know about the speed.
Draw them at 100% in colour 100, then 99% in colour 99 etc. To check if a ship can be seen you just need to look at the colour at it's location which gives the % cloaking that can be seen at that point, ie if it's colour 65 then ships upto 65% cloaking can be seen, ships higher than 65% can't
Report message to a moderator
|
|
|
Goto Forum:
Current Time: Sun May 05 23:46:03 EDT 2024
|