How to deal with stars near, but not on, starlanes?

[drek]

. If we do delevop a new method for Maze Generation I would still like to see Geoff's Method preserved as an Option, the more variety in the style of map lay out we can provide the better.

As Geoff ponts out, my idea is just a more effienct way of achieving the same results.

Anyway, I don't see any reason a tunnelling algorithm couldn't replace the culling I have in the first stage of post-Delauney processing... it would accomlish essentially the same thing. You'd just need to keep a list of connected systems, and an array of lists of the adjacent systems to each system.

True.

[Geoff the Medio]

m'kay, here's the rewritten code that makes a tree first by growing rather than culling, then checks all the potential starlanes from deluaney to be sure that adjacent systems aren't too far apart (as before)

http://home.cogeco.ca/~toppingwebspace4 ... Output.txt

The results are seen here:


Of note is the system Levitt, which has a whole slew of starlanes coming out of it. I think this is because it was very close to the root of the tree while it was growing, so had more room to grow out compared to later systems... This is a bit of a flaw of the tree method... (if it's even a flaw, which is debatable), though this could be gotten around by putting limits on the number of lanes from a particular system during tree growth, or perhaps having a minimum angular separation between branches from a particular star...

On the same thread, I still haven't put in any angle checking at all, actually... though don't so probly won't make any difference to the Levitt situation.

I'll also probably do some experimenting with using the distance of the shortest path, rather than the number of starlane hops... (though I'm slightly concerned that this will encourage more lanes across the gaps between arms / core of the spiral... but then again these can be removed in a post-processing step.)

[drek]

whoa, you've been busy.

That's a pretty interesting looking map. I'm really digging all the little loops--it's almost like they are rivers marking out the natural borders of empires.

Levitt situation is odd. I don't remember why, but at some point in time I had disregarded this sort of thing as a likely consequence of growing trees. When my brain's less frazzled I'll try to figure out what's up.

Occurs to me that if the Levitt "bug" could be considered a feature. It seems like it might be strategically interesting to have a couple few star systems that are more connected than average...they'd naturally be valuable systems to hold, but more difficult to defend.

[noelte]

looks very nice. levitt ...

Do you plan to take care of topologic constrains? I mean the different galaxy shapes.

Nice work.

[Geoff the Medio]

whoa, you've been busy.

Not especially... the difference between this and the previous version with culling instead of tree growing isn't that much...

Levitt situation is odd. I don't remember why, but at some point in time I had disregarded this sort of thing as a likely consequence of growing trees. When my brain's less frazzled I'll try to figure out what's up.

What's to figure out? I grow the tree by picking a star, adding lanes to all nearby systems that aren't yet connected to the tree, then adding all the stars that just got lanes made to them to the end of the list of connected systems. I then get the next system off the list, and repeat until the list is empty. This means that the first system has all of it's neighbours free, so makes as many starlanes as it has neighbours. Latter systems have progressively fewer unconnected neighbours, so have fewer branches created during the tree-growth stage. This is mostly hidden by the second stage that adds other connections, but the first few systems still have the "starburst" appearance with lots of lanes radiating from them, as I never actually remove any lanes.

It would probably help if I didn't add as many starlanes per star as possible when going through the list... Instead I'd add just one, then go to the next star, and loop back to the start when the end of the list is reached. I'd only remove a star from the list when it has no unconnected potential starlanes left. I might also need to have a separate list of stars that were connected during this pass through the list, and only add them to the "main" list after I'm doing going through the main list that time. Thus I wouldn't end up with a star adding the next star adding the next, meaning I'd just have a single snaking line of starlanes around the galaxy...

Occurs to me that if the Levitt "bug" could be considered a feature. It seems like it might be strategically interesting to have a couple few star systems that are more connected than average...they'd naturally be valuable systems to hold, but more difficult to defend.

Agreed. Though we'd probly want to grow the tree simultaneously from several roots in that case...

Also, the above linked algorithm is still horrendously slow on large galaxies (like... more than a minute). I'm fiddling a bit in the hopes of fixing this, but I think the main problem is all the calls to ShortestPath, which is probably N^2 at least. The calls are themselves in a loop that's probably about N^2 itself, so things tend to slow down quite a bit for large N. If simplifying a few redundancies in the algorithm as above doesn't fix things, I may have to write my own graph traversal / path finder algorithm that gives up after the maximum distance between systems, rather than using ShortestPath, which processes the whole graph, mostly needlessly.

Do you plan to take care of topologic constrains? I mean the different galaxy shapes.

You mean the lanes crossing the gaps between sections of the map? (like between arms of a spiral) ?

I'm not sure that that's really something that can be tackled at this point... I could limit starlane length, which would work for spirals, but with clusters, there needs to be a few long connections. The way to cut out the longer lanes will probly depend on what is decided for map stencil generation... If the current galaxy generation algorithms are used, then I'll need some sort of input from them that says where the arms are and where lanes shouldn't cross.... This could easily be done in the form of a series of lines I shouldn't have any starlanes cross. I'd just cull lanes that intersect with the barriers.

