How To Code a Falling Sand Simulation (like Noita) with Cellular Automata

falling sand simulations are a decades-old concept which have been mostly dormant since the early 2000s era of standalone java applets now that the average computer is much more powerful than two decades ago this concept has been revisited and falling sand sims can be pushed further with some clever coding and imagination in this video i will explain conceptually how to code a falling sand simulation showing through illustration and code samples how i solved different technical challenges first let's cover what a falling sand simulation is a falling sand sim is a derivative of cellular automata some examples of other games which borrow concepts from this are conway's game of life which is a true cellular automata minecraft pulls related elements with its blocky appearance and behavior and noita is a recent popular falling sand roguelike in a falling sand simulation the world is represented by a 2d grid each coordinate in the matrix is discrete meaning that only one element can occupy any cell at one time elements cannot be partially in a cell and cannot be in two cells at once each element has predefined a behavior or rules which allow it to act based on its intrinsic motivations and also its surrounding environment each element acts independently and while its surroundings can influence the way it acts the behavior is executed independently for each element let's take a basic example with the elements sand stone and water our simulated world is represented by a 2d matrix in each frame we iterate through all the elements in the matrix from the bottom row to the top empty cells require no processing so we will skip over these the stone is static and does not move regardless of its surroundings or forces so no further update is needed the sand elements rules determine that it will always first attempt to move downward one cell if it encounters stone or other sand it will attempt to go diagonally downward left or right until it is unable to find any empty cells in which case it will stay in the same location if you add a bunch of sand into the simulation on top of each other it will form pyramid-like structures water has similar movement logic to sand except if it cannot find any space below it then it will search for space horizontally allowing it to spread out further we can expand the sand behavior so that if encounters water then they will switch places effectively allowing the sand to sink now that we have discussed a basic scenario i'll explain how to structure this in code the 2d matrix is stored as a 2d array or an array of arrays i have created a wrapper class around this matrix which handles setup and mediates any interactions with the inner 2d array since the matrix is modified in place each frame by limiting the avenues through which the inner array can be accessed we can avoid unexpected or harder to trace issues as the complexity of the simulation increases for example standardizing the way elements swap sales reduces repeated code and makes debugging easier i structured my element classes in the following hierarchy there is a base abstract element class which has subclasses for liquid gas and solids which then has further subclasses for movable solids such as sand and immovable solids such as stone this structure allows you to place method definitions common to all types of elements in the highest applicable abstraction and this also allows you to override these methods in subclasses for customizable behavior for example i have a base method in the abstract element class which defines what elements should do when they receive heat from an ignited neighboring element this common logic applies to many elements but if i want water to turn into steam when receiving heat i can make that custom logic easily by overriding the method in the water class if i want stone to have no effect when receiving heat i can override the method with a blank definition if i don't want any liquids to have their color affected by explosions i can override that method at the liquid class level once you have the common logic set up for each of the main element types it becomes easy to create new unique elements by only tweaking parameters and specifying element interactions let's walk through some pseudo code for the step function on the movable solid class to get a better understanding of what happens during the processing stage of an individual element in this case sand first we get the contents of the cell below the current object cell if the target cell is empty we can simply move our piece of sand into the empty cell if the target cell contains any class inheriting from the liquid abstract class we will switch places with it and if the target cell contains any type of solid movable or immovable we will look diagonally for a new occupiable cell let's evaluate what we have so far it is predictable and consistent but how can we improve it water takes so long to spread out since it can only move one cell at a time in order to make the water disperse faster we can make it look further for an available space when encountering another element so if water looks below itself for an empty space and finds none then it will look x amount of cells to the right or left for an empty space let's make this a variable and store it at class level so different liquids can have different dispersal rates if the water simply looks five places to the left or right and occupies the empty space it finds there then it will effectively teleport and bypass any elements in between when the liquids travel multiple cells to any side it must check every cell between its current location and its destination otherwise it would pass through walls a simple solution is to use a basic for loop to move horizontally stopping when we hit another element and this works we can compare the old behavior with a new behavior to see that liquids are now dispersed much faster than previously we can apply this same concept vertically by adding gravity to the simulation and tracking an element's velocity with a 2d vector this allows it to increase in speed and travel more than one cell per frame again we want to check every cell along the way but what if we wanted an element to have both non-zero x and y axis velocity we can't just do a simple for loop or even a nested for loop this raises the question how can we travel between any two given cells in our 2d array following the shortest path we can create a general purpose algorithm for this it is generic enough that i use it for the user's drawing brush elements traveling through the 2d array particle movement and for the center explosion method i'll cover later fortunately there already is an equation to find the slope of a line drawn between two points the slope allows us to calculate the corresponding y values as x increases we can use a for loop to iterate to the desired x value since in this case x is the longer side each cell is discrete so if the calculated y value is not a whole number we will round up or down based on the first decimal place we can step through this example calculating the rounded y value for each x value and filling in the corresponding cell can see that the path taken closely follows the line drawn between the start and end point the actual algorithm becomes a little more convoluted when taking into account all possible directions the path can be so i have created an annotated gist which is linked in the description using this approach we can travel between any two points regardless of where they are in a logical and consistent manner a practical application of this method is used with the drawing brush previously an element would only be drawn at the mouse location each frame but since the mouse location can move a large distance between frames this would create a disjointed series of elements using a large brush size and moving slowly would create connected elements but with this matrix traversal algorithm elements are drawn between drastically different mouse locations frame to frame in an expected and believable manner now that we have sand stone and water working together let's explore some changes to make the behavior slightly less predictable but a little more organic in appearance when a grain of sand falls from a great height it will just smack the ground and stop moving because these are the rules that we gave it but it would make more sense for some of the energy to be conserved and push the sand elsewhere what we can do is when a grain of sand hits an obstacle at a high velocity we take a proportion of the vertical velocity and convert it to horizontal velocity so now when the sand hits the ground it will move sideways conserving some of that energy but now the sand endlessly runs sideways by applying some friction to reduce its horizontal velocity each time it comes in contact with an obstacle we can mitigate this behavior and the sand comes to a stop this allows sand to spread out a bit further when falling from a height and pile as it forms are no longer perfect pyramids another rule we can expand upon for the movable solids is where it looks to go each frame we can simulate one aspect of inertia by adding a flag to each movable solid indicating if it is currently moving or not i chose the name is free falling if the element did not change cells between this frame and last frame then is free falling is set to false otherwise it will be set to true while israel falling is set to true our sand will perform the previously mentioned collision behavior of checking all three cells below it for space when this flag is set to false then the sand will only look directly downward each frame for a place to go and no longer diagonally so once a solid comes to a rest it is more likely to stay there the way a solid can have is free falling set to true again and thereby look for places to go diagonally downward is either by the space below it no longer being occupied and it falls downward or when an adjacent element passes by and attempts to dislodge it elements with israeli falling set to true will check adjacent neighbors and attempt to set there is free falling flag to true you can see here that once the elements come to a rest i can delete the elements adjacent to them opening up a diagonal pathway for the elements on the side of the stack to move into but they do not take it since they have is free falling set to false but by dropping some new elements past these stationary piles we can trigger is free falling to be set to true causing one element to move again which causes a chain reaction for the whole stack the chance of history falling being set to true is based on the inertial resistance variable we assigned to it by adjusting the inertial resistance value we can change how likely an element is to be set back to free falling state we can compare the results side by side with the elements sand dirt and coal each with different inertial resistance values the higher the value the harder it is for an element to have is free falling set to true again these two features combine to make more organic looking stacks of elements and improve the way they look as they crumble we can see the old behavior compared to the new here so far all of our logic for elements has been with the assumption that everything moves downwards but what if we want to have sand flying around from explosions or water fountaining up from the ground we can create a new element type called particle this element will inherit from the abstract element class directly and we can utilize the same matrix traversal function for movement that other elements use but the particle element will have no interaction logic if a particle hits any other type of element it will replace itself with its contained element so let's say a force is applied to a piece of sand which would launch it into the air we remove the element from the matrix and replace it with a particle of the same color a reference to the element we just removed and apply the force to the particle instead if the particle encounters another element it will remove itself from the matrix and place the sand element in its current cell this keeps particle logic simple and versatile particles can also have no containing element and simply die when they hit something for a visual only effect explosions could be as simple as checking if an element is within a blast radius and destroying it if the explosion is strong enough but that would lead to more vulnerable elements being destroyed behind tougher elements which isn't predictable behavior i really like the way noita has explosions move from the center outward and don't affect weaker elements behind tougher elements so let's create an explosion which propagates from the center outward and stops once it reaches an element which has an explosion resistance higher than the strength of the explosion first we take a radius which represents the size of the explosion and make a box around the center of an origin point for each point on the perimeter of the square we utilize our matrix traversal method and travel from the origin point to the point on the perimeter as we travel across each cell we check if distance from the center is less than our determined radius so our area of effect is a circle and not a square and check the explosion resistance of the element present in the cell we either destroy it or break early from iterating to the square's perimeter there will be a lot of overlap in the paths from the origin point to the edge points on the box but we do not want to operate on the same cells twice we can cache the result so when we visit the same cell again we don't need to duplicate our actions the cached value for each cell indicates that the explosion was blocked at this location previously and should stop here again or if the explosion can continue along this path and act on further cells to achieve this targeting effect instead of just stopping when encountering a tough material a flag is set in the cache which indicates the explosion is no longer destroying elements past this point but just calling a darkened method common to elements add a random chance of falloff and you get some scorch marks which give a nice effect now that we have created some adjustable parameters for our solid and liquid classes we can work on creating a variety of new element types with minimal effort first let's revisit our step function pseudocode when an element collides with another element the act on other method is called on the current cell this act on other method is blank at the abstract element class level which is good for elements like sand and dirt which don't have any special effect on other element types but makes it easy to add custom logic for water to apply cooling or lava to apply melting try to make the acid element type which does damage to any elements it touches and dies once it has touched enough other elements and see how easy it is to do so we need to have the acid class inherit from the liquid class and then set some liquid specific parameters such as density and dispersion rate the method which acid will use to act on other elements will be called corrode we make a default definition in the abstract element class which means all element types will be affected by the corrode method we can create empty definitions of corrode in the acid class so that it doesn't corrode other acid and we can make another immovable solid called titanium which we don't want to have affected by corrode either that's all we need to do and now we have a fully functioning new element type now i'll show some other unique elements with their effects and the corresponding code required to make them work [Music] [Music] you [Music] operating on hundreds of thousands of cells in our 2d matrix at 60 frames per second is a costly procedure and the features we just added only slow it down further there are some optimizations we can implement which will drastically improve performance of our simulation let's get a baseline before implementing these i have scaled the simulation here to be a total of 256 000 cells by placing hundreds of thousands of water elements the simulation slows down to 10 fps at the lowest and settles at 18. let's see if we can improve on this instead of operating through every single cell one at a time we can implement some multi-threading to operate on multiple cells concurrently and cut processing time to accomplish some simple multi-threading i split the world into columns and execute threads which first process all odd numbered columns and then once those have finished the even numbered columns this ensures that they do not attempt to modify the same element simultaneously we can check our baseline simulation with multi-threading and i found that the frames per second dropped to only 40 and settled at 45. this is a significant improvement you may have noticed some step-like formations around the column borders i added some randomly generated offset to the columns positions each frame and this eliminated the issue often times elements will come to a rest and due to their movement behavior keep trying to enter the same occupied cells and do not move at all but are still fully processed every frame in this clip i set the elements to change to the color blue if they have moved since last frame and red if they have not we can see that once the elements find a resting point the vast majority are trying to move down into the side performing thousands of queries to the matrix to find an open space but each time getting the same result and staying in the same cell to eliminate these unnecessary calculations i split the world into a grid of chunks each chunk holds two states whether the chunks contents should be processed this frame and if they should be processed next frame at the start of each frame the should step next frame flag is set as the value of should step this frame and should step next frame is set to false essentially this means we assume that a chunk will be sleeping next frame and rely on its contained or neighboring elements to alert the chunk if it should awaken the next frame as each of the elements attempt to step this frame they check that should step this frame flag on the current chunk they belong to which is based on their current coordinates if it is false then the element stops processing at that point and saves resources whenever an element has something happened to it like being set on fire or changing coordinates the element will report to its chunk that it should process all contents next frame but how will a sleeping chunk ever awake if all the contents do no processing and have no opportunity to wake the sleeping chunk if a new element enters the chunk it will wake the chunk if an element reports to its chunk that it should process next frame and the coordinates are on the border of a chunk it will wake both adjacent chunks the chunk classes are very simple and do not have any knowledge of the elements within their bounds the elements simply tell the matrix wrapper class to alert the appropriate chunk based on its coordinates now let's try our baseline simulation again with both of these optimizations and see what our frame rate is in this case the fbs dropped to 50 at the lowest and settled at 60. given that my computer is a few years old there are over 250 000 cells and the drawing is currently unoptimized i am very satisfied with the stress test i have had a few people ask how i perform the drawing logic for this many cells i'm using the debug draw tool in libgdx to draw each square which is a terrible way to do this i am working on boarding this simulation to c plus and sfml so far it seems the best way to perform the drawing is to create a texture and update each pixel's color in the texture every frame for the elements which have moved and then drawing the texture as a sprite this is much better as there is only one draw call and you can process the sprite with custom shaders as well although i have yet to fully test this method i have spent a good amount of time trying to integrate the box 2d library with the simulation but have had limited success i hope to solve some of these problems moving forward and make another video explaining how to accomplish this as a review for the game loop here is a flowchart of what the simulation does each frame on startup we execute some setup logic such as creating the matrix the columns for the multithreading the chunks and some ui stuff each frame we reset the chunks create and launch our threads for processing the elements process explosions which are placed into the explosion queue during the element processing draw all the elements and then repeat this forever i have been working on this simulation for the past two years on and off i am not a professional game developer and this video merely explains the way that i was able to solve these challenges given my level of skill and knowledge at the time there very well may be better ways to accomplish the things talked about in this video and i would be grateful to hear them if you have any questions or would like additional details on any of the topics in this video ask in the comments and i will be glad to answer your questions i have provided a good number of links in the description to code samples and other resources i used while solving these problems i hope this information was useful to you and thank you for watching

