Universe generation and persistence of in-game modification

[lwho]

Well, since I suggested we should talk about WIP projects early, I should probably give a good example (well it actually isn't that early).

I'm just working at the possibility to explore systems in-game (i.e. changing a system from unexplored to explored during play). I've already working code in my system_exploration branch, but the more I thought about it, the more I came to the conclusion, that this is only a special case of a much broader problem: Modifying the universe from its randomly-generated form, saving the differences, and re-applying the differences when re-generating the affected part (e.g. the Sector/StarSystem).

I'm not sure which is the better proceeding now:

1. Solving that special case "system exploration" and later generalize from it (so essentially finishing above branch and merging it).
2. Trying to generalize a persistence overlay now and rebuild the "system exploration" feature on it.

I tend to a. as the better is the enemy of the good. Of course, one should keep the more general problem in mind.

I'm already quite tired now, so I will only give a very short overview about what I did so far (this is more the logical order, not the order in which the commits appear):

1. Moved the explored state from StarSystem to Sector::System, since this is a very coarse property of the whole system.
2. Made sure that of each sector there is at most one Sector object. This is important, since if this deviates from the randomly generated/custom system state, we do not want inconsistent information about the same sector. Thanks to fluffyfreak's SectorCache this was actually quite easy, as only a few places still generated their own sector. But this could become messier with threaded cache pre-population of #2604
3. Stored systems that were explored in-game in a static PersistSystemData structure and lookup if a system is stored there, when creating a Sector::System. This will definitely become a problem with #2604 as each Sector constructor needs to access the common data (from potentially different threads).
4. The explored state can be set from Lua on a StarSystem object (which needs to redirect to the associated Sector::System). This redirection doesn't feel totally right, but in my first try, I left the explored state in StarSystem and that didn't feel right, either.
5. I wrote a Lua module that just sets an unexplored system to explored when entering it.

Now, I welcome your comments and questions...

[FluffyFreak]

My recommendation would be to take the sector/starsystem and make a CustomSystem out of it.

Don't keep it in the list of existing custom systems though, instead create a new list of CustomisedSystems.
Then when creating a new StarSystem/Sector search your new CustomisedSystems before searching the existing CustomSystems so that you can overload CustomSystems with CustomisedSystems :)

You would need to save & load these CustomisedSystems.
We might need to add some mutexes in there to handle modifying the lists etc but that might be necessary for my generation work, I haven't noticed anywhere that it might but still... worth thinking about.

[robn]

Right now I'd just allow Lua to flip the explored bit, and then write an onEnterSystem handler that flips it and stores the path in a list. Save and load that list and you're good to go.

We've long had the shell of a redesign for the system generator and modifiable systems for a while. I'm not saying we have to do it this way, and it still needs heaps of thought and fleshing out. It does however incorporate all the ideas and requests we've had over the years.

There's two basic requirements:

• We need to be able to provide the properties we want a system to have to the sysgen and get something realistic. Things like "has a habitable planet", "has a population", "has an abundance of X", and so on. Its too hard to design systems or whole groups of systems (eg factions) using just seeds, particularly when code changes ruin it.
• We'd to be able to add or remove a station or a whole planet, or add minor elements like satellites, mining outposts, etc. We want to be able to modify existing systems in this way on from script for arbitrary story reasons.

The base system itself would be created from parameters worked out at a higher level. Somewhere combination of star type distribution and faction requirements. Each system is then built up of a series of operations, eg ADD_STAR, ADD_PLANET, ADD_STATION, REMOVE_STATION, etc.

The sysgen would simply produce a series of operations. Custom systems another. Scripts could then add their own operations to a system to modify it without having to care too much about how the original system was structured, which allows the base system to change without entirely invalidating the savefile. The stuff added to the base system is all that gets saved.

It might be too complicated - its all about creating and applying deltas. It might be acceptable just to copy the original system and modify it in-place, and then save that, and have the game always use it. Of course then it wouldn't take changes made to the base system. Maybe that's acceptable.

Whatever we do, the system generator needs to be rewritten (or so heavily restructured that it would look nothing like its former self). I've sunk about two months of evenings into in the past, to no avail. It is not an easy thing :/

[lwho]

Don't keep it in the list of existing custom systems though, instead create a new list of CustomisedSystems.
Then when creating a new StarSystem/Sector search your new CustomisedSystems before searching the existing CustomSystems so that you can overload CustomSystems with CustomisedSystems :)