[drek]

What's to figure out? I grow the tree by picking a star, adding lanes to all nearby systems that aren't yet connected to the tree, then adding all the stars that just got lanes made to them to the end of the list of connected systems. I then get the next system off the list, and repeat until the list is empty. This means that the first system has all of it's neighbours free, so makes as many starlanes as it has neighbours.

Judging by your screenshot that method produces a very interesting looking map, but it's not exactly a growing tree (in the maze generation sense of the word).

Growing tree maze generation:

1: Select a node (ie a star) at random
2: Add this first node to a list

do steps 3-6 until list size = 0:

2: Select node X from the list (randomly, or from the top/bottom of the list, depedant upon desired maze shape)
3: Select node Y from the unmade* nodes tangent* to node X
4: Connect nodes X to Y with a path (starlane)
5: Push node Y to the top of the list
6: If (unmade nodes tangent to node X)=0 then remove node X from the list

Your method is identical to a growing tree that always selected from the bottom of a list. Normally, a growing tree would select from the top or randomly, eliminating levitt situations.


* unmade nodes are those with no pathes connecting to other nodes.
* since our topology is not at all regular, the triangulation thingy is run first to determine which nodes are tangent

but I think the main problem is all the calls to ShortestPath

That's the problem.

You shouldn't need to call ShortestPath at all. My eyes are just glazing right now from working on Excel spreadsheets all day, going to think about this later.

The way to cut out the longer lanes will probly depend on what is decided for map stencil generation...

Easier method: before running triganulation, drop some "fake stars" in the empty spaces where no lanes should cross. before running maze generation, remove the "fake stars".

[Geoff the Medio]

Judging by your screenshot that method produces a very interesting looking map, but it's not exactly a growing tree (in the maze generation sense of the word).

I'm not quite sure what you mean by that, but if you mean the fact that there are loops, that's because the tree growing is just the first step. After that, I check for distance between "adjacent systems" along the starlanes that already exist. If it's too long, I make a direct connection between the systems, which produces the loops.

This is mostly hidden by the second stage that adds other connections...

If you mean the way I pick where to grow the next branch from,

Your method is identical to a growing tree that always selected from the bottom of a list. Normally, a growing tree would select from the top or randomly, eliminating levitt situations.

Then I disagree that my current method is not "normal". Either using the head or the tail of the list are both workable / normal ways to generate... as is any distribution between the two or using stuff from partway along the list... they just all generate different tree shapes. (more or less branches branches mostly)

You shouldn't need to call ShortestPath at all.

