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

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

Moderators: Committer, Committer

Message
Author
User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12485
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

#31 Post by Geoff the Medio » Fri Jul 23, 2004 11:54 pm

drek wrote:Wall adder tend to be slower and more complex, since you need to check for connectivety between all nodes after placing your wall.
You don't have to check after every removed starlane (removing a starlane is the same as adding a wall). You just do a graph traversal at the end, and undelete starlanes to reconnect isolated sub-webs to the main web. This is relatively simple, since all deleted starlanes were originally good and not conflicting with others, so you don't have to calculate whether they'd create secondary problems. (Your tree branching would need a similar system to add starlane in a later step, though it would be a bit easier to calculate since you'd already have connectivity, though you would probably need to add more connections.)

Deleting starlanes would happen one at at time, and would be either removal of an isolated starlane, or removal of a starlane that connect to a star where a starlane has already been removed. The ratio of how often these two are done would determine the ratio of dead ends to looped connections, I think.

There should be a minimum number of starlanes out of a system, at which more starlanes can't be removed (probably 1 starlane... or perhaps more).
I really want to avoid crisscrossing, aka weaving.
Any particular reason why?
With the Growing tree on that page, there's no need for dead end checking or an isolation removing step.
The basic geometry of growing tree is rather boring though... and is always basically the same. There's never any blockage of the direct path down the tree to the central / originating system. You can have a second step to add interconnections in the mid-branches (and leaves), but what makes things really interesting is when there's an interesting absence of starlanes, imho.

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

#32 Post by vishnou00 » Sat Jul 24, 2004 8:33 am

Is there really performance issues for galaxy generation? It is something that only happen at the beginning of a game. I think the only valid consideration to determine the algorithms are aesthetics (strategics) ones.

An idea to have only a low level of criss crossing:

1. do Delaunay Triangulation with all the stars
2. do Delaunay Triangulation with a subset of the stars
3. (optional) repeat step two with different subsets of stars
4. superpose (union) all the starlanes sets
5. prune until prettyness:
5a. with checks for small angles
5b. min/max/average number/lenght of starlanes
5c. average number of starlanes
5d. etc....
6. check for connectivity. To reconnect two parts, do step 2 with a set containing stars of disconnected regions.

I think that method could lead to better control over starlane generation, by controlling the pruning condition and subset creation.


I favor iterative generation over one-pass algorithms because I think the result will be more random/organic, it is simpler to generate different kind of galaxy by tweaking the generation process without touching the underlying algorithms and significant optimisation occur at specific places: the algo implementation (and there is surely a couple of CS master papers that only ramble about that).


