What is generated at "the edge"?

For LT discussion that doesn't fit into a more specific category.

Re: What is generated at "the edge"?

Postby Flatfingers » Fri Aug 26, 2016 4:38 pm

bkdevil wrote:This all does make me wonder if it will be possible for us to ever see a trader\explorer\mercenary in-system who has traveled from an extremely far distance away. I doubt the AI is going to be exploring just for the sake of doing so like a human would.

Not critical, just curious: why wouldn't NPCs do this as well?

I can imagine a "curiosity" trait in NPCs, and in the factions and cultures that emerge from the NPCs that form them, that's tied to a "find new information" behavior. And that behavior in turn could be expressed through either data diving (abstract information) or physical travel (practical information).

I've no idea if that's A Real Thing that Josh is considering, of course -- I'm just guessing it's possible.
User avatar
Flatfingers
Vice Admiral
 
Posts: 4398
Joined: Sat Nov 24, 2012 12:45 am

Re: What is generated at "the edge"?

Postby bkdevil » Fri Aug 26, 2016 4:48 pm

While it's certainly possible that AI players will have some trait like "curiousity" or "wanderlust" or whatever, I meant it more due to the idea that said NPCs wouldn't even be generated until the player got close enough (possibly in) to their system. Perhaps they would be taken care of by a statistical model as well, where random migrants are generated at the borders from varying distances away, with extreme travelers being very rare. If that's the case, however, then at least something will need to be known about their point of origin as they are possibly affiliated with a faction there, or carry tech from there, etc, and this would make the universe quite a bit bigger, all to have the occasionally visitor from 300 systems away.

Perhaps I'm overestimating how much generating these simplified versions of other systems would cost computer resource wise, so maybe it won't be a big deal. I would really like to see explorer AIs with nothing else on their mind but seeing the galaxy!
User avatar
bkdevil
Ensign
 
Posts: 49
Joined: Thu May 29, 2014 8:25 pm

Re: What is generated at "the edge"?

Postby BFett » Fri Aug 26, 2016 9:01 pm

Flatfingers wrote:Me, I still have the questions about this that I've had for a while now:

1. Under what conditions does the current edge of the existing universe expand; through the creation of new star systems and factions within them; around the part of the existing game universe?

a) Will the edge be moved only when your individual character's ship gets too close to the current edge?

b) Or will it be moved if any ships belonging to your faction approach the current edge?

c) Or will it be moved if any ships at all approach the current edge?

2. How few system hops away from the current edge of the universe does a ship have to be before new systems are generated to extend the area around that part of the edge? Just one hop away? Two? Five? Ten or more?

3. When new systems are generated to move part of the current edge of the universe, will there be a delay in the game while those new systems are generated?

Just thinking out loud again. Speculate away. :)


1.
a) No, expansion will likely vary based on asset locations
b) No, not exactly. The word "faction" would imply executive NPCs along with worker NPCs. I personally think only NPCs under your direct control would provide Line Of Site (LOS) of the regions they occupy.
c) No, for hardware reasons we can't simulate every NPC in every system because, well, LT is practically infinite.

2. I suggested 2 jumps and provided a reason why in my previous post.

3. No humanly noticeable delay should occur because the system already exists through the universe generation seed and because the content can be generated off screen while the player is exploring the current edge system.
User avatar
BFett
Vice Admiral
 
Posts: 2393
Joined: Thu Jan 23, 2014 6:44 pm
Location: A galaxy far far away

Re: What is generated at "the edge"?

Postby Flatfingers » Sat Aug 27, 2016 12:45 am

BFett wrote:
Flatfingers wrote:Me, I still have the questions about this that I've had for a while now:

1. Under what conditions does the current edge of the existing universe expand; through the creation of new star systems and factions within them; around the part of the existing game universe?

a) Will the edge be moved only when your individual character's ship gets too close to the current edge?

b) Or will it be moved if any ships belonging to your faction approach the current edge?

c) Or will it be moved if any ships at all approach the current edge?

2. How few system hops away from the current edge of the universe does a ship have to be before new systems are generated to extend the area around that part of the edge? Just one hop away? Two? Five? Ten or more?

3. When new systems are generated to move part of the current edge of the universe, will there be a delay in the game while those new systems are generated?

Just thinking out loud again. Speculate away. :)

