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 previous 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

 
Read Message icon5.gif
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Previous Topic: New stars! server clone proposal
Next Topic: 3D tool
Goto Forum:
  


Current Time: Thu Mar 28 14:57:18 EDT 2024