Yesterday I wrote a cellular automaton based procedural caves generator algorithm that fits in a business card. The algorithm itself is not new. I already did it in C++, Rust, Javascript and many more languages. It is my personal approach to “Hello World”: when I want to try a new language, write a PCG algorithm in it.

Background

Why I did that? Let’s start from the beginning. In the last couple of week I decided to start refreshing my C++ knowledge. I don’t really enjoy C++, in general. I think the language is cool, especially when you work with the most recent standard, C++14. But I hate the header stuff. It makes my head hurts, it makes compilation slow, it introduces an entire class of compilation errors that I hate to debug, and more. A module system for C++ will never arrive soon enough. Anyway… C++ is important, in particular for people like me that are in continuous contact with the game developer world. I need to keep C++ in my resume, someway. Therefore, after updating my internal knowledge base to the most recent standards and best practices, I decided to test it with a small project. I decided to do the most unoriginal thing I could imagine: a ray tracer algorithm. The project is going well, however, looking for resources I found this article by Matt Zucker. In it, he describes his challenge of writing a ray tracer algorithm that fits a business card. I thought it was cool. Even if I never got into code obfuscation challenges -it makes my OCD side to cringe and lay down in pain- I thought it was a nice idea for a business card. I wanted to try. Of course, I could not do the same with a ray tracer algorithm; I already had my problems with the non-obfuscated version. Then I remembered that I already had a C++ code doing something I like (Procedural Content Generation) that is a good candidate for this: my cellular automaton code.

The Experience

The final code (version 1.1) is shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>// Info: https://goo.gl/s3W2MG
using i=int;template<i W,i H>struct minicave{bool
map[H*W];minicave(){for(i r=0;r<H;r++){for(i c=0;c
<W;c++){k(c,r)=c==0||r==0||(c==W-1)||(r==H-1)||r!=
H/2&&rand()%10<4;}}}i e(bool C){for(i r=0;r<=H-1;r
++){for(i c=0;c<=W-1;c++){i w=nw(c,r,1);k(c,r)=k(c
,r)?w>=3:C?w>=5:w>=5||nw(c,r,2)<=2;}}}i nw(i x,i y
,i r){i w=0;for(i Y=y-r;Y<=y+r;Y++){for(i X=x-r;X
<=x+r;X++){if((X!=x||Y!=y)&&(X<0||Y<0||X>W-1||Y>H-
1||k(X,Y)))w+=1;}}return w;}bool&k(i x,i y){return
map[x+y*W];}auto str(){std::string s;for(i r=0;r<H
;r++){for(i c=0;c<W;c++){s+=k(c,r)?"#":".";}s+=
"\n";}return s;}};i main(){srand(getpid());
minicave<80,80>m;for(i j=0;j<4;++j){m.e(false);}m.
e(true);std::cout<<m.str();}

Reaching this point was not particularly hard. Most of the work went into reducing the automaton rules into a head-hurting sequence of ternary operators ?:, plus removing/inlining all the unnecessary functions. In a full morning, I reduced the original 3000 chars implementation into a <700 chars version. Because I reached this point without doing too much obfuscated stuffs, I decided to keep the code “usable” as much as possible. In fact, I could probably remove many other chars by hardcoding some value, but I prefer to have the code (relatively) scalable and functional. For this reason, it not just a code producing a random cave when executed, but it is a (relatively) “complete” library, so it is possible, in theory, to build any N*M map and apply different sets of rules. :)

What I learned

When I started I did not think to learn a lot. My first idea was to work as a brainless compiler and cut everything I could. However, in reality, I needed to do much more than that. During the experiment I learned many things and even found solution to improve the original Cellular Map code (the not-minimized one) such as avoiding heap allocation for the map, using boolean values instead of integers and killing few bugs in the process! In the end it was an interesting experience that makes me unjustifiably proud of the result. I enjoyed the process and inspired me to try to do the same to other PCG algorithms I have sitting in my hard drive (L-System, dungeon generators, solar-systems generators and more).

##################################################
####.....###...###...#############################
###.......#...........#..#########################
###.......................##################...###
###........................################.....##
####........................##############.......#
#####.................#.....##############.......#
######...............###....########..####......##
######...............####..########.....##.....###
######..............##############............####
#######..###......################.............###
#############.....#########..######............###
#############.....#######.....######...........###
##############...#######........####...##......###
#############.....#####..........####..##.......##
##########.......................####............#
#########........................###.............#
#########...........##............##............##
########............##..........................##
######..........................................##
#####...........................................##
#####..........................#.........####..###
######........................###.......######..##
#######.....................#####.......#####....#
######......................####.........#.......#
######...........................................#
######..........##..................##...........#
#####....#####..##.................###...........#
###.....######...##...#............##...........##
##......#####....########......................###
#.......####......########..##..................##
#........###......########..##...................#
#........###......########.......................#
##.........#.......######......#.................#
##..........#......######.....###...............##
#..........###.....######.....####..............##
#..........##.......######.....###...............#
##.........##........######.....###.....##.......#
###...................#####......###...###......##
####...................#####.....###....#.......##
####....................######.................###
###......................#####...............#####
###................##....###......##........######
##................###.............###......#######
##...............####.............####....########
###..............#####............######..########
#######...#......########.........################
############.....#########....#..#################
##############..###########..#####################
##################################################

This is the canonical example of the output. The commented code can be found on my repository.