FreeOrion

Forums for the FreeOrion project
It is currently Wed Dec 13, 2017 10:30 pm

All times are UTC




Forum locked This topic is locked, you cannot edit posts or make further replies.  [ 156 posts ]  Go to page 1, 2, 3, 4, 5 ... 11  Next
Author Message
 Post subject: Design: Starlanes
PostPosted: Tue Jul 22, 2003 7:20 pm 
Offline
FreeOrion Designer / Space Monster
User avatar

Joined: Thu Jun 26, 2003 7:07 am
Posts: 313
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:


Top
 Profile  
 
 Post subject:
PostPosted: Tue Jul 22, 2003 8:43 pm 
Offline
Creative Contributor
User avatar

Joined: Fri Jun 27, 2003 6:32 am
Posts: 215
Location: Kassel / Germany
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 :).


Top
 Profile  
 
 Post subject:
PostPosted: Tue Jul 22, 2003 9:55 pm 
Offline
Krill Swarm

Joined: Wed Jul 16, 2003 8:06 am
Posts: 12
Location: The Netherlands
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"


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 12:00 am 
Offline
Cosmic Dragon
User avatar

Joined: Fri Jun 27, 2003 12:37 am
Posts: 2175
Location: Auckland, New Zealand
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.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 12:17 am 
Offline
FreeOrion Lead Emeritus
User avatar

Joined: Thu Jun 26, 2003 6:23 am
Posts: 885
Location: Australia
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.

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


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 1:43 am 
Offline
Creative Contributor

Joined: Thu Jun 26, 2003 4:33 pm
Posts: 226
Location: Baltimore, MD
A generic shortest path algorithm is almost a necessity. I'd imagine it would probably be some variant of Djikstra

_________________
Empire Team Lead


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 2:06 am 
Offline
Space Kraken

Joined: Mon Jul 07, 2003 10:17 am
Posts: 146
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.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 2:35 am 
Offline
Creative Contributor

Joined: Thu Jun 26, 2003 4:33 pm
Posts: 226
Location: Baltimore, MD
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


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 2:45 am 
Offline
Psionic Snowflake
User avatar

Joined: Thu Jun 26, 2003 10:35 pm
Posts: 470
Location: Earth
Why have starlanes?? Why not have a movement system as discussed in this thread??


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 3:00 am 
Offline
Creative Contributor
User avatar

Joined: Fri Jun 27, 2003 2:35 am
Posts: 383
Location: Texas
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.... ;)


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 5:50 am 
Offline
FreeOrion Designer / Space Monster
User avatar

Joined: Thu Jun 26, 2003 7:07 am
Posts: 313
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.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 11:51 am 
Offline
Space Kraken

Joined: Thu Jun 26, 2003 2:17 pm
Posts: 167
Location: Pittsburgh, PA
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


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 1:47 pm 
Offline
FreeOrion Lead Emeritus
User avatar

Joined: Thu Jun 26, 2003 6:23 am
Posts: 885
Location: Australia
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.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 1:47 pm 
Offline
Space Squid

Joined: Fri Jun 27, 2003 9:00 am
Posts: 78
Location: Germany
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.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jul 23, 2003 2:15 pm 
Offline
Space Kraken

Joined: Thu Jun 26, 2003 2:17 pm
Posts: 167
Location: Pittsburgh, PA
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Forum locked This topic is locked, you cannot edit posts or make further replies.  [ 156 posts ]  Go to page 1, 2, 3, 4, 5 ... 11  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group