FreeOrion

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?

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.

_________________

BTW: There is no off-road travel

_________________
Press any key to continue or any other key to cancel.
Can COWs fly?

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:


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.

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)

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.

I can't find that documented anywhere. It's certainly not the sense of what was generally desired from the archived design thread:

http://www.freeorion.org/forum/viewtopi ... 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:

Also: http://www.freeorion.org/forum/viewtopi ... =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.)

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?

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.

A hundred times faster than half a second isn't really that important...
What qualifies as interesting is probably debatable... I (and others) would have to see the results to judge.
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... )

drek: The programmers haven't been that consistent...


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

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!

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.

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.

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?

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.



With the Growing tree on that page, there's no need for dead end checking or an isolation removing step.



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.