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

[Daveybaby]

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

... which is incredibly annoying, but i guess i will continue the discussion there also .

[Geoff the Medio]

Delauney triangulated, then selectively culled with pseudo-maze generation algorithm, starlanes in FO:


Again, this is not meant to represent the final product.

[noelte]

some stars seems to be unconnected or are the starlane simply not visible to your empire?

[Geoff the Medio]

not visible to empire. look closely, and you'll note that the two unconnected stars are near an unexplored system.

btw, this is why I put in that feature request for a debug/cheat menu to fully reveal the map to the player / tester.

Also, here's another screencap that was generated with my next version of the algorithm, which puts a limit on how far apart "adjacent" systems can be in starlane jumps. "adjacent" means systems that were directly connected after delauney triangulation. This means there'll be fewer long loops like in the earlier image, that appeared to enclose some unconnected systems.


edit: url for code no longer valid, so removed

Replace that function in Universe.cpp after putting in Delauny stuff earlier in the thread into Universe.*. Mostly this is in case drek wants it.

Todo: doing something about extra long starlanes across galaxy void spaces, perhaps preferentially deleting longer starlanes in general, limiting too-close angles between starlanes going from a given star, putting some degree of customizability into algorithm, optional cris-crossing starlanes (by adding links to next neighbours before culling)... Any other suggestions / requests?

[Daveybaby]

Looks good.

I would second the request for a debugging mode - that sort of thing is going to become more and more invaluable as development progresses.

Another thing that i have found *incredibly* useful when developing COW is to keep AI development at an equivalent level to the currently implemented gameplay features. Note that i'm NOT talking about anything other than a borderline retarded automated AI here, its just something to exercise the various game elements, not provide a challenge to a player.

Combine this with an auto-run capability (such as moo3 provided in one of the patches) and you can very quickly test lots of things like : victory conditions, simultaneous attempts at colonisation of a planet by multiple empires, overpopulation effects etc etc etc which would take AGES to test if driven by a human player.

For example, the COW AI simply builds colony ships and battleships in a mixture determined by the % of uncolonised planets in the galaxy, sends the colony ships out to empty planets, and splits the battleships between defending its own planets and attacking enemy planets. Not exactly rocket science, but it allows the game (though currently limited in features) to play itself through to completion in a matter of seconds. So, the first thing i do after implementing a new feature is to set off an auto-run game to see if i have broken anything. You have no idea how many issues this has brought to light.

[Impaler]

Nice work Geoff that map looks like it will be very interesting to play on.

As for removing StarLanes that cross large voids I have some possible ideas

1 Find the Center point of the lane and if its too far away from any star then deleate the lane.

2 If were using a bit map stensle (like was discussed on an earlier thread) then check one or more points along the lane (perhaps in short increments of length), if a point falls in a Star Exclusion zones deleate the whole lane.

This directly attacks the undesirable quality of the StarLane without unfairly penalizing long lanes that are in Star Rich areas of the map.

In either case you would want to run this check first before pruning the Triangulation so as to reduce the chances that the later pruning will create islands with these long undesiragle lanes being the only connections, thus creating a damnd if you do damnd if you dont situation for the function that tries to clear these long void crossing lanes.

[Geoff the Medio]

The way the Delauney Triangulation works is to create an inital "covering triangle" that encloses all the vetices to be triangulated. It then chops up that triangle into a bunch of smaller ones. When done chopping, any triangle that includes one of the three vertices of the covering triangle is removed, so that there aren't any starlanes connecting to these "artificial" stars represented by the covering triangle's vertices.

Something similar could be done with exclusion regions, as I think Davebaby has done with the territory regions around stars in COW. You'd mark a few "exclusion points" on the map that will be used when calculating the triangulation. After triangulation is done, any triangles that have one of the exclusion points as one of its vertices is removed. Because the exclusion points force all nearby points to share triangles with them, there'd be no triangles between stars on either side of the exclusion points. Thus when converted to starlanes after removing the "bad" triangles, there'd be no starlanes crossing the area near the exclusion points. You'd have to make the exclusion points in a fairly closely spaced line... and you'd have to be sure that you don't make it impossible for any groups of stars to make connections to the main web.

I don't think this would work very well with star density maps though... there's no obviously good way to put in exclusion points to automatically generate variable numbers of connections in a given area... it's best used for an all-or-nothing situation where you just want to manually draw a line on the map, through which no starlanes will pass.

Then again, in that case, you could just check for intersection of the line with any starlanes, and remove the offending ones...

Anyway, something to think about...

[drek]

Great work Geoff. My new hero, etc.

The untangled lanes really do look a whole lot better, at least to me.

The starlane culling algo woudl seem slow for super large galaxies; not really a problem since super large galaxies aren't all that playable to begin with.