How else do you suggest I determine the shortest path between two systems with the current graph? (This isn't involved in the tree growing stage, but in the stage after that adds the loops.) ... (But you're right, in that I don't actually need to call shortest path. I can write a faster / simpler breadth first graph visitor that works on my own data, rather than having to add lanes to stars, call InitializeGraph, then ShortestPath, as mentioned above )

Easier method: before running triganulation, drop some "fake stars" in the empty spaces where no lanes should cross. before running maze generation, remove the "fake stars".

I considered that. See earlier in thread.

Essentially, whether I use fake stars that get removed (like those of the covering triangle) or exclusion lines depends on how the map is generated and what sort of data the star placement routine wants to send to me. Right now I can't do either, because all I have is a vector of systems, and no indication of what the galaxy shape is "supposed" to be. So for now, the best I can do is to limit the length of starlanes, hopefully avoiding ones that cross big gaps undesirably.

[drek]

Yeah, I shouldn't be posting right now.

Something else just occured to me:

If you decide to keep your starlane generation more or less like it is now (with the whole Levitt situation), you could assign the first star in the tree with the name "Orion".

[Impaler]

If their is currently no "stensle" to define the Galaxyies shape then how are we able to generate the Galaxies shape in the current build of FreeOrion? Their must be some input involved. I seems that we can agree that we will need to use that stensle in some way inorder to cut out void crossing lanes.

Asuming the Stensle is some kind of Bit map that defiens at the very least "Fill this area with stars" and "Make this area the Void". Stars get generated randomly in the Fill zones and none are put in the Void. We can then do one of several things (these are taken from the thread none are my ideas).

1 - Put random "fake" or "void" stars in the void areas then triangulate and deleate all the fake stars and any lanes that were atached to them.

2 - Design each stensle with one or more lines on it and compare each starlane against thouse lines, if they cross deleate them.

3 - Compare the stensles "Fill" and "void" areas each time a pixel of Void borders a pixel of Fill add that pixel to a list esentialy creating an outline of each Fill area, use this outline the same as in method 2 to deleate any crossing StarLane.

4 - Simply store a list of every Void Pixel and compare each lane to see it it crosses any of that space and if so deleate it.

Conclusions: I favor options 3, it would require the least fuss when designing the stensle as the outlining is automatic durring the creation of the Galaxy map, also it delivers far fewer points to compare the starlanes against vs method 4 likly resulting in a faster build. Method 1 isn't completly fool proof (a random gap in the Fake stars alowed a lane through) and would result in much time being wasted in triangulation for stars that are doomed to be deleated anyways.

[Impaler]

Or Trantor!

I like the idea of a central "Nexus" System, do we have any method that can put the tree seed at the center of the galaxy? Perhaps if the stensle was marked with "seed spots" that the tree will know to grow from (also giving us the number of tree starts as well) The user could always chosse to over-ride though and place treeseeds randomly.

This also brings up an idea that I heard several of us discuss on other threads. Sectors and some method of creating them just after normal Galaxy generation, perhaps each sector could coincide with a tree Seed giving the sector a rather radial shape.

[Geoff the Medio]

If their is currently no "stensle" to define the Galaxyies shape then how are we able to generate the Galaxies shape in the current build of FreeOrion?

It's done algorithmically. For spirals, if the star's radial distance from the centre of the galaxy is less than some amount, say 0.25 galaxy radii (might be something different... I don't have the code handy to check), then the star's angular position is evenly distributed around the circle. If the radius is larger than 0.25, then the angle is something like:

(angle) = (coiling_factor) * (radial_distance) + (arm_number) * (2 * Pi) / (num_arms) + (random_factor)

So as the radius of a star goes further out, it's angle is rotated to give a spiral shape.

Their must be some input involved. I seems that we can agree that we will need to use that stensle in some way inorder to cut out void crossing lanes.

Not necessarily. The "barrier" lines could be generated algorithmically just as easily as the starlanes.

do we have any method that can put the tree seed at the center of the galaxy?

Yes, this would be fairly easy. Find average of star positions, find star that's closest from the average position.


Also, for a stensle system, keep in mind that not all galaxies have all their star-populated areas connected together like a spiral... for cluster galaxies, you'd want some starlanes to cross the void areas, as otherwise there'd be no way to go between clusters...


And rather than having to manually add exclusion lines or generate void-area boundaries or such things, it might be simpler to just put a distance limit on starlanes, so if you put your spiral arms or clusters or whatever far enough apart, then there won't be any starlanes connecting them.

[Impaler]

The downside to that would be that we cant have Galaxies with narrowly seperated arms and long starlanes also their will inevitably be lanes that cross at the uhumm "Galactic Arm Pit".

I know it may take some work (an trust me I do apreshiate what you guys are doing, I am just leaning the basics of C++ and know this isn't easy to do) but I feel that reading rules for starlane placement off a stensle will provide the most flexible solution. People will be able to literaly Paint their own Galaxy Maps in minutes and have fine control over the maps architecture by simply using differnt colors in their bit map.

If we have 3 types of zone "Stars+Lanes" "Lanes Only" "No Lanes or Stars" that would alow for all the possible map configurations.

[Geoff the Medio]

If we have 3 types of zone "Stars+Lanes" "Lanes Only" "No Lanes or Stars" that would alow for all the possible map configurations.

IMO marking areas for stars and putting barriers lines that lanes can't cross would be the simplest. Is there any problem with this system?

Edit: I suppose it would make the map a metafile, rather than just a bitmap, which might suck, as we'd need to have a specialized map editor, rather than being able to just use paint / photoshop / whatever.

Anything involving checking the ok/not ok status for starlanes of each pixel a lane crosses on the map might be a tad slow, however...

[Geoff the Medio]

Newest version. Uses custom graph visitor, rather than the ShortestPath function. Generates a 500 star galaxy in one to two seconds (rather than two to three minutes).

Edit: the url that was here is no longer valid

Added a helper function ConnectedWithin (which is the graph visitor) to the universe class, so the prototype for that is needed as well (in Universe.h).

[Impaler]

Perhaps if we coded a particular color to be used for the creation of boundry lines, then we could continue to use a simple Paint file to create Galaxy stensles. On another note we dont actualy need a complex grey scale to produce a variety of star densities. All we need is a High and a Low value and we just mix them in the bit map. It could go something like this.

Red - High Density stars, starlanes legal
Yellow - Low Density Stars, starlanes legal
Green - No stars, Starlanes Legal
Blue - No stars, Starlanes can not cross

The program scans the bitmap for these 4 colors only and drops stars at the desired density (say double our current rate in the High density and a quarter our current rate in low density). Blue and Green are different only to cut down by several orders of magnitude the # of pixels that must be checked against durring the lane killing process. The map maker would be instructed to make blue regions as small as possible to speed up starlane generation algorithims. Idealy they just Draw a thin blue line across the map in the desired spots. High and Low Density would be best when blended together with the spray paint function to alow a smoth seamless blending from one part of the Galaxy to the next. Super Low density would be achivable by spraying Yellow over Green.