Roguelikes are part of a family of games in which the participant builds 
something over time.  Relatives are of course roleplaying games and other 
storytelling games.  Distant relatives are games such as Civilization.

Since players often fail to achieve the primary goal (e.g. retrieve the 
artifact of lint removal which will cleanse the bellybuttons of everyone 
in the universe thereby ending world hunger) the secondary rewards (or payoffs 
(or utility for all you economists out there in RL land)) become very important. 
 Too much advancement too quickly (kill a kobold - get to 35th level) devalues 
the payoff, whereas too slow an advancement (kill everything in the whole 
game and maybe get halfway to level 2) means that they never even get to 
feel rewarded.

Of course experience might be handed out for a range of activities, not 
just killing things.  such a list is certainly not limited to: solving quests; 
receiving damage; causing damage; casting spells; using skills; getting 
treasure; idle gossip; donations to the (un)worthy cause of your choice; 
doing nothing or resting; healing; travelling, mapping, making other players 
laugh....

So lets consider the case of a fairly generic dungeon bashing roguelike. 
 The dungeon has sixteen levels, a predetermined number of monsters per 
level, and unique monsters.  There are no 'random' monsters.  We'll call 
our theoretical roguelike Jiavlo and code it in Java.  (Stop me if I infringe 
any copyrights ;-)  

Experience is only handed out when we generate a monster killing event.

Our first realization is that in this scenario there are a fixed number 
of monsters, and that this means that there is an upper limit for how much 
experience the player will ever get.

We need to decide how many levels we want the players to be able to gain. 
 So what constitutes a good number of levels that could be gained?  Most 
of the audience will have at least a passing familiarity with the D&D game 
family, in which you start at level one, and progress is technically unlimited,
 but which is less meaningful once you get into double digits.  And certainly 
once you get into the low twenties you are in danger of being accussed (unjustly 
of course) of being a 'power gamer'.  So most of the target audience is 
going to be happy with a top level of around 15 to 30.  Twenty is a nice 
round number in that range which should give a decent payoff in terms of 
achievement.

Note that the point is not to mirror any particular published system for 
which one runs the risk of being sued and losing the shirt off ones back,
 but rather to recognise and take advantage of this subconscious assumption 
that most people are going to make, ie that getting to level 20 is a superhuman 
feat and that getting to level 12 (say) is pretty spectacular.

The other thing to do is to make the experience scale exponential (this 
means that each level requires more experience to get to than the level 
before it).  Mathematically there is no reason for this, but people will 
expect it, and because of their expectation they will not feel as much of 
a payoff if they get the same amount of experience for killing a dragon 
as a kobold.  Because of this, I recommend using a spreadsheet to play around 
with the numbers till you some that you like.  Hopefully you won't need 
a spreadsheet to follow this article though!

It is useful to consider the linear case here though, because it forms a 
basis from which you can build the exponential formula, and if you do so 
you will be much more likely to get a well balanced game.  But before we 
look at the linear model, lets examine the constant model.  This is even 
worse in terms of payoffs, but much simpler again to balance properly.

For every monster you kill you get 1 xp.
There are 50 monsters per level.  (Times 16 levels is 800 xp)
We can now say something like, for every 40 xp you have, you go up a level. 
 (800 divided by 20).
Note that you start at level 1, so you would get to level 20 after killing 
760 creatures, ie you max out your levels shortly before you kill the UberLintDaemon 
which drops the game ending artifact, so that you have time to enjoy maxing 
out on levels before the game ends.

If the monsters on deeper levels get harder to kill, then logically players 
would try to clear a level before progressing to the next in order to get 
the 'easiest' xp first (minimise risk, maximise payoff).

Note that we are requiring them to kill 40 monsters in order to advance 
to second level.  This is far too harsh, and for many first time players 
this will take too long for them to get hooked.  Ten is a much more reasonable 
number.  And we want them to be able to get to say level 5 or 6 fairly quickly 
before it becomes hard slog.  So lets break it down, lets say that by the 
end of dungeon level 15 they are level 20, and they gain a level per level 
they clear back till say the player is level 10.  That means that we then 
need to plot the xp from 0 (at level 1) to 250 (which they have after clearing 
5 levels at level 10).  We could go back and rewrite our assumptions, and 
have them start at level 0, and then have them gain a level every 25 points. 
 That makes it nice and easy for us in terms of maths.

The effect this has on the game though, is to make the clearing of each 
level a hard thing at first, and then get easier halfway through each level. 
 This is actually not too bad in terms of payoffs, because the player begins 
to notice that the monsters are easier to clear after going up the level.

So lets modify how players go up levels.  Here is the table (level, xp required):
1	0
2	5
3	15
4	30
5	50
6	75
7	105
8	140
9	180
10	225
(and 50 per level after that).  

So at the end of clearing level 1 (50xp), they are fifth level, clearing 
level 2 puts them at sixth level verging on seventh, etc.  This uses a clear 
progression, in order to go up a level, you need as much extra xp as the 
last time you went up a level, plus five, until you get to needing 50 a 
level where it tops out).

Despite the plain maths behind this, I would be tempted to fiddle with it 
even more, because fifth level after clearing only one level of monsters 
seems 'too much'.

But lets take this 'constant' model, and see what happens when we make it 
'linear'.
We assume that all the monsters on level x of the dungeon are 'level x monsters' 
and we give x points for killing them.  The maximum amount of experience 
in the game is now: 6800.  The maths for working this out is starting to 
get more complicated, but the formula is: (((n squared) plus n) divided 
by 2) times the number of monsters per level).  Where n is the number of 
levels, and the number of monsters per level is still 50.

