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

[Geoff the Medio]

I've been working on a new starlanes generation algorithm to resolve some issues with the current one. One such issue is stars that are really near a starlane that does not connect to them, such as the orange ones in the image above. This is a problem because in some cases, the star looks like it is on the lane, when it is actually not.

There are two seemingly simple ways to deal with this, afaik. 1) Remove the offending star or starlane, and 2) connect starlane to the star(s) that are near it, by splitting the starlane into two or more smaller starlanes with the offending star(s) in the middle.

(1) is obviously simpler to impliment, but has the obvious drawback that you need to remove stars or starlanes that you'd previously generated. This isn't as bad as it might seem though, as the number of offending stars / lanes is generally quite low.

(2) can be quite complicated to impliment. After finding the offending starlanes (which (1) also has to do), you then have to order them along the starlane, and create a bunch of new starlanes and fix up the endpoint(s) of the old one.

It's also possible that moving or making new starlanes that don't quite align with the old one might make other stars now too close to a starlane, requiring furthur checks and modification steps. This probably isn't that big a deal though, as stars need to be pretty close to a lane to be too close, so the amount of shifting is unlikely to make other stars too close.

Additionally, unlike the image above, a star that's too close to a lane might already have a whole bunch of starlanes connected two it. This creates two problems. First, the star might end up with too many starlanes connected to it after being "spliced" into the nearby starlane. What qualifies as "too many starlanes" might vary, but if you've had a first step that sets how many starlanes you want everywhere, and then go adding more for some stars, things might get messed up. Second, the new starlane connection might be too close in angle to one of the one that were already on the offending star. I've made an effort to prevent too-close angular starlanes from a star, as it makes things hard to see, and not as nice looking when you do. (The angle issue also applies to the original end stars of the starlane, if the connections are moved.)

Moving the offending star away from the starlane isn't a good option, generally, but could be done, I suppose. (Note that this isn't the same as removing the offending star completely as in (1) above)

Anyway, my question is: what are people's thoughts on how best to deal with this sort of situation?

[vishnou00]

I think the best way is the simplest one (1).

That way, galaxy generation would be, but I see two possibility:

1. place systems
2. generate starlanes
3. check and remove effending starlanes
4. put back enough starlanes to satisfy generation conditions (eg at least one per system, max x per system)
5. goto 3. Give up after y number of try (maybe generation is asking an impossible situation)

OR

1. place systems
2. generate starlanes
3. check and remove effending systems
4a. put back enough systems to satisfy generation conditions (eg at least w systems)
4b. put back enough starlanes to satisfy generation conditions (eg at least one per system, max x per system)
5. goto 3. Give up after y number of try (maybe generation is asking an impossible situation)


The second one may be more complicated if the system placement algorithm doesn't support adding systems without regenerating completely.

EDIT: The main reason why I think this is the best way to handle the problem is that it doesn't involve messing with system placement algorithm. It is not because I think moving stars a bit is too difficult.

[leiavoia]

I would actually move the star itself. It seems hokey, but really it isn't going to be noticable if you only knudge it over by one parsec. You also avoid all the recalculation voodoo. The only problem is if you move the star and it is now in some OTHER lane's path.

so

Code: Select all

A--------B--------C

becomes

Code: Select all

A-----------------C
          B

Not too difficult.

Keep track of each star though. Record if the star has been "replaced" in the algorithm If you go through 2 galactic check passes and a star is "in the way" after 2 passes, rip the star out and put it down some other place.


Another Method:

Try the "pay as you go" method: When placing starlanes, check to see if each lane intersects an uninvolved star. If it does, don't connect the lane and find some other star to connect to. Now that i think about it, this is probably the best way to do it, although more computationally expensive. But what's a split second worth these days?

[drek]

It would also be nice to avoid crisscrossing starlanes.

I had code that checked against stars and other starlanes for intersection before placing a starlane, but the monty carlo method of placing lanes ended up producing strange results. (super long starlanes, etc).

