From an idea to a working game in 7 days — part 2

After being able to generate an endless variety of game levels, I needed to think about what my game should actually be, and what challenges I would have to overcome.

So, how did I get from this point to what can be seen in a screenshot of the final application below?

My first decision was that this project should not take more than a couple of days to finish (or about the same amount of time I would usually spend on Launch School over the course of one week). I would, of course, use Ruby for that project, since it’s the language I’m most comfortable with right now.

I then created a list of the absolute minimum number of features that would make a playable (and at least partly enjoyable) game experience:

1. a hero character that can navigate through caves tile by tile
2. monsters that follow the player and attack him
3. a combat system for dealing with those monster
4. a user interface that is at least a bit pleasant on the eyes

That was roughly the order in which I wanted to approach that project. Thinking about each of those features, I figured out a few major obstacles that I needed to overcome:

• Application output — I needed a quick and reliable way to draw my game on screen, either through the terminal window or in some kind of visual UI.
• Pathfinding algorithm — Enemies need to move and therefore need to determine a path to the player character. I knew there were probably algorithms that I could implement, but that was the extent of my knowledge.
• Code organization — This was the biggest programming project that I ever tackled, so I had no idea how I could keep my code from becoming a tangled spaghetti mess. I needed a way to restrict the responsibilties of each component and somehow orchestrate all those components into one big game loop.

Using Launch School’s trusted PEDAC approach, I methodically began to build every feature. My first decision had to be made quickly: how do I handle input and output?

The cost of graphical fidelity

My initial idea was to leverage the standard terminal to display my game in full ASCII like the Rogue-like games in the days of yore. I played around with Ruby’s IO#raw mode for reading character input, but the bigger problem was the output rendering: I found a way to use ANSI escape codes to move the cursor inside of the terminal and draw stuff where I wanted it to be, but the performance was abysmal. Drawing my cave maps on screen resulted in a flicker of quick cursor movements.

There are libraries like ncurses, which provide an API for the proper rendering of terminal applications, but the Ruby gems I found that wrapped this C-based library were either outdated or sparsely documented.

Being in the backend development part of Launch School’s Core Curriculum, I fell back to a much simpler solution: I would use Sinatra in the backend and be able to let the browser handle both user input and game output. That had a couple of advantages:

It forced me to keep a strong separation between the frontend and backend, which, in turn, would help me with the organization of my code. I was also free from the shackles of ASCII terminal output and could use both HTML and CSS to create a pleasing GUI. Lastly, it made handling user input as easy as creating a single Event Listener in JavaScript.

The different languages I used for the project

This decision for Sinatra had an interesting effect: only three quarters of my final code was written in Ruby. The rest is divided between the three frontend languages. I didn’t particularly enjoyed creating the frontend, since I still haven’t reached the Launch School courses on HTML, CSS and JavaScript. I had to resort to the spotty knowledge I had acquired in my futile attempts to learn coding in the past, and that made for an unsatisfying workflow, oscillating between Google, the MDN documentation and Stack Overflow.

Pathfinding, or: don’t fear the algorithm

It didn’t take long to implemented a general game loop and a character that could walk around in an empty map. Now it was time to face what I perceived as the biggest challenge: pathfinding.

The shortest path from a monster (M) to the player (P).

I figured that I needed an algorithm for a whole bunch of problems: first, to find the path that a monster needs to take in order to reach the player. But I needed even more info: how far away is the monster from the player? What is the farthest cell from the player (I wanted to put the level exit as far away as possible)? Is a monster in range of a possible player’s combat ability?

Ideally, I would have an algorithm that I could use for all of those cases. I looked at what Wikipedia had to say about pathfinding, and found out that the most commonly used algorithms all relied on the idea of representing the problem as a graph. Having dealt with graph-based data structures before, I adapted a simple Breadth-first search algorithm. Let’s look at how it works:

The root node of the graph

To get the path from a monster to the player, we create a tree-shaped graph with the monster cell as the root node. Each node is a simple construct, that holds information about its grid coordinates and can return the positions of its neighbor cells:

class Node
  def initialize(position)
    @x, @y = position
  end
  def position
    [@x,@y]
  end
  def neighbors
    adjacent = [
      [-1,-1], [0, -1], [1, -1],
      [-1, 0],          [1, 0],
      [-1, 1], [0, 1],  [1, 1]
    ]
    adjacent.map { |dx, dy| [@x+dx,@y+dy] }
  end
end

To create branches for our graph, we look at the root node’s neighbors:

The neighbor cells of the monster.

We can safely ignore wall cells (colored in grey), because they cannot be entered by either players or monsters. That leaves three neighbors for our example above.

Those three neighbors comprise the first branches of our tree. To represent this in code, we use two variables, an array and a hash, to store both the cells we need to explore and the cells we already visited:

@explore = []
@visited = Hash.new(nil)

Our root node is the initial cell to be explored, so it gets added to the array:

@explore << @root
@visited[@root.position] = [0, []]

In our hash, we save the distance from the root node (which is 0 for the root node itself) and information about the path we took to get to the current node (an empty array in the case of the root node).

Each of those three neighbors of the root node gets added to the array of cells to be explored. In a simple loop, we take out the first element of that array and visit it. That means, if that node hasn’t been visited before, we save information to the hash: a distance incremented by 1 from the parent node’s distance, and the node’s position added to the array of steps from the parent node. Finally, we add all neighbors of that visited node to the array of nodes to explore next.

The algorithm stops when there are no more elements in that array of nodes to be explored. We return our hash, that now contains information about the distances and possible paths to any cell. Voilá, we implemented breadth-first search and can now solve all the aforementioned problems: finding out about the paths to a certain position and the distances to all other cells in the level.

Breadth-first search in action

I implemented a basic enemy type and let it loose on the player. It was marvelous: I could play hide and seek! But as I added class after class to the project, I needed a solution to my now biggest problem: how can I orchestrate everything as I add even more features?

Read the final part 3 or look at the project’s GitHub repository (my pathfinding algorithm can be found in the lib/pathfinder.rb file).