Procedurally Generated Isometric Roguelite in Go AKA Diabgo¶

I've wanted to learn Go for awhile and I decided that building a game was the best way for me to learn a new language. There are two excellent simple game frameworks in Go, Pixel and Ebiten. I actually started out programming this in Pixel and ported 90% of it over to Ebiten, which only took a few hours. Some features that are available in Pixel I haven't figured out how to replicate in Ebiten, like live typing text and direct geometry drawing, but Ebiten can target mobile and is being developed more actively.

My favorite game growing up was Diablo II. I always thought it would be neat to build something like that. I've on a few top down games, but hadn't attempted an isometric game up until this point. Isometric games are 2D, but simulate 3 dimensions being seen from an angle. This is usually 60 degrees.

Painter's Algorithm¶

One of the challenges of making an isometric game is that the tiles are not square, and they must be drawn in a particular order. The further away tiles must be drawn after the closer tiles. The process of ordering these tiles is called the painter's algorithm. One complicating factor is that changing the draw target in Ebiten severely affects performance, so layering the elements of the scene requires intention around how to structure the draw function. Below is an example of what can go wrong:

Animations and Blender Scripting¶

Diablo 2 graphics had two characteristics that gave it its magic: a limited color palette and 8-way directional sprites generated from a 3D render. Nearly every Go game example I've come across has a gopher as its main character, so I figured mine would as well. I set out to find a 3D model of the Go mascot. I ended up buying this for $5:

But this model came with no animations. To animate my new gopher model, I exported it from Blender as an FBX file and uploaded it to Mixamo.

I picked out the animations I wanted, trimmed them to get good loops, downloaded these animations as an FBX file, and reimported them into Blender. To get 8-directional animations, I set my camera to Orthographic, attached it to a BezierCircle and contrained it to look at an Empty object on the ground at the origin. I locked all the rotations on the Bezier Circle except the Z. Now the stage was set.

I could output each angle manually, but that would take a really long time, and I would almost certainly make a mistake. Instead, I used a Python script to rotate the model and output animation frames to the appropriate directory:

import bpy
from math import radians
from os.path import join
import os

S = bpy.context.scene

renderFolder = "/Users/wegesdal/Documents/blender/gopher/render/idle"

camParent = bpy.data.objects["BezierCircle"]

animLen   = 60
numAngles = 8
rotAngle  = 360 / numAngles
startFrame = 1
skip = 6

for i in range(numAngles):
    angle = i * rotAngle
    camParent.rotation_euler.z = radians(angle)
    angleFolder = join(renderFolder, "angle"+str(int(angle)).zfill(3))
    if not os.path.exists(angleFolder):
        os.makedirs(angleFolder)

    for f in range(startFrame + 1,startFrame + animLen + 1, skip):
        S.frame_set(f)
        frmNum   = str(f).zfill(3)
        fileName = "angle_{a}_frm_{f}".format(a = angle, f = frmNum)
        fileName += S.render.file_extension
        bpy.context.scene.render.filepath = join(angleFolder, fileName)
        bpy.ops.render.render(write_still = True)

At this point I have a directory for each action (6) filled with each angle (8) filled with 10 frames of animation. That's 480 images to stitch together into a spritesheet. So I opened PhotoShop, created 480 layers, and moved them together with the mouse.

Just kidding. I used another Python script to stitch the images together into a spritesheet:

import sys
from PIL import Image
import os

def filter_hidden(s):
  if s.startswith('.'):
    return False
  else:
    return True

name = "gopher"

path = "/Users/wegesdal/Documents/blender/"+name+"/render/"
poses = [q for q in filter(filter_hidden, [p for p in os.listdir(path)])]

print(poses)

sprite_size = 512
max_height = sprite_size * len(poses) * 4
print("max_height: {}".format(max_height))
number_of_angles = 8
number_of_frames_per_angle = 10

