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

Summary

This video script delves into the revival of falling sand simulations, leveraging modern computing power to enhance the cellular automata concept. It outlines the process of coding a simulation with a 2D grid, detailing the behavior of elements like sand, stone, and water. The script explores coding structures, optimizations for performance, and introduces unique elements and behaviors, such as particles and explosions. The speaker shares their journey and invites feedback, providing a comprehensive look at creating dynamic and organic simulations.

Takeaways

• 🕰️ Falling sand simulations, once limited by computational power, have been revitalized with modern hardware capabilities.
• 🌐 The concept is based on cellular automata, sharing similarities with games like Conway's Game of Life, Minecraft, and Noita.
• 🔲 In a falling sand simulation, the world is a 2D grid where discrete elements follow predefined rules based on their surroundings.
• 🧱 Elements like stone, sand, and water have unique behaviors; stone is static, while sand and water move based on available space.
• 📚 The simulation uses a 2D array to store the matrix and a wrapper class to manage interactions and avoid complex issues.
• 📐 Elements are structured in a class hierarchy allowing for shared and overridden methods for flexible behavior customization.
• 💧 Water can spread out faster by looking further for space, and a variable dispersal rate can be set at the class level for different liquids.
• 🔢 An algorithm uses the slope of a line to calculate movement between any two cells, allowing for consistent pathfinding.
• 🔄 When sand falls from a height, it can now spread out more naturally by conserving energy through horizontal movement and friction.
• 🔍 The 'is free falling' flag simulates inertia, changing the movement behavior of elements based on whether they are moving or at rest.
• 💥 Particles, a new element type, can simulate effects like explosions, using the same traversal function but with different interaction logic.

Q & A

What is a falling sand simulation?

A falling sand simulation is a type of computational model that represents a world as a 2D grid where each cell can contain one element at a time. Elements follow predefined rules based on their intrinsic motivations and surrounding environment, acting independently of each other.

How is a falling sand simulation related to cellular automata?

A falling sand simulation is a derivative of cellular automata, which are computational models where space and time are discrete and elements interact with their local environment following certain rules.

What are some examples of games that use concepts similar to falling sand simulations?

Examples of games that borrow concepts from falling sand simulations include Conway's Game of Life, which is a true cellular automata, Minecraft with its blocky appearance and behavior, and Noita, a popular falling sand roguelike game.

How does the movement of sand elements work in a falling sand simulation?

In a falling sand simulation, sand elements first attempt to move downward one cell. If they encounter an obstacle, they try to move diagonally downward left or right until they find an empty cell or are unable to move further, in which case they stay in place.

What is a matrix wrapper class in the context of a falling sand simulation?

A matrix wrapper class is a class that encapsulates the 2D matrix used in a falling sand simulation. It handles setup and mediates interactions with the inner 2D array, providing a controlled way to access and modify the simulation's state.

Why is it beneficial to structure element classes in a hierarchy for a falling sand simulation?

Structuring element classes in a hierarchy allows for common method definitions to be placed in the highest applicable abstraction, reducing code duplication. It also enables easy customization of behavior in subclasses by overriding methods, making it simpler to create new unique elements with specific interactions and parameters.

How does the movement of water elements differ from sand in the simulation?

Water elements have similar movement logic to sand, but if they cannot find space below, they search horizontally to spread out. Water can also look further for an available space when encountering another element, which can be adjusted by a variable stored at the class level to control different dispersal rates.

What is the purpose of the 'is free falling' flag in movable solid elements?

The 'is free falling' flag indicates whether a movable solid is currently moving or not. If set to true, the element will look for places to move diagonally downward when it hits an obstacle. If set to false, the element will only look directly downward, making it more likely to stay in place once it has come to rest.

How can the simulation handle elements with non-zero velocities on both the x and y axes?

The simulation can handle elements with non-zero velocities on both axes by using a matrix traversal algorithm that calculates the shortest path between any two given cells. This allows elements to move in a straight line from their current position to a target position, checking every cell along the way.

What are some performance optimizations discussed in the script for a falling sand simulation?

Some performance optimizations discussed include multi-threading to process multiple cells concurrently and chunk-based processing where chunks of the world are marked for processing based on the activity of their contained elements, reducing unnecessary calculations.

How does the script suggest handling explosions in a falling sand simulation?

