FreeOrion

On the old board we passed that we'd use starlanes and that the ratio of Starlane Speed / Offroad Speed would be constant. This is passed and set in stone. (Unless I rememeber something very wrong.)

The purpose of this thread is to determine the other things we need to know about starlanes.

Aside from the actual ratio we also need to know how "long" starlanes are. Can they span the entire galaxy or are they limited? Do we allow for various starlane length settings at game start?

Well, this ought to be one of our shortest threads ever... Let's hear some thoughts anyway

I'd say starlanes should connect only neighboring stars.

Depending on the choosen "density" each star should have 1-4 starlanes.

So we look for each star for its closest neighbor, and connect them with a star lane. Next step: we detect the star, that now has the closest neighbor without a connection to the first star.

Depending on the "starlane density" we continue this X times. After all those connections are made, we controll if we can reach all stars form one given star. If not, we need more connects.

I'm tired, so someone else write some r... about starlanes .

will there be a generic shortest/fastest path algorhythem available ?

_________________
Crimson Rider takes out a purse and carefully picks two coins. With an elegant move he tosses them on the table. A slight smile is upon his face as he points at them and says : "Those are mine"

I think that you should be able to have starlanes that are as long as the galaxy and as short as to the next star.

You should be able to set such options or choose random.

We should specify two things.

First, the code to generate starlanes allows for any number (ie, from every planet to every planet) and any size . However, for our actual game, we limit those options. We just include the capability for modding or something later.

Anyway, I think that it should be 1-4 starlanes, with 2-3 on average

But we should have a few more options for less and more, along with I think a "no starlanes" option - but the game won't be balanced for this setting.

On that note, I think we should calculate speed based on the engine saying that while travelling along a starlane you move at 100% of the engine's capacity. Off-'road', say, 25% for example. For 'no starlanes' we just change the off-'road' penalty to 100% of the engine's normal capacity.



Very good question, I imagine that there will be both for the UI and for the AI.

A generic shortest path algorithm is almost a necessity. I'd imagine it would probably be some variant of Djikstra

_________________
Empire Team Lead

Has there already been any thought amid the programmers on a method of determining the placement of starlanes?

If we want to be able to reach every star system from any other via starlanes, I guess we'd have to use some variation of a maze generation function.

Well, I haven't been involved in the universe side of things, so I haven't thought too much about it. I would imagine that something like the maze generation algorithm would be the way to do it.

We may not necessarily want to have them all reachable though. It could be a selectable option whether all systems are connected or not.
In any case, something like a starlane graph is a pretty straightforward application of graph theory, so it wont be hard finding algorithms to use for placing and navigating starlanes.

_________________
Empire Team Lead

Why have starlanes?? Why not have a movement system as discussed in this thread??

Heres a novel idea ALL stars connect to ALL other stars. Every star will have N-1 Starlanes from it where N is the number of stars in the universe. Now we don't have to worry about off-road travel etc. And why even bother drawing the starlanes as they exists everywhere? It would be neat as the starlanes in the universe would be ubiquitous. And it would be easy to code as you'd just use the distance formula to determine the number of turns to travel from the various stars. It would look almost exactly like MoO 1-2

[/humor]

Sorry i'm just a little sour about the decision to include starlanes as i think alternate methods would work better. I'm sure however NF decides to do it will be fine. Though when we get to game-balancing we night have to change several things.

_________________
Aquitaine is my Hero....

Zanzibar: Starlanes are in because we decided to have them on the old board. Nearly everyone was in favor of them and they are in. As has been said several times before we cannot revisit every decision each time a new guy drops by.

Powercrazy: Well, there are a couple of features in our game I'm unhappy with, too. I think that's just normal as everybody likes different things about games. Fact is that I'd rather have a feature I hate in the game than see the design process bog down every time somebody isn't happy with a feature.

2 thoughts:

Thought 1: We're going to need a shortest path algorithm for lots of things....even without starlanes. For example, the tech tree (which is really technically a graph). We should probably come up with a base Graph class, and then subclass it for the starlane graph and the tech tree and anything else we need.

Thought 2: How about this? We treat a game with "no starlanes" as a game where there is a starlane connecting each system to every other system. This way, ships all move at the starlane rate all the time, since there is no such thing as off-road.

We don't necessarily have to actually store a weighted graphic in memory connecting all the systems in this case, since we can always assume the shortest path between 2 systems as being a direct movement to the destination system. Then the game will be balanced no matter what the player chooses.

Edit: For anyone that doesn't know yet, Starlanes ARE IN THE GAME....PERIOD. They are a user-option, however, and can be turned off if you don't like them, so those of you that aren't thrilled by starlanes, don't play with them on.

_________________
FreeOrion Programmer

For a game of no starlanes I think it is good like you say to assume a starlane to every system from every system. However, it would be good to have the off road limit changeable easily, probably in a config file. That will aid playtesting and also modding.

A shortest path algorithm has to deal with some problems, as "is this way save", and "does the player want this way"

It should be possible to create a path by clicking waypoints, so if you have situation, where the shortest way is unsafe due to enemy presence, or you want the fleet to go this way to group with another fleet waiting there should be possible.

For UI it would be nicest to have SHIFT-Click to create a Waypoint like in much other RTS games, so if you want, you can decide which way your fleet goes.

It would be nice, if there would be an option on game-creation how many starlanes and how long the average starlanes are, maybe late in development, but definitly not as a "possibility for a mod" but as a part of the game.

A shortest-path algorithm should do only what it states....find the shortest path. Finding the safest path would be up to the player.

Of course, the AI will need to have access to a "safest-path" algorithm, but we could simply use a modified shortest-path alogorithm, overriding the heuristic that evaluates each node. If there is a threat at the current node, it can add weight to the adjacent edge which makes the shortest-path algorithm "see" that node as further away....then, when the AI makes a decision about how brave it wants to be, it only needs specify that "bravery" in terms of "how far does it want to travel."

_________________
FreeOrion Programmer