Making A Grid With Extensive Cell Interactivity

News & General Discussion
1

I apologize if this is the wrong forum, but I have a somewhat broad question and I wasn’t sure where to put it. If a mod knows of a better place, by all means, send it there.

I’m trying to make a cellular automaton in Unity. To do that, I need to be able to make a grid of variable size (x number of columns, y number of rows) where each box or “cell” within those has things happen to it over increments of time. So I need each cell to act as an independent unit with some function running on that specific cell (that same function is applied to all cells simultaneously).

Additionally, cellular automata involve something called a “neighborhood,” which is the set of cells surrounding a single cell (the size of the neighborhood varies). Therefore, I need a way for each single cell to be able to reference some arbitrarily specified range of cells around it and gather information about them.

In addition to this, in some cellular automata, the things being studied (or, the stuff inside the cells) actually move around. One example is a number of gas molecules with a gravitational force upon them (they will trend down towards the bottom of the grid). Thus I need a way to have the contents of a cell actually move from one cell to another (with the necessity of being able to recognize if a cell is already “filled” or not, at which point that cell is unavailable for movement).

Another concern: this needs to be large. Some cellular automata have thousands and thousands of cells on a grid, each one independently iterating some simple set of rules. I’m currently using one designed for DOS (I have to use DOSBox for it to even run on my Windows 7 PC), and I regularly use a 2500-cell grid. I’d actually prefer to use a 10k-cell grid or larger, but it’s too slow to be very effective for rapid simulations.

I have only just begun looking at the different grid systems people have used in Unity, but I’m not aware of any that allow all of these different things. I know some, for example, simply create a bunch of cubes aligned in a grid, but I don’t know how speedy that would be for 10,000 or more of them.

Does anyone have any suggestions for where to start? Many thanks.

2

Probably a scripting forum question rather then a design question.

I’ve built similar systems by simply using a 2D or 3D array. Then simply iterate across the entire array with a for loop. I use a double buffer system, this helps keep the calculations clean. You’ll also need to deal with edge cases, as in the actual edge of the array.

For visualization you can write the contents of the array to a texture.

Here are some of the results of a previous attempt. The project use a 100x100 grid (so 10,000 cells). There were three different ‘substrates’ tracked for each cell. There was a diffusion model for each substrate. There were moving ‘agents’ that consumed and produced substrate in each cell. And since I’m a chemical engineer at heart the whole thing was mass balanced. (I did cheat and ignore thermodynamics). The whole thing ran fine in Unity.

Unfortunately the project was my harsh lesson in remote backups and version control. So I can’t share the code with you.

3

@Kiwasi is right, this is a scripting question, not a game design one.

Still, it’s a topic that I have a lot of interest in too. The PixelSurface class which I submitted to the Asset Store (still waiting for Unity to respond!) almost three weeks ago would be very helpful for the display part; it’s smart about not updating chunks where nothing has changed, and so ought to be about as efficient as you can get with the texture approach. You can read more about it in this thread.

It includes easy access to neighbors and also what I call “live pixels,” which move around on the grid. What it does not include is a double buffer of the cell states, which as B.M. mentioned, is pretty important to keep the calculations clean.

I’ve toyed with the idea of making a cellular automata asset, that would make this sort of thing easy… but I don’t know that there’s much demand for it.

4

Out of curiosity what do you use them for? What would be the general use case in games?

The one I built was literally designed to simulate cells and diffusion in a microbiology simulation game. But that hardly seems a common use case. There can’t be that many biochemical engineers building evolutionary simulators.

5

As far as I’m aware, most forms of cellular automata don’t do this. The cases I know of iterate over the entire grid per frame and double buffer, where it’s writing to a new frame while preserving the old one. It might be possible to divide up the area into chunks that can sleep and be woken up by neighbors.

Level generation is the one I usually see. I think I laid eyes on a siggraph paper once that talked about using it for smoke/fire/air/particle dispersal. Graph theory in general always seems to have some very weird uses that end up being everywhere.

1 Like
6

Right. You can simulate all sorts of obvious things with it, like spread of fire in a forest, diffusion of pheromones in an ant sim, and visual effects like flames. Then there are less obvious applications, like using them to control monsters (I once read a really nifty article on applying this to ghosts in Ms. Pac-Man — they were basically following scent trails, and it produced surprisingly complex yet efficient behavior). @RockoDyne 's level-generation example is another good one. But for those sorts of things, you don’t actually need to display the CA, except maybe for debugging.

Then there’s stuff like Wireworld, one of my favorite CAs ever. But no, I don’t have any practical application for it; I just think it’s cool.

I guess if you had some sort of sandbox game, you could use it to let players lay out circuits, Redstone-style… but then, if you’re making a Minecraft clone, you’d use the same CA concepts but a completely different implementation.

So yeah, I don’t see much market for it in general, which is why I’ve never bothered to code it up.

1 Like
7

Got ya. Come to think of it, I have seen a path finding solution that worked with vector fields on this sort of principle. And my infinite terrain engine vaguely followed this pattern.

Back to the OP, you definitely want to store the data in an array and iterate across it. Using 10,000 GameObjects to run the code in update will not work. It might also be worth stealing some principles from data orientated design.

1 Like
8

Thanks for the clear suggestion about the array. I was considering to use a list of objects that all have pointers to their neighbors but that probably makes it more complicated than neccessary and doesn’t really benefit me. I don’t think an asset for this makes much sense either, except maybe to show some examples to learn from. But I suspect there will be enough of that on the internet if someone really needs it.

I want to use it to generate city-like industrial levels and the concepts I have planned so far will do the computation on different steps and different grid resolutions. E.g. define the most important points of interest in a level first, with a cell size of about one screen (the game has isometric perspective). Then make the adjacent screens better guarded by enemies for example and generate some data for the next step. Then each of the cells gets turned into a new grid that is generating blocks for houses etc. and then I might increase the resolution once more and scatter small detail objects, decals etc. based on the data of the grid. E.g. roadblocks only get placed on streets and take their direction into account, crates tend to cluster up next to walls or on bigger open ares etc… I’ve made hundreds of screenshots of industrial areas with google maps and there are some interesting patterns to see.

One of the parts I haven’t put much thought into yet is how I could visualize what’s going on during development. I mean I could just spawn cubes and give them different colors and scale, but I’m not sure if the performance for that would be good enough to be viable. Thoughts?

9

Well, at the risk of seeming self-serving, I would suggest you use PixelSurface for visualization. Just iterate over your array and set the color of each corresponding pixel (using colors to represent states in whatever ways you want). This will perform much better than hundreds (thousands?) of cubes.

Unfortunately PixelSurface has been languishing for three weeks in the “pending review” state at the asset store, but if you PM me your email address, I’ll just send you a copy directly.

Or, you could just spawn cubes and give them different colors and scale. :slight_smile: If it’s just for debugging, performance probably doesn’t matter all that much anyway.

10

Thanks a lot for the offer! But I think the advantage of having 3D objects instead of a texture outweights the benefits I could get from any texture solution. I did a quick test because I was curious and it seems to take about ~1 second per 10k instanced cubes with random color each. And that was probably done in one of the least optimized ways possible (every cube was a prefab with his own script component to change the color, no pooling, and I just stuck my code into Update() and tested how many fps I still get, so it includes removing the cubes from the previous step).

1 Like
11

Many thanks for the tips! Gives me something(s) to think about.