Press space to switch to the next generation. This...this is the project that I've been working on for the past week. I dreamt about this system every day and night of Spring Break. It might not seem like much on the outside, but it's the index within this project that represents the true value. To explain why this is important, let me re-iterate how Conway's Game of Life works. In most Conway's Game of Life emulators, the system is very simple: Step 1) Transfer the raw grid data onto a temporary array. Step 2) Sweep through the temporary array and apply the rules to each item. Instead of replacing the items in the temporary array with their updated states, replace the items in the permanent grid array. Step 3) Delete the temporary array. Step 4) Render. Step 5) Repeat. This method may be simplistic, but it's effective. However, there's still room for optimization. Tons of methods and algorithms have been created to speed Conway's Game of Life up. Most notably, Hashlife. I won't go into the details of how exactly Hashlife works, but one of it's major tricks is to identify repeating patterns in the grid, and predict their next states. Hashlife is very, very efficient, and is capable of generating the trillionth state of a huge life form in just a matter of minutes. But...there is one experimental technique that reigns supreme above all others: Combinatorial Optimization, or CO for short. CO works by calculating the next generation of every possible state in a grid. The program stores this information into an array, and now the fun begins. Now that the program has an array with every single possible state cross-referenced, it can run at the speed of light (not actually, but still very, very fast). All the program has to do from here on out is retrieve the next generation from the array, switch to that state, and render. There are tons of methods (that I'm currently brainstorming) to optimize this system even further. There's one obvious flaw: storage. A simple 4x4 grid has 65,536 states, which is nothing. A 5x5 has about 33.5 million. (≈104.8 MB) And a 6x6 has over 68 billion. (≈309.2 GB) This is a devastating problem, but thankfully, there are a handful of ways to fix issues like this. Here are a few: - Eliminate all Garden of Edens (GoEs). GoEs are a term used in cellular automata for states that can't be reached by any other state. A great way to free up some space (after the index has already been created) would be to erase all impossible states. Also, there's a hypothetical formula that could be used before the index is finished that would allow the program to identify if a state is a GoE. This formula would be a game-changer, and could be the solution I need to make this system actually usable, and not just an neat little concept. - Instead of calculating all combinations of a huge grid, divide it into several 2x2 subgrids, and create a new index that operates by determining the subgrid's next generation based on the state of the surrounding subgrids. There are about 68,719,476,736 possibilities. - I'm researching more optimization methods as you're reading this, so stay tuned for more! It should also be noted that this index I've created has more uses than simply making CGoL programs run fast. Using the data I've collected, we could discover tons of things about not only Conway's Game of Life, but cellular automata as a whole! I'm definitely going to make some projects using the index in the future, illustrating my findings. One last thing: I'm sure that there's at least one person who has done something like this before, but I couldn't find anything on the web, so this is, AFAIK, the first time the entire 4x4 index has been mapped out, which is epic. Also, "Combinatorical Optimization" is just fancy-talk for bruteforcing, which is sorta what this is. There's probably a better term for this, so please let me know if you find one. In the case of TL;DR, here's a step-by-step of my program's process: Step 1: Go through every possible state that the grid can be in and calculate said state's next generation. Add the next generation's data to an array. Step 2: Identify the current state's (which will be the user-input life form on G0) placement in the array, and find the next generation. Step 3: Render. Step 4: Repeat from Step 2. Good morning, and in case I don't see ya, good afternoon, good evening, and good night!