The script suggests creating a particle element type for handling explosions. When an explosion occurs, elements within a certain radius are affected based on their explosion resistance. The explosion propagates from the center outward, and the simulation uses a matrix traversal method to determine the path and effect of the explosion.

Outlines

00:00

🌟 Reviving Falling Sand Simulations with Modern Coding Techniques

This paragraph introduces the concept of falling sand simulations, which have been revitalized due to the increased computational power of modern computers. The speaker explains how these simulations, which are a form of cellular automata, can be enhanced with clever coding and imagination. Examples of games that use similar concepts include Conway's Game of Life, Minecraft, and Noita. The paragraph also describes the basic mechanics of a falling sand simulation, where elements like sand, stone, and water interact based on predefined rules within a 2D grid. The speaker outlines the independent behavior of each element and how they respond to their surroundings, as well as the process of coding these simulations using a 2D array and a class hierarchy to manage different types of elements.

05:00

💧 Enhancing Liquid Dynamics and Element Interactions

The second paragraph delves into the specifics of improving the behavior of liquids in the simulation, particularly water. The speaker discusses the limitations of basic movement and introduces a method to allow water to disperse faster by looking further for available spaces. This is achieved by modifying the water's behavior to search horizontally when no space is found below. The paragraph also covers the implementation of a matrix traversal algorithm that enables elements to move between any two points in a 2D array in a logical manner, which is applied to user drawing brushes and particle movement. Additionally, the speaker explores making the simulation more organic by introducing energy conservation in falling sand and simulating inertia through an 'is free falling' flag, which affects how elements like sand move after coming to rest.

10:01

🔥 Introducing Particles and Explosion Dynamics

In this paragraph, the speaker introduces a new element type called 'particle' for simulating phenomena like explosions or water fountains. Particles inherit from the abstract element class and utilize the same matrix traversal function for movement as other elements, but with a simple interaction logic where they replace themselves with their contained element upon collision. The speaker also discusses creating realistic explosions that propagate from the center outward, stopping when encountering an element with sufficient explosion resistance. This is achieved by using a matrix traversal method to check each cell's explosion resistance and either destroy the element or break early from iterating. The paragraph concludes with the idea of creating a variety of new element types with minimal effort by adjusting parameters and specifying interactions in the 'act on other' method.

15:18

⚙️ Optimizing Performance for Large-Scale Simulations

The fourth paragraph focuses on performance optimizations for handling large-scale simulations efficiently. The speaker describes a significant drop in frame rate when operating on a large number of cells and introduces multi-threading as a solution. By splitting the world into columns and processing them in separate threads, the simulation's performance is greatly improved. The speaker also discusses the issue of elements repeatedly attempting to move into occupied cells, which leads to unnecessary calculations. To address this, the world is divided into chunks, each with a state indicating whether it should be processed in the current or next frame. This approach significantly reduces unnecessary processing and, when combined with multi-threading, brings the frame rate back up to an acceptable level.

20:19

🔄 Continuous Development and Future Improvements

In the final paragraph, the speaker reflects on the ongoing development of the simulation over the past two years, highlighting the challenges faced and the solutions implemented. The speaker acknowledges that they are not a professional game developer and that the methods discussed may not be the best but have worked for them. They express openness to suggestions for improvement and invite questions from viewers. The speaker also mentions plans to port the simulation to C++ and SFML for better drawing performance and hints at potential future videos discussing these developments. The paragraph concludes with a review of the game loop, detailing the steps taken each frame and the setup logic executed on startup.

Keywords

💡Falling Sand Simulation

Falling Sand Simulation refers to a computational model that simulates the behavior of granular materials like sand. It is a derivative of cellular automata and is used in the video to demonstrate how elements like sand, stone, and water interact in a virtual 2D grid. The concept has been revisited due to increased computing power, allowing for more complex and realistic simulations, as illustrated by the video's exploration of different elements' behaviors and interactions.

💡Cellular Automata

Cellular Automata are mathematical models used to simulate dynamic systems based on discrete cells, each with a set of states and rules governing their transitions. In the context of the video, a Falling Sand Simulation is a type of cellular automata where each cell can contain one element, and the state of each cell evolves based on its own rules and the states of neighboring cells, as seen in the basic example provided with sand, stone, and water.

💡2D Matrix

