Complexity in Game Design

My Travian game is coming to a close, ie nearing its one-year mark. I've been poking around at other browser games to assess the competition, thinking about switching, and it reminded me of one of the lessons of game design that I picked up long ago.

I remember playing Warcraft 2 and thinking, "you know, this game would be even better if it had even more upgrades and building types and everything."

A few years later, while playing Kohan, I realized that I was very wrong. WC2 was so awesome because it wasn't any more complex. Kohan (another real-time strategy game) had a different, but relatively straightforward, combat model. It didn't add more building types, or more troop types, or more upgrades -- it just configured armies differently than WC2.

Complexity is great for World of Warcraft because people play that game for thousands of hours. Yet at the lower levels, the game starts out very simple. Starcraft, currently enjoying years of professional play in Korea, isn't any more complicated than Warcraft 2. Chess is much simpler than both.

What makes a game fun is the interplay of choices. With a ton of choices, sometimes randomness sets in and dominates play. "Is unit A better than unit Z732? What about Z731, or Q986? Gah there's so many, forget it! Just build unit A!?" It's difficult to figure out a good strategy (or to be happy with the strategy you chose) when combinations start spiraling up.

Warcraft 2 and Kohan and Starcraft all found a balance with a small number of troops and buildings. Even then, they gradually added all their options in over the course of the game. They don't throw new players into the deep end (the full game); they work up to it over 30 hours or more.

It's like getting decent at chess and thinking, "ok, now that I've learned how all these pieces move, what I need now is more pieces! A larger board!" What makes chess interesting isn't those new pieces; instead, the game changes. The focus shifts to strategy and positional play, thinking ahead and mind games, learning the books and the endgames.

Part of Travian's appeal is its simplicity. If the game got too much more complex -- twice the number of buildings, more complex combat, etc -- then it would be a much harder game to get into. Part of its appeal is its chess-like simplicity. Even in that simplicity there is a lot of interplay, since so much of the game works on an exponential curve.

Good designs are simple designs. Let the fun be in the interplay of a handful of archetypes, not in the mindless proliferation of abilities and powers and resources and buildings and technologies...

Tips on Hiring Agile Programmers

We're looking to hire another couple programmers here, and while I was talking about it with the coding crew, we had some thoughts, there was a rant or two, so now I'm here.

First, What is Agile Programming?

It's not a buzzword. Agile programming is a methodology, which is just a $10 way of saying it's a set of methods. What brings those methods together is that it makes programmers and the code they write more agile. As in flexible. Bendable. Responsive, dextrous, nimble. Agile programmers should be able to adapt the code they write to changing requirements. That's really the whole point. There's a subthread in discussions about "what is agile?" that basically says you won't understand a problem until you try to solve it, and so changing requirements are a natural outcome of exploring the solution domain until you understand it -- but that's not really my point here. We can argue that later.

Using interfaces and patterns is nice, but that's not agile programming. Interfaces and objects are just a part of object-oriented programming, and patterns appear in any programming language (although most well-known patterns are OO patterns).