It's important that SystemPathes do not change during this process. I have a feeling that it would be hard to ensure that the system index stays the same that way.

Right now I'd just allow Lua to flip the explored bit, and then write an onEnterSystem handler that flips it and stores the path in a list. Save and load that list and you're good to go.

That means it is explored, when you're in the system, but it does not stay explored when you leave it again. Actually that's where I started with that project ;)

Other than that, it's quite similar to what I did, except that I did the persisting on the C++ side, not the Lua side. Other than that, most code goes into ensuring, that we have no inconsistent exploration state for the same system (i.e. multiple object, where one says it's explored, and one says it's not).

It might be too complicated - its all about creating and applying deltas.

Indeed my first thought was, "that's sounds much too complicated". I think it's premature optimization, when saving the whole object just achieves the same goal. But I have just started thinking over it, so it's only a first feeling.

It might be acceptable just to copy the original system and modify it in-place, and then save that, and have the game always use it. Of course then it wouldn't take changes made to the base system. Maybe that's acceptable.

Indeed, that sounds better. When the universe changes due to code changes (that's how I understand your "changes made to the base system") then savegames are incompatible anyway and a savegame bump is needed.

What would be needed (and that's quite independent from how systems are generated):

1. A way to serialize and unserialize every field of a StarSystem/SystemBody...
2. A map of SystemPath -> StarSystem (probably a refcounted pointer) that is (un-)serialized (could of cause also be broken down to lower granularity, like SystemBodies)
3. When generation of a system is requested, we look it up in the map. Take the one in the map if present, or continue with random generation as usual.
4. Accessors from Lua. As soon, as a system is changed from its generated form, it's put in the persisted map.

Whatever we do, the system generator needs to be rewritten (or so heavily restructured that it would look nothing like its former self). I've sunk about two months of evenings into in the past, to no avail. It is not an easy thing :/

As I sketched above, this could be completely independent of how changes are persisted.

In my experience, while one should have a coarse "big plan" in the head, in most cases it's better to proceed in small isolated steps, instead of a big-bang rewrite. Yes, that results in touching and modifying the same code lines again and again, but it's not as if code lines wear off when touched too often ;) In the end this also results in code "that it would look nothing like its former self" in the end. But it's more evolution than revolution.

Anyway, I need to think about all that a bit. You have given my brain a lot of food to digest ;)

[robn]

It's important that SystemPathes do not change during this process. I have a feeling that it would be hard to ensure that the system index stays the same that way.

I think that we'll need to decouple system and body indices from the relative positions of objects they point to if we start messing around with the structure of systems during the game. Paths need to always point to the same object regardless of what happens around that object.

That means it is explored, when you're in the system, but it does not stay explored when you leave it again. Actually that's where I started with that project ;)

You're right of course. Yeah ok, not so trivial ;)

Other than that, it's quite similar to what I did, except that I did the persisting on the C++ side, not the Lua side. Other than that, most code goes into ensuring, that we have no inconsistent exploration state for the same system (i.e. multiple object, where one says it's explored, and one says it's not).

Yeah, we only ever want one of any system object. That doesn't mean we have to keep them around, as long as we can feed the wanted changes (like "system is explored") into the sysgen when its regenerated.

Indeed my first thought was, "that's sounds much too complicated". I think it's premature optimization, when saving the whole object just achieves the same goal. But I have just started thinking over it, so it's only a first feeling.

I don't really think its optimization at all - there's nothing about it that seems optimal to me :P

Mostly I'm trying to see a nice structure where we can create a description of a system and then give that to something that actually creates the StarSystem/SystemBody objects. So we'd have a RandomSystemGenerator that creates from a seed or other parameters, a CustomSystemGenerator that creates from a description in a file, and it would be possible for scripts etc to layer changes on top of that.

Indeed, that sounds better. When the universe changes due to code changes (that's how I understand your "changes made to the base system") then savegames are incompatible anyway and a savegame bump is needed.

Yes. Somewhat aside from that, I'm working on a new savefile format and supporting code that will have a defined mechanism for upgrading old savefiles and won't require the bump anymore. Its got a few things blocking it but its getting there.

In my experience, while one should have a coarse "big plan" in the head, in most cases it's better to proceed in small isolated steps, instead of a big-bang rewrite. Yes, that results in touching and modifying the same code lines again and again, but it's not as if code lines wear off when touched too often ;) In the end this also results in code "that it would look nothing like its former self" in the end. But it's more evolution than revolution.

