Dream Tutor: Learn To Love Associative Lists

by Lummox JR

Few novice programmers understand the power of lists in BYOND. DM's support for lists is one of the great strengths of the language, and using lists to their fullest potential can make difficult programming challenges much easier.

Lists vs. Hash Tables

A list is simply an array, a bunch of items grouped together. Unlike in many other programming languages, DM doesn't care if you set up the size of the list in advance; the list will grow or shrink as you wish, and can be very easily manipulated. If you have experience with other languages, you've probably often run into a situation where you want to change the size of a list; in BYOND this is a snap. You also don't have to make a list for just one kind of thing, so a list in DM can use numbers, text, atoms and more all mixed together.

Several programming languages also have a concept called hash tables, which are more than simple lists: Every item in a hash table has a unique key that goes with it; this key can be anything, like an object or text, but usually isn't a number (though it could be). Items in the list come in pairs: A key and a value. This is very good for looking up names, for example.

What do hash tables have to do with BYOND? Lists in BYOND are also hash tables. Any unique item you put in the list can be used as a key for another value that goes along with it. This value is said to be associated with the key, so you can say a list set up like this is an associative list. All you have to do is something like this:

L[key] = value

If you want to see all the keys and values in the list, try:

for(var/key in L)
  var/item = L[key]
  world << "L\[[key]\] = [item]"

So What?

At this point you may be wondering what good this does you. Well, for a minute let's consider a shopkeeper in a simple RPG. We'll say this shopkeeper has a bunch of objects in his inventory, and that's what he's willing to sell you. When you use the buy() verb on him, a window will pop up asking you what you want.

mob/shopkeeper/apothecary
  New()
    contents=newlist(/obj/potion/heal,
                     /obj/potion/confusion,
                     /obj/potion/poison)

  verb/buy()
    set src in oview(1)
    var/list/choices = new
    var/obj/O
    for(O in contents)
      choices += O
    var/item = input(usr, "What do you want to buy?","Buy","Nevermind") \
                     as null|anything in choices
    if(!item) return
    O = item    // the user selected an item
    if(usr.gold < O.price)
      usr << "You don't have $[O.price] to pay for \a [O]!"
      return
    usr.gold -= O.price
    O=new O.type(usr)   // create a new object of this type
    usr << "You pay $[O.price] for \a [O]."

What's wrong with this picture? There's no price var in obj, right? Well no, let's assume that's all been set up for us, and that mobs have a gold var too. If you said the player can't see what the prices are, you're right. A player won't know if he's paying $60 for a healing potion or $30 for the rat poison until he's already shelled out the dough. Shopkeepers would love this, but people don't just buy things without checking the price first, and there's no code in there for haggling.

The trick here is to change the choices list so that the input() proc shows more information. But, say you used code like this:

for(O in contents)
  choices += "\A [O]: $[O.price]"

Well, that's dandy, but once the choice comes back from input(), item is going to equal something like "A potion of confusion: $85". How is your code supposed to change that back into the /obj/potion/confusion the shopkeeper's carrying?

Here's where associative lists come in. For every piece of text we add to the list, we associate an object with it. When you include a line of code like L[key]=value, the key is added to the list automatically. The keys are the things that are actually going into the list, so they're what the input() proc would show us. That's exactly what we want.

for(O in contents)
  choices["\A [O]: $[O.price]"] = O
var/item = input( ... ) ...
if(!item) return
O = choices[item]   // item is text, O is the associated value

This adds text to the list, but associates the object with it. The object itself can be retrieved later when we need it. Neat, huh?

A Step Further

So, this obj.price variable is kind of unwieldy, isn't it? You've got to set a price for everything you might conceivably want to buy, and that price is fixed for every shopkeeper who sells the same thing. Oh sure, they could change the prices individually, but then that price is forever set on the item you buy, and that could affect any selling code you might eventually add. You could fudge your way around this by having a shopkeeper offer discount prices or something, but that's not a very practical solution, is it? Wouldn't it be nice for the shopkeeper to set the price instead, and not make the objects responsible?

Another thing you should know about associative lists in BYOND is that there's a nifty DM syntax for creating associations in lists when you create the list:

var/list/L = list("key1"=3, "key2"=8)

This, as you might expect, associates the key "key1" with the number 3, and "key2" with 8. It's identical to this:

var/list/L = new
L["key1"] = 3
L["key2"] = 8

Looks like it's time to revisit that shopkeeper.

