CA implementation architecture planning

[7yl4r]

@InfiniteSearchSpace has raised some issues while working on the CA implementation and there are some details we need to figure out.

The main issues I think need to be solved are the following:

1. Cell Data Storage: a. Data Type (Bool, Int, Float, RGBA) b. CPU-side storage, GPU Texture storage, Mix of both c. How do we access and assess this data? 'Who' can do it?
2. Rule Execution: a. Are rules local or global on a single cell-space layer? b. How do we run rules on a world larger than the screen size? Minecraft-like chunk systems? c. How do we handle multiple different rules? In one layer? Each in their own cell layer? d. What speed and resolution do we require? e. What happens 'off-screen' f. Are the rules run on the CPU, GPU, or as a combination? How do we handle competition between rules? g. What happens when a CGoL glider wants to travel further than some limited distance? (out of screen, out of global field (wrap?), out of local field, ...) h. How many rules, of how many family types are we wanting to work with?

[BrianErikson]

1. Cell Data Storage

A, B I'm a huge proponent of CPU-side storage, probably as a Byte array. Boolean wouldn't give us enough flexibility if we wanted to add attributes to certain cells, and they both take up the same space in memory.

How do we access this data? Storing it in the CPU solves this question pretty succinctly I think.

I have no experience with CAs really, so I can't give an informed answer to the other issues.

[7yl4r]

Here is my opinion on some of the issues raised in by (2):

a. Are rules local or global on a single cell-space layer?

Maybe both? Some are local, some are on a shared layer. Local-layer would be cosmetic only, wheras we could use the unified layers for interactions.

b. How do we run rules on a world larger than the screen size? Minecraft-like chunk systems?

Maybe, I think we only want to run what is on-screen or nearly on-screen. Ideally we have some dynamic saving/loading of the last seen state, but I think we can get by without it as well.

c. How do we handle multiple different rules? In one layer? Each in their own cell layer?

I'm not sure how to handle different CA in one layer, but this is how we may want it to look at least. The vyroids will change rules as you progress through the game but should maintain a similar visual appearance and interaction (colliders, etc).

d. What speed and resolution do we require?

I'd put bare minimum resolution at 60x80 (10px/cell) and minimum speed at 1fps in three layers.

e. What happens 'off-screen'

Nothing! =) Retro-rpg style. That'll be easiest, right? We probably will want to have a "buffer" around the screen where cells get loaded and start cycling before showing to the player though, but this is not strictly required.

f. Are the rules run on the CPU, GPU, or as a combination? How do we handle competition between rules?

I suspect we'll do best with a combined approach here. I'd like to keep things limited enough that we don't have to worry about competition for resources, there should be enough to go around.

g. What happens when a CGoL glider wants to travel further than some limited distance? (out of screen, out of global field (wrap?), out of local field, ...)

Fugget about it.

h. How many rules, of how many family types are we wanting to work with?

I'd like to start out with about three and then add on more as we go into different regions of the game or start adding more features. I haven't played around with CA enough to have any great suggestions, but we're looking for rules that look cool (at low resolutions) and ideas on how they might fit in. Then I want to try to make it happen. Some random ideas: i) cyclic CAs for cosmetic use in machinery/tech, ii) still-life/oscillators to be used in scenery, iii) fractal-type growth for "plants", iv) vyroids! rules which start off with a small spawn and then spread across the landscape.

In addition, I'd also like to work in some CGoL for historical significance and familiarity.

[InfiniteSearchSpace]

@BrianErikson,

(1a) By bool I meant bits, or whatever the most atomic unit of storage is. I personally don't like the idea of CPU storage, as that forces us to do one of these: (1b)

• Cart the full data to and from the GPU for shader rule execution for every processed frame update (or group, if several frames at once)
• Use the CPU to run the rules, which will cause awful fps hanging on heavy rules/slow HW, or at the least suck up a majority of CPU time leaving us with very little overhead to work with for the game itself.

