Motivation is key when survival is not at stake.
Let me unpack that. You have no lives to save in making your video game. You aren’t fending off starvation. Nor are you placating an angry god, or proving worthy to a prospective meal ticket. No, if you have the ‘luxury’ of making a game then it’s unlikely that anything at all in your universe could be said to be truly urgent. Which incidentally, is why I despise the use of the arrogant if not histrionic term ASAP, but that’s another story.
In short, if nothing is urgent then the only motivators we can rely on must come from within. To support this, we need to find something that truly excites us. Something that will keep us coming back to our game again and again, to finish what we started. Especially when the self-doubt starts to creep in. And it will.
I know the kind of games that I love to play. But that doesn’t necessarily equate to the kind of games I love to make. Having played with many ideas over the years, I’ve come to understand that the one thing that really excites me is emergence.
The interaction of components within a system that gives rise to unexpected outcomes is fascinating to me. I want players to come up with strategies that I did not envisage. That is what will keep me working on my game. That is my personal mechanic; you’ll need to identify your own.
However I’m not about to embark upon a full-blown emergent physics sandbox title for my first game. (That’s my second game). I haven’t even learned how to use Unreal Engine — my game engine of choice — at this stage, so it’s very important not to let one’s ambition run amok.
"When you’re going to be doing absolutely everything yourself, there’s no such thing as unambitious."
I decided to pick a genre that I know implicitly. I thought of the arcade classics and I remember loving top-down maze-based games like Pengo and Bomberman. The intricate mechanics and the fast-paced play provided a great core experience and I definitely wanted to incorporate some aspects from those games into my own.
The first step then is to prototype this idea. Often what sounds simple enough in game design is anything but, in implementation. These homing mines will need to be able to detect enemies potentially anywhere on the grid. So a simple square-by-square search should solve this. Here’s an example grid, with our homing mine in the bottom-left and a target near the centre.
So we’ll search every neighbouring square, then in the next step search each of the neighbours’ neighbours and so on, until we locate the target.
Let’s create a rule. Each time a square is reached during the search, this new square ‘remembers’ which neighbouring square it arrived from. Let’s call this the parent square. Neighbours are easily located as they are either up, down, left or right of any given square.
Upon locating the target, the search ends. Then we back-track from the target to the origin by re-tracing our steps. Each searched square remembers its parent square, so we simply follow the breadcrumb trail back. This provides us with the exact path that the mine should follow in order to reach the target.
This works well enough for a simple grid and indeed this algorithm is a classic example of a breadth-first search. In fact, an A* algorithm would generally be more optimal for this problem. But what if we introduced a pair of portals into the grid? Searching immediate neighbours becomes more complex, because sometimes a square’s neighbour may be on the other side of the grid, rather than adjacent to it. Consider the following.
To account for this, we need to explicitly tell each square where its neighbours are located, rather than a simple cardinal direction. We do this by creating a list of locations that each square can get to in a single step. So any square with a portal on it can have potentially five neighbours: up, down, left, right and… over there where the portal’s twin is located.
We store all of these sets of neighbours for each square in an adjacency list. Now we can perform the same method as previously and the algorithm will solve the search, traversing portals where the path is shorter than by using the standard cardinal directions
The beauty of this approach is twofold. First, we can solve the path to any square on the grid, from any square on the grid. This means that we can easily trace paths for all mines on the grid without having to perform another search. Until the grid changes of course. Obstacles could be potentially added and removed. And the portal sets themselves may relocate.
The second benefit is that this approach will work for any number of portal sets. It will even resolve the adjacency list in pretty much the same amount of time regardless of how many portals there are. Here’s an illustration with two sets of portal twins.
So there you have it. That’s the primary mechanic; a simple set of rules that will hopefully give rise to multiple tactics, some that I may not even foresee. This excites me enough to believe that there’s a genuine game here that has not been seen before. And that, ladies and gentlemen forms the cornerstone of our motivation.
Breadth-first Search With Portals — AKA The Minesheeper Algorithm
Darby Costello is a software developer, learning technologies consultant, solo game dev, graphic designer, mad scientist and educator. If you ever see him out, he'll either be sat in the corner exchanging views on Chomsky with a pot plant, or in the centre of the dance floor befriending complete and probably non-reciprocating strangers.
Other articles in this series: