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

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

Moderator: Committer

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

#16 Post by noelte »

Geoff the Medio wrote: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.
I didn't target your galaxy image, it's nice. I was talking about the current fo starlanes. I have also nothing against crossing starlanes in general, they should only be limited to avoid confusion.
Press any key to continue or any other key to cancel.
Can COWs fly?

User avatar
Zanzibar
Psionic Snowflake
Posts: 470
Joined: Thu Jun 26, 2003 10:35 pm
Location: Earth

#17 Post by Zanzibar »

Here's my whole $.02 worth on this topic. I believe that we should have a few stars with NO lanes connecting to them, kinda like in the most recent image from Geoff. The stars with no lanes should have some sort of super special or some other thing that makes them actually worth wasting the extra time off-roading to get to them. Maybe not something so uber as to be game breaking, but definitely worth the player or AI visiting to get an edge in the game. Anyhow, that's just what I think about it.
Image

Image

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

#18 Post by noelte »

BTW: There is no off-road travel ;-)
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

#19 Post by drek »

There are small disadvantages to davebaby's method, such as that removing lanes would have a denser graph to traverse when verifying connectivity
You wouldn't have to prune via a purely random method, eliminating the need to traverse to verify connectivity. Notice how the Voronoi Diagram looks like a bunch of cells. One these cells are defined, could use a maze generation algo to lay out starlanes (or prune).

http://www.astrolog.org/labyrnth/algrithm.htm

In particular:
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.
Creaing a Voronoi Diagram then using the Growing tree maze algorithm should be about a hundred times faster than the current method. (if not more) It should produce a interesting topology to the starlane web, without crisscrossing starlanes or running a non-connecting starlane close to a third party system.
Last edited by drek on Fri Jul 23, 2004 6:46 pm, edited 1 time in total.

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

#20 Post by Geoff the Medio »

Zanzibar wrote:I believe that we should have a few stars with NO lanes connecting to them [...] The stars with no lanes should have some sort of super special or some other thing that makes them actually worth wasting the extra time off-roading to get to them.
I have no objection to this, though I don't think it's really necessary to make isolated stars extra good to make it worth exploring them. They presumably contribute to the galaxy pooled production and physical resources (or maybe not? Could limit pooling by friendly system starlane connectivity, including tactical blockading, if we wanted to dive into that minefield of an argument). Isolated systems would certainly contribute to research and money, though.

Isolation is also an advantage, as difficulty getting to isolated systems also makes invading them harder. And even if isolated stars are sucky compared to connected ones, so what? It adds variety.

Also: if you don't require all stars to be interconnected (or if you cut lanes to encouraage isloation), then there can also arise sub-webs of stars that are isolated form the main web... like an island. We could think of starlane connected systems like continents on earth... with a single connection between groups of stars as isthmus... and going offroad woudl be like crossing an ocean or sea. An isloated group of systems not connected to the main web would be an island (continent). (The standard game convention of higher movement rates for naval vessels compared to land units is lost... but that's ok)

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

#21 Post by drek »

I have no objection to this
BTW: There is no off-road travel
There's the objection. There's no way to reach stars that have no connections to the starlane web. Though off-road travel might be added in (post v1 perhaps, or in a mod) for now we should assume that every star needs to be connected to the greater starlane network.

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

#22 Post by Geoff the Medio »

noelte wrote:BTW: There is no off-road travel ;-)
I can't find that documented anywhere. It's certainly not the sense of what was generally desired from the archived design thread:

viewtopic.php?t=138&start=150&postdays= ... highlight=

There's also no public review, afaict.

The design thread seems to settle on having the options for:
a) no offroad with full connectivity
b) offroad with full connectivity
c) offroad without full connectivity
d) offroad without any starlanes

(and options for number of starlanes in general, and/or their lengths, and some other things like only having a single value for starlane speedup)

If it was decided somewhere else or by executive decision to completely omit offroad travel, I hope it was decided such for v0.2 to simplify things, but could be changed in future versions.