1.
a) No, expansion will likely vary based on asset locations
b) No, not exactly. The word "faction" would imply executive NPCs along with worker NPCs. I personally think only NPCs under your direct control would provide Line Of Site (LOS) of the regions they occupy.
c) No, for hardware reasons we can't simulate every NPC in every system because, well, LT is practically infinite.

2. I suggested 2 jumps and provided a reason why in my previous post.

3. No humanly noticeable delay should occur because the system already exists through the universe generation seed and because the content can be generated off screen while the player is exploring the current edge system.

Just to continue the pure speculation:

1. If the edge of the universe doesn't expand when non-player-controlled NPCs approach the current edge, doesn't that mean that this is an important way in which NPCs in LT can't do what the player character can do?

Maybe that's OK, or necessary. But if one of the design goals of LT is that "NPCs can do what the player character can do," then this seems like it would be a noteworthy exception to that goal.

2. What you described is not quite what I asked about. To say that when a triggering ship enters system A, system B is generated that's connected to system A, and system C is generated that's connected to system B, implies that system A was at the edge of the universe until that moment.

What I'm actually asking is whether the algorithm that generates new edge systems needs to do so before a triggering ship enters a system at the edge of the universe, and if so, how many systems away from the edge should this occur.

This is actually connected to the third question I asked. My guess is that when new systems are generated at part of the current universe's edge, it won't be just one new system -- it'll need to be several at once in order to be able to create new factions that span multiple star systems.

