Computational Models of Experience
There are many active models of "experience" in use today. The canonical example is the role-playing game (RPG), except that the experience models vary widely. Some real-time strategy and even turn-based strategy games also implement an appropriately limited experience system. Each model uses some method to convert a combination of what a player's character "knows" and "has experienced" into a set of numbers. Those numbers can then be compared to either a predefined standard or another character's number set. The results of such comparison are used in diverse ways, but the systems used to arrive at the numbers to compare -- and the predefined standards for comparison -- are the main concern here. Therefore, references to "level" and "gaining a level" and such should be considered generic terms for the use of said results.
First, what are the conversion techniques for changing an "experience" into a usable number for computational purposes? The four types discussed here are equal and fixed "value" (for every "experience"), unequal but fixed, equal and decreasing, and unequal and decreasing.
In many games (RPG or otherwise), some portion of the player's goal is to engage and destroy "enemies"; thus, a simple measure of "experience" is the number of enemies destroyed, which is an "equal and fixed" system. For example: raw kill counts improve armor and accuracy in Total Annihilation (on multiples of 5). Another example of this is when a player's character obtains ten "knight's crest" items in The Legend of Zelda: Windwaker -- almost always by killing certain monsters -- then brings them to the appropriate non-player-character (NPC). The NPC then gives the character a new skill to use.
"Assigning different values to different experiences" is the most common model in RPGs, which is unequal and may or may not be fixed. A monster in a game will be assigned an "XP" (shortened form of eXPerience) value, and killing that monster gives the killer that much XP to add to their total. The player should expect that not every monster carries the same XP value (e.g., Ragnarok Online, at least a couple in the Final Fantasy series).
The system of assigning different values to different experiences may be too simplistic in some situations, and this leads to changing models -- both equal and unequal. Of this kind, unequal and decreasing systems are probably the most common. The system in this type of game is to reduce the amount of XP the player receives from a certain task based on an increase in the player's "level" -- e.g., Neoquest, where different amounts of XP are given upon defeating monsters, based both upon the monster's amount of HP ("hit points") and the monster's level, and upon the difference between the monster's HP and level and the character's HP and level.
Each of these models achieves the goal of assigning a value to an experience, but that value typically needs a system under which it can be redeemed for things which are deemed "valuable" to a person. "Gaining a level" is the canonical RPG reward, as it implies certain (sometimes configurable) bonuses that are (or can be) applied to the player's character.
"Value" or "Reward" Systems
These systems can be described in (essentially) the same way as experience systems, except "value" is replaced by "cost": equal and fixed, unequal but fixed, equal and increasing, and unequal and increasing. Balancing an experience system with a value system can be a relatively simple matter of matching: for example, equal and fixed "cost" can go well with equal and fixed "experience value" (e.g., kill counts directly improving accuracy and armor rating).
RPGs using unequal and fixed or unequal and decreasing systems are perhaps the most widely known and recognized examples, and each is likely to use either an exponential or an asymptotic predefined standard:
- The games in (most of) the Final Fantasy series: XP and AP systems are both unequal and fixed with exponential-like standard. (Many other games in this category.)
- Neoquest/Neoquest II: XP is an unequal and decreasing system with polynomic/hand-tuned standard, and has an equal and fixed reward system (each level gain yields one skill point to use).
- NetHack: like Neoquest, XP is an unequal and decreasing system, but instead with an exponential standard; the same skill point method is used.
- Ragnarok Online: XP is an unequal and fixed system with an exponential-like standard, but a portion of the rewards system (stat points gained upon gaining a level) is equal and increasing with a polynomic standard. The player gains linearly more stat points to spend with each successive level (floor((level-1)/5)+2), and must spend linearly more stat points for each successive stat increase (floor((statvalue-1)/10)+1) in any of six stat types. Thus the player can get max stats that look like this (at maximum level): 1 / 99 / 1 / 9 / 99 / 1, or 1 / 93 / 1 / 30 / 80 / 50 or even 50 / 54 / 50 / 54 / 54 / 54. (Yes, these are each realistic possibilities that will use up all or nearly all of the available stat points, though the last one might not be considered a useful build in this particular game.)
Online's system also exhibits one clear example of level grind
: to gain level 99 with a character who starts at the beginning of level 98, 100 million experience points are required. The average XP gain per minute from killing monsters for such a character is probably around 10,000 and is (probably) no more than 20,000, thus it would (likely) take 5000 to 10,000 minutes (100 to 200 hours) of killing monsters to gain that one level.
Some real-time strategy (RTS) games have implemented varying degrees of experience systems as well. Total Annihilation has been mentioned, and Total Annihilation: Kingdoms also falls in this category. The Kingdoms release implemented an unequal and fixed system, where each enemy dispatched added some amount of XP (possibly based on the enemy's initial "HP" count), and there are three levels of increasing damage, armor and accuracy bonuses. Since there are only three points of reference, this system could arguably fit into any of the four mentioned function types. To a more limited extent, Warcraft III also implemented a similar experience system with ten major levels; this system was only applied to specific characters in the game.
One turn-based strategy that implemented an experience system is Space Empires IV. Each ship gains combat experience during fights, and if that ship survives the encounter, that combat experience amounts to accuracy and dodge improvements for that ship. (Unfortunately, I'm not familiar with the exact XP and reward system, but it seems to fall under the "fixed and equal with artificial cap" category.)
Some of the predefined standards -- polynomic and exponential -- have been mentioned, and the other two to include are "hand-tuned" and "asymptotic". Below are some more-detailed descriptions of each of these four systems. A major philosophical point in any experience-based system is that successive experiences of the same type and difficulty are worth decreasing amounts of experince... thus each of the examples listed below of these four models attempts to fit with that philosophy.
Polynomic enforcers are the most general of the four kinds. They are those functions of the form x = a_1*yn_1 + a_2*yn_2 + ... where y = f(x) and for all i, a_i and n_i are integers. One way to easily use this type of enforcer (in general) is to cycle through each expected level number and plug that value in for y, then save the values of x and simply test the XP values against this list of x values to determine the current level. For example, consider x = y2. Under this system, the player "levels up" at XP counts of 1, 4, 9, 16, etc. and these levels are 1, 2, 3, 4, and so on. Technically, every system can be described as polynomic, since for every set of points which map to another set of points, it is possible to create a polynomial which also yields that same mapping (note Lagrange's interpolation polynomial). Neoquest uses a polynomic enforcer (whose function is of degree 2 or 3), and this works pretty well as the game simply moves forward (at "normal" difficulty) throughout, without noticable amounts of level grind.
Exponential functions are quite possibly the most common specific enforcer actually used (for reasons too numerous to mention), with probably the main reason being the ease of implementation compared to the amount of "useful/interesting" gameplay. f(x) = floor(a*logb(c*x)) is an easy function to use for this (works best when a is greater than one and b is positive). In a system that uses something like f(x) = floor(log2(x))+1, the player's maximum level has no natural limit, so artificial or practical limits come into play (programmer resources, available system memory, maximum size of the numbers used for XP or level, etc.). This particular system would sport level gains at XP amounts of 1, 2, 4, 8, 16, etc., and this corresponds (roughly) to the system in NetHack. Exponential systems often suffer from the "level grind" problem for characters whose level is near the maximum, and this problem isn't necessarily offset by other features of the system (e.g., the level 98 -> 99 issue in Ragnarok Online, as mentioned earlier).
Hand-tuned functions may look like one or another of the preceding enforcers, but are essentially just that: hand-tuned. There may be a specific domain in which hand-tuned functions are the only way to balance a system properly, but in most cases -- due to time or resource restrictions -- it is best to pick one of the other function classes and then tweak a known function with predictable outcomes. By way of example, consider the system where, for levels one through ten, the required XP values are (1, 1, 1, 3, 3, 5, 7, 11, 17, 29). This is a hand-picked list of primes (and ones), and it will accomplish the goal of providing a semi-decreasing influence of XP on level.
Asymptotic functions ought to be fairly common, due to their definition: each one has a guaranteed, built-in and finite limit (hyperbola-style asymptotes are also finite limits in their own sense), so there is no need to impose artificial caps. For example, f(x) = floor(a*tan-1(b*x)) where a is greater than one and b is positive. Regardless of what positive number is used for x, this function will return an integer within a finite range (0, a*pi/2). Thus it is easy to set a limit on the maximum: just let a = (2k+1)/pi for some positive integer k, then k will be the maximum possible value of f(x). Another function that works is f(x) = floor((a+1)*(1 - e-x)), where a is the maximum possible value of f(x). A couple of the near-maximum-possible levels would almost certainly suffer from "level grind" issues in an asymptotic system, but this isn't absolutely certain since the "shape" of the curve approaching the asymptote -- and the distance between the value required for the maximum level and the asymptote -- can be changed relatively easily.
In the game I hope to implement someday, I expect to use a mixture of asymptotic and exponential systems for various game elements. The asymptotic portions will be those where "perfection" is the asymptote, and the character gets ever closer, but will never get there. The exponential elements are those that I intend (and hope) to make "infinite"... as much as that may or may not be possible.
Thanks to Cletus the Foetus, kalen, and others in the RPGers group (and possibly e^2 also) for proofreading and giving suggestions.