One part of being agile is avoiding tight coupling. If there's a one-to-one relationship between two class hierarchies, then any time you add a class to one branch, to have to make a similar change to the other branch. This ties those two trees together; they're now tightly bound. One agile approach would be to use smaller bits, like methods (or delegates, in C#) instead. Or to embed the behavior of the second class in the first. Or to get rid of whatever it is that requires you to have two trees with all of the same class types in them.

Being agile means being responsive to change. Writing all your code through interfaces is nice in theory, but whenever you need a client to pull more information out of a subclass of that interface, you're stuck with a problem -- throw in a using clause, or what? Is the interface providing something specific? If there's a 1:1 mapping between interfaces and implementations, ie one interface class for every implementation class, then you haven't done jack. There's already a way to hide implementation from a client, and it's the fucking private keyword, you moron. If the client is going to break through the interface anyway, then get rid of it, it's not actually hiding anything. You should only write code once; there should only be one class exposed to your client. (A 'using' clause etc winds up exposing two classes.) This is the principle of Once And Only Once. If you've got an interface, there better be a reason for it other than "my teacher told me to." If you're doing something and you don't know why, then you better need to do it to get something to work. If you can skip a step that someone told you was required, and your code works just fine without that step, then you've got smaller, more nimble code. That is what Agile means. (And that your guru is full of it.)

Which gets me to the rant: some programmers do things just because they're supposed to. Like adding interfaces for everything, even if there's no hierarchy there. Or using patterns everywhere. I write patterns all the time, but I don't obsess over it. It just happens. If you have to scan through Gang of Four to figure out what pattern to use, then you're not yet a jedi. That's OK, but it's also not the best way to program. Understanding patterns is better than throwing patterns at a project. That's like throwing bailout money everywhere.

Likewise, you don't need a factory for every object. The constructor works just fine! Just call the constructor! I've seen this problem in programmers that have misunderstood the factory pattern. A builder is a class (or method) that assists with complex construction code; a factory is a class (or method) that can build one of several different objects, and returns them through a common base class (which might be an interface). Again, if a factory only builds one type of object, then why do you have the factory? If a class only has one constructor and construction is simple, then why do you have a builder? Both add to code bloat and complexity, and thereby inhibit the ability of future programmers to add new features or fix bugs. Or even understand what the hell you were doing. And here again is the benefit of agile programming: if your code is small and nimble, you can change it more easily.

Wait, I thought you were talking about hiring programmers?

Many academic programmers heed rules that they don't understand. You want the guys that have figured things out for themselves. There's a lot of clues here to figure out how to tell the first group from the second.

In general, the best way to hire programmers is to get them to do the job they're about to do. Give them a written test before the interview, or stand them in front of a whiteboard and ask them to pop out a design.

Not just a function; a design. The stuff that matters, for agile, is design -- not algorithms. (Algorithms are important, but ultimately agile isn't about algorithms. Test algorithm knowledge, sure, but that's not why you're reading this.) Good programmers have a sense not only of algorithms but also data structures. Good OO programmers can think in module-sized units (as well as class-sized units, method-sized units, or statement-sized units). Ask your candidates to express some designs. If you're interviewing a senior candidate, then he should understand framework-sized units. Ask him to sketch a framework for handling a large, complex data set and a wide variety of operations, probably something related to your personal problem domain. You don't really want a correct answer so much as strong thinking. (Don't judge a candidate by how closely they parrot your personal favorite design, or the one that your office has chosen. That's not what you're looking for here.)

For juniors, start with the simple stuff: persistance and streaming, three-tiered architecture stuff, de novo object creation, parsing. And ask them to get specific; where are the interfaces? What patterns do you use here?

And the money question: why?

The thing to look for is not their answer so much as how they answer. Is the candidate trying to think up a good reason for their answer, or are they just struggling to translate their understanding into words? The faster you can get a candidate to talk, the less rationalization goes on. It's ok if they're stumbling around their words or gesturing a lot with their hands, or just drawing circles on a white board and using too many pronouns -- this suggests that they're thinking of objects, not trying to reconstruct some quiz question a prof gave them once.

Object-oriented designs are inherently visual. They're visual creations. This is why whiteboards are a must in interviews, and why it's very difficult to assess a programmer over the phone.

Getting a candidate to explain what agile means is less important than hiring a candidate that inherently does agile things. And the way to test that is not to get him to talk, but to get him to do.

Noobs and Information

Many games have large noob populations, and they suck. Dealing with noobs is a pain. They don't know what they're doing, they don't know what to ask, and they're asking all the wrong people in the wrong places.

I think the same thing happens in many domains, not just in online games.

The problem is that the noobs have no information. Games with strong documentation and community features reduce their noob load; games where information is spread out among third-party sources and where game mechanics are not explained by the developer have much higher noob loads.

Warcraft has extensive online documentation, but they still have a high noob load. 'Preventing' noobs requires addressing the needs of the noobs, not the needs of the marketing department. Keeping players interested, getting them to come back, giving them something to look forward to -- these are all great. But it's not what noobs need.

Travian has crappy documentation. There's a lot of different info sites, but many of them are paltry. They focus on a few of the major concepts in the game, and although often broad and deep, are broad and deep in the wrong places.

Single-player games tend to not have noobs. Single-player games tend to require that they explain themselves to new players or else players just stop playing. I've played a number of 'innovative' single-player console and PC games that just didn't make sense. Although these games hint at depth and complexity and something fun, they hide it. And if I can't find it, the game gets returned and I don't recommend it. And I expect they get bad reviews, too.

What noobs need is direction. They need to know how the game scores them. They want to know the roles that they are expected to take. They want to know the consquences of their actions, before they take them. They want a place to go for this information, plus a forum lively enough where they can ask obscure questions.

Direction

Single-player games tend to have scores or mission directives that communicate to players what it is that they're trying to accomplish. Warcraft is fairly open, yet there are a few major goals: get to the level cap (80), accumulate gear, and work through the hardest dungeons. A more subtle point is the things that they should look out for along the way; some guidance on which goals are worthwhile. Many mid-level players worry about gear, spending hours and days getting just the right piece. Then they out-level it a few days later.

Travian takes pride in its opaqueness, supposedly because it gives players 'freedom' to choose their own path. Yet there are a few paths that are extremely useful to the over-arching goal of winning the game. Winning the game is something that's done by an alliance, not by a solo player, or one player that happens to be in an alliance with some friends. It requires the cooperation of dozens, if not hundreds, of players. There are a few strong roles that players can take, as well as some rules for how to be most effective. Yet the publishers don't do any of that; they leave it up to players to discover all of that on their own.

The discovery process can be fun, but there's two important concepts that limit where a game designer should put discovery: consequence (see below) and direction. If a player first has to figure out where he's going, then he's not discovering the game world, or developing strategy; he's figuring out what the user manual would look like, if the user manual had something more constructive than a simple list of all the units in the game and their cost.

Roles

Role is related to Direction. Whereas Direction shows the player what they have to do to win (what obstacles they have to overcome), Role is the set of tools that the player has available to do it.

A Priest in World of Warcraft knows about the spells that he can cast, but a good role is a bit more than "cast these three spells over and over." In a raid, a healer can stay focused on one target, heal several targets, look over a whole bunch of people and top them off -- or stick to some of the utility spells that they have.

Over a career levelling a priest, that player might go Holy (and heal in groups), Shadow (and focus on damage and mana generation), or Discipline (for... PvP?). Ignoring the accuracy of those descriptions, these are ways of telling new players: if you choose this class, you will have these roles that you fit into.

In Travian, roles could be as a Defender, Hammer, or Feeder; one might work solo or in a group. There's an infinite variety of combinations, obviously -- yet there are no general guidelines. Travian noobs wonder what they should be focused on. They try to do all things, without picking a role. They want to be offensive, but don't know how that plays out over a year. It's very frustrating to spend a lot of time on a game building a character (as in WoW) or a bunch of villages (as in Travian) to find out that you made fundamental mistakes early on, and that your current effectiveness is gimped because of it.

Giving new players guidance on the Role that they'll play can help players get started on the road to contributing during a game, rather than observing. Links to discussions will help them understand how other players feel about that role, letting new players find their sweet spot that much faster.

Score

Score defines direction. Score tells players how they win. It gives them feedback, and it's through feedback that players learn to play better. I don't like mashing buttons; winning for random reasons is not an achievement. Score tells me if I mashed the right buttons, so that I can see patterns in the game, start developing a strategy, start discovering the game world, meeting new people, and then killing them.

Open games sometimes have visible 'score' charts that measure inconsequential things. Statistics can be fun to browse; some people like that. I often do. But if you give everybody a useless metric (but one easy to manipulate), many will shoot to maximize that metric, even if it is a detriment to their play experience. If you put up a score-board but that score-board only applies to some players, or is completely irrelevant to the rest, you misdirect your players.

Travian shows village population for all the players. This is the major score rank in the game, since it's something that everyone has and it's relatively easy to see. Yet it, ultimately, isn't a strong measure of performance. But that's a problem with team games; how do you measure 'performance' when so much of the contribution one makes is building social networks, establishing trust, etc?

For vague, open games like travian, maybe the best way to communicate 'score' to players is to give them an overview of previous rounds. Show them the target, and how they measure progress, and then what last round's measuring stick looked like. They might choose a different metric, but at least with this kind of guidance they can make an informed assessment about how well they are proceeding.

Consquences

This was one big problem in many MMORPGs: players were 'free' to destroy their characters, spending hundreds of hours building a character that was sub-par. I remember putting points into Charisma in Dark Age of Camelot. As a Cleric. It did nothing for my character; they were wasted points. The 'freedom' to distribute points as I felt wasn't backed with enough information to make a good choice (unless I had been playing the game through to the end-game already, which didn't even exist when the game first shipped). Further, my choice was hard-locked; it could never be changed. This was a combination of asking players to make choices without sufficient information and then penalizing them, for the rest of their online career, for the wrong choices.