But creating several new star systems (which by definition won't have already been created by the initial universe generation process), including NPC ships (with character traits), factions, and colonies in addition to all the physical information, may be computationally expensive. In that case, you probably wouldn't want to generate multiple new systems when a triggering ship enters the last star system at the current edge; you'd want to use a predictive algorithm to reduce the number of systems that have to be created in order to reduce CPU load. And that means activating the new-system-generation function some number of hops before entering an edge star system.

So to phrase my question #2 more precisely: how many hops away from an edge star system should the arrival of a triggering ship generate new systems in order to optimally minimize the computational impact while still being able to create system-spanning factions?

3. There may be some tricks Josh can devise to minimize the cost of generating new star systems and all their information.

I'm guessing that it's probably still true that systems and NPC activity outside the player's Zone of Factional Operations (ZFO) will be reduced to high-level simulations, and that these will only be converted to detailed elements as the player's ZFO moves or expands to cover them. If so, then new systems generated beyond the universe will not be covered by the player's ZFO, and so may only need the high-level simulation values to be generated. That could be enough to make creating new systems unnoticeably cheap... or maybe Josh is creating so much complex content for new star systems at even the highest level of abstraction that the predictive algorithm for creating new systems will have to constantly "stream" new content in small chunks whenever the player is nosing around the current edge of the universe.

Speculation. :D
User avatar
Flatfingers
Vice Admiral
 
Posts: 4398
Joined: Sat Nov 24, 2012 12:45 am

Re: What is generated at "the edge"?

Postby kostuek » Sat Aug 27, 2016 1:32 am

There is no need for any "edge". Take for example the surface of the earth: it is limited, but you can start to walk in one direction and you will never have to stop (let's assume you can walk on water). After a while you will end up at your start position, but you will never see an edge. I would expect the same here. To do that in a game universe is even easier: just connect the "jump gate" or whatever of you "last" system to your "first" system, in between there can be any amount of other systems your system generator is capable of.
kostuek
Ensign
 
Posts: 37
Joined: Mon Dec 22, 2014 6:17 am

Re: What is generated at "the edge"?

Postby Flatfingers » Sat Aug 27, 2016 2:02 am

kostuek wrote:There is no need for any "edge". Take for example the surface of the earth: it is limited, but you can start to walk in one direction and you will never have to stop (let's assume you can walk on water). After a while you will end up at your start position, but you will never see an edge. I would expect the same here. To do that in a game universe is even easier: just connect the "jump gate" or whatever of you "last" system to your "first" system, in between there can be any amount of other systems your system generator is capable of.

I'm pretty sure this would be easily doable in LT if connections between star system "bubbles" are just bits of data. You just have to decide if you want a cylindrical wrapping, or spherical, or something more arcane.

But why?

The very title of Josh's Kickstarter project was "Limit Theory: An Infinite, Procedural Space Game".

In that Kickstarter campaign, Josh spelled this out:

JoshParnell wrote:No matter how far out into the universe you delve, you will never find an edge. The algorithms behind the universe have been designed very carefully, such that they are mathematically-guaranteed to generate universes of infinite size, each and every time.

If non-finiteness presented an extremely difficult problem, then certainly I'd have to be OK with Josh declaring that all game universes would be finite after all.

I'm not sure that deciding how to handle universe edge updating constitutes an extremely difficult problem, though. The fact that we forum visitors are banging around some ideas out here in the darkness doesn't mean Josh hasn't already figured this out long ago, perhaps even before the Kickstarter began (because he has specifically said he worked on universe generation logic before the Kickstarter to prove that it could be done).

On the other hand, Josh has also said that an infinite universe would be an option, and that we could instead choose to have a game universe that's finite (e.g., if we want to play LT in a more 4X-like way). So maybe if you pick the "Finite Universe" start-up option, you can also select from several "Connectivity" options such as Flat, Cylindrical, Spherical, and Random.

A universe whose systems are randomly connected could be a real head-scratcher for strategic players. :D
User avatar
Flatfingers
Vice Admiral
 
Posts: 4398
Joined: Sat Nov 24, 2012 12:45 am

Re: What is generated at "the edge"?

Postby kostuek » Sat Aug 27, 2016 2:56 am

Actually, infinite just means there is no edge. You can further distinct between "closed infinite" and "open infinite" universe. Closed infinite means you will end at your start position at some point if you keep going. In an open infinite universe you can keep going forever and will never see your start position again.
Now, a true open universe is of course impossible on a finite machine like a PC. I guess you can simulate one, even I don't know why you would bother. At the end of the day, you can even generate a finite universe. Just make sure it's big enough, so no one can reach the edge in his lifetime.
kostuek
Ensign
 
Posts: 37
Joined: Mon Dec 22, 2014 6:17 am

Re: What is generated at "the edge"?

Postby Dinosawer » Sat Aug 27, 2016 8:20 am

Only somewhat related, but I had a random idea yetserday:
in the end, the size of the universe will be, logically, determined by your CPU. No matter how light the LOD AI calculations are, at some point it's gotta be too much to handle.
So maybe, for lighter systems or something, you could borrow a technique that is often used in physics, namely periodic boundary conditions.

Image
The idea behind it is that you can simulate a small part of a roughly homogenous something (such as the universe, or a fluid) by pretending the entire universe is a repeated pattern of the block you're simulating.
Interactions are then calculated "over the edge" too, so you don't notice there's a boundary in your simulation, while still limiting the space you actually have to simulate.

In LT, that would mean that systems near the edge of your universe box would have wormholes that lead to systems near the opposite edge of the universe - that way you don't have "dead ends" anywhere, while still having a finite universe to simulate.

Just a random thought. :ghost:
Warning: do not ask about physics unless you really want to know about physics.
The LT IRC / Alternate link || The REKT Wiki || PUDDING
Image
User avatar
Dinosawer
Admiral
 
Posts: 5447
Joined: Fri May 09, 2014 1:08 pm
Location: Belgium

Re: What is generated at "the edge"?

Postby Mistycica » Sat Aug 27, 2016 8:34 am

Image

So the universe is basically this.
panic
User avatar
Mistycica
Captain
 
Posts: 905
Joined: Thu May 29, 2014 1:02 pm
Location: Hungary

Re: What is generated at "the edge"?

Postby BFett » Sat Aug 27, 2016 9:37 am

Flatfingers wrote:1. If the edge of the universe doesn't expand when non-player-controlled NPCs approach the current edge, doesn't that mean that this is an important way in which NPCs in LT can't do what the player character can do?

Maybe that's OK, or necessary. But if one of the design goals of LT is that "NPCs can do what the player character can do," then this seems like it would be a noteworthy exception to that goal.

2. What you described is not quite what I asked about. To say that when a triggering ship enters system A, system B is generated that's connected to system A, and system C is generated that's connected to system B, implies that system A was at the edge of the universe until that moment.

What I'm actually asking is whether the algorithm that generates new edge systems needs to do so before a triggering ship enters a system at the edge of the universe, and if so, how many systems away from the edge should this occur.

This is actually connected to the third question I asked. My guess is that when new systems are generated at part of the current universe's edge, it won't be just one new system -- it'll need to be several at once in order to be able to create new factions that span multiple star systems.

a) But creating several new star systems (which by definition won't have already been created by the initial universe generation process), including NPC ships (with character traits), factions, and colonies in addition to all the physical information, may be computationally expensive. In that case, you probably wouldn't want to generate multiple new systems when a triggering ship enters the last star system at the current edge; you'd want to use a predictive algorithm to reduce the number of systems that have to be created in order to reduce CPU load. And that means activating the new-system-generation function some number of hops before entering an edge star system.

b) So to phrase my question #2 more precisely: how many hops away from an edge star system should the arrival of a triggering ship generate new systems in order to optimally minimize the computational impact while still being able to create system-spanning factions?

3. There may be some tricks Josh can devise to minimize the cost of generating new star systems and all their information.

I'm guessing that it's probably still true that systems and NPC activity outside the player's Zone of Factional Operations (ZFO) will be reduced to high-level simulations, and that these will only be converted to detailed elements as the player's ZFO moves or expands to cover them. If so, then new systems generated beyond the universe will not be covered by the player's ZFO, and so may only need the high-level simulation values to be generated. That could be enough to make creating new systems unnoticeably cheap... or maybe Josh is creating so much complex content for new star systems at even the highest level of abstraction that the predictive algorithm for creating new systems will have to constantly "stream" new content in small chunks whenever the player is nosing around the current edge of the universe.

Speculation. :D


1. It's probably not important because the player will never see the data that shows NPCs pushing past the edge. For sake of argument, I'd allow NPCs to expand the edge during universe generation but would stop that ability after the player enters the game. I imagine that there would be plenty of systems for the NPCs to interact with, so exploring past the edge shouldn't be much of a problem.

2. The seed for the universe determines the system locations, so this occurs at universe generation the moment the player clicks "generate universe". So, I'd answer your question with 'Yes' and the second part is still "2 systems away when a player controlled ship approaches the edge". (I'm having a little trouble understanding what you are asking for so I'm sorry if I'm not answering the question)

a) The connected systems are generated in low LOD (level of detail) which increases when the player enters that system. The time it takes the player to go from system A to system B should be enough for the computer to work out any stats that it needs.