At least, those were major problems I encountered in the CA generation apps I've written.

(1a) Something to consider is that most of my experience with CA have been with 1/0 on/off cell states, but there are many rules that use more states than this, or even the full state-space of a Float. A good simple example is cyclic automata, or Reaction-Diffusion systems. I have also had some great success using signed-integer-cells for things like storing thresholds and pre-made state-transitions for various cell behaviors.

(1a, 1b) If we use a simplified storage state that natively stores only 'black and white' (or a very limited set of states to assign colours), we'll have to colour the cells with post-generation shaders or with the CPU(SLOW). Using shaders with RBGA formats can solve this by allowing us to work directly on colours, but that comes with its own minor issues (colour expectations, typically associated with the neighborhood assessment stage of a rule)

[InfiniteSearchSpace]

@7yl4r,

(2a) global/local layers

Maybe both? Some are local, some are on a shared layer. Local-layer would be cosmetic only, whereas we could use the unified layers for interactions.

Local layers that are cosmetic procedural CA would be a bit wasteful of device resources, but it would mean we could be far less strict on the interactions, allowing us to take 'simple sloppy shortcuts' etc. A good trade-off IMO if local non-or-semi-interacting CA are desirable.

These can probably be CPU generated at a slow rate with no issues, but we'll probably want a dynamic scheduler so we don't have 100 assets accidentally trying to update their CAs all in one frame, and doing nothing for the next 29 frames.

(2b) Chunk System, off screen stuff

Maybe, I think we only want to run what is on-screen or nearly on-screen. Ideally we have some dynamic saving/loading of the last seen state, but I think we can get by without it as well.

This actually depends on the speed of CA generation. The actual cell states don't need to be conserved if the rules/rule locations are preserved and they run above ~15ish fps. CA are somewhat indistinguishable, and the player will likely not notice, or be bothered if we reseed things just off-screen. If it runs much slower, or if the specific cell configurations have a large impact on the player, then we will want to preserve the states, and data storage becomes an issue. Random emergent number-like systems are not so compressible.

(2c) Multiple rules, one layer

I'm not sure how to handle different CA in one layer, but this is how we may want it to look at least. The vyroids will change rules as you progress through the game but should maintain a similar visual appearance and interaction (colliders, etc).

I have a couple of ideas of how this could work. They're not so GPU shader friendly (unless the rules are heavy), and would probably work better on a CPU implementation.

First idea is, every cell has one, or several Rule-ID and Neighbour-ID values, where the value of that ID determines the neighborhood/number ranges to act on. It'd have to be somewhat dynamic, as many rules have several coordinate neighbourhoods and several 'check-num-range>act' parameters that must be executed in order.

Second idea would be to have a "blank" 'OmniRule' that is given parameters like the cellspace to act on, the coord-neighbourhoods, the rule-actions for those neighbourhoods. Essentially, One rule to rule them all - a Tabula Rasa every frame.

(2e) off-screen

Nothing! =) Retro-rpg style. That'll be easiest, right? We probably will want to have a "buffer" around the screen where cells get loaded and start cycling before showing to the player though, but this is not strictly required.

Hm, we could actually do something neat to give the player a sense of CA cell permanence - taking a lead from the heavily procedural game, No Man's Sky: Have a static random seed for the whole game world & all the chunks, so if a chunk is unloaded and reloaded, it would play out the same way - until the player interferes or some other nondeterministic interaction takes place.

(2f) CPU & GPU resource management

I suspect we'll do best with a combined approach here. I'd like to keep things limited enough that we don't have to worry about competition for resources, there should be enough to go around.

CA are always hungry for more, More MORE! :P More resources = more complexity usually.

(2g) CA Boundary errors/handling, Edge cases

Fugget about it.

Eh? O_o

(2h) Families and Diversity

we're looking for rules that look cool (at low resolutions) and ideas on how they might fit in.