Social Dynamics in Travian

Travian is a browser-based MMO. I've mentioned it a few times before. The game is a cross between Risk and SimCity. You construct buildings and improve them, train troops, and go wage war. Players have villages that spawn on the big grid, which ranges from -400 to +400 in both X (east-west) and Y (north-south). There are roughly 20,000 people on each server; right now, there's around 12,000 people that have been active on my server in the past week.

Only one person can win, but that win is really for his alliance. And, since alliances are limited to 60 people, his confederation (which is a group of alliances; there is some in-game support for confeds). After a server runs for about 10 months, an NPC race show up. You (and your alliance) beat them up, get plans for a new building type, then you up that building to level 100 (whereas 20 is the max for most building types).

Out of those 12,000 active players, roughly 120 will be said to win. That's 1%. What are the other 99% doing?

Usually alliances in the game divide up into the quadrants -- to the northeast, southeast, southwest, and northwest of the origin. That's four confederations, one per quadrant. Those confederations might be two or three multi-wing alliances, so generously about 1,500 people are in the running to win. That still leaves over 10,000 people that are actively playing and not likely to win.

And let me qualify that 'likely to win' bit. Prices in the game are exponential -- a level 2 building is 29% more expensive than level 1, level 3 is 29% more expensive still, and so on. A player with all level 20 buildings is 29% more powerful than one with all level 19 buildings, and nearly thirteen times (1278%) more powerful than one with all level 10 buildings. If you're not up there at the top, you have no chance to compete.