b) I'm going to stick with 2 jumps just to stay consistent. It could easily be more depending on CPU power and other factors.

3. I agree.

Interesting wording:
high-level simulation = low Level Of Detail
User avatar
BFett
Vice Admiral
 
Posts: 2393
Joined: Thu Jan 23, 2014 6:44 pm
Location: A galaxy far far away

Re: What is generated at "the edge"?

Postby Cornflakes_91 » Sat Aug 27, 2016 4:30 pm

I think two jumps is far too short.

How should an enemy empire be a consistent enemy when you stop generating its constituent systems the second you turn around after encountering scouts?

it has to be a range thats large enough for other societies to be well within generation range before you could encounter them.
That they can have an influence on the world even if you turn around after seeing the first forward scout ship.


Spoiler:      SHOW
Image
Green=explored/visited systems.
Blue=generated systems
red=Edge systems


take this example image here.
would you take it as believable that a, say 5 system large, civilisation wouldnt know about another civ in that range?
Without them knowing theres no interactions and no lore that would be believable.
And they cant know without the systems/civ being generated.
Booooring.


So, to use that image for the purpose i made it:
Green systems are systems the player has data of or has visited personally.
They have full fidelity generation and any AI in them acts without huge abstractions.

Blue systems are fully generated as well, but arent directly known to the player.
AI's can act in them without large abstraction as well.
They are where strategic/operational gameplay happens between AIs that arent known to the player (yet).
Enemy invasions etc.

The red systems only have low levels of generation and simulation.
they are mostly there to define where influences from the high abstraction "beyond the edge" areas enter the high sim systems.
They are defined by their topological position in the universe and maybe some abstracted statistics (mineral contents, state of industrialisation etc).

Beyond the red systems, beyond the circle i've drawn on the image, lies the abstracted space where its differential equations and vastly simplified AI to simulate the influence of what lies there to infinity.
That there can be influences from "everywhere" in the universe, but its not on a per system basis anymore but based on averages and the underlying functions that generate system compositions.
Basically sum everything up from there to infinity and guesstimate what it would do on the borders of directly simulated space.

