Dream Tutor: For the Math of It

by Lummox JR

Your game needs math.

Yes it does.

Yes it does. Stop shaking your head. And the places it doesn't need much math, you can apply a little more to make it cooler. Math is your friend.

All right, it's my friend, but it can be your friend too. I'll tell it to play nice and show you how you can get it to perform tricks. Let's go over a few useful formulas you can use in your game. I promise your head won't explode, at least until we get near the end.

It's All About Experience

The most basic math problem in a typical BYOND game is handling experience counters for increasing your character's level. Most experience tables follow an exponential progression, where each level needs n times more experience than the one before, like this one:

• Level 1: 0-19 exp
• Level 2: 20-59 exp
• Level 3: 60-139 exp
• Level 4: 140-299 exp
• ...

In this experience chart it takes 20 experience points to reach level 2, but it takes 40 more to get to level 3, 80 more to hit level 4, and twice as many with each new level. Another way to do this is that the starting experience for each level is exponential (with level 1 always starting at 0):

• Level 1: 0-19 exp
• Level 2: 20-49 exp
• Level 3: 50-124 exp
• Level 4: 125-312 exp
• Level 5: 313-781 exp
• ...

In this example, you need 20 points to get to level 2; after that, the amount of additional points for the next level is 1 1/2x the one before. (The amount of total points is 2 1/2x more, which is important to know too.)

So how do you calculate this? Well, let's look at the first one. At level 1 it takes 20 points to get to the next level, and at level 2 it takes another 40 after that. Basically what we want to be able to calculate is the first number in each line of the table: 20, 60, 140, and so on. There are two ways to do this. The first I can present as a little snippet of code:

mob
  var/level = 1
  var/exp = 0
  var/exp_needed = 20
  var/exp_next_level = 20  // to start

  proc/LevelCheck()
    while(exp_needed <= 0)
      ++level
      exp_next_level *= 2
      exp_needed += exp_next_level
      // add in stuff to gain abilities and stats here

This is a little bit unwieldy because every time you gain experience, you have to update two vars: exp and exp_needed. It's a bit ugly. The second way to do this is to figure out in advance where the next level starts. The sequence goes 20, 60, 140, 300.... Each number is twice the number before it, plus 20.

mob
  var/level = 1
  var/exp = 0
  var/exp_next_level = 20  // to start

  proc/LevelCheck()
    while(exp >= exp_next_level)
      ++level
      exp_next_level = exp_next_level * 2 + 20
      // add in stuff to gain abilities and stats here

That's a lot nicer, isn't it? But if you want to get rid of that pesky exp_next_level var, which is really taking up space for little reason, you can find a formula. In this case the formula works out like this:

proc/ExperienceForLevel(level)
  return (2 ** level) * 10 - 20

(The ** operator is how BYOND handles exponents.) The second table is a little easier to manage. Because the starting value is 20 for level 2, and goes up 2.5x per level after that, it's simpler:

proc/ExperienceForNextLevel(level)
  if(level <= 0) return 0
  return round(20 * (2.5 ** (level-1)), 1)

So why did I put in that (level-1) part? The experience to move from level 1 to level 2 is 20, which is 20x1, or 20x2.5⁰. For the next level jump from 2 to 3, I'd want 50 total points, which is 20x2.5¹. The exponent is always the current level minus 1. The whole thing is included in round(formula,1) so it gets rounded off.

Going In Circles

Circles can come up in lots of situations. One common use is to create explosions with a certain range. We all know explosions don't happen in a square, so if you were to create your special effect everywhere in oview(4,target), for instance, it'd look silly.

To make an explosion happen in a circle, you have to calculate the exact distance from any given point in range to the center of the circle. get_dist() won't cut it. Finding that distance requires a little something called the Pythagorean Theorem. Chances are you've heard of it, but basically it says that if you take a right triangle (that is, it has a perfectly square corner), where a and b are the shortest sides and c is the long side, c²=a²+b². Distance works the same way:

d² = (x₁-x₂)² + (y₁-y₂)²
d = sqrt((x₁-x₂)² + (y₁-y₂)²)

To make a circle, you need to find every point whose distance from the center is no more than the circle's radius. (The radius is the distance from the center to the edge of the circle.) So let's take a look at how we might place things in a circle.

proc/PlaceExplosions(turf/center, radius=3)
  for(var/turf/T in range(radius, center))
    var/dx = T.x - center.x
    var/dy = T.y - center.y
    if(dx*dx + dy*dy <= radius * radius)
      new /obj/effect/explosion(T)