Channel: SCREAMINGSNAKE

Views: 8,395

Keywords:

Id: 5Ka3tbbT-9E

Length: 21min 18sec (1278 seconds)

Published: Sun May 23 2021

Reddit Comments

[u/[deleted]]

[removed]

[u/tophatstuff]

Awesome!

Few questions

1) It seems (from the bit on multithreading) like the cellular automation checks and modifies cells in the same pass. If there was a separate logic pass (check what change will happen to the cell depending on its neighbours) and once this is done for every cell a separate state mutation (apply the changes to each cell) or double-buffering (read from one buffer, but write to the other, then swap the two), does the simulation behave in visually the same way? This could mean multithreading can avoid the second odd/even column step and avoid the random offsets used to hide artifacts.

2) Are you drawing every pixel anew on a clear canvas each frame? Could you avoid starting from scratch each frame and simply update the cells that have changed (e.g. if a sand falls, restore the background colour at the previous position, and draw the sand at a position below, but don't need to redraw stone that hasn't moved).

[u/goodm1x]

So cool! Hopefully some day I’ll be able to understand more than 10% it lol

[u/colelawr]

Great summary! I can easily tell how to port this logic to my favorite languages based on the great explanations. Thanks for sharing

[u/gordonfreemn]

These pixel simulation / falling sand simulation / sand game systems are so fascinating.

I just started a sand game of my own. Last night I got sand and water behaving decently alone and with each other, and it's amazing how few simple rules end up in a decently realistic behaviour. And often even in surprisingly realistic behaviour, showing effects you didn't specifically intend but it still happens.

One of the pulls for me is that is it's not especially taxing to code these things (lines of code wise) and after you have a good system, adding a new "species" can be really simple. You can create a decently complex world from scratch and with relatively little code.