The players in alliances outside of the top 4 have 0% chance to win. I haven't chased down who has won each game; I'm don't even know that it's recorded anywhere useful. But once you drop off the top dozen alliances, power drops considerably. Number 20 is 1/3rd the size of #1, number 40 is half of #20, and the 60th alliance is an order of magnitude smaller than the top dog.

So what do you do? Or, what do I do? If I'm not in one of the top few alliances, then I'm just ... having fun? Not winning, that's for sure. So why play? Why do other people play?

Judging from the forums, the two main reasons people play this game are (1) they're stay-at-home moms, or (2) they got beat up a lot when they were kids.

#1 is somewhat related to my previous post about who has time to play games that require you to log in frequently -- kids, college students, and the unemployed. Stay-at-home parents are kinda like the unemployed. And those are the people that play. Kids (and college students) are still coming to grips with being beaten up a lot; Travian is a great outlet. Someone pisses you off? Destroy their village and everything they've spent months working on! Hah!

It's a war game, though. Some people lose.

It's funny to see how some people respond to being attacked. A good many don't realize the "war" aspect of the game. And it also seems the developers want to hide that part, too. Not a lot of stay-at-home moms like getting their village destroyed by 12-year-old kids. The solution seems to be "don't tell them that happens," then just hope they don't find out. It's not like every mom gets her village 0-popped. When 12-year-olds gets attacked, whether it's a full-on assault or just a small raid, some of them respond with vitriol characteristic of someone that's just learned some new swear-words and has the freedom to act outside of parental control. More mature

What should someone in this game do when they are attacked? I think a better question is: should you be attacking your neighbors?

There are two reasons to attack another play - (1) to steal some of their resources, called "raiding" in the game, and (2) to destroy some of their buildings and/or kill off their troops. In the late-game, when alliances are competing to finish a world wonder, slowing down your competition is as important as building your own wonder faster. Before that, though, the primary reason to send troops at another player is to steal their resources. A corollary here is to prevent other players from stealing resources, so you attack them to kill off their troops and their ability to train troops.

Stealing resources is a plentiful source of resources. You can easily double your hourly production, and (if you focus heavily on troop-building) gain considerably more from raiding than from you produce through your crops. A maxed-out village will produce over 5000 resources an hour, but can support a couple thousand troops -- which themselves can produce 10,000 resources an hour. Some villages can support 5000 troops, and if that type of village is your capital, it can support up to 180,000 troops. Raiding is big business.