If not, I'd like to know why, as it seems like a big mistake. It's not pathfinding for the UI... tzlaine and others have, I believe, said this is not an issue:
tzlaine wrote:Offroading is built into the pathfinding algorithm I wrote
Also: viewtopic.php?p=4564#4564

(The v0.1 requirements mention that starlanes will be decided on in future. The v0.2 requirements just say you can't have no starlanes.)

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

#23 Post by noelte »

hmm, i'm pretty sure we talked about that issue. If i remember correctly, one argument was, that it is this way simpler to code the ai. please don't start argueing. First, it wasn't me who made this decision and second, if we have starlanes then we don't need unconnected systems. And i expect the ai codeing to be easier, too.
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

#24 Post by drek »

Pathfinding is not the issue. Actually, I'm not sure what the issue is, as it was decided on the old boards before I joined. But the programmers have been fairly consistant in saying that it has been decided: there will be no off-roading for the foreseeable future.


---------
An interesting possibilty, re: the Voronoi Diagram.

If we keep it in memory, could use it to define poltical maps and regions for display on the UI. For example, if starsystems X, Y, Z belong to Region I, then color the cells blue.

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

#25 Post by Geoff the Medio »

drek wrote:Creaing a Voronoi Diagram then using the Growing tree maze algorithm should be about a hundred times faster than the current method. (if not more)
A hundred times faster than half a second isn't really that important...
It should produce a interesting topology to the starlane web
What qualifies as interesting is probably debatable... I (and others) would have to see the results to judge.
without crisscrossing starlanes or running a non-connecting starlane close to a third party system.
Both of these can be done with other methods.

So... the only "solid" (imho) advantage is an aesthetics judgement? Will need to code up both and check, I guess... (?)


~~~~

Re: Offroading

noelte: I'm just trying to find out why this decision was made... not arguing... (arguably... :P )

drek: The programmers haven't been that consistent...
tzlaine, Tue Sep 23, 2003 wrote: both the absolute and the stalane distances between systems
I think I'll PM Tyreth and Aq... somebody must know why this was decided. I'd ask tzlaine, but I seem to have annoyed him into ingoring me :cry:

Aquitaine
Lead Designer Emeritus
Posts: 761
Joined: Thu Jun 26, 2003 1:54 pm
Location: Austin, TX

#26 Post by Aquitaine »

No offroading was in one of the first public reviews we had. A lot of people wanted it, actually, but it came down to the fact that a strict, simple set of rules about galaxy movement means only one set of rules that the AI has to follow; offroading is one of those things that a player can take advantage of but not an AI. Without offroading, the AI can deduce strategic choke points and defend things appropriately; with offroading, it would be trivial to do an end-run around the AI's Krak de Chevaliers and go straight to the chewy nougat center.

I believe our caveat when we passed it was that, if (one day) after we make Slashdot or become famous or whatever, we get some brilliant AI programmers who want a challenge, we would add this feature, since there certainly is demand for it. But until then, it is indeed the case that offroading is out.

-Aq
Surprise and Terror! I am greeted by the smooth and hostile face of our old enemy, the Hootmans! No... the Huge-glands, no, I remember, the Hunams!

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

#27 Post by drek »

So... the only "solid" (imho) advantage is an aesthetics judgement? Will need to code up both and check, I guess... (?)
The "solid" is that delauney triangulation is a well understood and in common usage, as is the Growing tree maze algorithm (and other maze algos). The results are very predicatable in terms of the general topology of the web generated and execution time. Once the web is created via delauney triangulation, it should be easy to experiment with different kinds of maze generation: perhaps multiple maze generation algos could be represented by different game options.

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

#28 Post by Geoff the Medio »

The maze algorithms are in common usage for (fittingly) generating various kinds of mazes, but I'm not sure how many often work with the limitations of a starlanes web-type pre-tesselation. I do see your point(s), and agree that treating the full web/triangluation as anwalled maze in need of walls is worth investigating.

I'm not convinced that delauney triangluation is better than connections to nearest neighbours, though...
-The execution time difference is minimal.
-The added requirements of angular separation between connections aren't yet part of the delauney triangulation. I haven't examined it so am not sure how difficult they would be to add, while ensuring connectivity is maintained. Has anyone done this sort of thing successfully?
-The crossing starlanes issue is debatable... but for nearest neighbours, adding connections to stars in order of proximinty results in maps like the one I posted previously... some crossing, but not enough to be horrible.
-The possibility of unconnected smaller webs of stars with nearest neighbours can basically be eliminated by the angular separation of starlanes requirement, I think. Each star would get as many starlanes as it can fit, including some facing away from the cluster for stars on the edge of the cluster. Thus the stars on the edge of an isolated cluster would get some connections to the nearest stars of another cluster, which would have open angular space on that side, since there's no other stars in the way to fill the space.
Last edited by Geoff the Medio on Fri Jul 23, 2004 10:25 pm, edited 1 time in total.

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

#29 Post by Geoff the Medio »

drek (or anyone): Regarding the maze algorithms, based on the page you linked to, I assume we want a "Crack, Partial Braid, Wall Adder" where Crack means there's no regular tesselation, partial braid means there's some dead ends, but lots of loops as well, and wall adder means you start with all nodes connected to all nearby nodes, and add walls, or breaks in the connections to make the maze. We'd want either 2D or weave, where 2D would be the result of the delauney tesselation with direct noncrossing connections only, and weave is like 2D, except starlanes could cross, and a starlane could cross where a "wall" is (where a "wall" is a starlane that has been removed).

To create the walls for a braid maze, the page's algorithm says to add single isolated walls at random, but to check to make sure no dead ends are created in doing so. This could create isolated subsections of maze (could have a loop with no dead ends, but which isn't connected to other loops) so we'd need an isolation remover (as on page). This could create bottlenecks of perhaps too much significance strategically though. That is, one system that all paths between two halves of galaxy must pass through... (this is one reason I dislike no offroad, btw)

