Page 3 of 9
Posted: Fri Jul 23, 2004 11:54 pm
by Geoff the Medio
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.
Posted: Sat Jul 24, 2004 8:33 am
by vishnou00
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.
Posted: Sat Jul 24, 2004 9:57 am
by Geoff the Medio
vishnou00: Delaunay has no crossing already, so what's the advantage / purpose of your multistage suggestion?
Posted: Sat Jul 24, 2004 12:55 pm
by noelte
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.
Posted: Sat Jul 24, 2004 6:38 pm
by Geoff the Medio
I thought that a major reason to use delauney was to avoid intersections...?
Posted: Sun Jul 25, 2004 4:29 am
by vishnou00
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.
Posted: Sun Aug 01, 2004 10:54 am
by Geoff the Medio
Delauney Triangulation in FO:
Edit: This is not intended to represent the final results of starlane generation for the game. Refinements will be done.
Posted: Mon Aug 02, 2004 5:38 pm
by The Silent One
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.)
Posted: Mon Aug 02, 2004 8:29 pm
by Geoff the Medio
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.
Posted: Tue Aug 03, 2004 12:40 am
by drek
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?
Posted: Tue Aug 03, 2004 2:27 am
by Geoff the Medio
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...)
Posted: Tue Aug 03, 2004 2:41 am
by drek
thanks. looks clean; easy to modify.
Posted: Tue Aug 03, 2004 4:49 am
by leiavoia
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.
Posted: Tue Aug 03, 2004 5:07 am
by Geoff the Medio
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)
Posted: Tue Aug 03, 2004 7:24 am
by Impaler
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.