But let's look at this at a meta-level. Either you steal resources from someone else, or they use them themselves. If they use their own resources, they can upgrade their own buildings. The game is fairly balanced, such that each upgrade provides roughly the same return. There's a slight negative bias, such that upgrading a low-level resource gives a bigger ROI than a higher-level resources. Hence, "the universe" produces more resources if you let a low-level farm improve himself. Raiding transfers wealth from an efficient producer to an inefficient producer.

But, because of attacks and raids that prevent a player from building anything, a great many people stop playing. Inactive players are a great source of resources -- they aren't using it. And that's a legitimate reason to farm them; a low-level but inactive user is wasting resources. Anything he produces over his warehouse's ability to store it is just thrown away.

So why 0-pop someone? It removes a source of resources from the game.

Thinking about all this suggests, to me, that the strongest way for an alliance to win is to have a bunch of active players building a bunch of villages, raiding inactive players, and suppressing their foes. Raiding active players, if they're not competing with you for resources, seems to be pointless. And if they are competing with you, then allying with them is a better use of resources than throwing away troops on attacking them.

So why not ally with everyone in your quadrant? That seems like the strongest way for your quadrant to win.

And now we get to "your quadrant." Do you really care who wins? Isn't choosing to root on your quadrant just tribalism? "My quadrant is better than your quadrant!" The other 2,999 active players in your quadrant aren't your friends and relatives. They're a bunch of strangers, half of them 12-year-olds (at least in mind).

So let's come back to why to play this game. If you're competent and active, being big enough to get into one of the confederacies-that-has-a-chance-of-winning isn't difficult. If you're not the sort of person that tortures small animals and snaps at anyone that talks to you, you shouldn't have difficulty getting into those alliances. A little bit of diplomacy and a little bit of activity and presto you're in.

So if you've read this far, you, too, have a shot of winning a Travian game. But why play Travian?

Why play any game? Because it's fun, for a chance to socialize, to build up a cool little city, to compete against other players at a game with well-defined rules, for a chance to take out your aggressions on small forest creatures^H^H^H on other players.

But why attack other active players? Isn't that just griefing? I'll explore griefing in a future post.

Bit Haxorz

You can change code like:

if (accumulator >= test)
{
accumulator -= test;
x += stepx;
}

into

int subtract = accumulator - test;
int hibit = 1 - (subtract >> 31) & 1;
accumulator -= test * hibit;
x += stepx * hibit;

Magic! No conditionals! You might use something like this if you're working on a REAL inner-loop, such as code that'll run on a GPU or likewise run many times on a mobile or handheld CPU.

Efficient Ellipse Drawing - Part 1

This is the first in a multi-part series on drawing ellipses, pixel by pixel. Part 1 (this part) covers the basics of shape rendering, using lines as an example. Part 2 covers drawing circles. Following parts will cover ellipses.

My thesis is that any programmer can learn the math and tricks to write shape-drawing code. That's the point of this series -- to show you how to write your own code. If you just want code to copy-n-paste, go to the bottom of this post.

WARNING: Blogger.com likes to eat my code. I've reviewed this a few times, but there's no promise that it hasn't suddenly gotten hungry again. If something looks screwy, drop a comment and I'll take a look.

Background

I needed to implement efficient ellipse-drawing code in the tile editor I'm making, and I searched the net for some sample code but was thwarted. I vaguely remembered the algorithm, but I knew there was some math involved and some tricky stuff to make it fast, so I wanted to get it right. I looked at some sample code, converted it, but it didn't work. I wound up having to re-derive the equations by hand.

Part of the problem is a general problem with all sample code -- you have a specific purpose which may or may not match the sample. In my case, I was working in C# and had to clip the ellipse to the small tile. Plus little stuff, like how you specify the ellipse. A corner-to-corner definition (a bounding rect) can define an ellipse whose center is a pixel, the point between four pixels, or possibly even a point on the midpoint of an edge between two pixels. How do you adapt ellipse-drawing code to those situations?

