FreeOrion

Thanks guys, DaveBaby's solution looks very workable, it seems to be esentialy what I was doing just quite a bit more compressed, the vector is esentialy equivilent to a Rise/Run from a Point. The use of 2 equations though gives a lot more information in the final stage as to the lines crossing or being parrelel.


Here is a plan for executing a preferential Atatchment based Power-Law network, this is just one of several such networks that can be created but this one has the advantage of not requiring any actualy exponential math.

1 Start with a full list of Stars now create a second vector list of stars that starts out empty. Let the User pick some stars manualy or enter a number so we can randomly pick that many stars off the list. Move the stars from the first list to the second list and dont give them any lanes (dont worry these seed systems will eventualy get lots of connections).

2 Randomly pick a star off the first list and grow X number of lanes out of it towards stars that are already on the second list. X is some user input determining how many lanes we will have, each star grows this many lanes when it added to the list. When this many outbound lanes have been created move the star onto the second list and forget about it.

3 Preference, each time a star grows a lane it dose a random roll to deside what star to attach it too. Each star on the list is first given a value equal to BASE + # of Lanes. BASE is a critical user input that will determine how preferential the network is, as Base incresses to infinity the assignment becomes random. BASE needs to be greater then 0 so that initial Seed stars will be able to atract lanes but it can be vanishingly small resulting in practicaly ever lane running into one system. Add up the value for each star on the list (in the begining its just #Seed Systems * BASE) and then roll a random number between 1 and that total. Iterate through the list += ing the values untill the desired number is meet or exceeded. Now attacth the lane to the star that we stoped on. Increment the starlane count on the lucky star and Increment the total value count by BASE + X.

4 Keep taking stars off the first list untill that list is exausted and all stars have been moved onto the second list and your done. If their is only 1 Initial Seed star we are guaranteed full conectivity and if their are very few its still very likly that we will get everything conected.

My goal here is not to eventualy merge Power-Law networks with Delaunchy Trinagulation networks and then cull in some interesting way to produce a network with interesting architecture.

_________________
Fear is the Mind Killer - Frank Herbert -Dune