mob/shopkeeper/apothecary
  var/list/selling

  New()
    ..()
    // notice where the prices are?
    selling=list((new /obj/potion/heal) = 60,
                 (new /obj/potion/confusion) = 85,
                 (new /obj/potion/poison) = 90)

  verb/buy()
    set src in oview(1)
    var/list/choices = new
    var/obj/O
    for(O in selling)
      // selling[O] is the associated price
      choices["\A [O]: $[selling[O]]"] = O
    var/item=input(usr, "What do you want to buy?", "Buy", "Nevermind") \
                   as null|anything in choices
    if(!item) return
    O = choices[item]
    var/price = selling[O]
    if(usr.gold < price)
      usr << "You don't have $[price] to pay for \a [O]!"
      return
    usr.gold -= price
    O = new O.type(usr)     // create a new object of this type
    usr << "You pay $[price] for \a [O]."

Notice the main changes:

• There's no longer price var for objects.
• The list of items to sell is no longer in the shopkeeper's "inventory" (contents), but is in a new list called selling.
• There are two associative lists now: choices and selling. In choices, each item is a text string with an associated object. In selling, each item is an object with an associated number (the price).

Now, because the prices are no longer fixed, this means several things: First, a particular shopkeeper can be set up with different prices than his competitors'. Also, the price is not constant and can be changed according to demand; a clever shopkeeper might raise the price if something is bought often enough, or lower it if too many are sold back to him. (There's no sell verb for my shopkeeper, though. You have to do that yourself!)

More Associative Goodies

Let's say for the sake of argument that you've designed a bank for your RPG where characters can store their money, but you used single-player code and just realized you want to make it work for more than one player.

obj/bankcounter
  var/money = 0
  density = 1

  Bumped(mob/M)
    if(!M.client) return
    switch(alert(M, "What do you want to do?", ,\
                 "Withdraw", "Deposit", "Nothing"))
      if("Nothing") return
      if("Deposit")
        var/amt = input(M,\
                        "How much of your $[M.gold] do you want to deposit?",\
                        , M.gold) as null|num
        if(!amt) return
        amt = round(amt, 1) // no decimals!
        if(amt <= 0) return
        if(amt > M.gold) amt = M.gold
        M.gold -= amt
        money += amt
        M << "You deposited $[amt]. You now have $[money] in the bank."
      if("Withdraw")
        if(!money)
          M << "You have no money in this bank."
          return
        var/amt = input(M,\
                        "You have $[money] in your account. How much would \
                         you like to withdraw?", , money) as null|num
        if(!amt) return
        amt = round(amt, 1) // no decimals!
        if(amt <= 0) return
        if(amt > money) amt = money
        money -= amt
        M.gold += amt
        M << "You withdrew $[amt]. You now have $[money] in the bank."

Notice the problem? The money var is the same no matter who does the transaction. This is like every player in your game sharing a joint account. So, how do we adapt that to work with more than one player? You guessed it: Another list. We'll change var/money=0 to:

var/list/accounts

Now, we change every reference to money to accounts[M.client.ckey]. This means that now every user can have their own account under their own key, and the value associated with their key is the amount of money they have in the account. You'll also have to add this line to the deposit code just before the deposit is added:

if(!(M.client.ckey in accounts)) accounts[M.client.ckey]=0

Here's a sample of how the updated code will look:

      if("Withdraw")
        var/money = accounts[M.client.ckey]     // for simplicity
        if(!money)
          M << "You have no money in this bank."
          return
        var/amt = input(M,\
                        "You have $[money] in your account. How much would \
                         you like to withdraw?", , money) as null|num
        amt = round(amt,1)    // no decimals!
        if(amt <= 0) return
        if(amt > money) amt = money
        // you have to use the list here, not the money var
        accounts[M.client.ckey] -= amt
        M.gold += amt
        // use the list here too, because "money" still has the old amount
        M << "You withdrew $[amt]. You now have $[accounts[M.client.ckey]] \
              in the bank."

This piece of code still uses money a lot, instead of accounts[M.client.ckey]. Why is that? Because it's shorter, quicker to type, and BYOND won't have to look up the appropriate list entry a hundred times. By assigning money the value that's in the list, we've made a copy, and we can use that to look up the amount of money in the account more quickly. Of course, this value is only good up until we take money out. When money is taken out, we need to use the list again, because if we subtract from money, the value in the list (that holds the real data, not the copy) is left untouched. To show how much is in the account when we're done, we need the list again because the list value has the current amount of money in the account, whereas money tells us how much was there before the withdrawal.

Of course this brings us to another problem: What if a user has more than one character? They end up sharing all their accounts, which is probably not what you'd want to do. Well, no matter; we'll just use a more complicated key.

Bumped(mob/M)
  if(!M.client) return
  var/pkey = "[M.client.ckey]:[M.name]"
  ...

proc/OpenAccount(list/party)
  var/obj/bank/safedepositbox/box = new
  for(var/mob/M in party)
    var/pkey = "[M.client.ckey]:[M.name]"
    accounts[pkey] = box

Getting Heavy

