Complex Shader Life 0.1; I'm sure someone can do better

So, inspired by redacted and @Andrew_Stacey, I decided to try using Stacey’s GameOfLifeshader to do something more complex.

And I failed! :slight_smile:

To be fair, I think I succeeded in principle. My main frustration was that, using regular drawing tools and lua, in any simulation I tried to make the draw cycle would slow down drastically before I could get even a hundred organisms on screen. I wanted something that could have hundreds of organisms and be fast!

Since that’s just what Stacey’s GameOfLife shader does, I set out to hack it, and I have. Mostly.

I set up a system whereby the mechanic of Stacey’s GameOfLife shader can model more complex behavior. Here’s how it works:

Stacey’s system uses two different shaders; a game logic shader and a pretty-for-the-world shader. The game logic computes what happens each turn and the pretty shader makes it pretty colors.

In my version of the logic shader, the texture is broken into series of a 2-pixel-by-2-pixel grids. Each pixel is used to store different information:

V M
D D
V - visible color - this is the color the user will see in the visible shader
M - movement data - this color tells the logic shader whether or not this grid is an organism, and what direction it will move
D - these can hold different data, but I didn't get far enough to configure them to do anything

Right now the way it works is that the V pixel is the only one allowed to have any red in it at all, and the pretty shader just goes along, reading every 2x2 grid and looking for the pixel with red in it. Then it draws that color for all four of the positions. Right now the “ground” color is a green with 0.004 red in it, and it doesn’t look red at all. The obligation to have a little red doesn’t really constrain the possible color range.

The game logic cycle is all about the M pixel right now. Most of the 2x2 grids have no data in the M pixel, and they get drawn green. But when the logic encounters an M pixel with data, it puts a solid red color in the V position. So when you run the project you see red blocks moving against a green background.

Right now the M pixels only encode movement instructions, and only two kinds. The creatures can move left, and diagonally down and to the left. The whole thing works by a system where one kind of marker tells the logic where to draw the other kind of marker, and vice versa. So markerA says to the logic, “hey, put a markerB to the left of me,” and markerB says “hey, put a markerA down and to the left of me.”

Also right now: the world is 20 pixels by 20 pixels. I way enlarged it so I could see what was happening. But I believe it can scale up to thousands of pixels fairly easily.

It’s very primitive, though I think there’s lots of potential. I think I also ran up against my programming limitations because I’m sure someone else could do the same thing better in 1/2 the code. I would love it if anyone with better skills could make this work more efficiently and actually make the little critters do something cool.

It’s not much to look at right now, but with the help of some more capable programmers, it could be an awesome way to rapidly model life simulations with hundreds of organisms!

Here’s the code:

https://gist.github.com/GlueBalloon/67fd3f00b927257861e2

I ran the code but I’m not really sure what I’m looking at. It hurt my eyes though! :stuck_out_tongue:

in any simulation I tried to make the draw cycle would slow down drastically before I could get even a hundred organisms on screen.

Are you talking about having lots of little sprites flying around? You should be able to have a few thousand flying around before you see FPS drop, as long as you draw them right. The trick is to have all the objects as rects on a single mesh, move them round with setRect, then draw the mesh with a single draw call. For drawing lots of similar objects this is much, much faster than using sprite, or translating and rotating a mesh then issuing a draw command (on an iPad Air, I can get around 3000 20x20 rects flying around at 60fps). If you search the forum for mesh profiling or mesh speed you’ll see a number of tests that people have done so you can experiment with different ways of drawing.

The reason why, I believe, is that the bottleneck is the CPU talking to the GPU, so the key is to minimise, as far as is reasonable, the number of draw calls you make.

In other words, a shader might not be the best way to go with this, though its hard to tell what you’re after at the moment. What do you see the graphical parameters of the project being? ie how big do the blobs have to be (in pixels), how many organisms do you anticipate there being (is 3000 too low a ceiling?), does the FPS have to be 60, etc?