Obviously we cannot now just multiply the cost of going up levels by 8.5 
 (6800 divided by 800) because that would mean we would need 85 xp to get 
to second level, which means clearing all of level 1, and a third of level 
2.  All of a sudden things look a lot harder!  One way of solving this, 
is to try to match monsters killed to levels gained, assuming that all the 
low level monsters are killed first.  This is easier than it sounds for 
levels 10 through 20, because we already know that we want the player to 
advance at the mid point of the level.  And this is not too hard to work 
out (especially with a spreadsheet).

>From 10th level and up (level, xp required):
10	900
11	1225
12	1600
13	2025
14	2500
15	3025
16	3600
17	4225
18	4900
19	5625
20	6400

(The formula for this is: (((n squared) plus n) / divided by 2) plus (25 
times (n plus 1))  where n = level required minus 5.  The minus five is 
because we have five more experience levels than the last level of the dungeon 
that we cleared)

Now if we want to keep the same progression, that is, getting to level five 
after clearing the first level of the dungeon (yuck!) we leave that bit 
of the table alone, and figure out a progression from 5th level to 10th 
level.  Or, we can choose another formula to govern low level advancement,
 such as: (n times n) plus (14 times n) minus 1, where n is the current 
level which yields:
1	0
2	14
3	45
4	95
5	166
6	260
7	379
8	525
9	700

Which is a much nicer fit to the lower levels of the dungeon and how fast 
they should advance.  Unfortunately I've just noticed that it bears a striking 
similiarity to the xp curve in Crawl.  What a shame :-)

But of course noone wants to get 12 xp for killing a Dragon, so we need 
to think about how much xp we want to hand out for killing a monster of 
each level.  I suggested at the start of the article that making it exponential 
is probably more in fitting with the players expectations.  Lets say that 
on level one you get 1 xp per monster killed, and on level 16 you get 10,
000 xp per monster (so level 16 has half a million xp of monsters on it 
- suitably impressive amount :-)

A 'basic' formula for this would be: (n to the power of ((n minus 1) divided 
by (15 divided by 4)))

Which gives these results:
1	1
2	1.847849797
3	3.414548874
4	6.309573445
5	11.65914401
6	21.5443469
7	39.81071706
8	73.56422545
9	135.9356391
10	251.1886432
11	464.1588834
12	857.6958986
13	1584.893192
14	2928.644565
15	5411.695265
16	10000


You then need to figure out how many xp are needed for each level (use a 
spreadsheet!), and split the difference between levels, and then somehow 
figure out a formula for advancing.  I came up with (2 to the power of n) 
plus (n cubed) minus (25 times n).  Which is ok, but given more time we 
could come up with something better.  In particular, I'd reduce the base 
number of the power to something in the range of 1.97 to 1.99 so as to get 
closer to the 'ideal' value for that last level (you would get to 20th level 
with three creatures remaining given the formula above).

Some things to think about: do the rewards actually match the difficulty. 
 For instance if a level 12 monster isn't really much harder to kill than 
a level 8 monster, why hand out ten times as much xp for killing it?

In fact, the difficulty of balancing even a limited scenario as outlined 
above means that you are far better off having a 'complicated' function 
for handing out experience, than aiming for some mathematically pure function.

An example: Offense * Defense is a very good measure of combat capability 
(ignoring the effects of swarming, assume that the character can always 
retreat such that they only fight one monster at a time).  Offense is the 
average damage they do (ie chance to hit times average damage times number 
of attacks) and defense is how much damage they can take on average (ie 
chance to avoid damage times hit points).

Example 1: a rat which does 1-2 points of damage, has a 1 in 3 chance of 
hitting, has no chance of dodging and 2 hitpoints would be worth 1 xp.  
((1.5 times (1 divided by 3)) times 2)
Example 2: a balrog which does 10-20 points of damage, has a 100% chance 
of hitting, gets three attacks a round, avoids (dodges/deflects/counterspells/whatever) 
50% of attacks and has 100 hit points would be worth (15 times 3) times 
((100 divided by 50)  times 100) or 9000 xp.  Actually, that might not be 
enough :-)

You can increase the spread by raising the amount of xp from the above formula 
by some power greater than 1, try 1.1 or 1.2.  9,000 to the power of 1.2 
is 55,602 which should keep the players happy.  Whereas 1 to the power of 
anything is still 1.

Other factors to consider are the dungeon level the character has gotten 
to, what resistances the monster has, whether the monster has ranged attacks 
(these are really nasty in roguelikes, you may wish to reward the players 
accordingly) and whether it drops items that help the player (which are 
a reward in themselves in that they improve the character) when it dies. 
 Of course killing an Elder Dragon and having the experience it gives you 
reduced by 10% because it dropped a +1 dagger, would suck.

In terms of experience to go up levels, something to avoid is requiring 
as mush xp to go from 1 to 2 as from 2 to 3.  This can happen when you use 
an exponential curve that doubles for a while.  Just as a wild totally random 
example, take a fighter that needs 2000xp to get to level 2, and 4000xp 
to get to level 3, and 8000 xp to get to level 4 etc.  Now think about this,
 in order to get to level 2, the fighter had to gain only 2000xp, but this 
is also the amount they need to gain in order to get to the next level, 
but now they have an extra levels worth of hitpoints, better chances to 
hit etc, which means that it is easier to get from 2 to 3 than it was to 
go from 1 to 2.  And the game shouldn't get easier as they go up levels.

cheers,

Rick