(I have some more thoughts on that, but its half past midnight and i have troubles staying awake typing this)
User avatar
Cornflakes_91
Admiral
 
Posts: 8896
Joined: Wed Mar 06, 2013 1:53 am
Location: Austria

Re: What is generated at "the edge"?

Postby BFett » Sat Aug 27, 2016 5:08 pm

So you are arguing for 3 jumps in distance as opposed to 2 jumps?


Wait, the blue is what's generated? That's exactly what I was arguing.
User avatar
BFett
Vice Admiral
 
Posts: 2393
Joined: Thu Jan 23, 2014 6:44 pm
Location: A galaxy far far away

Re: What is generated at "the edge"?

Postby Flatfingers » Sun Aug 28, 2016 1:29 am

kostuek wrote:Actually, infinite just means there is no edge. You can further distinct between "closed infinite" and "open infinite" universe. Closed infinite means you will end at your start position at some point if you keep going. In an open infinite universe you can keep going forever and will never see your start position again.
Now, a true open universe is of course impossible on a finite machine like a PC. I guess you can simulate one, even I don't know why you would bother. At the end of the day, you can even generate a finite universe. Just make sure it's big enough, so no one can reach the edge in his lifetime.

Or as I put it nearly three years ago now during one of the other times we've talked about the "edge" question:

Flatfingers wrote:Rather than "infinite," it might be a little more precise to say that the universe of a LT game, like our own, is infinite-but-bounded (or maybe "infinitely expandable").

That is, the universe of every LT game has a circumference where, at any snapshot moment in time, it stops. But if you go to one location on that edge, new regions are generated around that location, in effect making every LT universe functionally infinite.

The LOD feature doesn't really determine the "infinite" part -- I'd describe it as a necessary mechanic for maintaining performance as a game universe grows ever larger. It probably does affect the "simulation of history" feature, though, since it allows the coarse simulation used to create the history of newly-generated regions.

Meaning: If an edge-expanding trigger object (such as the player's ship) never approaches the edge of a procedurally-generatable universe, then the universe of that game never expands, and the question of edge connectivity is moot (other than let some people complain that "Josh spent time developing code that will never be executed"... for this one player of LT).

BFett wrote:2. The seed for the universe determines the system locations, so this occurs at universe generation the moment the player clicks "generate universe". So, I'd answer your question with 'Yes' and the second part is still "2 systems away when a player controlled ship approaches the edge". (I'm having a little trouble understanding what you are asking for so I'm sorry if I'm not answering the question)

I'm sorry I haven't been able to do a better job of explaining.

I'd just add that, if I understand Josh's intent correctly, then yes, a large universe is generated from a seed value when you start a new game of LT, but that universe has an edge: at any specific moment in time, there are a finite number of star systems, and their connectivity is probably defined by default as a kind of 2D planar circle. The star systems on the circumference of that circle would be "edge systems," and the player would start the game in a star system somewhere roughly near the middle of the entire connectivity map.

Then as the player sees a star system some number of jumps away from one of the edge systems, new systems would be generated that connect to the edge systems somewhere in the general vicinity of the direction the player seems to be traveling (making new system generation dependent on some kind of light predictive algorithm).

The question I was asking (badly) was, how few jumps away from one of those edge systems should a player ship be able to get before the new-system-generation code gets called?

You seem to be thinking 0. Cornflakes disagrees ( :shock: :lol: ) and thinks the number of hops should be larger. But the question's still open: how much larger?

Dinosawer wrote:in the end, the size of the universe will be, logically, determined by your CPU. No matter how light the LOD AI calculations are, at some point it's gotta be too much to handle. So maybe, for lighter systems or something, you could borrow a technique that is often used in physics, namely periodic boundary conditions.
[attractive image]
The idea behind it is that you can simulate a small part of a roughly homogenous something (such as the universe, or a fluid) by pretending the entire universe is a repeated pattern of the block you're simulating. Interactions are then calculated "over the edge" too, so you don't notice there's a boundary in your simulation, while still limiting the space you actually have to simulate.

That's one way.

