[piratepad link]

Pad archive as of Oct 26 2011 00:59 UTC

We require each SBody to have a unique ID of some sort. At the moment, this is SystemPath. SystemPath consists of <sector XYZ, system index, body index>.

System generation

System generation is hierarchical, based on sector XYZ + universe seed (is this right? just an educated guess I haven't grappled with the relevant code to confirm this yet). This means that given a universe seed + a sector XYZ, you can do sysgen for that sector. Given the way SystemPath works, I also assume that generation is split into a two-level hierarchy. That is, given sector XYZ + universe seed you can generate a bunch of systems in that sector (names + locations), and then given <universe seed, sector XYZ, system index> you can generate the SBodies in that system.

robn: Yes, pretty much right.

As it stands, SystemPath is an output of the system generation code. That is, given a SystemPath to an SBody you cannot generate only the information for that SBody: you have to generate all the systems in the sector so you can look up the right one from the system index, and generate all the bodies in the system so you can look up the right body index. As far as computational and memory resources are concerned, I have no particular problem with that -- computation is no problem as long as system info is cached and given how much RAM computers have nowadays that system info cache is not a problem.

Correct.

However, it also means that there's gotta be some careful book-keeping to ensure that SystemPaths are unique in the face of modifications.

There is no such bookeeping right now. If we need to generate an entire system to get info for a specific body, we do. The system cache helps with this but there's nothing special about it - its just a cache.

Proposal

Rather than SystemPath being an output of the generation code, make it the input to the generation code. Rather than being <sector XYZ, system index, body index>, it becomes something like:

<sector XYZ, system seed, body seed 0, body seed 1, body seed 2, body seed 3, body seed 4, body seed 5>

Two things have changed: 1) index has become seed, 2) body index has been split up into multiple levels. The levels correspond with levels in the SBody tree for a system. The individual components of the seed needn't be particularly big -- maybe 8 bits per body seed level -- so the overall size of SystemPath can be kept pretty much the same as it is right now (ie, it's still light-weight enough to copy around and use as a value type).

To generate an SBody, you have to generate its parents, probably all the way up to the sector level, but you don't have to generate any of its siblings. To be clear, an individual body seed value is not enough to generate an SBody. SBody generation must still be hierarchical, for two reasons: most importantly, attributes of an SBody will be affected by attributes of its parent, so you have to generate the parent first, and secondly as a more minor point, if you wanted an SBody to be generated from a single seed value (as opposed to the aggregated and processed seed values along the whole chain of universe seed -> sector XYZ -> system seed -> body seed) then you'd need plenty of bits for the body seed, so SystemPath would have to be much larger.

The only trouble I see here is that the sysgen algorithms (as I understand them) actually do require siblings to be generated - at least some of them. Part of how it works is that there's a fixed amount of mass per system (based on star type, sector density, etc). Each body created consumes some amount of that mass. So if I'm interested in, say, Foo a 5, I need Foo a 1-4 to be generated first before I can know how much mass is available for 5.

Of course, algorithms can be changed. This is a killer right now. Algorithms can be changed, but this won't fly if they have to be made worse: portioning out total system mass sounds like a good thing to do, I wouldn't want to drop it. It could be done probabilistically to get somewhere close without needing the siblings, but I'd be worried that variance would be too high. Another possibility would be to shift any information like that up a level -- that is, decree that sysgen has to be able to generate info for a SystemPath without generating the siblings, and any information from the siblings that is needed gets pushed up to the parent so that it's available. But I'm not sure that would work (certainly not sure it'd work for all plausible cases). The current algorithms try to implement current theories about how starsystems are created from a big pile of accreting matter. In terms of changing algorithms I only meant that there might be a way to produce convincing results with a different algorithm. I'm not a math guy by any stretch though; I wouldn't even know how to begin.

The benefit of using SystemPath as a hierarchical seed value to drive sysgen are: 1- It automatically makes SystemPath a galactically unique identifier for an SBody, independent of any changes that have been made to siblings. 2- sysgen can be pruned more finely: that is, if a Lua script decides to delete an SBody + all its children from a system, then generation of all the other SBodies is unaffected and generation of the deleted one can just be skipped. This works at any level of the hierarchy. 3- it makes it easier/faster to look up info about a specific body

How it works with custom systems

