Design: Starlanes

Past public reviews and discussions.
Locked
Message
Author
User avatar
Nightfish
FreeOrion Designer / Space Monster
Posts: 313
Joined: Thu Jun 26, 2003 7:07 am

Design: Starlanes

#1 Post by Nightfish » Tue Jul 22, 2003 7:20 pm

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 :wink:

User avatar
Bastian-Bux
Creative Contributor
Posts: 215
Joined: Fri Jun 27, 2003 6:32 am
Location: Kassel / Germany

#2 Post by Bastian-Bux » Tue Jul 22, 2003 8:43 pm

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 :).

Crimson Rider
Krill Swarm
Posts: 12
Joined: Wed Jul 16, 2003 8:06 am
Location: The Netherlands

#3 Post by Crimson Rider » Tue Jul 22, 2003 9:55 pm

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"

User avatar
utilae
Cosmic Dragon
Posts: 2175
Joined: Fri Jun 27, 2003 12:37 am
Location: Auckland, New Zealand

#4 Post by utilae » Wed Jul 23, 2003 12:00 am

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.

User avatar
Tyreth
FreeOrion Lead Emeritus
Posts: 885
Joined: Thu Jun 26, 2003 6:23 am
Location: Australia

#5 Post by Tyreth » Wed Jul 23, 2003 12:17 am

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.
will there be a generic shortest/fastest path algorhythem available ?
Very good question, I imagine that there will be both for the UI and for the AI.

jbarcz1
Creative Contributor
Posts: 226
Joined: Thu Jun 26, 2003 4:33 pm
Location: Baltimore, MD

#6 Post by jbarcz1 » Wed Jul 23, 2003 1:43 am

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

drekmonger
Space Kraken
Posts: 146
Joined: Mon Jul 07, 2003 10:17 am

#7 Post by drekmonger » Wed Jul 23, 2003 2:06 am

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.

jbarcz1
Creative Contributor
Posts: 226
Joined: Thu Jun 26, 2003 4:33 pm
Location: Baltimore, MD

#8 Post by jbarcz1 » Wed Jul 23, 2003 2:35 am

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

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

#9 Post by Zanzibar » Wed Jul 23, 2003 2:45 am

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

User avatar
PowerCrazy
Creative Contributor
Posts: 383
Joined: Fri Jun 27, 2003 2:35 am
Location: Texas

#10 Post by PowerCrazy » Wed Jul 23, 2003 3:00 am

Heres a novel idea :twisted: 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 :twisted:

[/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.... ;)

User avatar
Nightfish
FreeOrion Designer / Space Monster
Posts: 313
Joined: Thu Jun 26, 2003 7:07 am

#11 Post by Nightfish » Wed Jul 23, 2003 5:50 am

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.

tsev
Space Kraken
Posts: 167
Joined: Thu Jun 26, 2003 2:17 pm
Location: Pittsburgh, PA

#12 Post by tsev » Wed Jul 23, 2003 11:51 am

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

User avatar
Tyreth
FreeOrion Lead Emeritus
Posts: 885
Joined: Thu Jun 26, 2003 6:23 am
Location: Australia

#13 Post by Tyreth » Wed Jul 23, 2003 1:47 pm

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.

elfstone
Space Squid
Posts: 78
Joined: Fri Jun 27, 2003 9:00 am
Location: Germany

#14 Post by elfstone » Wed Jul 23, 2003 1:47 pm

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.

tsev
Space Kraken
Posts: 167
Joined: Thu Jun 26, 2003 2:17 pm
Location: Pittsburgh, PA

#15 Post by tsev » Wed Jul 23, 2003 2:15 pm

elfstone wrote:A shortest path algorithm has to deal with some problems, as "is this way save", and "does the player want this way"
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

Locked