The answer, really, is that you have to understand the algorithm itself. If you just want a library to do it for you, you can do that. In this case, that's not what I needed. I didn't want to spend an hour or two finding, downloading, installing, and integrating some third-party library -- or even just a single function -- to get something that I could do by myself in the same amount of time. What I wound up coding isn't actually an "efficient ellipse-drawing algorithm" -- I used a subfunction to calculate the error value for each pixel, with no strength-reduction accumulation code to make it faster. For what I was doing, that was fast enough, and the extra work to optimize the function wasn't necessary.

Goal

My thesis is this: line and ellipse (and circle) drawing is simple enough to learn.

Once you understand the basics, implementing your own code is straightforward.

Drawing a Line

Let's say you want to draw a line on a bitmap. If it's a straight vertical or horizontal line, the code is simple enough:

for (int x=0; x<length; ++x)
{
PlotPixel( x, y );
}

When you implement this algorithm in your own code, changes are it's gonna change to something like this:

int data = bitmap->GetDataPointer();
int offset = x + y * bitmap->GetRowStride();
for (int i=0; i<length; ++i)
data[offset+i] = pixelColor;

This is an example of what I meant above when I mentioned rolling your own. Most likely, any time you take an algorithm like this, you're going to change it enough that it won't look like the sample code you're using as a reference. That's why it's important to understand the algorithm. Straight lines are pretty simple, and you might not see much point here, but ellipses are much more complex.

Let's say you want to draw a diagonal line. That's also pretty easy.

for (int x=0; x<length; ++x)
PlotPixel( x, x );

That's kinda cheating, tho. When you adapt that bit of sample code, more likely you'll do something like this:

for (int i=0; i<length; ++i)
{
x = x1 + i;
y = y1 + i;
PlotPixel( x, y );
}

But that just draws a diagonal line. What if you want to draw a horizontal line, or a vertical one, or a diagonal that's at an angle other than 45º? Usually, you have a routine like "draw a line between these two points," and you have no idea where those two points are relative to each other. The complications pile up.

Let me start with changing that function to one that will draw a 45º line in any direction, including vertical and horizontal lines. Say that x2 and x1 are forty pixels apart. I'm going to draw forty pixels; one at each X coordinate. This means I start at X1, draw a pixel, move one pixel to the right, and repeat. This code handles going left or right with a loop:
for (x = x1; x!=x2; x+=inc)
The trick there is that 'inc' variable. If x2 is to the right (greater than) x1, then the increment is positive (+1). If x2 is to the left (less than) x1, then the increment is negative. I actually do the same thing with y.

Another option is to check to see if x2 is to the right of x1; if it's not, then swap the two points.

Anyway, this function will draw a line between two points, either flat (horizontal or vertical) or at a 45º diagonal.

DrawLine45or90( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx < 0) ? -1 : 1;
int stepy = (dy < 0) ? -1 : 1;
int len = dx * stepx;
if (dx==0)
{
stepx = 0;
len = dy * stepy;
}
else if (dy==0)
stepy = 0;
int x = x1;
int y = y1;
for (int i=0; i<len; +=i)
{
PlotPixel( x, y );
x += stepx;
y += stepy;
}
}

On modern machines, conditional code is expensive. Whether you're working on a PC, a modern console, a mobile device, or writing code for a GPU, if statements should be avoided in inner loops. That's why I do this business with stepx and stepy. Those increments also mean you don't need separate implementations for vertical lines, horizontal lines, and diagonals -- this loop does them all. Once you've got len, stepx, and stepy set up, just let it run.

Next: What if you want to draw a line at a different angle, something other than 0° or 45°? That's really the heart of a line-drawing algorithm -- handling lines between two arbitrary points.

From here on (except for the last sample, which is the final working algo), I'll assume that you're drawing a line where dx is greater than dy, ie a mostly-horizontal line.

Here's a simple implementation:

DrawLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int length = dx * stepx;
int x = x1;
int y = y1;
for (int i=0; i<length; ++i)
{
PlotPixel( x, y );
x += stepx;
y += stepx * (dy / dx);
}
}

This doesn't work, though. If dy is less than dx, then you wind up with a horizontal line (image on the left). If dy is greater than dx, then the line doesn't end at your target point -- it climbs at a constant rate and doesn't match what you want (image on the right).





The y value needs to be calculated in the loop:

DrawLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int length = dx * stepx;
int x = x1;
for (int i=0; i<length; ++i)
{
int y = y1 + stepx * (i * dy) / dx;
PlotPixel( x, y );
x += stepx;
}
}

The next trick is to get rid of that division in the inner loop. The way we do that is by conditionally incrementing y. This is why we assume a mostly-horizontal line. Since Y will change by either 0 or 1 each time through the loop, we can always change X but only sometimes change Y. For a finished implementation here, you will probably want two functions -- one for steep (mostly-vertical) lines and a separate function for shallow (mostly-horizontal) lines. The code samples will still be able to handle cases where point one is above, below, to the left, or to the right of point two.

OK, so to get rid of the division, we just keep an accumulator, adding dy every time, and check to see if it's greater than dx. We're going to have to watch the signs, tho.

DrawHorizontalishLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int stepy = (dy<0) ? -1 : 1;
int length = dx * stepx;
int x = x1;
int y = y1;
int yAccumulator = 0;
int yIncrement = dy * stepy;
int yTest = dx * stepx;
for (int i=0; i<length; ++i)
{
PlotPixel( x, y );
x += stepx;
yAccumulator += yIncrement;
if (yAccumulator >= yTest)
{
yAccumulator -= yTest;
y += stepy;
}
}
}

Final Algorithm

DrawLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int stepy = (dy<0) ? -1 : 1;
int lenx = dx * stepx;
int leny = dy * stepy;
int x = x1;
int y = y1;
int accumulator = 0;
if (lenx >= leny)
{
int increment = leny; // note the substitution here
int test = lenx;
for (int i=0; i<lenx; ++i)
{
PlotPixel( x, y );
x += stepx;
accumulator += increment;
if (accumulator >= test)
{
accumulator -= test;
y += stepy;
}
}
}
else
{
int increment = lenx;
int test = leny;
for (int i=0; i<leny; ++i)
{
PlotPixel( x, y );
y += stepy;
accumulator += increment;
if (accumulator >= test)
{
accumulator -= test;
x += stepx;
}
}
}
}

Further Parts

Part 2 - Drawing a circle
Part 3 - pending; circle complications
Part 4 - ellipses

Difficulty Levels in Games

I enjoy a good challenge, but I don't like losing.

Most console games, e.g. platformers, have relatively low death penalities. Whether it's save points or infinite respawns, dying only sets you back a few minutes -- the time to run back to where you were before. Really challenging games might require that you re-run an especially difficult gauntlet -- the biggest setbacks might be ten or twenty minutes.

The Lego games -- Lego Star Wars and Lego Indiana Jones -- are prime examples. "Dying" means you lose some points, but you can get them right back most of the time. The biggest setback in the game is realizing you skipped a level, that you went through a one-way door and now have to replay the entire level to get back to a previous screen. Which is only relevant if you're trying to get all of the secrets/treasures/etc in a level.

I used to enjoy playing the Hardcore difficulty levels on FPS games, but the single-player portion isn't usually a skill challenge; it's more often annoying and time-consuming than challenging. I just want to see the content. After playing a few levels of Doom 3 on the highest difficulty setting, I decided to go back and play on a lower setting, just to breeze through it.

One of the side effects of that choice was that the game was much less scary. When the spooks and scares didn't suggest that I'd actually die, then I didn't need to fear them. It was actually fun, in a horror-movie sort of way, to conflate the fear of getting your progress thwarted conflated with the fear of the demons. Turn the lights on, play during the day, and crank the difficulty level down, and the game loses any emotional impact it might have had. If you like horror movies, you probably know seeing one late at night is the best time. When the house (or movie theater) is quiet, every little creak and groan can make you jump.

But the Lego games aren't about scares. They're about content. You get to play through the movies, which is fun, and you get to spend time looking for hidden secrets. Both are great fun, and neither one is the sort of challenge that can even have setbacks. I remember playing the old Sonic games, and Mario, and whatnot, and in those, death was a threat. But you only died while you learned a mechanic; after a while, death wasn't so much an ever-present threat as it was something to keep you on your toes. Ratchet and Clank, Banjo Kazooie, and Sly Cooper are similar. Dying (at least, dying several times and losing all of your Lifes) could set you back a good bit, maybe fifteen minutes, but you didn't die that true death very often.

