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
noelte
Juggernaut
Posts: 872
Joined: Fri Dec 26, 2003 12:42 pm
Location: Germany, Berlin

#46 Post by noelte » Tue Aug 03, 2004 8:23 am

I agree with Impaler.

BTW: In the code snipset you can easyly get rid of that nasty duplicate helper by using break when setting duplicate to true and check for itCur2 == itEnd2 instead of !duplicate.
Press any key to continue or any other key to cancel.
Can COWs fly?

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

#47 Post by Geoff the Medio » Tue Aug 03, 2004 8:28 am

The posted picture is just the results of Delauney Triangulation. It is not a final result for starlanes in game.

As drek mentioned, and as has been discussed previously in this thread, various methods of removing starlanes from the result of Delauney Triangulation will be explored. drek is pretty keen on maze generation, and I think it's probably a good idea as well. Other limits on starlane length and angles between starlanes at a given star are also in need of testing.

The main point of doing the Delauney Triangulation is to get a fully connected web of starlanes, with connections to all nearby stars and no crossovers, from which lanes can be removed to make interesting geometry. It's also a good place to start from for adding lanes, like making connections to all next-nearest-neighbours to make some interesting crossing starlanes. Random generation works pretty well for galaxies with crossing lanes, but there are occasional flukes where groups of systems are not connected to the main web, which needs to be avoided.

This sort of thing is very easily set up to work with user options as well... So if you like having no starlanes crossing arm gaps, I imagine you'll be able to set things up galaxy creation so that's what you get. If someone else likes having crossing starlanes (me, The Silent One) s/he'll be able to, while drek will be able to play without them (single player, anyway).
noelte wrote:BTW: In the code snipset you can easyly get rid of that nasty duplicate helper by using break when setting duplicate to true and check for itCur2 == itEnd2 instead of !duplicate.
Yeah, I'm a bit rusty with the coding... It's been almost a year since I did anything in C++. I also originally coded the algorithm in VB for easy visualization of the results, and found the "exit while" type commands would always exit the least-nested level loop, rather than the most nested, making it useless for this particular algorithm.

What I'd really like though, is a way avoid doing that loop at all (at least in code I have to write). Is there not a prebuilt list-like container that can do what the excerpt does, as described in the post with the excerpt? Maybe not in the STL... but in boost perhaps?

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

#48 Post by Daveybaby » Tue Aug 03, 2004 9:09 am

Wow, looks good. Note that another advantage of this approach is that you can fairly easily specify the degree of pruning to be carried out using a slider, so players would be able to specify a desired level of interconnectivity for their maps. For example, it might be interesting to play a game without *any* pruning, which would provide gameplay closer to Moo1/Moo2 (i.e. without many easily defended chokepoints).

W.r.t. starlane crossover, one good reason to avoid it is this: if you have a fleet travelling along a starlane which crosses another, at the crossover point it is difficult to tell which starlane the fleet is on. A minor niggle, i know, but there you go. Plus IMO crossovers just look messy.

Another thing that may be worth checking out at this point : the 'inverse' of a delauney triangulation is a voronoi diagram, which is perfect for displaying empire borders (if thats something you want).
Last edited by Daveybaby on Tue Aug 03, 2004 9:18 am, edited 1 time in total.
The COW Project : You have a spy in your midst.

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

#49 Post by Geoff the Medio » Tue Aug 03, 2004 9:14 am

Daveybaby wrote:W.r.t. starlane crossover, one good reason to avoid it is this: if you have a fleet travelling along a starlane which crosses another, at the crossover point it is difficult to tell which starlane the fleet is on. Minor, i know, but there you go. Plus IMO it just looks messy.
The path of a fleet is animated with scrolling dotted lines... I don't think there'd be any confusion. The fleet's icon could also be oriented along the direction of the starlane.

You might find it messy if there are crossovers, but I find it boring if there aren't any...

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

#50 Post by Daveybaby » Tue Aug 03, 2004 9:19 am

Fair enough, i guess its just down to personal preference then. I guess there's always the option of adding wormholes (as in Moo3) after initial map generation is done.
The COW Project : You have a spy in your midst.

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

#51 Post by Daveybaby » Tue Aug 03, 2004 10:14 am

Geoff the Medio wrote: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...)
You may find it well worth your while implementing a general purpose fast sort class - this game is going to require a LOT of sorting for a lot of different purposes (UI lists, AI decision making) and its going to be very useful if everyone has access to something efficient and flexible.

A good analysis of different sorting algorithms is here.

What i did in COW was this : implement a fast sorting algorithm (i chose a heap sort for the best combination of high efficiency with low complexity, i.e. it was the most efficient algorithm that i could actually understand without making my brain bleed), but divorced the sort from the actual array itself. Thus what gets passed to the sorting algorithm is the following structure:

Code: Select all

struct sort_data_type {
    int index;
    int data;
};
The indexes are the indexes of the array being sorted. The data gives the values to sort by. The indexes arent even looked at by the sorting algorithm, they just get sorted along with the data values. If you are using a linked list or class or somesuch to store your data instead of a boring old array, then you can replace the integer indexes with pointers to individual items (i.e. use void* instead of int).