The crack maze algorithm on the page says to add walls from an existing wall to a random other location (straight line, not crossing another wall). This conflicts with the braid maze algorithm, but that's because the crack maze was treated as a type of perfect maze (meaning not braided). The crack maze stuff is also intended for chopping up a basically empty maze space, whereas we have predefined system locations if using the delauney tesselation or nearest neighbour stuff.

I guess we'd impliment this by randomly picking two systems, and finding a starlane path between them that doesn't touch any other walls, but which is also of limited length (so you don't get a giant gash across the galaxy). Finding the shortest / a good wall path between two systems might be computationally expensive, since our tesselation is so irregular, and we need to be sure we're not connecting to other "walls" in a bad way by doing so. Having delauney tesselation might help with this a bit... (not sure though... could be irrelivant).

Alternatively, we could generate systems at the same time as lanes, using a crack maze-like algorithm, though interfacing this with galaxy shape geometry and such might be difficult.

Thoughts?

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

#30 Post by drek »

Wall adder tend to be slower and more complex, since you need to check for connectivety between all nodes after placing your wall. It would be easier to assume each segment generated by delauney triangulation is a -potential- starlane (a direction travelable from that particular cell/star in the maze.) Real starlanes would be added, rather than removed.

I really want to avoid crisscrossing, aka weaving.
(could have a loop with no dead ends, but which isn't connected to other loops) so we'd need an isolation remover (as on page).
With the Growing tree on that page, there's no need for dead end checking or an isolation removing step.
Alternatively, we could generate systems at the same time as lanes, using a crack maze-like algorithm, though interfacing this with galaxy shape geometry and such might be difficult.
imho, "simplest" method:

1: Generate stars as they are now.
2: As each star is generated, update delauney triangulation.
2: Use a maze generation to add starlanes.

Yes, it'll be a "crack" maze, but there's nothing special we would have to do to make it so.

Post Reply