new_im = Image.new('RGBA', (sprite_size*number_of_angles*number_of_frames_per_angle//4, max_height))
for i in range(len(poses)):

  angles = sorted([r for r in filter(filter_hidden, [s for s in os.listdir(path + poses[i])])])
  print(angles)
  for a in range(len(angles)):
    pics_list = sorted(filter(filter_hidden, [p for p in os.listdir(path + poses[i] + '/' + angles[a])]))
    pics = [Image.open(path+poses[i]+'/'+angles[a]+'/'+p) for p in pics_list]
    max_width = sprite_size * len(pics) * len(angles) / 4
    print(max_width)
    num_frames = len(pics)
    for f in range(num_frames):
      # paste
      y_offset = i * sprite_size * 4 + (a // 2) * sprite_size
      x_offset = (a%2)*num_frames*sprite_size + f*sprite_size
      new_im.paste(pics[f], (x_offset,y_offset))

new_im.save(name+'.png')

A* Pathfinding¶

What prevents the character from moving through the walls? In most modern games, this behavior is usually handled by a physics system that detects collisions by modeling the physics of all objects in a scene. In games like Diablo II, the pathfinding system actually simulates the appearance of collisions by simply not allowing movement outside a discrete number of nodes. The map data already contains information about what texture to render on it, so we can add to that structure a boolean value: whether the tile is walkable or not. When the mouse is clicked, how does the character know where to move on the screen? When the player clicks the mouse, the game converts the screen coordinates into map tile coordinates and accesses the level array. If the chosen tile is 'walkable' then the A pathfinding algorithm commences. A is a graph traversal algorithm that calculates a path by looking at the neighbors of the current node and calculating the distance to the target square. Depending on whether or not you are allowing diagonal moves, you use either the diagonal or manhattan distance for this calculation. The return value is a list of nodes representing fastest path between the actor and its destination.

You can check out my implementation of A* in Go here: https://github.com/wegesdal/diabgo2/blob/master/a_star.go

Symmetric Shadowcasting¶

The next thing I set out to do was implement a method for calculating which cells would be visible or not. I tried out a few algorithms and finally settled on this one: https://www.albertford.com/shadowcasting/

The whole point of this project was to get the hang of Go, and a great way to learn a language is translating stuff from one language to another. His original article is written in Python, which I am very familiar with. The algorithm is called symmetric shadowcasting, and the basic idea is that the slopes of all the lines extending from the player in 4 quadrants are calculated row by row one quadrant at a time to detect sight blocking terrain. In my case, I just used the same condition as walkable as I did for sight blocking, but this would be trivial to change. You can see in this picture the pillars create shadows behind them as they move away from the player.

You can check out my implementation on github: https://github.com/wegesdal/diabgo2/blob/master/fov.go

Floyd-Steinberg Dithering¶

The sprite is in the game world, but it looks a little odd. The reason for that is something I mentioned earlier, the limited color palette. If you simply reduce the palette size in Aesprite as I did here, it reduces the palette pixel by pixel to its 'nearest neighbor.' It looks for the smallest Euclidean difference between each pixel and the RGB values of the chosen palette. I decided to use the palette of my map tiles, which had 16 colors. The reason this sprite and the map tiles clashes is that it nearest neighbor doesn't have any dithering. So I got out my spray can tool and manually dithered all 480 sprites. Just kidding. I used an algorithm called Floyd-Steinberg dithering: https://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dithering

My script for the algorithm is slow on large sprite sheets, so I am going to work on speeding it up by using numpy matrices rather than PIL getpixel and setpixel functions. Here it is in its current form:

I also added a little something extra to this Floyd-Steinberg implementation, a black outline. If the alpha of the neighboring pixel is 0, it makes that pixel black instead. This gives the sprite a classic pixel art look.

Perlin Noise and Procedural Generation¶

But we haven't talked at all about how the world is procedurally generated yet. I reached out again to the wonderful world of algorithms and pulled this article: https://en.wikipedia.org/wiki/Perlin_noise

Perlin noise was first famous for being used in the movie Tron, where it was used for mind-blowing (at the time) computer visuals. Perlin noise is also famous because it is used in Minecraft and countless other games to produce organic looking noise. This is usually used for map features like elevation or vegetation, but it can also be used to place clouds, items, monsters, etc.

Perlin noise works by taking an array of pseudorandom vectors representing gradients between each cell and its four neighboring cells (in 2D) and interpolating between them for each tile in the map (because the map array is larger than the gradient array). At any position x, y in the level tilemap, a number is calculated (the level position is projected onto the gradient array). This number could be big or small and these values can be mapped to tile types or monster types or whatever you can dream up.

Here is my implementation of Perlin-Noise in Go: https://github.com/wegesdal/diabgo2/blob/master/noise.go

Here is a procedurally generated map:

One additional feature I added to the map generator is a road builder and a river. The road builder attempts to find a path with A* pathfinding (no diagonals) and if unsuccessful, a new map is created with tweaked parameters. The change in parameters makes it successively less likely for movement blocking terrain to be created. Once a suitable map has been found, a river is constructed by connecting two random points across the other map axis, and if the road tile is encountered, a bridge tile is put there instead of a water tile.

You can check out the map generation script here: https://github.com/wegesdal/diabgo2/blob/master/map.go

AI State Machine¶

The AI is a state machine based primarily on proximity for non player characters and mouse input (and proximity) for the player character. The state machine controls animation state, movement, and damage. For example, if the non-player actor has a hostile actor in its pursuit range, it will path to that actor, otherwise, it will move toward its destination (the end of the road). If the non-player actor has a hostile actor in its attack range, it will enter the attack state, and deal damage on its last frame of animation. Check HP for death state transition and check for dead actors in a separate cleanup loop. If the player character has reached its destination, it enters the idle state, otherwise it enters the walk state. Unless it has a target, then it moves on the target until it is in range to attack.

If you've made it this far, you understand everything that went into making that silly GIF at the beginning.