Suppose for the sake of argument that you're setting up a list where you want some members to be picked more than others. You could of course add something to the list more than once, so something is two or three times (or more) more likely to be picked than something else. But that's a big inconvenience to code, and it doesn't help with more complicated situations like where you want something to be just 50% more likely to be picked. (That's the same as having 1.5x normal chance. To do this by adding to the list, you'd have to make everything else appear twice, and then make this item show up three times. Talk about inconvenient!) Wouldn't it be easier to assign weights to each item in the list, so they'll get picked more or less often?

Weighted lists are a great way of getting more bang out of random selection than the pick() proc, since pick() is a little too democratic. Whatever proc we use to pick from the list, it will pick according to a weight we assign, so items with a bigger weight are more likely to get picked. The chance of something getting picked is its weight divided by the total weight of everything in the list, so something whose weight is 2 has twice the chance of being picked that a 1 would have.

Starting with the simple case, suppose we have a list of items to be randomly placed on the terrain for a beach:

turf/beach
  randomitems = list("driftwood", "driftwood2",
                     "shell", "shell2", "shell3", "starfish")

  PlaceItem()
    if(prob(6)) // 6% chance of something here
      var/obj/O = new /obj/decoration(src)
      O.icon = turn('beach.dmi', rand(0, 3) * 90)   // just to make things interesting
      O.icon_state = pick(randomitems)

Hey, now that's a great-looking beach we have there. But suppose it's not exactly to our liking; half the objects on the beach are lousy shells. Let's say you want only a quarter of the items to be shells, another quarter starfish, and the rest driftwood. That means each driftwood piece has a 1/4 chance of being picked, and each shell 1/12. You're probably not ready to work with fractions in a custom pick proc yet, so let's change all those to integers. Digging into a little of the old high school algebra, 12 is the common denominator of all those fractions, so if you multiply everything by 12, 1/4 becomes 3, and 1/12 becomes 1. The 3's and 1's will be weights in the list.

randomitems = list("driftwood"=3, "driftwood2"=3,
                        "shell"=1, "shell2"=1, "shell3"=1, "starfish"=3)

Notice the weights all add up to 12. So each shell, weight 1, has a 1/12 chance of being picked. The starfish have 3/12 (1/4) chance. Just to have some fun, suppose you also like shell2 more than shell3 and want it to appear more often, so we'll change its weight around. To keep the totals for each category the way we want, we'll borrow from shell3 to add to shell2's weight. Let's do that for the driftwood, too, for the heck of it.

randomitems = list("driftwood"=3.5, "driftwood2"=2.5,
                        "shell"=1, "shell2"=1.5, "shell3"=0.5, "starfish"=3)

Aw, darn it, we've got decimals and fractions again. Well, to get rid of it we'll just multiply everything by 2.

randomitems = list("driftwood"=7, "driftwood2"=5,
                        "shell"=2, "shell2"=3, "shell3"=1, "starfish"=6)

There. Now we have a weighted list. Let's write a proc to use the associations and pick a random item based on the probabilities we chose.

proc/pickweight(list/L)    // make this global
  var/total = 0
  var/item
  for(item in L)
    if(!L[item]) L[item] = 1    // if we didn't set a weight, call it 1
    total += L[item]
  total=rand(1, total)
  for(item in L)
    total-=L[item]
    if(total <= 0) return item
  return null   // this should never happen, but it's a fallback

Fantastic. Time to throw that back into the turf code:

turf/beach
  randomitems = list("driftwood"=7, "driftwood2"=5,
                     "shell"=2, "shell2"=3, "shell3"=1, "starfish"=6)

  PlaceItem()  // called by the terrain randomizer to put something here
    if(prob(6)) // 6% chance of something here
      var/obj/O = new /obj/decoration(src)
      O.icon = turn('beach.dmi', rand(0, 3) * 90)
      O.icon_state = pickweight(randomitems)

When you have a weighted list like that, you can play around with the weights as much as you like until the proportions are just right. At the end of this article, I have a pickweight() proc that can handle fractions and decimals (within reason), which means you could use things like 0.5 or 0.7 or 2/3 as weights, that is if you're as masochistic when it comes to math as I am.

Lists of Lists

DM can handle lists that contain other lists. Associations can be lists too. So let's say there's a restaurant in your game with different types of food, and you want to draw up a nice menu in the mini-browser that shows all the food by category: Meat, side dishes, beverages, etc. We'll say that each restaurant is an area, which has a list of objects it sells as food much like the shopkeeper in the earlier example. (The code you're going to see can be adapted to shopkeepers too.) Let's have a list called foods that we'll fill with objects like /obj/food/chicken and /obj/food/bakedpotato and /obj/food/tea. And heck, like the shopkeeper, let's say foods has each object set up with an associated price.