This thread:

http://codea.io/talk/discussion/6005/what-is-the-most-efficient-way-to-draw-lots-of-meshes

Also this (this is the one that I get 3000 rects at 60 fps on the Air. I’d be interested to know how the iPad 2 handles it):

http://codea.io/talk/discussion/6356/a-quick-comparison-profiling-of-3-ways-of-drawing-meshes

First point: your instinct is right about shaders and speed. Shaders are blazingly fast and in general will out perform any other implementation.

However, shaders are also severely limited in their capabilities. For a given problem, it is quite likely that no shader solution actually exists.

So much for the generalities, let’s to the specifics. I saw your post on the original GoL shader thread (NB always best to start a new thread when going off on a different tack, especially if the original is quite old and the original poster no longer active). I then went looking for the thread where you and redacted originated the idea. What I found did not look like GoL so I assumed it was some private discussion or some amalgamation that I didn’t have time to follow. But from what you post here it would appear that the discussion I found was the right one. That was this one, incidentally. If that’s not right, let me know.

I haven’t read that thread in great detail. I skimmed the first post when it was originally posted to see if it was GoL, but concluded that it wasn’t and so haven’t kept up with it until now. So this analysis may be wrong.

But from what I understand, what you are trying to do is make your agents move. And that is very, very hard to do with a shader.

In GoL, the agents do not move. They are born, live, and die all in a single cell. This is what makes it possible to do in a shader. A shader works by a point knowing what colour it should be. That point can use information from other points, but the more we have to scan, the longer it will take. GoL has a small scan region, one pixel to each side, so is fast. If your agents are moving, then to figure out what colour a pixel is I have to query each agent and ask “Are you going to move here next go?”. That’s infeasible.

That’s not to say that movement isn’t possible. There have been a few fluid simulations here that use shaders (see this thread for an example). But the method is fiendishly ingenious and relies on the fact that the dynamics are reversible and so each pixel has a previous point which can be calculated easily for that pixel. That doesn’t seem to match your situation.

In conclusion, then, before analysing your shader to see what the issue with that is, I’d want more convincing that shaders were the right solution for you.

redacted, I was thinking along the same lines but couldn’t make it work. For some reason I was unable to make the shader detect fine differences in color values. That’s one of the “I think someone else could do this better” moments I had.

@yojimbo2000, re: what you’re looking at:

  • you’re seeing a 20 pixel by 20 pixel grid that’s resized to fill the screen, rendered by the visibleWorld mesh
  • in the corner is a sprite-rendering of the same 20 by 20 grid, as drawn by the worldEngine mesh
  • both meshes draw themselves each draw cycle, based on the current state of the worldEngine texture
  • the worldEngine reads its own texture and executes the logic described above, which is why the cameo looks like a bunch of green and red dots separated by blank space–the dots are the colors in the V positions of each 4 x 4 grid
  • the visibleWorld reads the same texture and only draws the colors in each V position, which is why the main screen looks like a big field of green with some red squares here and there
  • if you pause the screen, you’ll see that the worldEngine shows either a blue pixel or a light-blue pixel next to each red dot. This is the M data.
  • every time the engine reaches a V position, it looks to the surrounding M positions to see what to do; should it turn red, because an organism is moving onto that position, should it turn green, because an organism is moving off of it, or should it just stay whatever color it is?
  • every time the engine reaches an M position, it also looks to the surrounding M positions, and updates itself accordingly–in some cases copying the M data to itself, in some cases erasing its own M data, in most cases doing nothing
  • the M pixels alternate colors between blue and light blue, flipping to the other color each draw cycle; one cycle reads only blue M pixels, and draws only light blue M pixels, and the next cycle only reads light blue M pixels, and only draws blue ones, and on and on like that
  • right now, encountering an M pixel only does one thing: it shifts the data in that 4x4 grid over by 2, basically putting it all one grid to the right. So you see the red blocks move rapidly right.
  • the same process could do many other things!

