| 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
|
|
|
|
Members
Search
Help
Register
Login
Home