That's tougher than it sounds, at least with 2-state cells. The smaller neighbourhoods are very prone to simple crystallization or quick deaths, and very few have interesting behaviors.

Some random ideas: i) cyclic CAs for cosmetic use in machinery/tech, ii) still-life/oscillators to be used in scenery, iii) fractal-type growth for "plants"

Once the CA engine is sufficiently developed, we will turn it into a CA creation/discovery workshop tool, and then you'll finally have an abundance of CA assets to work with (In other words, delay those until the CA engine is mature).

For iii) 'plants', probabilistic growth models and diffusion-limited aggregation are what you're looking for.

Users could also have access to this sandbox, and use it to customize a 'house' or even the game world directly. Custom levels, tricky player-made gauntlets, art, etc.

vyroids! rules which start off with a small spawn and then spread across the landscape.

Got further info on what makes Vyroids different to 'typical' CA? (most of which replicate in some manner)

In addition, I'd also like to work in some CGoL for historical significance and familiarity.

Of course! For the moore neighbourhood with 2-state cells it's probably the 'perfect' configuration of all possible simple rule configs.

[BrianErikson]

@InfiniteSearchSpace

Cart the full data to and from the GPU for shader rule execution for every processed frame update (or group, if several frames at once)

This is not a problem at all. Any decently-composed piece of 3D geometry is going to be vastly more costly than a 2-dimensional array that would be no larger than 1000x1000. I think we're wanting the CAs to render far larger than the size of a pixel on the screen, so you'd only be able to show 200x200 at most anyway.

Use the CPU to run the rules, which will cause awful fps hanging on heavy rules/slow HW, or at the least suck up a majority of CPU time leaving us with very little overhead to work with for the game itself.

I'm aware of some optimizations for CGoL that make it far less costly to compute (rightfully so), such as HashLife which stores cells in a QuadTree. Would this be unreasonable to implement?

I'm just concerned that the interaction between the player and the CA layer is going to be extremely limited and inflexible if we keep it on the GPU, especially since this is supposed to be an RPG. I guess we need to figure out what we can't do GPU-side, and then decide if it's worth it.

[7yl4r]

I think I derailed this conversation a bit through a lack of topic focus. Sorry about that.

Let's talk/worry specifically about the midst important CA first: the vyroids. Furthermore, I think we can focus on the first "species" and then talk about connecting in others to the same layer, cosmetically or programmatically.

[BrianErikson]

So, to get this straight, the 'layers' we want are:

• Cosmetic (On a per-entity basis)
• Dynamic-Onscreen interaction
• Static-starting seed layer

The interaction we're looking for:

• Player-caused erasure of CAs on the dynamic layer via weapons
• ??
• ??

I feel like the player's valid interactions with the vyroids is a pivotal part of how they should behave for gameplay reasons. What makes vyroids unique from a standard CGoL implementation?

[7yl4r]

What makes vyroids unique from a standard CGoL implementation?

I think the primary difference is the rules used. Vyroid implementation need not differ much from other CA implementations aside from the interactivity.

the 'layers' we want are:

• Cosmetic (On a per-entity basis)
• interactive (collide-able)

The "seed" layers are not a required feature, but a means to accomplish spawning cells into the above two layers.

The interaction we're looking for:

• destruction via weapons
• collision with player/buildings damages player/building

Perhaps it will benefit us to break out just one of these pieces to focus on.

[7yl4r]

My biggest question at this point I think is "where do we put the global CA state arrays?" I think makes sense to define each entities interactions with the CA layer(s) as components, but the rendering is a global action which should be put on the scene itself. I think this means that a lot of this code will go into an entity which is added to the scene (in Scenes/Test). Does that sound right?

[BrianErikson]

That's the way I'm leaning as well. I think at this point we just need to start with an implementation and revise it as the need arises

[7yl4r]

Basic implementation in progress on #34

[7yl4r]

This discussion is stale enough that I'm going to close it for now. There is certainly room for improvement on the current implementation, but that should be addressed in another issue.