As to speed, drawing lots of things is not the only issue. The other is executing decision-making logic for all those things. If you comment out the line local w,h = 20,20 At the beginning of setup, you’ll see the world drawn the size of the whole screen, with roughly 1200 organisms moving at once. It goes a lot more slowly than Andrew Stacey’s Game Of Life shaders, which is why I think there is very likely a better way to code all this.

But the question is, would the decision-making go any faster if it were the lua processor evaluating a decision-making tree 1200 times per frame? I think it would go much slower, with my data set having only two entries: Stacey’s GOL shaders and redacted’s altruism sim.

@LoopSpace, I encourage you to do these three things:

  • run Stacey’s GOL shaders
  • run redacted’s final version of his project (you have the right thread)
  • run my project at full resolution, with the local w, h = 20,20 line commented out of setup

As I’m sure you’ll perceive on your own, there are lots of substantial differences between these projects, so any comparison is likely to be inaccurate to some degree.

But in general, the first is the fastest, with a lot of organisms and a moderate level of decision making per organism, the second is the slowest, with the most complex decision making and fewer organisms, and the third (at least on my iPad), is in between the others in terms of speed, having slightly more complexity than GOL and substantially more organisms than redacted.

I’m totally open to this not being the best solution!

Okay, I’ve run both projects in this comment and the project at the top of this discussion; I’m very familiar with Stacey’s GoL project.

  1. redacted’s projects are absolutely nothing like Conway’s Game of Life and I strongly believe that shaders would not be suitable for processing the mechanics of this.
  2. The project in this thread is really too simplified to tell. It seems more of a proof of concept and as such I can’t tell what direction you want it to go. If the goal is to be like redacted’s projects, then I strongly advise you to ditch the shaders and go for meshes.

Let me reiterate the crucial difference:

In GoL, the agents do not move.

They might appear to, but that is an illusion. What is really happening is new agents are born in slightly offset positions (and the old ones die) giving the illusion of movement without anything actually moving.

@LoopSpace–Bold font in quotation format? Really? Please allow me to lightly mock your choice of emphasis:

I KNOW

Loopers, my project is built on Stacey’s GoL code. There is no way I could do what I did without understanding the differences between what’s happening in Conway’s GoL and what I was trying to do. I directly coded all the differences. The point you’re making, I’ve got it.

What I ultimately want is a sim that can of model thousands of individuals a generation. What I’ve done, while unimpressive as is, is nevertheless a framework for cellular automatia capable of true motion. The organsims don’t die or reproduce. They just move. At around a thousand organisms, I see around one generation a second. Not great, not awful. A good start, I think.

I am totally open to your suspicion of Shaders. I would love to do this without Shaders; constantly switching my brain back and forth between C and Lua is quite taxing. My ultimate criteria are population size and speed. If you can point me to something with anywhere near the population size and speed of Stacey’s Conway’s Game of Life, I’ll ditch Shaders in a second.

Okay, okay, I’ll tone down the rhetoric!

Next question: given a location, can I predict where the agent moving there will come from? The information in a shader is all about locations, not agents. Your current code works, I think, because all your agents are moving in the same direction and with the same speed. Once the speeds become agent-specific, I think you’ll have to drop shaders.

At least, shaders used in the GoL sense. If you look at the explosion shader, that might be more suitable. You can find it here.

So, okay, yes, movement speed is an issue. I think speed can only be zero or one grid-space per turn.

Right now, since I only wanted to see if this would work at all, each pixel in an M space looks to the left to see if anything’s coming its way. In practice, each M space would look to all 8 positions surrounding it to see if anything was coming its way.

This makes 1-space-per-cycle movement feasible in any direction. To have any other rates, the M pixels would have to read and evaluate 24 other pixels per frame, which seems to be pushing it to me. (Not when processors improve though! :wink: )

