Galaxy Maker

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderators: Committer, Committer

Post Reply
Message
Author
vishnou00
Space Kraken
Posts: 157
Joined: Tue May 25, 2004 3:15 am

Galaxy Maker

#1 Post by vishnou00 » Tue Aug 03, 2004 8:35 pm

This is a attempt to move a sub-thread of the "How to deal with stars near, but not on, starlanes?" thread to a new thread. The sub-thread (as I see it now) goes from

viewtopic.php?p=13495#13495

to

viewtopic.php?p=13500#13500





My proposal is the galaxy generation method I used for a Stars!-like game I began a while ago.

I use a graymap to express the probability of having a star there. Every pixels of the map is a location. When you add a star, you modify the graymap to control how near a star can be of another one, and galaxy clumping, if you increase the probability of having another star nearby.

I think the technique is powerful by its simplicity: to define the general shape of the galaxy, you just need a bitmap editor. A probability of 0 would be a "deleate star zone" Impaler spoke of.

I don't know how FreeOrion work right now.


Back then, I did it in C++, with prototyping in Perl. I don't know if using Python would be easier.

User avatar
Impaler
Creative Contributor
Posts: 1060
Joined: Sun Jun 29, 2003 12:40 am
Location: Tucson, Arizona USA

#2 Post by Impaler » Wed Aug 04, 2004 3:16 am

Nice idea I think we should be doing something along thouse lines. I though up an idea for adding some additional layers that could help us map starlanes at the same time. (note I am only just starting to learn some programing so I am just guessing that this will be simple to program and fast to execute)

1 Start with a simple bit map file For each Color present specify a number from 0 and up. (sugjest we use the Luminosity of the color in question giving a range for 0 to 120)

2 For each Point on the bit map make a random number roll to deside if a star is at that point. Multiply the Luminosity value 0-120 by some arbitrary scaling constant that we can deside on later (this scaling factor could possibly be adjustable to effect the star density across the whole map), the goal will be to have 120 be the maximum density that dosent cause catostrophic problems. If you role is equal to or greater then the Luminosity value of the point then no star is present. For the first pass ignore the effects of neiboring stars.

3 Run through the map of stars and see if any stars are too close to each other, if so randomly deleate one of the offending stars untill no more proimity violations are present.