See how I precalculated dx and dy? I calculated (T.x-center.x) in advance because it's easier than doing it twice. Typing dx*dx is also faster than using (T.x-center.x)**2, because ** is quite slow. Notice, though, that radius*radius is being multiplied every time. This is pretty wasteful, and should really be done before the loop. I'll get to that in a minute, but I left it this way for the moment because it's a little clearer. Take a look at the shapes this will render for varius explosion sizes:

                         #
               #       #####
       #     #####    #######
 #    ###    #####    #######
###  #####  #######  #########
 #    ###    #####    #######
       #     #####    #######
               #       #####
                         #

Those are some awfully pointy ends. Computer graphics programs draw smoother circles than that. Isn't there a way to smooth that out?

The reason for those pointy ends is that d² (distance, squared) is exactly the same as r² (r being the circle's radius) at that point. Go just a single square to either side and you've got d²=r²+1, which is too much. The way to smooth this out is to pretend the circle's radius is half a tile bigger than it actually is. That would mean instead of d²<=r², you'd use d²<=(r+0.5)²=r²+r+0.25. We can ignore the 0.25, which makes this r²+r our upper limit; this is the same as rx(r+1).

proc/PlaceExplosions(turf/center,radius=3)
  var/rsq = radius * (radius+1)
  for(var/turf/T in range(radius, center))
    var/dx = T.x - center.x
    var/dy = T.y - center.y
    if(dx*dx + dy*dy <= rsq)
      new /obj/effect/explosion(T)

Now, the circles look smoother:

                       #####
              ###     #######
      ###    #####   #########
###  #####  #######  #########
###  #####  #######  #########
###  #####  #######  #########
      ###    #####   #########
              ###     #######
                       #####

If you want something a little in between those two, try changing rsq to use radius*(radius+0.5) instead.

This is all well and good, but what if you don't want to make explosions? It might be a good way to make a monster circle around a target before moving in for the kill. It's also handy for radar with a circular range.

Half-Life and Taxes

A lot of situations in nature involve exponential decay, where one value approaches another more and more slowly the closer they get. Radioactive atoms break down into smaller elements faster in greater quantities, and slower as more and more atoms break down. Growth and healing follow the same principles, as do many chemical interactions inside the body. See where I'm going with this?

Picture an RPG with a heavy slant toward magic. You want powerful characters with lots of mana to regain their points at a decent rate, so they can use their powerful spells. (Otherwise, what's the point?) It makes sense then that everyone should regenerate mana at the same rate, proportional to their potential. In other words, if two characters' mana points are depleted at the same time, they should each be at about half strength some time later. There are two ways to do this of course: One is to set a fixed time for complete regeneration. But a more realistic model would make it difficult to recharge fully. Instead it might take an hour to return to the halfway mark, two hours to hit 3/4, etc.

This sort of system is pretty easy to do. Ignoring, for the moment, whole numbers, take a look at this formula:

// call every second
MP = 0.99*MP + (1-0.99)*maxMP

The value of MP will slowly approach maxMP every time this formula is used. The gap between maxMP and MP will narrow by 1% each time. If it's called every second, then MP has a half-life of about 69 seconds. (The formula is lambda=log(0.5)xunit/log(k), where k in this case is 0.99 and unit is 1 second.) The half-life (lambda) is how long it takes for the value to reach halfway to its goal from where it starts.

So let's say you want MP to return halfway to its full mark every 5 minutes of gameplay. You wouldn't want to call this formula only every 5 minutes. Instead you'd want to call it fairly often. For starters, say it's called every 10 seconds; that's not so unreasonable. You can use a calculator to figure out the rest. Using the formula above:

(5 minutes) = log(0.5) x (10 seconds) / log(k)

log(k) = log(0.5) x (10 seconds) / (5 minutes)

log(k) = log(0.5) / 30

k = e^log(0.5)/30 = 0.5^1/30 = approx. 0.97716

So to use this formula, you'd call this every 10 seconds (100 ticks):

MP = 0.97716*MP + 0.02284*maxMP

When displaying MP in a stat panel or measuring it to cast spells, round(MP,1) will give you a close whole number. It doesn't matter if the player really only has 3.7 points instead of 4 needed to cast a spell, since they'll see 4 on their screen. This way, magic will also appear to fully regenerate. Of course, if you insist on MP never ever going below 0 no matter what, then use round(MP) and consider this alternate formula instead:

MP = 0.97716*MP + 0.02284*(maxMP+0.5)

The net effect is about the same. Incidentally, both these formulas still work if you exceed maxMP. You could always add a magic-raising potion that bumps MP up past the max. The extra magic would have to be used right away or go to waste as it slowly dwindles to a normal level.

This sort of thing can be cleverly used in other ways as well. It can drive a monster's fear/hunger response for AI. It can help control shop prices for items that are bought or sold frequently. It can calculate interest in a bank.

proc/CheckBalance(mob/M)
  if(!lasttime[M])
    return M.OpenAccount()
  var/rt = world.realtime    // get this value once, so it stays the same
  var/elapsed = rt - lasttime[M]
  lasttime[M] = rt
  // 1% interest a day
  savings[M] *= 1.01 ** (elapsed/864000)
  Save(M)
  M << "You have $[round(savings[M])] in your account."

The interest rate here is based on game mechanics more than real life. At a rate of 1% per day you'd double your money every 10 weeks. You'll notice a few differences from the magic formula, though. For one thing, the amount of money in savings isn't recalculated constantly, but only when it is checked. Since world.realtime is measured in ticks, is has to be divided by 864000 to give a number of days.

If you can update this kind of value on an as-needed basis, it really is ideal. For stats which are displayed constantly on the screen or in a stat panel, it may not be feasible to do so. However one alternative approach is to figure out how long it will be before a display indicator needs to be changed (such as changing a health icon from yellow to green). There's a formula to tell you how long you need to wait.

t = abs([log(abs(new_value-target_value))-log(abs(value-target_value))] / log(k))

This formula will tell you how long it takes for value to become new_value. By knowing this, you can wait until that time comes, and then update the values at that time. For example, if your health bar ranges from 0 to 20 pixels, and health currently uses 11 pixels, then all you need to know is when health would be about 11.5 out of 20 so it will round up to 12.

// target number of pixels for next health meter change
var/next = round(HP / maxHP * 20, 1) + 0.5
// health required for those pixels
next = next * maxHP / 20
// time to reach this health
t = (log(maxHP - next) - log(next - HP)) / log(k)
// round up to nearest 1
t = -round(-t)
sleep(t)
HPmeter.Uptate()

Realistically Random

One common way to introduce variety into a game is by using random elements. For example, you might use randomness to generate buildings in a town, or to populate a field with creatures, or perhaps to give such creatures different characteristics like a real population. Well, you may have noticed that towns and populations don't have even spreads. They kind of cluster around some central average. Some people may be very tall and some very short, but in general adult humans reach around the same height.

Whether you're doing any realistic landscape generation or playing around with monster stats, you'll probably want something a lot more realistic than rolling a die. But if you were to roll a lot of dice and sum them up, you'd get closer to what's called a Gaussian distribution (also called a normal distribution, or bell curve), where values cluster around the average. We're about to take a very short walk through the field of statistics.

In statistics, any spread of data is called a distribution. The two things you need to know about it is that it has a mean (the average) and it has a standard deviation. Standard deviation controls the width of the curve. On a bell curve, 68% of the population falls within one standard deviation of the mean. That is, if your monsters have an average strength of 9 and a standard deviation of 1, then 68% of them have a strength stat between 8 and 10. 95% of them will be within 2 standard deviations, so they'll have strength between 7 and 11. 99% are within 3 standard deviations, and 99.99% are within 4.

You can use this to your advantage when creating monsters, or even land features like trees in a forest (by finding a distance from the center). To do this, you'll have to know how to generate Gaussian random numbers. The numbers produced by a Gaussian generator will average a value of 0, and a standard deviation of 1. 68% of them will be from -1 to 1, 95% from -2 to 2, and so on.

proc/GaussRand()
  var/x,y,rsq
  do
    x=2*rand()-1
    y=2*rand()-1
    rsq=x*x+y*y
  while(rsq>1 || !rsq)
  return y*sqrt(-2*log(rsq)/rsq)

This proc comes a formula that will actually produce two Gaussian numbers. The other number is x*sqrt(-2*log(rsq)/rsq), but since we can't return two values without using a list, and BYOND does not use pointers like C does, we'll just have to throw that one away. It doesn't matter much; we can always make more.

Now, how do you use this? Well, let's think of something practical. Say you want to distribute chunks of a meteor from the impact center, to decorate your landscape or possibly provide ore players could mine.

// radius is just 1 standard deviation; some framents will spread out farther
proc/CreateMeteorChunks(turf/center, radius, fragments)
  var/obj/meteor/M
  for(var/i=fragments, i>0, --i)
    var/r = GaussRand() * radius
    var/a = rand() * 360
    var/xo = r*sin(a)
    var/yo = r*cos(a)
    M = new(locate(center.x+round(xo,1), center.y+round(yo,1), center.z))
    M.pixel_x = round((xo-round(xo,1))*32, 1)    
    M.pixel_y = round((yo-round(yo,1))*32, 1)

That proc is going to spread out your meteor chunks in a circle with most of them concentrated toward the center. You could also do something similar to populate a town with buildings as long as street layout isn't important; you would however want to prevent overlap, so you'd have to cull some of the buildings out of your results.

Summing Up

Now, that wasn't so bad, was it? Well maybe a little, but you don't have to use all of this. There are other formulas out there, too, that might serve you better. The key is, all you need to do is think in terms of formulas for some basic tasks like leveling up or building a circle. Game programming involves math by its nature; if you were doing 3D programming it'd just be that much more of it. In BYOND, you don't have to drown in math, but if you're willing to get a little wet your game will be a whole lot better.

Appendix A: Experience Formulas

All formulas similar to experience table 1 or 2 can be derived as follows:

exp(L) = a^Lb+c

L is the current level, and exp(L) is the total experience required for the next one. (Note: Total experience includes points you earned for previous levels.) This formula is valid for L>=1, since the experience scale starts at 0 points no matter what. You have to decide what a, b, and c are. The easiest to find is a; if your value is doubling each time, plus or minus some small amount, then a=2. Then you can solve using the values from your table. Going from the first table where exp(1)=20, exp(2)=60, exp(3)=140, and so on:

a = 2exp(1) = 20 = 2¹b+c
exp(2) = 60 = 2²b+c

Subtract those two and you get:

(2²-2¹)b = 40
2b = 40
b = 20

And then you can find c:

exp(1) = 20 = 2¹20+c
20 = 40+c
c = -20

total_exp_for_next_level = (2 ** current_level) * 10 - 20

The same process can be applied to the table that goes by 20, 50, 125, etc. If you don't know what a is in advance, you can always divide one level's experience by the one before it; as the levels get higher, this should get closer and closer to a.

a = 2.5
exp(1) = 20 = 2.5¹b+c
exp(2) = 50 = 2.5²b+c
30 = (2.5²-2.5¹)b
3.75b = 30
b = 8

exp(1) = 20 = 2.5¹8+c
20 = 20+c
c = 0

exp(level) = 2.5^level8

Because 8 is the same as 20/2.5¹, as you can see from the solution for c, another way to write the formula is:

exp(level) = 2.5^level(20/2.5¹)
exp(level) = 2.5^level-1 x 20

To be safe, you should always round these formulas off using round(formula,1).

Appendix B: A decay meter

A meter for a stat which only updates periodically may look something like this:

var/obj/meter
  var/mob/owner
  var/size = 30     // range of values, i.e. 0 to 30
  var/V,maxV,targV,hl,logk
  var/lastupdate = 0
  var/nextupdate = 0

  // specify half-life in ticks
  New(client/C, position, varname, maxvarname, targvarname, halflife)
    if(!C) return
    screen_loc = "[position]"
    owner = C.mob
    V = varname; maxV = maxvarname; targV = targvarname
    owner.client.screen += src
    hl = halflife
    logk = log(0.5)/hl
    lastupdate = world.time
    Update()

  proc/Update(deltaV, newmax, newtarget)
    var/first=1
    var/targ,kt,v,mv,n,tn
    while(owner && owner.client)
      targ = targV ? owner.vars[targV] : 0
      if(lastupdate < world.time)
        kt = 0.5 ** ((world.time - lastupdate) / hl)
        lastupdate = world.time
        owner.vars[V] = owner.vars[V]*kt + (1-kt)*targ
      if(first)
        owner.vars[V] += (deltaV || 0)
        if(!isnull(newmax)) owner.vars[maxV] = newmax
        if(!isnull(newtarget) && targV) owner.vars[targV] = newtarget
        if(nextupdate == world.time) return    // still meant to update later
        first = 0
      v = owner.vars[V]; mv = owner.vars[maxV]
      n = min(max(0, round(v * size / mv, 1)), size)
      icon_state = "[n]"
      if(nextupdate > world.time) return
      nextupdate = 0
      tn = min(max(0, round(targ * size / mv, 1), size)
      if(tn > n) n += 0.5
      else if(tn < n) n -= 0.5
      else return     // no updates pending
      nextupdate = (log(abs(targ-n*mv/size)) - log(abs(targ-v))) / logk
      // round up
      nextupdate = -round(-nextupdate)
      sleep(nextupdate)
    del(src)

You should call Update() for this meter whenever the value of the stat, the maximum stat, or the target value changes. I.e., you might create a hit points meter using this:

new/obj/meter(myclient, "EAST,1", "HP", "maxHP", "maxHP", 3000)

That's a meter with a 5-minute half-life which displays regenerating hit points. It doesn't change HP or maxHP, but it does anticipate when they'll change based on the data you provide. If the value of HP or maxHP is changed by taking a hit, healing, or gaining a level, you'll need to update this. To take a hit or heal, simply call meter.Update(gained_HP), and to change the maximum HP, call meter.Update(ganted_HP, new_maxHP). By calling Update() the value is brought up to date before your changes are made. If you really want to enforce a maximum of maxHP or a minimum of 0, you can always change HP manually after the call.