I like the idea of using Voronoi Diagrams to do toponymy stuff (it was suggested as something related to VGA Planets galaxy map.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12485
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

#33 Post by Geoff the Medio » Sat Jul 24, 2004 9:57 am

vishnou00: Delaunay has no crossing already, so what's the advantage / purpose of your multistage suggestion?

User avatar
noelte
Juggernaut
Posts: 872
Joined: Fri Dec 26, 2003 12:42 pm
Location: Germany, Berlin

#34 Post by noelte » Sat Jul 24, 2004 12:55 pm

Geoff the Medio wrote:vishnou00: Delaunay has no crossing already, so what's the advantage / purpose of your multistage suggestion?
when he does the delaunay with a subset of stars in 2, he might generate starlanes which intersect with those who have at least one star which isn't in the subset.
Press any key to continue or any other key to cancel.
Can COWs fly?

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12485
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

#35 Post by Geoff the Medio » Sat Jul 24, 2004 6:38 pm

I thought that a major reason to use delauney was to avoid intersections...?

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

#36 Post by vishnou00 » Sun Jul 25, 2004 4:29 am

The advantage is to control intersections. One can decide if he want to have a lot, a little, or no intersections at all using the same (well researched) algorithm.

I think intersections, used sparringly, can be interesting aesthetically.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12485
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

#37 Post by Geoff the Medio » Sun Aug 01, 2004 10:54 am

Delauney Triangulation in FO:

Image

Edit: This is not intended to represent the final results of starlane generation for the game. Refinements will be done.
Last edited by Geoff the Medio on Tue Aug 03, 2004 8:35 am, edited 1 time in total.

User avatar
The Silent One
Graphics
Posts: 1018
Joined: Tue Jul 01, 2003 8:27 pm

#38 Post by The Silent One » Mon Aug 02, 2004 5:38 pm

Generally, this looks like a good approach;I currently see two disadvantages:

1. No crossing of starlanes at all, which limits the stategical options.
2. Each star is connected to every adjacent star. The result of this is a boring, regular look, and a limitation of strategical choices, as above.

When you change or add to the code, you might want to take that into account. (If you thought of this already, ignore me.)

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12485
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

#39 Post by Geoff the Medio » Mon Aug 02, 2004 8:29 pm

Not having crossing starlanes is apparently what some people very much want to have. I'd personally rather have crossing, as I think it does make things more interesting, but this can probably be made into an option fairly easily.

The triangulation shown isn't the final product. A maze-generation algorithm will be run in order to make... well... a maze, in which not all stars are connected to all adjacents. The shown triangulation is a good starnding point for maze generation because it is guaranteed to have all stars connected to all other stars.

drek
Designer Emeritus
Posts: 935
Joined: Thu Jun 26, 2003 8:07 am

#40 Post by drek » Tue Aug 03, 2004 12:40 am

hey,

neat. I was having a tough time working out all the syntax/logic errors from my own delauney triangulation code (hate hate hate c++), it'll feel good just to throw the mess I have into the recycle bin.

imho, already looks a lot better than the results of the current starlane generation.

It might be fun to play around with maze generation. Is there someplace that you can upload your code?

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12485
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

#41 Post by Geoff the Medio » Tue Aug 03, 2004 2:27 am

There is no maze generation yet... I've been working on other stuff since getting the triangulation working.

The modified files are [EDIT] no longer available at the url that was here...

There is a new namespace in both files called "Delauney" which has all the new stuff, and I rewrote Universe::GenerateStarlanes. If anything else has changed in Universe.* since I updated from CVS, it shouldn't matter.

If someone knows a better way to do the list of integers sorted by a value other than that of the integers, I'd like to hear about it (if it doesn't involve writing a custom list class, which I figured I probly shouldn't be doing...)
Last edited by Geoff the Medio on Sun Dec 19, 2004 12:49 pm, edited 1 time in total.

drek
Designer Emeritus
Posts: 935
Joined: Thu Jun 26, 2003 8:07 am

#42 Post by drek » Tue Aug 03, 2004 2:41 am

thanks. looks clean; easy to modify.

leiavoia
Space Kraken
Posts: 167
Joined: Sun Jul 20, 2003 6:22 pm

#43 Post by leiavoia » Tue Aug 03, 2004 4:49 am

If someone knows a better way to do the list of integers sorted by a value other than that of the integers, I'd like to hear about it (if it doesn't involve writing a custom list class, which I figured I probly shouldn't be doing...)
Could you restate that a different way. i'd like to help on that one but am not sure what you're asking for.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12485
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

#44 Post by Geoff the Medio » Tue Aug 03, 2004 5:07 am

In this code... (excuse the linewrap breaking in the forum)

Code: Select all

						// iterate through list, finding insert spot and verifying uniqueness (or add if list is empty)
						itCur2 = pointNumList.begin();
						itEnd2 = pointNumList.end();
						if (itCur2 == itEnd2) {
							// list is empty
							pointNumList.push_back(Delauney::SortValInt(num, mag));
						}
						else {
							duplicate = false;
							while ((itCur2 != itEnd2) && (!duplicate)) {
								if ((*itCur2).num == num) {
									duplicate = true;
								}
								else {
									if ((*itCur2).sortVal > mag) {
										pointNumList.insert(itCur2, Delauney::SortValInt(num, mag));
										duplicate = true;
									}
								}								
								itCur2++;
							}
							if (!duplicate) {
								// point wasn't added, so should go at end
								pointNumList.push_back(Delauney::SortValInt(num, mag));
							}
						}
I needed a list of integers "num" that would not have duplicate elements (same "num"), and which is sorted by a separate sorting value "mag".

(You'll probly need to check out the linked files above for context)

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

#45 Post by Impaler » Tue Aug 03, 2004 7:24 am

Just wanted to add a small coment here.

I noticed on one of your posted 3 arm Galaxies that their are often starlanes crossing across the gap from one arm to another. I dont know how others feel about this but to me thats undesirable, it visualy takes away from the spiral shape of the galaxy and removes the bottle neck that the arm represents. If other agree with me on this then I would propose that we include a step that simply deleates all starlanes that cross the star exclusion zones that form the shape of the Galaxy.
Fear is the Mind Killer - Frank Herbert -Dune

Post Reply