It might be better to start from scratch, and use some sort of maze generation algo for starlane creation. I had one in my head a couple monthes ago, though I can't seem to remember the details now.

edit, just came to me. Might be a dumb idea:

It might be advantageous to generate the starlanes and planets together at the same time. Like a pool of water on high ground, each star would "pour" out a random number of starlanes, each forming a new star. A check would be made to ensure that new stars/starlanes don't touch existing stars/starlanes or go outside of the galaxy shape's boundries. The galaxy shape would hopefully "fill up"--though there might have to be some "motivation" type rules to ensure that all the corners are filled in spiral galaxies (like a bounce rule).

After all the stars have been generated, the current starlane algo runs to create random starlane connections. A check is made to ensure that no randomly generated lane crosses existing lanes or within a certain radius of existing stars (exluding the target and source stars of the lane). Unlike my current modification, the starlane generator could give up much sooner because each system would already be gaurnteed to be connected to the greater starlane network. (improving speed of generation and avoiding super-long starlane)

[Geoff the Medio]

I would actually move the star itself. It seems hokey, but really it isn't going to be noticable if you only knudge it over by one parsec. You also avoid all the recalculation voodoo. The only problem is if you move the star and it is now in some OTHER lane's path.

Moving a star is fairly simple... IF the star has no starlanes attached to it. If there ARE starlanes, then several problems arise.

1) The simplest method to move a star is to give it a random new location, check if that location violates any placement rules (proximity to other things) use it if it doesn't, or find another if it does. If there are starlanes, you can't do this, as the star is now half way across the galaxy and the starlanes are all screwed up.

2) The next simplest method, I think, is to find the vector from the star to the nearest point on the starlane, and move the star along that vector so it's just far enough away. This is problematic for several reasons. Minor issues arise regarding changing the angles of the starlanes connected to the star (at the star and the stars the lanes connect to), as well as the minimum spacing between stars. Major issues arise if an offending star is too close to two different starlanes, for which the direction to move the star to get it away from one starlane puts it closer to the other... or even worse, puts it just past the other, so it ends up being move a rather large distance, ending up somewhat like (1).

Another Method:

Try the "pay as you go" method: When placing starlanes, check to see if each lane intersects an uninvolved star. If it does, don't connect the lane and find some other star to connect to. Now that i think about it, this is probably the best way to do it, although more computationally expensive. But what's a split second worth these days?

I guess it would add another order of (numStars) dependence to the algorithm execution time... this shouldn't be a problem though. I like this method better than anything involving moving stars around, as that leads to too many sub-problems and such, as described above.

[Geoff the Medio]

It would also be nice to avoid crisscrossing starlanes.

It's not really that bad, if kept to a minimum...

If they really bother people, adding a no-crossing condition can be done, but that doesn't look too offensive, does it?

(yes I know there are stars with no starlanes)

I had code that checked against planets and other starlanes for intersection before placing a starlane, but the monty carlo method of placing lanes ended up producing strange results. (super long starlanes, etc).

It might be better to start from scratch, and use some sort of maze generation algo for starlane creation. I had one in my head a couple monthes ago, though I can't seem to remember the details now.

What I do is:
1) place stars, keeping them a minimum distance apart
2) cycle through stars, generating a maximum # / starlanes per star for each
3) cycle through stars, compile a list of nearest 10 stars to each
4) cycle through list of nearest stars indices, and in that loop:
4a) cycle through planets, making connection to one star on list of nearby stars for each star per outer loop iteration, if doing so doesn't duplicate a lane already connected to the star, or put a star over its starlanes limit or make a starlane too close in angle to another

There are still issues if every star has to be connected, and I'd have to do graph traversal and make connecting lanes to fix them... though I'm still hoping offroad travel will be allowed, making doing so unnecessary... though the starlanes review makes it sound like that should be an option, so maybe it'll have to be done anyway.

[Geoff the Medio]

each star would "pour" out a random number of starlanes, each forming a new star. A check would be made to ensure that new stars/starlanes don't touch existing stars/starlanes or go outside of the galaxy shape's boundries. The galaxy shape would hopefully "fill up"--though there might have to be some "motivation" type rules to ensure that all the corners are filled in spiral galaxies (like a bounce rule).

