Skip to content

Recursive Algorithm Design For Fools

I’m currently working on developing a tile-based (and turn-based) strategy game. The core movement procedures are similar to games like Fire Emblem, Advance Wars and the like; select a unit, and based on that unit’s “speed” or “movement” rating, the surrounding tiles will be highlighted to visibly indicate where this unit can make a legal move this turn. The player, with the unit selected, then selects one of the available tiles, and unit makes its move. Fun!

The highlighted tiles show you the legal moves this happy little unit can make Image via edge-online.com
Screen from Advance Wars series. The highlighted tiles show you the legal moves this happy little unit can make
Image via edge-online.com

This mechanic requires an algorithm! In a nutshell, we need to be able to start from some origin tile, and spread outward, one tile at a time, collecting available tiles, eliminating unavailable tiles (eg. obstacle tiles), and ultimately returning a complete list of the legal tiles our unit can end up on.

I’m a self-taught developer, so I’ve never taken any formal lessons in designing algorithms. When I approached this challenge originally a few months ago, I decided to try to be cleverer than I was, and solved this using a recursive function. (A recursive function is a function that makes reference to itself – check out my upcoming example and you’ll see what I mean.) I like recursion as a concept, and thought this would be a fitting opportunity to use it, rather than a simple  for loop.

Before coding anything, here’s what it would do:

Given XY coordinates of a tile in the grid system, it would…

  1. Check if the tile was accessible, by:
    1. Comparing the tile against a list of tiles occupied by the enemy
    2. Checking if the tile had the “obstacle” property
  2. If the tile was accessible, and not already in our list of accessible tiles, add it to our list
  3. If our current depth into the algorithm is less than the unit’s “movement” value (the maximum distance it can move in a turn), then it’s time to go one unit deeper by getting a list of the tile’s immediate neighbour tiles (the tiles that share an edge with our current tile), and moving on to step 4. If we’re as deep as our unit’s movement allows, finish checking the tiles at this depth, then move to step 5.
  4. Iterate over each of the neighbour tiles, and for each one, start from step 1!
  5. Return a complete list of our tiles deemed accessible

At the end of step 4 there, where we go back to step 1 with the new tile, that’s the point where the function calls itself again. This is why it’s recursive.

Here’s what the simplest final form of this algorithm looked like (Oh, yeah, forgot to mention, this is a JavaScript game):

cantPass is an array containing tiles that our unit can’t get passed. For now, this is just a list of tiles occupied by enemy units. The idea is that an enemy does not let a unit pass through.

By comparison,  cantRest is an array of tiles that our unit can pass through, but can’t stop on. This includes tiles occupied by the player’s own units. The idea is that friendly units will let you pass through without blocking your path, but you can’t be in the same place at the same time, because basic courtesy suggests that you not crowd your friends.

The selected unit (centre) can pass through its ally (pink, above) but cannot pass through an enemy (red), as can be seen in the inhibited tile selection beyond the enemy
Available tiles are dark. The selected unit (centre) can pass through its ally (pink, above) but cannot pass through an enemy (red), as can be seen in the inhibited tile selection beyond the enemy

The recursion happens at line 27 above, where the function calls itself with a new XY value, a subtracted-by-one value for distance, the same  cantPass array, and — what’s this? — an empty cantRest  array. Also, we pass in a new variable, tiles , which is an array of tiles we’ve already marked as available.

The empty cantRest  was one of my first bad-design red-flags. The most efficient way to eliminate tiles from the final list was to just do it a single time, after we were finished collecting all the tiles. This means that I wanted to do it only at the base iteration of the function (depth = 0), and never again at any other depth level. Without explicitly having a variable to keep track of our current recursion depth, the simplest way I thought to do this was to just tell each recursive function call that there were no cantRest  tiles to worry about. Pretty ugly!

Passing around that  tiles value was another flag. Every recursive function call needed to know the tiles we had already looked at, to prevent repeating work we’d already done. In order to achieve this, the ongoing list of tiles needed to be passed in at every recursive call, and then passed back as the return value. This passing around of an array variable just felt really dodgy to me. I’m sure there’s a better technical term than “dodgy” for why this design approach is not ideal, but like I said, self-taught.

Despite these things really bugging me about my design, the fact is, this approach worked for my early testing needs, so, still being pretty into the idea of recursion, I said to myself, “Cool!”, and moved on.

Until today.

Today I started testing the limits of this method. It ran arbitrarily fast for “movement” values (and therefore, recursion-depth values) of up to about 10 tiles. But when I gave a unit a “movement” value of 11, it started to take about a half-second to calculate. This is unreasonable, given that the single-threaded nature of my game code means that it’s slowing down animations. Up it to 12- or 13-tile movement, and forget about it. It took exponentially longer with each extra movement point. Frig. This was a terrible design.

I revisited my approach, using a simple for-loop method, rather than a recursive algorithm. This had a few advantages: No more passing around and manipulating of array variables between function calls; explicit iteration depth counting (which, okay, I could have done with the recursive method too); and way more readable design. Recursion, cool as it is, can be a bit of a mind-freak when an unfamiliar reader wants to get an idea of what is happening to each variable at a given point.

So using the same basic logic as before, I put it into a for loop, with an upper iteration limit of the unit’s movement speed. It currently looks like this:

It could still use a little cleanup, but this algorithm is WAY faster than before. For movement values of 25 tiles, I’m clocking speeds of about 2 or 3 milliseconds with the new method, compared to 2 or 3 universe-ages with the recursive method.

There’s probably many ways I could improve the recursive method to speed it up. But the gains I got from switching to a regular for loop are too massive to ignore.

My Takeaway Lesson: If I can do it with a for loop rather than recursion, I should do it with a for loop rather than recursion.

I should stop trying to be too clever for my own good.

2 Comments

  1. Sebastian Sebastian

    Hey Andrew.. it’s been a while, hope you’re doing well!

    I think you were pretty close with the recursive method. I think passing the lists doesn’t help, but the main culprit is probably checking the tile through every possible path.

    Try adding properties to each tile – occupied, cantrest, cantpass, and checked to avoid passing lists. When checking the tiles, mark them as checked so you don’t end up re-checking them or going through that path again. I haven’t coded in javaScript much, but if you need some help let me know!

    Happy New Year!

    Sebastian

    • plorry plorry

      Hey Sebastian,

      Yep, without a doubt, my naive recursive solution was retracing steps already tread, which is why it exploded exponentially. Logging the checked tiles in an array was my way of keeping track, but I wonder if using a “checked” property on each of the tiles themselves would be more efficient than referencing against this array.

      Thanks, and happy new year to you too!

Leave a Reply

Your email address will not be published. Required fields are marked *