At any rate, I am willing to accept uniform motion speed as a limitation of the paradigm–you can still do a lot with that. In fact, thinking of it just now, you can very easily have things go slower than that. So it’s not necessarily all that uniform in the end: 1-space-per-frame is merely the speed of light. :slight_smile:

That explosion shader is very interesting. The key question: what can vertexes tell about other vertexes? If they can read position, that’s great, but if they can also read color, that’s very great. Would it be possible, in theory, to do Conway’s Game of Life by modifying only the vertex shader?

What if you have two agents that both want to move to the same square? They would, I think, essentially have to become one agent because remembering their history would be very difficult - and even if you could do it for two, what about three or four or a hundred? There’s only limited space in a texture.

In a vertex-driven shader, vertices can’t know anything about other vertices. There’s nothing like the texture that holds all the information in accessible memory. At least, not that I know of.

The data structure I’ve created leaves room for lots of different possibilities.

Let’s assume creatures that are only one step more complicated than my current creatures. My current creatures only move right. If you made them have random motion, and gave them no other characteristics, two or more creatures that moved to the same square would just become one creature. You wouldn’t have to code this specifically, it would be the natural byproduct of not coding for collisions at all.

If added no further complexity to the organisms, but wanted to avoid the merging behavior, you could easily stack them. Just use the D pixels to track how many organisms are at a given location at the same time. Figuring out how to move those organisms off the location in the next turn would be a challenge, but the challenge would be merely finding the most efficient way to do it, not figuring out whether or not it was possible.

Of course, we do want to make the organisms themselves more complex, and the more complex they are, the harder they’d be to stack. It wouldn’t be impossible, up to certain point, but determining that point is probably more trouble than it’s worth.

Much simpler and more interesting would be to decide that any individuals moving onto the same square must interact in some way that leaves only one individual alive. The D pixels offer the possibility of a great deal of complexity in that evaluation. For one example, we could say that every organism can move 255 times before it dies, and track that by ticking up one of the color values on a D pixel every time it moves. Then, if it encounters any other organism, we could decide that the youngest one kills the other one.

Let’s see, would it be possible to do something like the Selfish Gene sim that redacted posted? You could definitely create three different kinds of organisms–and you could do that in the C pixel itself, just via color. redacted has a way to decide which organisms move towards each other, which we’d have to drop for organisms more than one grid-space apart. Hmmm… how close could we get… have to think on it.

Anyway, there’s lots of possiblities!

…okay, I think Selfish Gene would be do-able, albeit much adjusted for the cellular automata paradigm. I’m thinking of the simplest way to do something close to it, which could then be improved upon afterwards if desired.

  • all organisms have an identical lifespan of x, which ticks off in one of the color slots of the D pixels
  • altruists, cheaters, and grudgers are differentiated by color, and their color darkens if they’ve been infected
  • all organisms become infected halfway through their lifespan
  • infection prevents reproduction
  • all organisms move randomly, each turn generating a random number 1-8 and storing it in their M pixel
  • every organism is capable of reading the M pixel in the location it is moving to as well as checking the 8 cells surrounding that M pixel
  • if an organism detects that different organisms are also moving to its target destination, the interaction is evaluated by each participant according to the same rule set:
  • if more than two organisms are moving into the target destination, the youngest two become the “interactors”, and the others head off in a different direction. In the case of identical ages, precedence goes clockwise starting from 12 o’ clock,
  • if two identical kinds of organisms interact, they both stay in their spot and a child is born into the target location
  • if two different kinds of organisms interact, the younger of the two will move into the target location, and the infection-curing-or-not-curing interaction will take place

…I think we could see Selfish Gene effects with no more than that.

Start off with only altruists, from which we’ll be able to determine the amount of altruists that are necessary for random interaction to compensate for 100% infection rate.

With that known, we can introduce cheaters. Cheaters likewise need a minimum population in order to be stable. It will be interesting to see how small we can make the initial population of cheaters and still have a high likelihood of cheaters becoming a stable population, and ultimately squeeze out altruists.