4 Your finished with starmaking and can move on to Starlane creation (adsactly how this will be done is still under debate but we know we will have a variable for "# of lanes that connect to stars" and possibly one for "average length of lanes".



The effect here is as you sugjest some areas can be made high density (aka the Galactic Core) and other areas progressivly lower densities and even "empty" zones that start out at an initial value of zero (the exclusion zone). Think of it like multiple screen sifting a rain of sand to form a pather. Density is directly proportional the the Fields Density number, an area with a starting value of 30 will acumulate twice as many stars per unit of area as one with 15.

The same color patern can then also be used when starlanes are being generated.

It might even be possible to use the Hue/Saturation/Luminosity value of each color as the build values Luminosity for stardensity (light = High density, Dark = Low), Hue Starlane density, Saturation for some yet to be determined value (maybe starlane length or star age). It would be a piece of cake to make your own Bitmap template and generate nice looking yet still random Galaxies over and over and with what ever overall architecture you want. Highly refined templates (and silly things like smily face shaped galaxies) could be made and swaped by the comunity.

So for example I could paint a 3 arm Galaxy use light Purple (Lum 170/Hue 201) For a Dense well connected Core, Forest Green (Lum 71/Hue 79) for arms of modest density and conectivity and a ring of near Black yellow (Lum 25/Hue 41) surounding the whole thing for low density poorly connected stars of the Galactic Halo. Beyond that a filed of total Black gives me the Intergalactic Void with 0 Lum.
Fear is the Mind Killer - Frank Herbert -Dune

vishnou00
Space Kraken
Posts: 157
Joined: Tue May 25, 2004 3:15 am

#3 Post by vishnou00 » Wed Aug 04, 2004 7:24 am

If we're going into specific, I could as well say how I did it.
  1. Create an array of x*y unsigned integers, with initial value around 100.
  2. Evaluate the sum of all the elements (so if x*y=160000, it is around 16000000).
  3. Generate a random value between 0 and that sum.
  4. Consider the following for loop

    Code: Select all

    for ( i=0; RValue > 0 ; ++i ) /*RValue is the value generated in the last step*/
    RValue -= bitmap_array[i]; /*bitmap_array is the array created in step 1*/
  5. When the loop ends, i is at the location of the new star, so we add a star there.
  6. Here we modify the array. It is in that step that we do funky stuff that will really shape the galaxy: assign 0 to array locations around the new stars to avoid too nearby stars, add a falloff so other stars tend to be a little farther, multiply the area around the new star by a value >1 to "encourage" formation of cluster. Control the last step with the number of stars nearby (inside a radius) so there isn't jus one big clump (like, if there are already 3 stars nearby, begin to discourage other stars from establishing there by lowering array elements' value, if there are already 7 in a cluster, 0 the zone so it doesn't get bigger). Those rule could be more complex to generate arms and spirals. It is important to always multiply values, not add them, as you could "add" chance to have two stars too near.
  7. goto step 2 as long as you have stars to add
To sum up, there is two place you control the shape of the galaxy: in step 1, where you define the initial values, and in step 6, where you modify these values.



I don't know the detail of the plans about starlanes, but I don't think using bitmaps is especially suited for the task. Other checks would be much more important (angles, connectivity, overlapping) but I agree bitmap could be used in someway (a probability of a starlane to be culled from the Delauney Triangulation, for example).

I think the strengt of my proposal is that there is never any delete step: every star appear in a definite, correct location.

All the talk about bitmap is just to highlight that paint programs are damn cheap map editor in term of interface quality vs. programming time requirement (on our part, I'm sure graphic software developpers worked very hard! ;) ). I don't mean wrap the idea around the capabilities of bitmap (multiple channels, etc), but it could be used (nebula probability? special event locations? system richness?) a lot of options could be packed in a couple of layers.

User avatar
Daveybaby
Small Juggernaut
Posts: 724
Joined: Mon Sep 01, 2003 11:07 am
Location: Hastings, UK

#4 Post by Daveybaby » Wed Aug 04, 2004 8:23 am

w.r.t. fitting the desired number of stars within a template (as discussed on the previous threads) - the way i have done this in COW is as follows:

(1) Work out the average area required to fit the desired number of stars at the desired average density.

(2) Work out the area inside the template.

(3) Scale the template so that the area inside it matches the area calculated in (1).

(4) Place stars randomly. Each star must be a minimum distance from any previously placed stars (determined by the desired average density). If a star is too close, delete it and try again.

(5) If you have tried (say) 10 times in a row to place a star and have failed, then decrease the minimum distance (multiply by 0.75) and try again. Repeat as necessary.

I've found this works very well for placing stars. The whole point being that you determine the size of your galaxy from the number of desired stars, and the desired density, rather than just trying to cram the desired number of stars into a fixed space.




w.r.t. the stellar density bitmap - it is a nice idea - i've been planning to do something pretty much identical to this for COW. I was gonna suggest it for FO, but i dont know how well it would work w.r.t. starlanes (i.e. by decreasing density in an area all you are doing is increasing the travel time between stars, instead of creating terrain like you would be in a Moo1/2 type of map).

Also, i havent yet worked out how to incorporate it into the above technique for star placement - i.e. how to work out how big the template (or bitmap) needs to be scaled to in order to fit in the desired number of stars. Its easy to work out for a simple yes/no bitmap - but using greyscales for densities always seems to mess things up (particularly when you have areas of very low density).

In addition to this, i use border displays in my maps, and to get good borders i need strongly defined galactic boundaries. Areas of low density also tend to mess up this side of things as well.



w.r.t. using templates to prune starlanes (in order to avoid connections between spiral arms, for example), note that this can potentially lead to problems, in that you may cut the only lane which connects the star to the rest of the galaxy. I'm not absolutely certain that this would ever actually occur, but it certainly seems like it would be possible, particularly if you had, say, several tightly spiralled narrow arms on a galaxy.
The COW Project : You have a spy in your midst.

User avatar
Impaler
Creative Contributor
Posts: 1060
Joined: Sun Jun 29, 2003 12:40 am
Location: Tucson, Arizona USA

#5 Post by Impaler » Wed Aug 04, 2004 10:34 am

Dave Babby: It seems your goal it to create a map with a very presise # of stars on it and you wish to scale the whole template up or down inorder to get the randomly droped stars to fit well. I think this should be avoided as compression could tend to pixelate and distort the bit map and remove the players ability to control the size of the map directly.

It would be better I think to simply scale the Arbitrary Factor I Introduced in Step 2 untill the predicted number of stars = the desired value.

It should be simple to calculate the expected # of stars for a given bit map before the stars are actualy generated. Simply multiply the Density x area x then sum up all the differnt density regions and multiply by the Scaling factor for a total.

(Density A x Area of A)
(Density B x Area of B)
(Density C x Area of C)
+___________________
Standard Star Count X Scaling Factor = Expected StarCount

Then run the Galaxy Generator with the Scaling Factor that will produce aproimatly the desired Quantity of stars (it wont be perfect cause its random) I dont think it will be off by more the 10% and we can do some clean up to get the total right on the button.
Fear is the Mind Killer - Frank Herbert -Dune

User avatar
Daveybaby
Small Juggernaut
Posts: 724
Joined: Mon Sep 01, 2003 11:07 am
Location: Hastings, UK

#6 Post by Daveybaby » Wed Aug 04, 2004 11:10 am

Thats fair enough, i just figured that it would be easier to have the bitmap defining just the shape of the galaxy, and then scale it to any size that is required, instead of having to produce a separate bitmap for every shape *and* size of galaxy that you might want to play. For COW i've tried to keep things extremely flexible, to the point that you can enter any number of stars you like (as long as you have the memory available) - i've successfully run galaxies of 5000 stars (although things do tend to slow down a bit with numbers this stupid :P ).

w.r.t. quantization/pixellisation/distortion due to scaling - i dont see that as a major issue. These are only density maps we are talking about - stars will be randomly placed within the defined areas, so unless you start going for the 5000 star galaxies i was talking about earlier, pixellisation effects wont tend to be visible. And even if it was, you could counter this by using higher resolution bitmaps (if youre going to scale anyway then there is no problem with this, you can use any size bitmap you like) and/or by using more advanced scaling algorithms which dont introduce as much pixellisation.

I will repeat that i dont see much benefit to greyscale density maps for a starlane based game. With Moo1/2 style travel you could use areas of low density to limit movement (at least until your engine tech is sufficient to traverse these areas). With a starlane system such as that used by Moo3 you dont have any limits on ship range. All you achieve by reducing density is that you make it take longer to get somewhere on certain parts of the map.
The COW Project : You have a spy in your midst.

User avatar
Impaler
Creative Contributor
Posts: 1060
Joined: Sun Jun 29, 2003 12:40 am
Location: Tucson, Arizona USA

#7 Post by Impaler » Wed Aug 04, 2004 12:59 pm

DaveBabby: Do you have a place ware your COW Project can be downloaded, I have been looking around your site but havent found anything Downloadable. I would very much like to play around with the various Galaxy Generators that have been made so far and if I ever get skilled enough to open up the Sourse Code and start making my own tinkerings.
Fear is the Mind Killer - Frank Herbert -Dune

User avatar
Daveybaby
Small Juggernaut
Posts: 724
Joined: Mon Sep 01, 2003 11:07 am
Location: Hastings, UK

#8 Post by Daveybaby » Wed Aug 04, 2004 1:38 pm

Not really, its compiled to run on a SPARC workstation using Xwindows. Been meaning to port everything to SDL, but havent even started yet (primarily due to the fact that its summer). I can send you an executable if youve got anything that will run it... :twisted:

I can give you the current version of the galaxy generation source code. Its pretty basic at the moment (just does a few hard coded shapes) but it does the job for now.
The COW Project : You have a spy in your midst.

Post Reply