Thursday, March 5, 2015

Code Dive: Custom iterators in Hellenica (Part 2)

In part one of this code dive, I talked a bit about using custom iterators with IEnumerator and yield return. In this exciting(!!) conclusion post, I want to circle back and provide a concrete example from Hellenica where we made use of a custom iterator.

Let's set the scene: Diona is trapped along with a pirate enemy atop some rocky pillars, deep in the Mediterranean. By now, she's likely fed up with all the 'yarr'-ing and 'avast'-ing that comes with close proximity to a pirate wielding a barrel of wine, and she's ready to send an arrow his way.

For most ranged attacks in Hellenica, we need to check for obstructions between the character performing the attack and their target. If there are any obstructions that are sufficiently... obstructing, then the attack can't be made.

Here's a picture with all of the possible targets drawn. Notice how a couple positions right of the medium pillar, as well as the positions immediately below Diona's pillar, are untargetable.

So how do we determine which tiles to check for any given set of attacker and target positions? I decided to stay true to our old-school aesthetic and walk a pixelated path between the two positions. To do this, I summoned forth the classic Bresenham's Line algorithm. You've likely seen it in action before in your (least?) favorite paint program.

Originally devised to plot out lines on a screen, the algorithm is usually implemented using an iterative approach. That is, from the start position, proceed towards the end position by iterating over the discrete integer values of x that fall in between. As you iterate, you'll use an error metric to decide when you need to step up or down in the y-axis. Then it's just a matter of filling in one new pixel for every x position. If you're interested in more details, the internet has you covered.

In our case, we can use a similar approach if we treat each of our game positions like pixels on a screen. And, we should be able to create a custom iterator like the one we explored last time since this is just another collection of values (positions, in this case). The difference is that this time, instead of processing some data we've stored somewhere, we're now going to generate the data as we go!

Here's the gist of it:

What's most important here is that you pay special attention to those yield return lines that output the game positions to us.

Here's how we'd use it to check for obstacles in our original problem:

The get_discrete_line function returns an enumerator that acts just like a list of game positions, but it's actually computing those positions as the user asks for them. In more computationally expensive functions, it may be worthwhile to only calculate exactly what you need as you go, instead of generating the entire list up front, and this approach provides a clean way to do just that.

Here's the path that the algorithm computes for this example:

Looks clear to me! Fire away, Diona.

Hopefully this exploration has given you some new ideas about using custom iterators. I'll leave you with a teaser: If you think of this IEnumerator object as a way to space out the execution of a function over time, there are even more interesting applications that don't involve collections at all. I may take some time to cover this a bit more in the future.

No comments:

Post a Comment