As I mentioned in my previous post (about train tycoon games), I've been playing Railroad Tycoon 2 again lately. I bought RRT3 and Railroads! (aka RRT4) at the same time, and I'll go through them again later, but for now I'm playing through this high-rated classic game.

When you screw up in RRT2, you lose the mission. You don't have to win the mission. In fact, you could just Resign your way through the game and see what each of the levels is about. There's no content block -- the entire game is open to you as soon as you buy it. So what's the challenge? Somewhat like a toy, the challenge is up to you. You don't have to get gold medals, but it's the highest reward the game offers. So you've got a few choices -- play all the missions through, win or lose; win all of the missions; or win all of the missions with gold medals.

For me, getting the gold medals was my goal. It was a bit of a pain, because I had to learn how to make money. I played through all of the Canada mission (#6) and lost -- I had nowhere near enough money to win. I wasn't really sure why. I looked around a bit, and from the comments I saw, I realized that I needed to focus more on long-distance hauls, be less focused on getting strictly to each coast (going to Halifax early is a waste of time), and to spend more time supplying and exploiting the industries available. Another change I made in my second run-through was to be more careful where I laid tracks, exploiting terraforming and avoiding congested routes.

A lot of learning is required to do well. Unlike, say, Lego Indiana Jones, I can't just plow my way through an RRT2 mission and win. The game makes it hard to pay attention to elevations, but I can't just ignore them. The game makes it hard to mind consists and stations, but I can't ignore them either.

When I lost the Canada mission the first time, I felt like it was out of my control. I didn't know what I was doing wrong. When you lose a life in a platformer, it's usually pretty obvious what you did wrong -- there's lava there (oops, didn't see it the first time); you have to fight this boss a different way (and a few minutes of trial and error usually shows you how); or you need to time your jumps and swings and whatnot better. There are skills in some of those games, timing related skills, and usually practice is a trivial way to increase your skills.

In RRT2, I found out that it takes six years (about ninety minutes of real time) to send a train from Halifax to Vancouver. Geez! I started a year too late. Figuring out how long it'd take to send a train that far... is not really possible. The best you can do is to spend a half-hour testing and measuring, and that's a horrid waste of time. F that.

Platformers are often safe exploration games. Or, if you have good combat skills in the game, the challenge isn't too onerous. Once you defeat the foes, they stay dead, then you can go explore without hindrance. Other games force you to explore the mechanics -- how do you make money in RRT2? You have to tease the profit equation out of the game.

And here we get to what I ranted about in yesterday's post: the feedback loop for figuring out that equation is slow. Deadly slow. "F this, I quit" sort of slow. Lose the mission enough times and you go hunt down a FAQ. Why bother solving it by yourself? I kept losing the Whistestop Tour mission as my train ran out of sand, and I thought, wtf?! There's only one way to get the gold medal, and it requires (as the game often does) to ignore the help that the game offers. (That Whistlestop mission offers you an upgrade if you get to a town in time, but there's no way to get there -- none of the engines are fast enough to get close enough before you run out of sand.) These are trial-and-error lessons, but the downside is that you have to error a lot, and spend a lot of time doing so, before you move on.

Games should calibrate themselves to players. If a player doesn't have the skill or the knowledge to get a gold medal, platformers give them silver and bronze medals. They say, "thanks for playing, here's your twinkie" and tell you you did a good job and let you move on to the next game, brag to your friends that you finished, and score a few achievement points.

Telling the player "ha-ha! You lose! Now you have to do that all over again!" sucks. And it sucks in builder games where you build this big cool rail empire... then never see it again. You throw it away. As awesome and profitable and elegant as it was, it's gone. Oh, and cuz you lost? Yeah, you're throwing it away with nothing to show for it but some bruises and an admonition to try harder next time.

The skills you gain when playing sports and lose, at least, are something. Throwing away my cool rail empire and the hours I spent building it just to gain skill at beating the remaining levels -- that's not really a skill I want to be proud of. I can't say "I accomplished nothing last night but learning how to beat this game that I'm gonna play for a couple more weeks then never touch again." Who cares? Getting better at shooting baskets, or pitching, or hitting, and saying "well we lost and I sprained my ankle, but I think I learned a lot about the sport" is worthwhile.