The sort function header looks like this:

Code: Select all

void sort(struct sort_data_type *sort_array, int array_size);
So to perform a sort you initialise the sort_array with your indices (or pointers) and values to sort by. Then call the sort function. On completion the numbers array will have been sorted in order of the data fields. ermmm..... example:

Code: Select all

struct horrendously_complex_data_type array[100];

struct sort_data_type sorted[100];

/* initialise sort array */
for (i=0; i<100; i++) {
    sorted[i].index = i;
    sorted[i].data = some value derived from array[i];
}

sort(sorted, 100);

/* now access array items in sorted order */
highest_sorted_element = array[sorted[0].index];
tenth_highest_element = array[sorted[10].index];
lowest_sorted_element = array[sorted[99].index];
Hope this makes some sense. I just got back off of holiday and my brain hasnt actually started working again yet.

I you want i have the C source code for this class - it will sort using integers, floats or strings in the data field.
The COW Project : You have a spy in your midst.

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

#52 Post by noelte » Tue Aug 03, 2004 10:42 am

@Daveybaby: There is really no need to implement a sort algo. qsort is available everywhere and it's quite fast (the fastest?). It's somewhat like reinventing the wheel.
Press any key to continue or any other key to cancel.
Can COWs fly?

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

#53 Post by Daveybaby » Tue Aug 03, 2004 11:00 am

True. I could have used qsort instead of the heap sort, but i'm just kind of stupid like that. :)

The main point, though is having a 'wrapper' around your sort algorithm, to decouple the array being sorted and the data values to sort by - which gives you a simple and effective generic interface which lets you sort *anything* without writing a whole slew of comparison functions to pass to qsort.
The COW Project : You have a spy in your midst.

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

#54 Post by noelte » Tue Aug 03, 2004 11:29 am

hmm, even so, you should use qsort. You can use qsort with your data stucture sort_data_type. You already have a whole slew of comparison functions!?
Press any key to continue or any other key to cancel.
Can COWs fly?

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

#55 Post by Impaler » Tue Aug 03, 2004 12:29 pm

More coments by myself:

I think it would be nice if we developed a Map making program outside of the game itself (much like StarCraft). We can incorporate as many starlane making/pruning options as we wish and alow the user to initiate them at their leashure from a menu. Their would also be mechanisms to manualy perform any task such as.

Create/destroy individual stars
Create/destroy stars enmass with the "stellar Shotgun/stellar vacume cleaner" tool
create/destroy individual starlanes
configure the planets inside a system
create/destroy worm holes
create/destroy random/race-specific starting locations
Create "star stensels"

(I am asuming that the Galaxies shapes are being created by deleating stars from a randomly generated field by use of a "deleate star zone" that cookie cuts the Galaxy out. This basicly will alow differnt kinds of stensels to be created by the user in a Paint like manor, these could then be used easily in future Galaxy generating events)

The advantage of such a Galaxy Maker is that we can provide a great variety of tecniques and options for experimentation on how to run the "official" map maker and still preserve all of the options for the end user to play with and in nessary manualy tweek their Galaxies to perfection.
Fear is the Mind Killer - Frank Herbert -Dune

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

#56 Post by noelte » Tue Aug 03, 2004 12:48 pm

Impaler wrote:(I am asuming that the Galaxies shapes are being created by deleating stars from a randomly generated field by use of a "deleate star zone" that cookie cuts the Galaxy out.
IMO, if we do it this way it would hurt. For instance if i want a two arm spiral galaxy with 200 stars. How many stars do i have to generate to get what i want after you apply your "deleate star zone"? IMO, it's a nice idea in theorie but not applicable in practice.
Press any key to continue or any other key to cancel.
Can COWs fly?

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

#57 Post by drek » Tue Aug 03, 2004 1:12 pm

Map making program outside of the game itself
Obviously not a priority now, but eventually it would be cool to have a scenario/save game editor.

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

#58 Post by Impaler » Tue Aug 03, 2004 1:35 pm

Good Point Noelte, I think I have a solution

Start with a random field of stars, use the stensle to cut away the undesired stars, then count the total # of remaining stars and either randomly deleate more stars if their are too many or randomly add new stars if their not enough. Each time you randomly add a star check to see if it fell in an exclusion zone and if so dont place it and try again untill the star count is correct.
Fear is the Mind Killer - Frank Herbert -Dune

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

#59 Post by noelte » Tue Aug 03, 2004 1:54 pm

Still not good ;-)

I would suggest using your stensle to generate those stars. Removing star isn't a good approach if you target an overall number of stars. But even if we do it this way, we will still get far to much stars which don't match the stencil.

It's much better to use an algorithm who generates stars which match the stencil in the first place. Maybe we will be able to do this by using phyton.
Press any key to continue or any other key to cancel.
Can COWs fly?

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

#60 Post by vishnou00 » Tue Aug 03, 2004 8:44 pm

I replied in a new thread.
viewtopic.php?t=819

Post Reply