Home World Forum
Stars! AutoHost web forums

Jump to Stars! AutoHost


 
 
Home » Stars! Clones, Extensions, Modding » FreeStars » Efficient Algorithm for Scanning planets/fleets/etc.
icon5.gif  Efficient Algorithm for Scanning planets/fleets/etc. Wed, 07 February 2007 16:36 Go to next message
sirgwain is currently offline sirgwain

 
Senior Chief Petty Officer

Messages: 86
Registered: March 2004
Location: Tucson
I've been doing a little performance tuning on my Stars! game because it has felt sluggish to me. I've made numerous improvements and added even more numerous log messages to determine where my pain points are. I've isolated one really nasty one in my turn generation function.

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.

I know the original Stars! devs must have had this algorithm done very well because even really complicated turns don't take very long to generate.

Any whizbang algorithm programmers have any ideas?

Btw, if anyone is thinking "12 seconds, that doesn't seem like too much..." I'm doing this on a dual Xeon 2.4 Ghz machine with 3GB of RAM. That's a little bit above the original Stars! specs. I fear my clone being run on a machine bought in 2005 or earlier. Smile

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Wed, 07 February 2007 17:33 Go to previous messageGo to next message
m.a@stars is currently offline 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. Twisted Evil

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. Whip

I'd directly exclude planets from "openspace" scanning... Rolling Eyes

Cloaked fleets/starbases still pose some challenge, tho, as they cannot be "tagged out" until a satisfactory scan has been obtained. Sherlock

Perhaps your distance check could be improved too... Teleport



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Wed, 07 February 2007 19:20 Go to previous messageGo to next message
NingunOtro is currently offline 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. Wed, 07 February 2007 23:03 Go to previous messageGo to next message
LEit is currently offline LEit

 
Lt. Commander

Messages: 879
Registered: April 2003
Location: CT
One thing I did in FreeStars is to keep a list of objects at each location, this is useful in a lot of areas and not hard to build and maintain as things move around.

One place it's useful is in scanning. If you check if one fleet/planet is in range, you know the whole stack of them are or are not in range. Then you have to check cloaking/tachyons...

The other thing you can do is quickly rule out some objects by checking if the x or y is out of range first. IOW, if the scan range is 100ly and the scanner is at 1000, 1000, anything beyond 1100 x or y is out of range, no need to calculate the exact range or cloaking/tachyon for that combination.



- LEit

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Thu, 08 February 2007 15:16 Go to previous messageGo to next message
Kotk

 
Commander

Messages: 1227
Registered: May 2003
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.

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. Wink

Do not forget that minefields scan (SD) and are discovered bit differently than usual.


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.

6) apply pen scanners to orbiting objects. Everything that is scanned move to scanned objects list.

7) do what you want with scanned objects. Wink

If it is still slow then switch to C++ or something. Very Happy



[Updated on: Thu, 08 February 2007 15:17]

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Thu, 08 February 2007 17:08 Go to previous messageGo to next message
sirgwain is currently offline sirgwain

 
Senior Chief Petty Officer

Messages: 86
Registered: March 2004
Location: Tucson
LEit wrote on Wed, 07 February 2007 23:03

One thing I did in FreeStars is to keep a list of objects at each location, this is useful in a lot of areas and not hard to build and maintain as things move around.


I already have that list for determining what fleets are involved in battles. I was thinking I needed to make it more globally accessable to the game. I'll chock up one more reason to do so. Smile

Quote:


One place it's useful is in scanning. If you check if one fleet/planet is in range, you know the whole stack of them are or are not in range. Then you have to check cloaking/tachyons...

The other thing you can do is quickly rule out some objects by checking if the x or y is out of range first. IOW, if the scan range is 100ly and the scanner is at 1000, 1000, anything beyond 1100 x or y is out of range, no need to calculate the exact range or cloaking/tachyon for that combination.



Thanks for the explanation. I was looking through the Freestars code and I noticed there was a lot more in there than just a simple nested loop. You also used the tagging approach m.a@stars described above. I need to implement that.

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Thu, 08 February 2007 17:20 Go to previous messageGo to next message
sirgwain is currently offline 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. Wink


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. Smile

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. Wink



Quote:


If it is still slow then switch to C++ or something. Very Happy


Ooooh a little C# jab there. Smile 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. Smile

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Thu, 08 February 2007 17:30 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
Kotk wrote on Thu, 08 February 2007 21:16

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.