I like the basic idea, though have a few worries.

First, you'd end up with a branching tree from the first starlane, which might make the galaxy starlane geometry rather boring / repetative... though I'd have to try it to see.

Second, the galaxy shaping would be rather difficult to get working for anything with complicated internal structure, like a spiral, using this method, I think. It might be possible to connect each star to the nearest already connected star as soon as its generated, rather than have a star spawn several other stars (which would have an implied position restriction which is what might be problematic with galaxy shape). This would lead to certain "hub" stars accidentally getting lots of connections though, meaning you couldn't have very hard limits without some fiddling around with what to do when they're gone over...

[Geoff the Medio]

1. place systems
2. generate starlanes
3. check and remove effending systems
4a. put back enough systems to satisfy generation conditions (eg at least w systems)
4b. put back enough starlanes to satisfy generation conditions (eg at least one per system, max x per system)
5. goto 3. Give up after y number of try (maybe generation is asking an impossible situation)

I'm wary of anything that involves too much looping back and iteration. Yes, it does work, generally, but I don't like it, and it feels like using it is a kludge, when better systems could be found.

The second one may be more complicated if the system placement algorithm doesn't support adding systems without regenerating completely.

I don't know why any system placement algorithm would be broken by some other algorithm adding systems later...

[drek]

First, you'd end up with a branching tree from the first starlane, which might make the galaxy starlane geometry rather boring / repetative... though I'd have to try it to see.

A branching tree from the first star, which should be near the center of the galaxy. Doesn't sound all that bad to me.

Second, the galaxy shaping would be rather difficult to get working for anything with complicated internal structure, like a spiral, using this method, I think.

I was thinking of something like a particle system.

If the galaxy shape is defined by splines (or just a lot of little lines) then it would be possible to calculate a "bounce". If a generated starlane would "hit" the wall of the galaxy, it's end point "bounces away" based on the normal of the point of impact on the spline. Haven't tested it, but I'm imagining star positions would naturally tend to bounce into the crevices and corners of the galaxy shape.

(alternately, there could be more than one "seed" star, strategically located through out the galaxy's shape, with a path traversal algorythm ensuring that all the seeds are connected to each other.)

1) place stars, keeping them a minimum distance apart
2) cycle through stars, generating a maximum # / starlanes per star for each
3) cycle through stars, compile a list of nearest 10 stars to each
4) cycle through list of nearest stars indices, and in that loop:
4a) cycle through planets, making connection to one star on list of nearby stars for each star per outer loop iteration, if doing so doesn't duplicate a lane already connected to the star, or put a star over its starlanes limit or make a starlane too close in angle to another

Seems almost identical to the method FO already uses, save the angle check.

[Geoff the Medio]

A branching tree from the first star, which should be near the center of the galaxy. Doesn't sound all that bad to me.

There's nothing inheirently bad about the branching tree, but I'm just worried that the geometry it gives rise to might be rather boring, even after adding the random interconnections. There might be ways to work around this though... like making some stars have no branches during the initial sprouting phase, but have more branches created during the later filling-in-connections phase... Could also have exclusion zones as part of the galaxy "shape" where stars can't be formed, but which long starlanes might cross in the filling-in phase. I think davebaby has something like this regarding the regions around stars in his program.

If a generated starlane would "hit" the wall of the galaxy, it's end point "bounces away" based on the normal of the point of impact on the spline. Haven't tested it, but I'm imagining star positions would naturally tend to bounce into the crevices and corners of the galaxy shape.

That seems reasonable... It might be nice to be able to define an arbitrary galaxy shape and have the program fill it out for you. Might be a pain to code though...

1) place stars, keeping them a minimum distance apart
2) cycle through stars, generating a maximum # / starlanes per star for each
3) cycle through stars, compile a list of nearest 10 stars to each
4) cycle through list of nearest stars indices, and in that loop:
4a) cycle through planets, making connection to one star on list of nearby stars for each star per outer loop iteration, if doing so doesn't duplicate a lane already connected to the star, or put a star over its starlanes limit or make a starlane too close in angle to another

