Le Subrat CDR Blob Sim

Historical Context

This project was completed in a rapid two-day span during my first finals season at Berkeley.

Technologies

Utilized a combination of C++, SFML, and Java.

Challenges

• Defining an abstract problem and devising a solution strategy.
• Working under a strict deadline.
• Ensuring algorithm efficiency.
• Addressing issues related to determinism and the halting problem.

Achievements

Successfully overcame all challenges, conceptualized, designed, and implemented an innovative algorithm.

The Story

My first semester at Berkeley was very busy; I didn’t have any freedom or time to code anything for fun 🙁. That is until CS 61b announced the BYOW project! Before I fully understood the spec of the project, I heard “Build Your Own World” and instantly thought “oh man, I’ve been thinking about Microcraft-Rat for years now, I’ve been meaning to go back and realize that project's vision for so long…” The last time I worked on it, I was trying to create a better world generation system. Wait, if BYOW is just a world generator program, I should go all out so I can use the ideas and code for my own project.” That was essentially my mentality for the whole project. Because of that, I instantly got to work and started thinking about what makes a cool world… “Biomes” I realized. So I instantly turned to one of my favorite games for inspiration, Wollay’s Cube World (alpha). I looked at the biomes/regions in that game and tried my best to understand how the game made theirs. My initial thought was Perlin noise; however, a limitation was that we couldn’t use any external libraries, meaning I would have to implement a Perlin noise generator myself in Java. This didn't bother me; however, it just didn't look like Perlin noise was used to create the biome shapes. After some deliberation, I came to the idea of cellular automatas. I had made some before thought that maybe if I just create a cellular automaton where clusters of cells “blobs,” I called them, grow organically/randomly. Essentially, each generation of the cellular automaton, a mass of cells would “grow” a new cell somewhere on its perimeter, and after enough generations, the mass would take some random organic shape. Before sitting down and writing any code again, and because now I was taking a data structures class, I thought about some math and CS. What is the time complexity if i do it like this? What about the space complexity? Is it deterministic? If the probability distribution of where on the perimeter the blob can spawn is even everywhere, then will the blob converge to a circle? Pondering all of these questions and optimizing the algorithm to achieve the desired behavior twice, I was happy with the implementation in mind, so I sat down and got to work. CS 61b is a class taught in Java, but I am so comfortable in C++ and SFML and already had a cellular automaton framework written that to prototype the idea, I wrote it in C++ over the course of 2 days. Amazingly, it worked better than I had initially thought. And by the quirk of the cellular automaton framework I had, I discovered an incredible unintended feature (not a bug) of the algorithm which excited me a lot. Anyways, I had proved to myself that the algorithm creates organic cellular shapes so I could use it for biomes in BYOW.