I was under the impression that "scannerless scan" yielded too poor info to happily discard a better scanning of the same target... Confused



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Fri, 09 February 2007 05:16 Go to previous messageGo to next message
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. Smile

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. Smile


Uhh... i did not say that switch to C. Shocked 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... Confused

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 11:55 Go to previous messageGo to next message
sirgwain is currently offline sirgwain

 
Senior Chief Petty Officer

Messages: 86
Registered: March 2004
Location: Tucson
Quote:


Uhh... i did not say that switch to C. Shocked C++ is similar enough with C# and whatever they say ... C++ does calculations about 5 times quicker than C#.



You got me curiuous. I had always heard C# was approx the same speed, but never done any research on it. I did a little code test to see what my results were. I wrote a simple console app in C++ and C# to do this:

   double d1 = 0.727272;
   double d2 = 0.26252;
   double d3 = 343432.232;

   for (int i = 0; i < 100000000; i++)
   {

      d3 = d1 * d2;
      d1 = d3 * d2;
      d2 = d2 * d2;
      d3 = d1 * d2;
      d3 = d3 * d2;
   }


The C# time was between 595 ms and 607 ms. The C++ time was between 594 ms and 598 ms. That doesn't quite seem like a factor of 5 difference to me. Smile

Obviously the more complicated the code the more crap C# is going to throw on top of things (like in Windows forms and using complicated data structures), but the language speed itself is equivalent in speed for doing raw calculations.

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Fri, 09 February 2007 15:42 Go to previous messageGo to next message
Kotk

 
Commander

Messages: 1227
Registered: May 2003
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. Very Happy

//C# code

using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime time1 = DateTime.Now;
            double d1 = 0.727272;
            double d2 = 0.26252;
            double d3 = 343432.232;

            for (int i = 0; i < 100000000; i++)
            {

                d3 = d1 * d2;
                d1 = d3 * d2;
                d2 = d2 * d2;
                d3 = d1 * d2;
                d3 = d3 * d2;
            }
            DateTime time2 = DateTime.Now;

            TimeSpan span = time2 - time1;
            
            Console.WriteLine("{0};{1};{2};{3}",span, d1,d2,d3);
        }
    }
}


Displays:
00:00:02.1089395;0;0;0
I get it means 2109 milliseconds?

//C++ code

#include "stdafx.h"
#include <sys/timeb.h>
#include <sys/types.h>
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{

    timeb time1;
    ftime(&time1);
    double d1 = 0.727272;
    double d2 = 0.26252;
    double d3 = 343432.232;

    for (int i = 0; i < 100000000; i++)
    {

        d3 = d1 * d2;
        d1 = d3 * d2;
        d2 = d2 * d2;
        d3 = d1 * d2;
        d3 = d3 * d2;
    }
    timeb time2;
    ftime(&time2);
 
    std::cout << (time2.time - time1.time)*1000 + time2.millitm - time1.millitm 
        << ";" << d1 << ";" << d2 << ";" << d3 << "\n";
    char c;
    std::cin >> c;
    
    return 0;
}


Displays:
594;0;0;0

C++ runs bit less than 4 times quicker but not much.
Both examples were compiled with very same Visual Studio 2005 Professional.


[Updated on: Fri, 09 February 2007 15:54]

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Fri, 09 February 2007 16:49 Go to previous messageGo to next message
sirgwain is currently offline 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. Very Happy



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. Smile

Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Sun, 07 October 2007 16:38 Go to previous messageGo to next message
yartrebo is currently offline 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. Wed, 24 October 2007 15:49 Go to previous messageGo to next message
sirgwain is currently offline sirgwain

 
Senior Chief Petty Officer

Messages: 86
Registered: March 2004
Location: Tucson
I thought about partitioning the universe into quadrants and putting the ships in buckets, but I think I really need to work on the overall server algorithm. There is too much "loop through all fleets to find out x", then "loop through all the fleets to find out y" in my code. I think I need to do an overall architectural look at the server code, but alas there is so much to do on the project it's hard to justify optimizing yet.



Report message to a moderator

Re: Efficient Algorithm for Scanning planets/fleets/etc. Thu, 25 October 2007 07:01 Go to previous message
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

Previous Topic: New stars! server clone proposal
Next Topic: 3D tool
Goto Forum:
  


Current Time: Thu Apr 25 11:22:07 EDT 2024