Conway's Game Of Life - 4096 x 4096 @ 100FPS!

What's this?

This is an implementation of Conway's Game Of Life written in DOTS, that dynamically grows when it needs more space. It's written for Turbo Makes Games' Dots Community Challenge #1, and a video about my process making it might appear on my YouTube channel later.

Controls

• Mouse / Left Click - Interact with UI and Draw
• Delete - Clear Screen
• L - Toggle Load Menu
• Space / P - Pause / Unpause
• Q / E - Cycle different algorithms
• WASD / Arrow Keys - Move view around
• Number Keys 1-9 - Zoom Level
• Number Key 0 - Turn off rendering
• K - Toggle UI
• R - Reset FPS counter
• Alt+Enter - Toggle fullscreen

Reading the UI

In the top left there's the following info:

• Algorithm - What algorithm is currently being used of the ones listed at the bottom of this page
• VisScale - How many tiles are being sent to the shader every frame (NB: Might be more or less than what's shown on screen depending on your resolution and where you pan)
• Simulating - False if the simulation is currently paused (only rendering is happening)
• ActiveGroups - How many groups of 1024 are being simulated
• InactiveGroups - How many groups of 1024 are ready to be simulated

The top right and bottom left is data from Graphy

Stats

I've tested it on two computers:

1. Intel(R) Core(TM) i7-6700k CPU @4.00GHz [8 cores]
   1. Graphics API: Direct3D 11.0 [level11.1]
   2. GPU: NVIDIA GeForce GTX 1070
   3. VRAM: 8067MB
   4. RAM: 16330 MB
   5. OS: Windows 10 (10.0.19045) 64bit [Desktop]
2. Intel(R) Core(TM) i7-9750H CPU @2.60GHz [12 cores]
   1. Screen 1920x1080@144Hz
   2. Graphics API: Direct3D 11.0 [level 11.1]
   3. GPU: NVIDIA GeForce RTX 2070 with Max-Q Design
   4. VRAM: 8031MB
   5. RAM: 16303 MB
   6. OS: Windows 10 (10.0.19045) 64bit [Desktop]

Below is the framerate data for how the different algorithms with rendering turned off and it being filled with only gliders. The number in parenthesis is which computer was used for testing.

Algorithm  (Computer)	QuadTree (1)	EntityHashMap (1)	EdgeHashMap (1)	QuadTree (2)	EntityHashMap (2)	EdgeHashMap (2)
1024 x 1024	35	570	610	49	750	830
2024 x 2024	9	220	240	13	320	350
4096 x 4096	2	70	75	3	95	108
8192 x 8192		18	20		27	29
16384 x 16384		4	5		6	7

Algorithms

Each entity stores a component with 4 * 4 values of 8 * 8 bits of data. The entities are marked as either active (has alive tiles) or inactive, and are created or destroyed so that there's a layer of inactive entities around every active entity. Any inactive entity not next to any active entity is destroyed.

There are 3 algorithms used to process the data:

• QuadTree
  • Finds surrounding tiles using quadtrees and IComponentLookups
  • Places all relevant bits into another quadtree,  then uses that to count surrounding tiles for each tile on the entity
• EntityHashMap
  • Finds surrounding tiles using a HashMap and IComponentLookups
  • Creates an array of neighbor counts for each tile, then uses a lookup to decide if a bit should be enabled or not.
• EdgeHashMap
  • Creates a datastructure containing the outer values of each entity so that they can be accessed without an IComponentLookup
  • Creates an array of neighbor counts for each tile, then uses a lookup to decide if a bit should be enabled or not. (same as previous)
    

There are also a few tricks used multiple times across the project:

• Setting multiple sequential bytes at once by casting the memory address to an ulong
• Treating the entity data as a big array by casting the pointer to an ulong pointer.
• Passing the raw bit data to a shader, and having the shader deal with drawing pixels.

Dev Process

I've made a lot of cellular automata in the past, so I first wanted to try a completely different method of solving the problem than I normally used, hence the quad tree. This also gave me a good way to compare & validate future algorithms. 

I also knew I wanted to use a double buffer strategy, and decided to store both the from buffer and the to buffer on the entity itself. This let me use the "SimulateStill" bool to easily see exactly what the input and output of a simulation was.

I also heavily utilized reusing allocated memory regions by using ChunkJobs and allocating outside the entity loop. I tried a few different counts of data per entity, before landing on 32x32 to have a decent entity to chunk ratio for parallelization. 

Not seeing a good enough performance with quadtrees I decided to swap over to arrays, since I knew grid based operations tend to work a lot better with them.  At some point I decided to start rendering stuff, and immediately wanted to try just passing a native array of data to the shader since I had seen methods for this earlier. 

After that I swapped between working on QoL changes and a slightly optimized simulation method, and eventually had to make it easy to use in a build. Since I felt like a random array wasn't the best way to showcase it, I decided to bundle a few different patterns that I felt were cool in their own way, and made a simple UI for it.

I did have some mishaps- I wanted to load from an image, but it ended up being too much of a hassle to be worth doing. I also tried a fourth simulation method based on 7x7 tiles, but it ended up being a lot of copy paste with minor modifications, and I didn't feel like debugging that.

Speaking of debugging, I ended up having to resort to a lot of tricks to get the debugger to work even with burst off. I also had issues with the editor not recompiling after I made changes, making my measurements way off when trying to pinpoint an issue.