Finally, grudgers. With each organism type, I think the interesting question will be, how small can we make the initial population, while still having a high degree of certainty that we’ll see the desired outcome? How few altruists are needed for stability? Given that, how few cheaters does it take to de-stabilize them? And given both of those, how few grudgers does it take to right the balance?

…not sure I actually want to do all that work, but I think it would be do-able under this system.

You say you “get it” and yet you’re still talking from the point of view of the organisms. You have to think in terms of locations.

Let’s ignore the encoding for the moment. That can be worked out later when we know what has to be encoded. Consider a cell. To work out what happens in that cell, we look at the 3x3 grid surrounding it. Each cell might contain something. For those cells that do, we look at their “velocity” vector which tells us if they are going to move into our location. We also need to look at our own cell to see if our velocity vector means that we will be moving out.

From this information, we can construct a list of all organisms that will be in our location on the next draw. From this population, we need to build a new organism in our location.

Now, we assume that organisms “move” according to a timer that says how many ‘ticks’ to wait before actually moving (so 1-cell per tick is our “speed of light” as you said). If only one organism is at our location then there are two possibilities; either it was there before, in which case we increment its timer, or it came from elsewhere, in which case we reset its timer.

If several organisms are at our location we need to devise rules for combining them into a single organism. This is where some of the fun could come in, with different rules for different combinations. The key is, though, that the result is only one organism.

However, it might be possible to include a kind of fission as well. It could be the case that an organism could split if it can be given two velocity vectors.

Combining these two rules, one could simulate a collision where some organisms meet and recombine in some fashion, somewhat like a particle collision.

Okay, so to implementation. We have 8 possible directions, and we want a magnitude vector. Everything’s going to be a power of 2, so let’s say we have 2^k magnitudes. We’ll see what k will be later. To allow for fission, we might have two or three (?) velocity vectors. So we’re at (8 x 2^k)^3 to encode up to 3 velocity vectors. Now each vector comes with a timer, the idea being that we increment the timer according to the magnitude of the vector. So the timer needs the same space as the magnitudes. This gives (8 x 2^k x 2^k)^3 = 2^{9 + 6k}. If we split into two rather than three then it is 2^{6 + 4k}. On top of that, you want some information about how the organisms combine and split.

Each pixel can encode 2^24 bits. But we can use more than one pixel per cell.

We could get away with less if fission is a bit more predictable. Suppose fission works according to simple rules, such as the velocity vector splitting so that it splits off one on either side (so if it is currently E, it splits as NE, E, SE) and with the same magnitudes.

Right, I’m stopping here for now. I’ve run out of steam!

I’m not sure what I’m saying that makes you think I’m describing anything other than location. As far as I can tell I’m thinking in the exact same terms as you are, except I’m calling a particular set of data encoded at a particular location an “organism”. I would like to avoid giving the wrong impression, so it would be very helpful to understand what it is that I’m doing erroneously. From my perspective, I’ve spoken of location exclusively.

To wit, from the previous post:

  • all organisms move randomly, each turn generating a random number 1-8 and storing it in their M pixel [the 1-8 signifying the eight possible directions of travel]
  • every organism is capable of reading the M pixel in the location it is moving to as well as checking the 8 cells surrounding that M pixel (emphasis added)

…at any rate, we’ve both discussed different ways to add different behaviors to the cells/organisms, and we’ve both run out of steam discussing those behaviors. :slight_smile:

Maybe it’s more interesting to think about getting the most out of the wide range of possibilites the framework offers. Here are the things that actually intrigue me the most:

  • the potential for organisms/cells to carry things from one location to another.
  • the potential to model environment and changes in environment. One of the D cells in each 4x4 grid could be assigned to an environment variable, and then each region of the screen could be given distinct environment characteristics–and the environment/environments could change over time, using, perhaps, a constant supplied by Codea that gets changed every 1000 draw cycles. Then each organism/cell could have different behaviors making it more or less ‘fit’ for a given kind of environment.