A 2D Matrix, as mentioned in the script, is a two-dimensional array used to represent the grid of the simulation. Each element within the matrix corresponds to a cell in the grid, which can contain different elements like sand, stone, or water. The video explains how the simulation iterates through this matrix to update the positions and states of the elements, which is central to the functioning of the Falling Sand Simulation.

💡Element Behavior

Element Behavior in the video refers to the predefined rules that dictate how each type of element in the simulation reacts to its environment and intrinsic motivations. For instance, the script describes how sand moves downward or diagonally if it encounters obstacles, while water spreads horizontally if it cannot move downward. These behaviors are crucial for creating realistic interactions within the simulation.

💡Inheritance (in programming)

Inheritance is a fundamental concept in object-oriented programming where a class can inherit properties and methods from another class. The video uses inheritance to create a hierarchy of element classes, with an abstract base class and subclasses for different types of elements like liquids, gases, and solids. This allows for shared behavior across multiple element types while also enabling specific customization through overridden methods.

💡Matrix Traversal Algorithm

The Matrix Traversal Algorithm discussed in the video is a method for determining the shortest path between two cells in the 2D matrix. It is used for various purposes, such as moving elements diagonally or simulating the spread of water. The algorithm calculates the slope of a line between points and iterates through the x-values to find the corresponding y-values, ensuring elements move in a logical and consistent manner.

💡Optimization

Optimization in the context of the video pertains to improving the performance and efficiency of the simulation. The script describes two main optimization techniques: multi-threading to process multiple cells concurrently and chunk-based processing to avoid unnecessary calculations on resting elements. These optimizations are crucial for handling the large number of cells in the simulation without compromising the frame rate.

💡Multi-threading

Multi-threading is a technique used in the video to enhance the simulation's performance by allowing different parts of the 2D matrix to be processed simultaneously. By dividing the matrix into columns and processing odd and even columns in separate threads, the video demonstrates a significant improvement in the simulation's frame rate, highlighting the effectiveness of this approach in handling large-scale computations.

💡Chunk-based Processing

Chunk-based Processing is another optimization technique mentioned in the script, where the 2D matrix is divided into chunks, and each chunk decides whether to process its contents based on the activity of its elements. This method reduces the computational load by avoiding processing on chunks that are 'sleeping' or not changing, thus conserving resources and improving the simulation's performance.

💡Particle Element

The Particle Element is a special type of element introduced in the video for simulating phenomena like explosions or water fountaining. It inherits directly from the abstract element class and uses the matrix traversal function for movement without any interaction logic. When a particle encounters another element, it replaces itself with its contained element, allowing for versatile and dynamic visual effects within the simulation.

💡Inertial Resistance

Inertial Resistance is a variable used in the video to simulate the tendency of an element to remain at rest or to continue moving. It is applied to movable solids to determine how likely they are to start moving again after coming to a rest. By adjusting the inertial resistance value, the video shows how elements like sand, dirt, and coal can have different behaviors in how they crumble and settle, contributing to a more organic appearance of the simulation.

Highlights

Falling sand simulations, once dormant, are now revisited with modern computing power.

Conceptual coding of falling sand simulations explained through illustrations and code samples.

Falling sand sim as a derivative of cellular automata, with examples like Conway's Game of Life and Minecraft.

World represented by a 2D grid where elements have discrete behaviors based on surroundings.

Elements like sand, stone, and water have predefined behaviors influenced by their environment.

Sand forms pyramid-like structures when piled up, and water spreads horizontally when space is limited.

Sand can sink when encountering water, demonstrating element interaction in the simulation.

2D matrix stored as an array, with a wrapper class to handle setup and interactions.

Element classes structured in a hierarchy for efficient code and customizable behavior.

Pseudo code for movable solid class illustrates element processing during simulation.

Water dispersal improved by looking further for space, introducing variable dispersal rates.

Gravity and velocity introduced to simulate faster movement and multiple cell traversal.

General purpose algorithm for shortest path traversal between any two cells in a 2D array.

Drawing brush elements use matrix traversal for smooth and continuous drawing.

Sand's behavior modified to conserve energy upon impact, simulating a more realistic spread.

Inertial resistance variable introduced to simulate the resting state of elements.

Particle element type created for effects like explosions, utilizing matrix traversal for movement.

Optimizations like multi-threading and chunk-based processing to improve simulation performance.

Custom shaders and texture updates explored for more efficient drawing of elements.

Flowchart provided for the game loop, detailing the simulation's frame-by-frame operations.

Transcripts

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