Most of the code should treat the galaxy as a black box database, and ignore the virtual (procedural) aspects of it. The galaxy DB keeps multiple mappings from SystemPath -> Sector/StarSystem/SBody: some of these mappings are just caches used to avoid regenerating information all the time, others store information for Sectors/Systems/SBodies that Lua has modified.

If Lua scripts don't use any custom system functions, the entire galaxy will be generated procedurally. Lua isn't given any special way to "suppress" generation at any level, it's just allowed to request Sector/StarSystem/SBody objects for a SystemPath, and either modify them or replace them completely. In practice, replacement will suppress procedural generation for that SystemPath because any time that the information would be generated it'll just fall through to the modified-system table and grab the replacement object instead.

I like that. Obviously I haven't thought it through in detail yet, but the concept sounds nice and general.

How do scripts add new bodies?

One thing that's somewhat tricky about this is how to cope with adding objects. This is a more specific part of the problem of how to know which SystemPaths are valid (given that as seeds they could all generate information). My simple solution to this is that each object has to know what SystemPaths are valid children (though technically it wouldn't have to store the full system path for its valid children, only the set of valid next values in the SystemPath tuple).

Sectors can't be added because their seed values have real meaning (XYZ coords). If a script wants to add a new System or SBody, it'll have to be given an unused SystemPath, replace the information for that SystemPath with its new object, and modify its parent to add that SystemPath to the set of valid children. As a variation on this some subset of the values at each level of the SystemPath tuple could be reserved for use by scripts.

This isn't an ideal solution, and is quite important since adding new systems/sbodies is a big part of what custom system scripts will want to do, so suggestions for better ways of handling this would be welcome.

So to sum up, to add a sub-body you first need to obtain a parent body and add to that. That does not seem at all unreasonable. You have to obtain the parent, but the odd part is that you have to take a SystemPath that sysgen could turn into a real body (but never has because it wasn't on the list of valid paths) and then replace it. It just feels kinda odd because it's a replacement not an addition. I think there's two modes. One where you want to update an existing body (change its properties but not modify the hierarchy), and one where you want to add a new body/hierarchy. I suppose the only difference with the current system is that in this proposal, all SystemPaths are potentially valid -- it's just that some (actually a lot) are never accessible because they're never linked from their parents. In either system there are of course a finite number of possible SystemPath values (finite but huuuuuuuuge). Yep. I think this works. Make everything a replacement - yes, it feels odd, but it is the right thing. Some pseudocode:

b = Get(x,y,z,si,h1,h2) -- first time "generates" it, later times pulls from cache b.property = value b.Update() -- commits it

Now I look at that its clear that the sysgen algorithms will have to change quite radically. If you had a fully-generated system and you requested a path that does not exist within it, then it effectively has to conjure up a pile of mass from nothing. On the other hand, a fully custom system overrides all this anyway so maybe it doesn't matter. The onus is on the system designer to make it look "real". In reality they're probably only going to add a space station anyway. In the case of adding things there's nothing we can do w.r.t. total mass -- it's just going to increase. Obviously we can't take mass off the other system objects when a script decides to add a station, or even if it decides to add a whole moon (or DEATH STAR!). And yes, for fully custom systems it shouldn't be a problem anyway.

How much will the existing sysgen code have to be rewritten?

I don't know. This is my big concern with this proposal.

I think it could be written without changing any of it, as we're really talking about an interface. It will mean a lot of unnecessary generation which we'd likely want to remove long-term, but initially we might be able to get away with few changes.

I agree, if the interface is acceptable the best way to proceed is to retain current sysgen & SystemPath and code up the Lua API and galaxy DB API, with whatever book-keeping is necessary internally. Which I believe actually matches exactly, or almost exactly what your work so far in new-lua-custom-systems does anyway.

Oh dear, so I've unconciously decided that my way is best!

Do you think the seed hierarchy business to replace the body index will come at a later stage, or do we build it in from the start? We could make a kind of compatibility layer if we wanted, bodyindex->real systempath lookup. Oh, while I think about it, right now individual custom bodies can have their own seed that is contributed to the current system seed. That might be usable here. It is really only meant for fully-customised systems though (which is kinda the only choice you have right now anyway).

Hierarchy to replace body index is contingent on everyone being happy that sysgen could be implemented well enough based on that, which I'm not given your and Ae's comments. Could go half way and use system index -> system seed, but retain body index as it works at the moment.

Well as I noted in my original ramble somewhere, we can keep using body index provided we don't reuse them when one is deleted. So keeping slots in StarSystem::m_bodies there but with TYPE_DELETED or something like that might be an option. Doesn't get the flexibility you're looking with making SystemPath the input though - its really just keeping the current system.

As I noted earlier, the only thing sysgen and the user are forced to have as unique (well almost unique for sysgen) is the names. If a seed was based on the names of the bodies before it .

Names are not unique, and are not required to be.

(we could force it, if it was a custom system? and the combined name from the tree of names is likely to be unique, unless someone made two moons the same)

We could force it, but I think the goal here is to have as few differences as possible between "generated" and "customs" sectors/systems/bodies. So I'd rather avoid placing restrictions on things if at all possible.

With regards to heirachy, the main obstacle is the mass and the amount of planetary disc radius left ..the planetary disc radius is affected by all sorts of considerations, and probably will have the roche limit there as well.

Sounds like all SBodies do have to be generated in one process.

Yes, unless you're smart enough to make it look convincing some other way.

Individual components of the sysgen algorithm might well be duplicated to some extent, but I think requiring generation of SBodies to be separable will be a repeated pain in the ass as far as getting sysgen to behave the way we want it. I'd rather take the hit of slightly trickier bookkeeping/a slightly less "neat" system than make sysgen rely on hard to tweak maths.

I tend to agree. We only need to get the bookeeping right once.

Yep, and it probably won't turn out to be that hard anyway as long as we can hide it well enough behind a single access point (which we should do anyway).

Agreed.

Well it is the fallback, but how to uniquely id a body?

SystemPath.

Using the deleted tag, which might place a more severe restriction on modification especially if John implements his rts stuff which will create a huge list of deleted items. RTS is not going to be deleting planets very often. I doubt it'll even add or delete starports much.

Starports?

a) RTS doesn't exist and may never. b) It could be implemented with some kind of sparse data structure - it doesn't have to be a sequential list with big holes in the middle. Not a concern imo.