area/restaurant
  var/list/menuitems
  var/list/foods
  var/letterhead    // has the name of the restaurant in HTML format for a menu

  New()
    SetupMenu()

  proc/SetupMenu()
    menuitems = new
    for(var/obj/F in foods)
      // each food has a category, like "meat"
      var/list/L = menuitems[F.category]
      if(!L)
        L = new
        menuitems[F.category] = L
      L[F] = foods[F]   // now L is an associated list, with foods and prices

  proc/MenuToHTML()
    var/output = "<table border=0><tr><td colspan=2><center>[letterhead]</center></td></tr>"
    for(var/category in menuitems)
      output+="<tr><th colspan=2>[category]</th></tr>"
      var/list/L = menuitems[cat]
      for(var/obj/F in L)
        output += "<tr><td>[F.name]</td><td>$[L[F]]</td></tr>"
    output += "</table>"
    return output

So you see, menuitems is an associative list. The keys are category names like "Side Dishes" or "Beverages" that are set for each kind of food. Each value that goes with it is another associative list, containing the foods in that category and the prices the restaurant charges. We didn't have to make this list associative too, as foods[F] would produce the same value as L[F], but there was no reason not to, either. Sometimes it's nice to have that information in more than one place.

The End of the List

Well, that's all for now. I hope this has given you a good idea of what you can do with associative lists. I've used them for lots of other things besides the sorts of things in this article. They're also great for caching altered icons (I use a key like "[name][rotation]" or "[name]:[color]" associated with the icon), which has helped me no end. You'll probably find some interesting uses too.

Free Code Inside!

What, you didn't think I'd finish this without leaving you some more complete code, did you?

What's this Bumped(), anyway?

You noticed the Bumped() proc in my examples, I'm sure. I'm not sure who originally came up with this, though I've seen Shadowdarke mention it a lot on the BYOND forums. Here's the basic code you need to set it up:

atom
  proc/Bumped(atom/movable/A)

mob
  Bump(atom/A)
    A.Bumped(src)

Pretty simple, really. It just transfers handling of the bump action from the mob to whatever it bumps. For most games, this is the preferred action.

The bank counter example

This is the final code from my bank example, with all the modifications in place. You can work from here to make an even better bank. The first place I'd start with modifications would be to make the "Deposit" or "Withdraw" buttons appear only if you have something to deposit or withdraw. Actually I'd prefer to use input() instead of alert(), or maybe better yet use verbs. Play around and see what comes to you.

obj/bankcounter
  var/list/accounts
  density = 1

  New()
    accounts = list()

  Bumped(mob/M)
    if(!M.client) return
    var/pkey = "[M.client.ckey]:[M.name]"
    switch(alert(M, "What do you want to do?", ,\
                 "Withdraw","Deposit","Nothing"))
      if("Nothing") return
      if("Deposit")
        var/amt = input(M,\
                        "How much of your $[M.gold] do you want to deposit?",\
                        , M.gold) as null|num
        if(!amt) return
        amt = round(amt, 1)     // no decimals!
        if(amt <= 0) return
        if(amt > M.gold) amt = M.gold
        M.gold -= amt
        if(!(pkey in accounts)) accounts[pkey] = 0  // create the account
        accounts[pkey] += amt
        M << "You deposited $[amt]. You now have $[accounts[pkey]] in the \
              bank."
      if("Withdraw")
        var/money = accounts[pkey]
        if(!money)
          M << "You have no money in this bank."
          return
        var/amt = input(M,\
                        "You have $[money] in your account. How much would \
                         you like to withdraw?", , money) as null|num
        if(!amt) return
        amt = round(amt, 1)     // no decimals!
        if(amt <= 0) return
        if(amt > money) amt = money
        accounts[pkey] -= amt
        M.gold += amt
        M << "You withdrew $[amt]. You now have $[accounts[pkey]] in  the \
              bank."

The pickweight() proc

I use this code myself in a random name generator. It's incredibly useful. This pickweight() proc, unlike the one above, allows fractional or decimal weights. It uses the raw form of rand() which is not limited to whole numbers.

proc/pickweight(list/L)
  var/totweight = 0
  var/item
  for(item in L)
    var/weight = L[item]
    if(isnull(weight))
      weight = 1; L[item] = 1
    totweight += weight
  totweight *= rand()
  for(var/i=1, i<=L.len, ++i)
    var/weight = L[L[i]]
    totweight -= weight
    if(totweight < 0)
      return L[i]

You could also pick a random index from such a weighted list.

proc/pickweight_byindex(list/L)
  var/totweight = 0
  var/item
  for(item in L)
    var/weight = L[item]
    if(isnull(weight))
      weight = 1; L[item] = 1
    totweight += weight
  totweight *= rand()
  for(var/i=1, i<=L.len, ++i)
    var/weight = L[L[i]]
    totweight -= weight
    if(totweight < 0)
      return i
  return 0