void Universe::GenerateStarlanes(StarlaneFreqency freq)
{
//Theirs no Control input for these yet so they are defined Here to experiment with different values
//Change them here, eventualy these should become arguments to the Function

double Base =1;
unsigned int Seed_Systems = 10;


std::vector<System*> sys_vec = FindObjects<System>();

for (unsigned int i = 0; i < sys_vec.size(); ++i) {
{System* system = sys_vec[i];}

if (sys_vec.empty())
throw std::runtime_error("Attempted to generate starlanes in an empty galaxy.");
if (Seed_Systems <= 0)
throw std::runtime_error("Attempted to generate with 0 or less seed systems.");
if (Base <= 0)
throw std::runtime_error("Attempted to generate with a Base value of 0 or less.")

//Create the done vector to hold system that have already grown lanes and are the targets of
//subsequent growths
std::vector<System*> done_vec;

//Create the Value Array and Initialize with the Base, the lower the base the greater the
//attachment is weighted towards heavely connected systems
new System* = double Value[sys_vec.size()] = {Base};

//Create the RollCounter and Initialize it
double Roll_Counter = Seed_Systems * Base;

// Start by moving the desired # of systems fron the sys_vec to the done_vec to give us something to atatch too
// This just takes the systems off the bottom of the vector rather then randomly, the stars were created randomly though
// so this should not be a problem, if it turns out to be a randomization can be added
for (i=0; i < Seed_Systems; i++)
{done_vec.push_back(sys_vec.back()); sys_vec.popback()}

System* dest_system;
System* system = sys_vec.back();

while (!sys_vec.empty())
{
//Make starlanes with destination system based on the Random Roll
for (i = 0; i < starlanefreq; i++)
{
double Roll = inline DoubleDistType DoubleDist(0, Roll_Counter);
double Total =0;
int Counter =0;

//Use the Value array to weight the search for the random star
while (Total < Roll)
{dest_system = done_vec[Counter]; Total += Value[Counter], Counter++}
if (system->HasStarlaneTo(ID(dest_system)))
{continue;} //It rolled the same system twice so reroll

// Create the lane
system->AddStarlane(dest_system->ID());
dest_system->AddStarlane(system->ID());

// Add 1 to the Value slot that coresponds to the next element of the done vector which will
// soon hold the system currently growing lanes and increment for the system that was atatched too.
int Next_Value = done_vec.size() + 1
Value[Next_Value] += Value[Next_Value] + 1;
Value[Counter] += Value[Counter] + 1;
}

// When the desired number of lanes have been created the for loop exits and the star is
// pushed and poped to the done list, lastly increment the Roll Counter and take the next system off the list
done_vec.push_back(sys_vec.back());
sys_vec.pop_back();
Roll_Counter = Roll_Counter + starlanefreq + Base;
system = sys_vec.back();
}

delete[] Value; //Always clean up
Return 0;
}


Boy these Vectors are much better then regular arrays (asuming I am using them correctly). How dose the above stuff look? Have I called stuff properly and used the right forms? If I wanted to go about Runtesting this how can I get it into my copy of FreeOrion, I asume I will need to recompile FreeOrion which I have never done before would my GNU compiler be up to the task?

_________________
Fear is the Mind Killer - Frank Herbert -Dune

Had some thoughts on Galaxy Generation

If we want to run multiple Independent Starlane generators and later merge the results together we are going to need to clean up after each Lane Generator runs and stip all the Stars of their lanes and store the lanes in some kind of Matrix or Vector that the Lane Generator Returns.

The reason is that under the current implemention if you run a Starlane generating Algorithm it assumes that its working with a Virgin Galaxy with no lanes, if infact their are lanes atatched to stars already then all kind of calls for # of starlanes and haslaneto will come up wrong and likly screw up the Generator.

Thus I propose we create some kind of "LaneStripper" Function that will strip off all the langes from the Galaxy store them into some kind or Vector and then Return a pointer to said vector. By running this function imediatly after each Lane generation we can encapusalate the results of that algorithm into a single object and create a blank slate for the next algorithm to run on.

Once the desired lane generators have run we can them run a List merging function that mergest 2 or more LaneVectors into a single unified list and eliminates duplicate entries or combines them based on some boolian logic choices that we feed it.

Then the merged list can be feed into one or more Culling Algorithms that chop out the lanes that they dont like (possibly substituting in "correction" lanes as well"). Now we can use the Merger to once again merge these list into a single unified list using boolian logic.

For example Lets say we have a large list of raw lanes A and we feed that into 2 culling Algorithms (one for "lanes that are too near stars" and one for "lanes too long") These culls return list B and C respectivly. We then merge with D = (B && C) and D will contain only lanes that are present in B and C and thus passed both tests. But lets say that we want something differnt like all the lanes that were rejected that would be D = (A !! C) && (A !! B). This should allow us to keep the lane culling and lane generating algorithms as seperate as possible and give the user as much end use flexibility as possible as it will be easy to add in a new algorithm and imediatly make use of them.

_________________
Fear is the Mind Killer - Frank Herbert -Dune

This is not necessary. Current while generating lanes, my code stores data in a temporary structure:

std::vector<std::set<int> > laneSetArray;

Every time my algorithm decides to add a lane between two systems, it adds to the sets in the vector like so:

laneSetArray[sys1].insert(sys2);
laneSetArray[sys2].insert(sys1);

When you're doing all your galaxy generation, you loop through the vector, and iterate through each set, added all the appropriate lanes to systems using AddStarlane.

There's no need to actually add lanes to systems using AddStarlane until you're completely done all funky algorithms and know the final set done lanes you're going to add.

My culling function and my function that checks if two systems are connected within N starlane jumps both take a reference to a std::vector<std::set<int> > as a parameter.

It's also sometimes handy to have more than one laneSetArray. My multiple root tree growth function takes references to two std:vector<std::set<int> >, one for all possible lanes that could appear in the growing tree, and one into which to insert all the lanes that make up the growing tree.

The wiki Programming Work page says something that should have been done for v0.2 was to "treat neutron stars and blackholes differently w.r.t. starlanes, planets, and wormholes". I can't find any mention of this in the design docoument thought... What does this refer to, and what should be happening?

If I remember correctly they were going to have a greater probability of worm hole connection. Seeing as how worm holes havent yet been implemented in any form that should be our first priority in my opinion.

_________________
Fear is the Mind Killer - Frank Herbert -Dune

I wrote that. Right now, a black hole or neutron star is just as likely as any other star to have habitable planets, starlanes, and/or a wormhole. It seems that maybe the design team should change that; I wasn't going to do anything until a decision was made by one of them.

Regarding planets, a blackhole is less likely to have them, and they are much more likely to be hostile to human life. I'm not at all opposed to the values in the Planet Density chart being tweaked to increase the chance of the "no planet" result.

Regarding wormholes, I figured that if and when they are added to the game, they'd *always* have at least one end in a blackhole system.

I (unofficially) declare Geoff lord of the starlanes. If he wants to tweak one of his starlane generation algos so that blackholes have less lanes, then it's fine with me and I doubt Aq would say "no".

--esp. since we've never tickled starlane generation in the Design Doc.

I'd really like to see one of Geoff's starlane algos make into v.3. The results are, imho, much better than the current version.

I asume your refering primarily to Delaunchy Triangulation? Its a very nice algorithm and is definatly a tool we should use and I would love to see it used in v0.3 BUT I think we should retain the older model as an option and seek to expand into more optional algorithms and means of mixing them.

Should we add "Out of game Galaxy Generation/tweaking" to the road map and if so ware? v0.3 seems a bit too early as theirs already much on the plate, perhaps someware thats a bit thin now?

_________________
Fear is the Mind Killer - Frank Herbert -Dune

Do we have a way for you to imediatly see the whole map, so far as I know you have to explore the whole thing which I cant do because FreeOrion is crashing when I left click empty space rather then a star when moving a fleet. I can't go more then 10 or 20 turns before I inevitably misclick and crash. Has anyone made a "cheat and show all starlanes" button?

_________________
Fear is the Mind Killer - Frank Herbert -Dune

it's only possible with a special fo build

_________________
Press any key to continue or any other key to cancel.
Can COWs fly?

And unfortunately, even the special build does not work. Since this is definitely needed, I'll add a god-mode to the TODO list.

hehe, do you remember!?

I would like seeing ALL internal (debug-) settings to be setable from outside. For instance ship warp speed. This would make debugging/testing much more easy.

EDIT: typo

_________________
Press any key to continue or any other key to cancel.
Can COWs fly?

Good idea. Get to work.

I vaguely recall this being discussed, but I don't recall the answer...

Is there any reason that the "debug mode" couldn't have the ability to add or remove starlanes / wormholes?

And, actually, is there any reasons the game couldn't add or remove starlanes in normal play... perhaps with effects or something similar?