hmm, what if we created an rng based on the sector/system..rngs are guaranteed to have a sequence of length 2^n-1 or similar before they repeat. and simply assign unique ids based on that. The final state of the rng is saved, and if new bodies are added its incremented.

That doesn't gain you anything. You still have to map from body ID -> SBody, or body ID -> deleted. It just means you'll never have easy sequential IDs.

What's wrong with keeping a table? entries can be removed if deleted,

Nothing's wrong with keeping a table. The point is that a table works exactly the same whether the keys you use come from a sequence of 1-N or a randomised sequence within the set 1-N. Using an RNG to generate the sequence of body indexes doesn't change anything.

The reason it was used was to eventually not endup keeping a huge deleted list, when something gets deleted the table entry gets deleted too?

You can have exactly the same table and use sequential body indexes as keys. That doesn't stop you from deleting entries.

Ok fair enough.

Well, I don't see why it wouldn't work, so it seems the best soln..only concievable base that hasn't been discussed is partially procedural stuff, which is implementable but trickier.

As described at the moment, partially procedural corresponds to a script getting a procedurally generated object and modifying it somewhat. There'll be a bit of data generated needlessly, but I don't see a really good way round that in cases where separate bits of data affect each other.

The type of thing i was thinking was adding a few moons then letting the sysgen do the rest.

Oh, I see. Yeah, that's worth thinking about. I guess when a script creates a new object it'll have to have the option to ask for it to be initialised by sysgen, given a seed value (or maybe the seed just comes from the SystemPath of the new object). That'll need some flags or tweak values to give finer control though (e.g., enable/disable generation of starports and so on). Generation could be split from creation, too I suppose. So objects get one or a set of methods exposed to Lua that tell sysgen to (re)generate (some of) their properties.

It mostly requires just rearranging functions so you can tell sysgen here's a planet and a moon, generate starports and other moons. I'd imagine most custom system designers will be lazy about the minor details.

Right.

The mtrand has , what 6 state variables of type int , or something to that effect if the sysgen didn't have disc size / mass considerations , it would be possible to derive a seed struct directly from the mtrand state registers.