Over the past few days I have been working on an engine to create realistic life in the coding engine known as scratch. While it is no means realistically accurate and I will have to work much harder to make it look like real cells interacting, I would like to share with you my progress and how I implemented these things.
The first thing that I did was create a bunch of points in a list, these are all clones in the optimized version but I will tell you how I made them optimized later. Each of these clones put their x and y into a list in action to put a type or spices into a list, this can be any number but it is easiest with 3 to get the best results. This is so that each of the particles will be able to interact and see where each other is. In the end this looks like this:
Next I gave each of the particles the ability to move by changing their x and y by their xVelocity and yVelocity which I set to a random value between 1.0 to -1.0. Of course with movement comes collision so I implemented the naive collision algorithm which checks every other particle to see if they are colliding giving this result:(I increased the particle count for a better viewing experience)
After this I played around with adding cell spiting which happens every time a cell gets above a certain energy level but that didn't last long on around of the collision being to high of a performance cost. Here is what it looked like:
Wish I knew how to do video because it is pretty mesmerizing to watch but anyway no to the fun part, particle life. Particle life is where you put a bunch of particles next to each other and give them rules to interact and they will do it in fantastic ways, It truly is a weirdly close life simulator. Anyway the way that I did this was first testing my attraction code by seeing if a particle was within a certain distance It would start to move together. Which works but isn't that interesting, It looks kind of like tissue.
Remember that type list that I said to add at the beginning, that comes in handy now because we can set rules for how the different types of particles interact. This allows us to make the simulation look like this:
Now that we have this wonder of code we can optimize it because I had to run It at half the particle count to get more than 5 fps and I'm using turbowarp, scratch's compiled version. The first and easiest part of this process was to implement the easiest optimization on the distance equation, Instead of using r < sqrt( DeltaX^2 + DeltaY^2 ) use r^2 < DeltaX^2 + Delta Y^2 because using square roots is expensive. Now that we got that one done lets go onto the optimization that made me have the biggest rewrite of code I have ever had, spacial partitioning.
This is where you make the entire screen into a grid and put each of the particles into that grid, for each particle only check the grid cells that are around the cell that that particle is in. For this through our everything and start from scratch, literally. Sorry about what I just had to, anyway the reason for this rewrite is because everything needs to be In the one sprite, no clones, no other sprites, no nothing. For this all of the points need to be in a grid as an X, Y, XVelocity, YVelocity, and Type, this makes it so that optimization is easier because you don't need to good through a bunch of clones to find a value, only a list. Now the way that I made my spacial partitioning Is by setting up 2 lists called Gidx and Gidy standing for Grid index x and y. The way that you find your Gidx is by taking you x and running it through this equation ceiling( x / GridTileSize ) and the same thing for Gidy but switch x and y. Next, when you are checking collisions before finding distance or anything else, see if your selected particle that your checking is in the range of Gidx - 1 < selectedGidx < Gidx + 1 then do the same check for y and then if it meats that criteria then check it. This boosted my fps on 1000 particles from 5 to 14, almost a 3x difference.
This my friends marks the end of this article but fret not, spring break is on the way and I am going to work on modeling actual cells as talked about in scientific papers, I am going to regret it but I have time to be smart when I'm older. Thank you all for reading and I will see you next time :)
Top comments (2)
Awesome work on this! Tackling naive collision and moving all the way to spatial partitioning in a single-sprite list system shows a lot of dedication. Huge respect for the rewrite.👍🏾👍🏾👍🏾
Next I will have a real enough cell