Velwar Range Highlighting

🎼 The Sacrifice and the Saint

“Velwar” is the current name of the Fire Emblem clone I'm working on for fun. One of the nice features of this style of game is the ability to select or hover over a unit on the map and see all of the spaces that the unit can move to and/or attack/heal, like shown in this image:

(Only movement will be discussed in this note, but the other ranges simply add onto it and use different colors for highlighting.) I wrote some prototype code in the game's drawing routine to do this — here's the pseudocode version:

for j := -unit.Move; j <= unit.Move; j++ {
for i := -unit.Move; i <= unit.Move; i++ {
        if abs(i) + abs(j) <= unit.Move {
                drawSquareAt(unit.X + i, unit.Y + j)
        }
}
}

Nice and simple, right? Iterate over the full region of tiles defined by the unit's maximum movement, and if the Manhattan distance of a tile's location (which is simply the sum of the absolute values of the coordinates) is within the unit's Move, then draw a highlighting square over that tile. However, this algorithm is far too limited once I add in two more features:

1) I also want to be able to select a set of enemy units and see the resulting danger region, like in this image:

With this, the original algorithm is bad because it doesn't keep track of which tiles have already been highlighted and will repeat work for overlapping regions. So, the improved version needs to track tiles somehow. That's easy enough to do with a set, and has a bonus side effect that I can generate the set only when units are moved, rather testing the larger range of tiles before every frame is drawn:

for j := -unit.Move; j <= unit.Move; j++ {
for i := -unit.Move; i <= unit.Move; i++ {
        if abs(i) + abs(j) <= unit.Move {
                addToHighlightSet(unit.X + i, unit.Y + j)
        }
}
}

And now in the draw function:

for p := range highlightSet {
        drawSquareAt(p.x, p.y)
}

2) I want different movement and terrain types, which affect the cost of moving into any given tile, as well as things like walls and enemy units that prevent tiles from being occupied. The simple loop is completely unable to handle this — or at least, doing it via that loop would be more convoluted than what I'm going to do.

And so, I ultimately realized that this is a tiny, innocent little search problem. The algorithm is now recursive, starting at the unit's position. Here's more pseudocode:

func collect(x, y, d int) {
        if inHighlightSet(x, y) {
                return
        }
        c := tileCost(x, y)
        if c > d {
                return
        }
        addToHighlightSet(x, y)
        collect(x - 1, y, d-c)
        collect(x + 1, y, d-c)
        collect(x, y - 1, d-c)
        collect(x, y + 1, d-c)
}

And the initial call for a unit is like so:

collect(unit.X, unit.Y, unit.Move)

Victory!

All in all, it's still pretty simple and CPU-efficient. The memory overhead is minor as well, since the highlight set is made up of pairs of small integers. And of course, it works.