If I ever get off my ass and start fiddling with this, I think I'll try a method that doesn't require the pathchecking to ensure connectivity. Should be possible to produce the same results, much much faster. (though, again, it's already fast enough for a "normal" sized galaxy.)

[Geoff the Medio]

The algorithm could probably be sped up significantly if it's deemed necessary to do so. Currently I call ShortestPath every time I add or remove a starlane, which could be easily replaced with a breadth first search that terminates after the maximum distance away is searched. Also every time I add or remove a starlane I have to call InitializeSystemGraph before calling ShortestPath. I'm not sure what InitializeSystemGraph does exactly, or how long it takes, but rewriting AddStarlane, RemoveStarlane and/or ShortestPath to be compatible with dynamic, rather than static, starlanes would help. I'm guessing tzlaine would need to do this, though...

Also, I'm not using ShortestPath just to verify connectivity... It's used in the second stage to determine if "adjacent" systems are too far apart in starlane jumps, which really does need some sort of shortest path between the stars (though I should be checking the distance, rather than the length of the returned list, which I'll fix). At that stage of the algorithm, all stars are already guaranteed to be interconnected.

Also more, in the culling stage, a actually path isn't needed for connectivity checking. That use of ShortestPath could easily be replaced with a "Connected" function, that just returns true if the lanes are connected, not bothering to find the shortest possible path. I've only used ShortestPath now because noelte said I'd need to ask tzlaine to write "Connected" for me, and I didn't want to do that until I was sure I'd need it.

[drek]

Actually,

I was thinking off adding "Potenial Starlanes" to the system class, counter of how many actual starlanes are in each system (counter might already be there), and a method to flip a potential starlane to a real starlane. A method to test starlane length could also be implemented, to remove the need for the shortest path pathfinding function.

The triangulation thingy would create the potential starlanes. The maze generation algo would "tunnel" to each system (ie, cell).

With these changes it's possible to use one the faster maze generation algos; one that doesn't need to verify at each step of the process. You only need to verify at each step of a wall-building algo, which is what you have. A tunnneling maze generation algo can create total connectivity without requiring verification.

from the maze generation webpage:

Growing tree algorithm: This is a general algorithm, capable of creating Mazes of different textures. It requires storage up to the size of the Maze. Each time you carve a cell, add that cell to a list. Proceed by picking a cell from the list, and carving into an unmade cell next to it. If there are no unmade cells next to the current cell, remove the current cell from the list. The Maze is done when the list becomes empty. The interesting part that allows many possible textures is how you pick a cell from the list. For example, if you always pick the most recent cell added to it, this algorithm turns into the recursive backtracker. If you always pick cells at random, this will behave similarly but not exactly to Prim's algorithm. If you always pick the oldest cells added to the list, this will create Mazes with about as low a "river" factor as possible, even lower than Prim's algorithm. If you usually pick the most recent cell, but occasionally pick a random cell, the Maze will have a high "river" factor but a short direct solution. If you randomly pick among the most recent cells, the Maze will have a low "river" factor but a long windy solution.

Plus, we'd be able to include some options at galaxy setup:
a: total connectivity (no culling, possible with your algo)
b: "low river"
c: "high river"
d: etc.

Again, great job with what you've done. I'm just nitpicking here.

[Geoff the Medio]

I've been making a point of not modifying anything other than the actual functions I'm rewriting. And really, it's not necessary to do so... All the relevant data can be stored locally in GenerateStarlanes.

A method to test starlane length could also be implemented, to remove the need for the shortest path pathfinding function.

You can already get the X and Y positions of the stars on either end, and calculate it yourself... and I don't really see how finding the length of the lanes out of a system replaces finding the shortest path across the graph for any purpose...

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.

[Impaler]

Geoff: Yes that sounds like a good way of going about it, these Exclusion points are basicaly fake stars that all "pop" after the Triangulation but before the Maze Generation and when they pop they take out all the Lanes that connected to them.

The only downside I see is that it will be invonvenient to have to draw in these points (or make a line of them) for each Galaxy stensle. Perhaps if we simply fill the "void" zones with the same random stars that were already making and designate them all as "fake" when they are in the Void zones. We can still use a StarDensity Bit Map in the Initial Random Generation too but instead of putting Nothing in the Void zones we fill the void with a sufficiently thick spray of fake stars with all get deleated later and hense kill any lanes going through that zone. The secuence without Star Density Bit map would be.

1 Gererate random starfield across whole map
2 Aplly Galaxy stensle, any star in a void zone becomes "fake"
3 Triangulate starlanes between all stars both fake and real
4 Cull all fake stars and the starlanes that connect to them
5 Generate Maze amung the remaining stars and Lanes

And with

1 Generate random starfield across whole map based on Bit map density, no real stars are put in the Void
2 Second pass on Stensle Puting only "fake" stars in the Void zones at some predetermined density, no fake stars are put in the areas filled by step 1
3 Triangulate starlanes between all stars both fake and real
4 Cull all fake stars and the starlanes that connect to them
5 Generate Maze amung the remaining stars and Lanes


P.S. 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. Only if the new system is able to fully replicate and expand upon the older stuff should we consider droping any Algorithms. I want to see some method for the User to Easily sellect the Maze Generation Algorith and feed it various inputs as drek sugjests, and as always we want to make it easy for people to insert New maze algoriths and run them in the same way.

[Geoff the Medio]

AFAICT, drek's method essentially just replaces one step of mine with a more efficient sub-algorithm. The stage in question generates a fully-connected tree, which I've done by culling starlanes, whereas drek is suggesting adding starlanes. There are minor differences in the results (I can get loops at this stage, he can't), but they're essentially the same, except that drek's should be faster.

Then again, maybe I'm wrong, and drek wan't to use just the tree-maze generation as the final product... I don't think that'd be a very good starlanes maze though... but it could be improved by adding severeal simultaneously growing trees starting at different locations.

If we want more other methods to generate starlanes, I'd suggest using something like what I used to generate this (from a few pages ago in the thread):

If that algorithm was paired with a pre-stage that added a fully connected tree, then it'd be guaranteed to be fully connected as well.

Also, the algorithm I'm uses does have a few magic numbers that can be replaced with user specified parameters (or parameters derived form user choices)... in particular, the maximum distance allowed between "adjacent" systems that aren't connected with a starlane before I say they're too far apart and need to be directly connected. This would have a significant impact on how "well connected" the final map is... and likely how many starlanes there are on an average star, though I haven't experimented much.

FYI, the only reason I'm not already using drek's suggestion in my implimentation was that I approached this particular soluation from a roundabout way... I originally was doing the culling / adding back in a single loop, but decided the results would be better with two separate loops, which in retrospect is essentially the same as making a fully-connected tree then adding some extras. The actual criteria I used to pick where to add more lanes than those of the initial tree is of my own creation (distance to adjacent systems) though...


That said, it'd probly be good to have a starlanes generation algorithm that doesn't start with any sort of fully connected tree...

[Impaler]

I like the different style of Lane archetecture created by your program, particularly the ability to create crossing lanes. Somepeople have expressed a distaste for these crossing lanes, I personaly think they look ok and could be tacticaly interesting to play on. By providing Triangulation as a method for lane creation we give the player the option of having no crossing lanes.

Perhaps their is a way to feed multiple starlane lists into a variety of Maze Generators. For Example (note everything in Parenthises is a User selectable Variable)

Input:
(80%) Delauney Triangulation
(50) Random Lanes of maximum length (30)
(10) Random Lanes of maximum length (10)
(3) Tree Fractals of Branchyness (12) and maximum length (40)

Maze Algorith:
(AND): Fractal Maze with Fractalness of (30%)
(OR): River Maze with Riverness of (12)
(NOR): Random Maze using (40%) of Lanes
D: None

The Inputs each create a seperate list of Starlanes based on its unique method and input (80% Triangulation would mean randomly use only 80% of the Triangulation list). All these list are merged into one big List of all possible leagal Starlanes (then check for connectivity of all stars if their are Island give an error message or repeat). Then pass the List on to the Maze Algorith witch just culls down the list by its method and input. Selecting None preserves the whole input list intact and makes it the map. If you run more then one Maze algorithm then the AND/OR/NOR input is used to deside whats include. AND keeps a lane if any other Algorithm also keept the Lane, OR keeps a lane regardless of weather other algorithms keept it and NOR overrides AND and OR to deleate all lanes that this Algorithm rejected (usefull for Culling Algorithms that do things such as remove Crossing lanes).

[Daveybaby]

Something similar could be done with exclusion regions, as I think Davebaby has done with the territory regions around stars in COW.
...
I don't think this would work very well with star density maps though... there's no obviously good way to put in exclusion points to automatically generate variable numbers of connections in a given area...

Yeah, thats what i do in COW - works pretty well (although i dont have starlanes to worry about). Unfortunately though, yes, a stellar density map totally screws all of that up.

HOWEVER What you CAN do is automatically create exclusion zones by placing a 'fake star' on every pixel of zero density which borders a pixel of non-zero density.

However, i feel it worth repeating that there is NO real benefit to having density maps in a starlane based system. COW uses the Moo1/2 style of travel and so density maps can be very useful in creating regions which are impossible to cross until sufficient engine tech is researched - but in a starlane approach, all you achieve is that you make stars take longer to get to in certain areas of the map. Not quite as strategically interesting - and probably not worth the effort.