I don't disagree in principle. I really did try hard to do this with the current system generator, but found it far too entangled to simply refactor to make it sane. And ultimately I don't think its serving its purpose anyway - its simply too inflexible.

Anyway, I need to think about all that a bit. You have given my brain a lot of food to digest ;)

Good. I hope you pick this up and run with it, because I don't want to ;) Please don't be put off by me saying "this is how it should be" - I have ideas based on my own experiences, but if you make something that works, that's much better.

[lwho]

Good. I hope you pick this up and run with it

Well, I will pick it up for now, but don't expect me to run ;)

That are the first steps I have in mind:

1. Separating generation of sectors and systems from their state. So, I factor out abstract SectorGenerator and SystemGenerator classes and put the current generation code in derived classes of that (I think, we currently have two: custom systems and random).
   This is intended to be a pure refactoring step, i.e. the generated universe will stay the same.
2. Providing serialization code for sectors and systems.
3. Providing the possibility to change stuff in sectors and systems (also from Lua). This step will not allow structural changes (i.e. no adding or removing bodies). Let's keep that for later.
4. Implement system exploration as a prove-of-concept for the mutability of sectors.
5. Now we can start thinking about adding other generators (such as your envisioned top-down generator).

There's one related thought, I was pushing around in my head: Would it make sense to push universe generation out to Lua? On the one hand, it would be cool to have moddable universe generation, on the other hand I'm not sure if that would be fast enough even with aggressive caching in the core. Also I don't know if Lua and multithreading are working together well. Would something like the multithreaded sector generation in #2704 still be feasible?

[robn]

Looks fairly sane.

Separating generation of sectors and systems from their state. So, I factor out abstract SectorGenerator and SystemGenerator classes and put the current generation code in derived classes of that (I think, we currently have two: custom systems and random).

This is pretty much exactly where I started last time, before it killed me. If you're in need of inspiration/warning, robn/starsystem-refactor may be of interested (old branch from over a year ago). Though ignoring it and coming at it with fresh eyes wouldn't hurt either.

There's one related thought, I was pushing around in my head: Would it make sense to push universe generation out to Lua? On the one hand, it would be cool to have moddable universe generation, on the other hand I'm not sure if that would be fast enough even with aggressive caching in the core. Also I don't know if Lua and multithreading are working together well. Would something like the multithreaded sector generation in #2704 still be feasible?

Threading Lua isn't really easy; you can't do it from inside Lua. You can put a separate lua_State on each thread, but then they don't communicate with each other (which isn't wanted here necessarily). Then there's something like Lanes, which I haven't really looked in to.

Right now I'd say just implement it in C++, but make it modular. If its obvious later that some parts can be moved to Lua, we can look into it then.

[lwho]

This is pretty much exactly where I started last time, before it killed me. If you're in need of inspiration/warning, robn/starsystem-refactor may be of interested (old branch from over a year ago). Though ignoring it and coming at it with fresh eyes wouldn't hurt either.

Do you remember any major blockers? I think I will look at your original work, when I've a more or less complete concept in my head. That way, it doesn't influence me while finding my solution, but maybe avoids me doing something stupid. Ideally, combining my and your solution may lead to "the better parts of both".

Right now I'd say just implement it in C++, but make it modular. If its obvious later that some parts can be moved to Lua, we can look into it then.

It was just a crazy idea. I hoped someone would talk me out of it, when I mentioned it, so thank you for doing this :D

[Ittiz]

Most of the code I've been looking at changing is the planet generation code itself. One thing I think this game needs, and should be easy to add, is rogue planets. Sure there are brown dwarfs, but there are ten times the number of planets free floating around in space. Not sure how easy they would be to add without messing everything else up though, but this game hasn't been released yet so I don't know how big of a deal that really is.

[robn]

Do you remember any major blockers? I think I will look at your original work, when I've a more or less complete concept in my head. That way, it doesn't influence me while finding my solution, but maybe avoids me doing something stupid. Ideally, combining my and your solution may lead to "the better parts of both".

The main thing I was trying to do was create a decent set of abstractions through the system generator. Right now its a deeply recursive mess that relies on being able to fish around in a big ball of effectively global state. I couldn't find a way of incrementally building an abstraction that worked.

That said, I was coming at it without a really good idea of what I wanted at the end, and I think I was trying to build with live modifications possible as well. I probably bit of more than I should have.