Another way might be to use the trick I proposed for simulating the positions of planets (and asteroid field centers) if they could move, in order to avoid having to move them when no one's watching. Namely, when you're not there, record their positions to a file along with a timestamp, and stop moving them. Then when you go back there, read in their information and calculate their current position based on the saved timestamp, the current time, and the appropriate position calculation.

A version of this might also be used for simulating high-level star system effects without actually calculating activity for those systems. When there's no player-related ship close enough, LT would identify the salient data about a system, save that data to disk with a timestamp, and stop simulating it entirely. Systems that connect to the saved system would be responsible for simulating at a high level what it would have provided (this is a bit of a handwave, but bear with me). The distant system would then be entirely static because it's all been paged out of RAM. It would thus have no direct effect on performance (only an indirect effect via the systems that connect to it using a little local data to simulate what that now-static system would have provided).

Then, later on, when a ship controlled by the player's faction gets close enough to the saved system (whatever that distance is), you read its information from disk along with the timestamp, then calculate what that system should look like after the passage of time between when it was saved and now. (This recovery process is what would be happening as you're "flying through a wormhole" between systems.) It then once again starts to have an active impact on the systems around it, even though it's still being simulated at a low LOD since you're not looking directly at it yet.

All speculation, of course. No one should be surprised if Josh already worked out this logic before the Dark Days and it's far more elegant than what I described here. ;)
User avatar
Flatfingers
Vice Admiral
 
Posts: 4398
Joined: Sat Nov 24, 2012 12:45 am

Re: What is generated at "the edge"?

Postby Cornflakes_91 » Sun Aug 28, 2016 6:45 am

BFett wrote:So you are arguing for 3 jumps in distance as opposed to 2 jumps?


Wait, the blue is what's generated? That's exactly what I was arguing.



Im saying that such a small number of jumps to generate in distance is far too small to generate.
Did you read what i wrote rather than just looking at the image? :V

Example image is example, i wont hand build a map with 20 jump radius to make explanations.
User avatar
Cornflakes_91
Admiral
 
Posts: 8896
Joined: Wed Mar 06, 2013 1:53 am
Location: Austria

Re: What is generated at "the edge"?

Postby Dinosawer » Sun Aug 28, 2016 6:59 am

Flatfingers wrote:That's one way.

Another way might be to use the trick I proposed for simulating the positions of planets (and asteroid field centers) if they could move, in order to avoid having to move them when no one's watching. Namely, when you're not there, record their positions to a file along with a timestamp, and stop moving them. Then when you go back there, read in their information and calculate their current position based on the saved timestamp, the current time, and the appropriate position calculation.

A version of this might also be used for simulating high-level star system effects without actually calculating activity for those systems. When there's no player-related ship close enough, LT would identify the salient data about a system, save that data to disk with a timestamp, and stop simulating it entirely. Systems that connect to the saved system would be responsible for simulating at a high level what it would have provided (this is a bit of a handwave, but bear with me). The distant system would then be entirely static because it's all been paged out of RAM. It would thus have no direct effect on performance (only an indirect effect via the systems that connect to it using a little local data to simulate what that now-static system would have provided).

Then, later on, when a ship controlled by the player's faction gets close enough to the saved system (whatever that distance is), you read its information from disk along with the timestamp, then calculate what that system should look like after the passage of time between when it was saved and now. (This recovery process is what would be happening as you're "flying through a wormhole" between systems.) It then once again starts to have an active impact on the systems around it, even though it's still being simulated at a low LOD since you're not looking directly at it yet.

All speculation, of course. No one should be surprised if Josh already worked out this logic before the Dark Days and it's far more elegant than what I described here. ;)

Well, that would only save CPU for systems the player never visits again, no? You still have to do the simulation, it's just bunched up instead of spread over time.
To use your planet position example, calculating positions by moving them in real time or in one big bunch is the same computational cost (unless you do dumb things in one of those, but lets not :ghost: )
Also, is simulating what a system would provide to other systems not already a simulation of the system (albeit it at a lower LOD)?
Warning: do not ask about physics unless you really want to know about physics.
The LT IRC / Alternate link || The REKT Wiki || PUDDING
Image
User avatar
Dinosawer
Admiral
 
Posts: 5447
Joined: Fri May 09, 2014 1:08 pm
Location: Belgium

PreviousNext

Return to General



Who is online

Users browsing this forum: No registered users and 3 guests