Seems almost identical to the method FO already uses, save the angle check.

I didn't mention, but I sort the list of nearby stars (which I don't think FO does now.. could be wrong though). I also compile the list by simply looping through all stars and computing distance (as opposed to the current grid box system). Again, I might be wrong, but it looks like FO currently loops through systems and adds starlanes, to fill the slots for each star before adding any (specifically) to other stars. Conversely, I loop through and give each star its first starlane, then loop through and give each a second... etc. Everyone gets one before anyone gets two. I'm also much more willing to not give a system up to its "max" starlanes, whereas FO currently seems to scan further and further away in search of a connection. I stop trying after using up my sorted list of 10 possible connections.

[noelte]

I hadn't much time to look into it, but i think we shouldn't go for an perfect starlane generation algorithm. If i remember correctly it's a NP problem. I would rather prefere an algorithm which reduces the issues of the current. For instance local star clusters usally have many intersecting starlanes which is imo unwanted.

Algo.
First i wouldn't try to move stars when they intersect with a starlane, reasons are already stated. Removing stars is also not an option.

So to fix the known issues, i would start generating starlanes which connects nearby systems. This shouldn't be a to big deal. Those starlanes shouldn't intersect with each other or a system which isn't connected by that starlane. At a second step i would add some starlanes which connects systems with a great distance from each other. imo, it would be quite ok if those starlanes intersect with other starlane or systems.

[Daveybaby]

Maybe you just need to look at starlane generation from another angle, i.e. instead of adding starlanes, then checking if you have any bad ones, first start off with a highly connected web, then prune.


Have a play with this little applet:
http://www.cs.cornell.edu/Info/People/c ... aunay.html
Click to create a set of points, then click on 'delauney triangulation' to see the interconnects.

What it gives you is each node connected to ALL of its close neigbours, with no crossovers. If you start with this, you can then prune away starlanes until you have the density you want. Start by pruning any starlanes over a certain length, then just prune the remainder at random. A check can be carried out before each prune to ensure that no parts of the map will be completely cut off.

Note that it is still possible to have a similar problem to the one above, e.g. if you create 3 points (A, B, C) on a line you get connections from A-B, B-C and C-A... where C-A passes over B. You can get around this by having an extra, initial pruning stage :

(1) For each star, check the angles of all starlanes connected to it.
(2) If 2 starlanes are too close together (i.e. the angles between them is too small, say, less than 10 degrees) then prune one of them.
(3) Always prune the longer of the two starlanes.

[muxec]

What if we just move offending systems a little or if we draw starlanes curved instead of straight?

[drek]

Daveybaby:

Perfect. I think that's exactly what we need.

[Geoff the Medio]

Could drek or davebaby or someone else outline the advantages of davebaby's system over random local connections and then a post-processing step to ensure everything is connected? I can't see any (advantages), other than avoiding crossing (see below) which can be done for random connections as well. davebaby's method seems like it's effectively doing the same thing, except by removing lanes instead of adding them... which doesn't seem like a significant difference, really... Both require connectivity checks when adding/removing a lane.

There are small disadvantages to davebaby's method, such as that removing lanes would have a denser graph to traverse when verifying connectivity (edit: and you'd need to do the traverse for every starlane pruned, not just at the end in a post-step), that you're stuck with however many closest neighbour connections you end up with for a particular star, and no more (unless you add another step that adds more), and if you want to reduce a star's # of lanes, you can't do so without reducing another star's as well, and that star must be from a very limited set (whereas adding allows you to search further affar, which is a bit more useful... (a bit)).

Also, drek, noelte:

Why are crossing lanes so bad? Look at my galaxy image above. It has some crossing, but it's not like FO now where everything is all over the place and confusing and distance has very limited bearing on what connections get made.

viewtopic.php?p=13230#13230