As you may or may not know, one of NIFTY’s core mechanics (if you want to call it a mechanic) is random/procedural generation of stuff. We’ve been discussing quite a bit about what parts of the game should be generated and what should be just fixed (balance between time consumption and awesomeness). One of many aspect we really liked but didn’t know if it was feasible was generation of enemies because of the huge amount of expected time we would need to implement it. As it turns out, generating sprites (and models from these sprites) is way simpler than we dared to dream. It only took 1 hour from an idea to a working prototype and a few more hours to get the whole thing to a useable stage.

Idea
First some restrictions for our generated sprites were necessary to make the generation easier and to get a rough picture of what we want. The most important restriction comes from the idea that these sprites should look like they represent something and what does the human brain like to find the most in random things? Faces. Simply put, everything that has a symmetry and some kinds of dots in it looks like a face to us. Be it animal, monster or robot, if it has a face we know we can interact with it. That said, our first restrictions is that the sprites needs to be symmetrical. Our second restrictions is as simple as our first one, we want all pixels in the sprite to be connected to each other.

The second restriction can easily be satisfied by using an algorithm which builds on already set pixels and ‘grows’ them into a sprite.

Algorithm
Enough text for now, let’s start with some more specific instructions:

1. Set a seed point in the middle of the sprite
2. While not enough pixels set do:
   1. Randomly select a pixel that’s next to a set pixel
   2. Compute probability for setting this pixel (decision function)
   3. Set the pixel using the probability from 2.B
3. Profit!

Well that’s it. Nothing spectacular here. One bit of magic is hidden in the decision function
but even if it always returns a constant value it already generates nice images:

By adding some lighter and darker spots (again at random) and changing the decision function we can influence the generated sprites more. In our case we want some ability scores (health, speed, power) to influence the look of the sprites so the player can estimate what type of enemy he’s looking at. Here are some examples of what the generator spits out in it’s current form:

High health: big, low detail

High speed: small, high detail

High power: medium size, high detail, more light/dark spots

Code excerpt
Here are two code snippets (in Java) from our implementation to give you some idea how it is implemented in NIFTY.
Note: the openList for storing points that haven’t been checked yet and the closedList for points that have been check are both of type HashSet<Position> .

Generation loop:

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

public void generate() {
	long seed = r.nextLong();
	r = new Random(seed);
 
	long time = System.currentTimeMillis();
	clear();
	int iterations = 0;
	for (int count = 0; count < (w * h / 2) * fillPercentage; ++iterations) {
		count += grow() ? 1 : 0; // count amount of pixels set
	}
	addDecoration();
 
	System.out.println("Runtime: " + (System.currentTimeMillis() - time) + "ms");
	System.out.println("Iterations: " + iterations);
	System.out.println("Random seed: " + seed);
	}
}

Growing step:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

public boolean grow() {
	// System.out.println("Open list size: " + openList.size());
	// System.out.println("Closed list size: " + closedList.size());
	int xx, yy;
	Position p;
	Iterator it;
	do {
		it = openList.iterator();
		p = it.next();
 
		// Randomly pick element
		int num = r.nextInt(openList.size());
		for (int i = 0; i < num; ++i) {
			p = it.next();
		}
 
		xx = p.getX();
		yy = p.getY();
 
		if (pixels[map(xx, yy)] != PColor.EMPTY) { // Pixel is already set
			// Move to closed list
			it.remove();
			closedList.add(p);
		}
	} while (pixels[map(xx, yy)] != PColor.EMPTY);
 
	int countSide = 0, countDiag = 0;
	for (int ix = xx - 1; ix <= xx + 1; ++ix) {
		for (int iy = yy - 1; iy <= yy + 1; ++iy) {
			if (ix < 0 || ix >= w || iy < 0 || iy >= h / 2) // outside drawing range
				continue;
			if (pixels[map(ix, iy)] != PColor.EMPTY) {
				if (ix == xx ^ iy == yy)
					++countSide;
				else
					++countDiag;
			}
		}
	}
	// Check if we should set this pixel
	if (r.nextFloat() < evaluator.getPixelSetChance(countSide, countDiag)) {
		pixels[map(xx, yy)] = PColor.NORMAL;
 
		// Move point to closed list
		it.remove();
		closedList.add(p);
 
		// Add surrounding points to open list
		addPoint(xx + 1, yy);
		addPoint(xx - 1, yy);
		addPoint(xx, yy + 1);
		addPoint(xx, yy - 1);
 
		return true;
	}
	return false;
}

This enemy generator is neither finished nor integrated in the game yet, and the colors need some tweaking as well. We hope to be able to show the first completely procedurally generated enemies within the game soon…