ID:39699
 

Dream Tutor: Green Programming

by Lummox JR

We've all seen programs that are too sluggish or use too much memory, and end up crashing under their own weight. Any language or platform is going to have certain limits, certain capacities, and it's important to understand them and prepare for them. It doesn't matter how clean or elegant your code is, if to run it the program will end up bogging down. This is no different in BYOND. If your game respects BYOND's limits, BYOND will respect your game.

List Husbandry

Lists are one of the most precious resources in DM, and unsurprisingly one of the most abused. They're great for a lot of purposes, but there are many situations where developers run into trouble. Take for instance this simple snippet, and imagine what would become of it in a large RPG with hundreds or even thousands of mobs:

mob
var/list
equipment
skills
quests
friends

New()
equipment = new
skills = new
quests = new
friends = new

BYOND has a limit of 65,535 user-defined lists, and here we've just told it that every mob--even monsters which would never use most of these lists--will have four initialized lists ready to use. This is of course a tremendous waste. If there are a dozen or so players on a server, and hundreds of monsters, only a fraction of mobs will ever use any of these lists. The trick here is to not initialize a list until it's needed. If it's null, it's just as good as if it was empty. And likewise, if you empty a list, you should delete it. Changing over code to use this approach is surprisingly simple. [Update: In newer versions of BYOND the list limit has been expanded to over 16 million, but conserving them will still save memory so it's a good idea to do anyway.]

If you check for an empty list using if(!list.len), change this to if(!list || !list.len). If you check for a list with contents like if(list.len), use if(list && list.len) instead. Because in theory there will be no more empty lists, you could use if(!list) and if(list) to do the same thing, but using the longer form is safer--just in case something slips through.

When adding to a list, instead of adding directly you must first check to see if the list has to be initialized:

if(!skills) skills = new
skills += "poetry"

And if you remove anything from the list, be sure to check the length when you're finished.

if(skills)
skills -= "panic"
if(!skills.len) skills = null

There are other ways to check if removing an item results in an empty list, but notice how clean this approach is. If the skills list exists at all, we'll try to remove a skill. If the skills list is empty, it can be removed. In this code, it doesn't even matter if "panic" was in the list. If it was accidentally already empty, it will still be deleted.

Finding items in a list shouldn't be any harder than before. You can use if("hiking" in skills) just like before. If you were using if(skills.Find("hiking")), then you were already doing something wrong--if the list had been null you'd have a runtime error. The only reason you need Find() is if you need to know the exact index something has in a list, which isn't that often.

With associative lists another approach might be preferred:

if(equipment && equipment["shield"])

On the off chance the actual shield was deleted, you'd still get a null value from equipment["shield"], so everything would work fine.

With all of the above changes, you no longer need to initialize your lists in New(), so now more monsters can run around without straining BYOND's resources with things they'll never use.

Purging Cleanly

It's pretty common for things to get deleted. BYOND is nice enough that when you delete the object, if somewhere a var has been set to that object, it will become null. If you've never used a language like C you have no idea what a relief that is, but it comes at a high cost: BYOND actually has to find all those vars and reset them.

BYOND avoids this much of the time using a technique called reference counting, which is how it usually knows when to delete things without being asked. Basically, a reference is anything that knows the object exists. There are several kinds of references:

  • Almost any var set to the object (exceptions are rare, including loc)
  • Any list containing this object, as an item or an associated value
  • The location of this object (if it is an atom), but not any objects it contains
  • The object itself, if it's a turf
  • Any procs running, sleeping, or spawned and waiting to run with this object as src
  • Ditto for verbs/procs where this object is usr or any other argument

Once all the references are gone, the item can be discarded safely, because nothing is going to use it anymore. So this means that if you have a useless trinket and set its loc to null, it'll be deleted on its own. And this is the easiest way to delete something, because it means you don't have to use del(trinket) and send the garbage collector looking for other references.

Did you notice the skills=null line above? Using that instead of del(skills) wasn't an accident. Once the skills var is set to null, there are no references left to that list whatsoever. The garbage collector will immediately recycle it. Had there been anything actually left in the list at that point, they would have each lost a reference, because the list was one of the things keeping track of them. If that was their last reference, then they too would be deleted. Because of this "cascade" effect, a lot of things might end up being deleted very cleanly. In the same way, had the mob been deleted, its skills list would have been deleted along with it, because nothing needed that list anymore.

Of course this doesn't work for everything. If two items reference each other, or if one references another which references another and so on in a circle, then BYOND will never get rid of them. The only way around that is to forcibly delete one of them, or to clear all its references.

The loc var doesn't count as a reference. An item's contents don't contribute toward keeping it in play; instead they depend on it. That way if the container runs out of references, everything in it can be deleted when it is. Consider a player with a weapon. If mob.weapon is set, then that weapon has at least two references: the mob because it's the weapon's loc, and the weapon var. But the mob doesn't have any extra references from the weapon itself. If the mob is moved to null, no client controls it, and it's basically now ignored by the game, then it will be deleted. When the mob is deleted, the weapon will be too (unless something else was paying attention to it), because the weapon depended on the mob which no longer exists.

The Proverbial Tree

If a mob wanders around in a forest, and no player's around to see it, does it really wander around? You bet it does, and it wastes a whole lot of processing power if hundreds of mobs do the same. In a game it just doesn't pay to have a lot of background actions going on that won't be seen by anyone. It's usually enough, once no players are going to be walking through an area anymore, to pause the area's monsters and possibly even move them to their "home" positions.

What you need for these situations is some sort of area manager that can control the mobs inside. In this case, let's say the area is very smart and knows exactly which areas neighbor it, so it will "wake up" when a player enters a neighboring area and "sleep" when a player is nowhere nearby.

area
var/list/neighbors
var/awake

Entered(mob/M)
// M might actually be an obj here; always check
if(ismob(M) && M.client)
for(var/area/A in neighbors)
if(!A.awake) A.Wake()

Exited(mob/M)
if(ismob(M) && M.client)
for(var/area/A in neighbors)
if(A.awake) A.SleepCheck()

proc/Wake()
if(!awake)
// anything standing on this area's turfs is also in src.contents
for(var/mob/M in src)
if(!M.awake && M.useAI) M.Wake()

proc/SleepCheck()
for(var/client/C)
if(C.mob in src) return // found a player mob here
var/area/A = mob
while(A.loc) A = A.loc
if(A == src || (A in neighbors)) return
// no players in this area or any neighbor areas
awake = 0
for(var/mob/M in src)
if(M.awake && M.useAI) M.SleepCheck()

This will automatically "wake up" creatures as you move into a neighboring area, which gets them ready for when you arrive there. This will work best with smallish areas. It's also important to remember to manually call area.Entered(player) if you teleport a player directly, since this is only called by player.Move() normally. Now that's not going to do much without the corresponding mob procs, so let's take a look at those too.

mob
var/useAI // set for any non-player that uses AI
var/awake

proc/Wake()
if(!awake)
awake = 1
AI()

proc/SleepCheck()
if(!awake) return
var/area/A = src
while(A.loc) A = A.loc
if(istype(A) && A.awake) return
awake = null

proc/AI()
while(awake)
dir = 1 << rand(0,3) // pick a random direction
var/turf/T = get_step(src, dir)
var/turf/A = T ? (T.loc) : null
// don't walk into a sleeping area
if(A && loc && A.awake)
step(src, dir)
sleep(rand(3,6))

Now the mobs have a basic AI() proc that they can override. It keeps looping as long as the mob stays awake. Here the mob is instructed only to stay in active areas, so it won't wander off onto unused portions of the map.

The only setup work you need for a system like this is to set up the neighbors of each area in advance. Of course, if you don't want to do this, one simple way to set up the neighbors is to do it as the players move around.

area
Entered(mob/M, area/oldloc)
// M might actually be an obj here; always check
if(ismob(M) && M.client)
if(!awake)
while(oldloc.loc) oldloc = oldloc.loc
if(oldloc)
if(!neighbors) neighbors = new
neighbors += oldloc
Wake()
for(var/area/A in neighbors)
if(!A.awake) A.Wake()

Too Many Items

Objects are limited in BYOND, yet many RPGs don't take this into account. If you buy a healing potion or a magic potion, it gets thrown into your inventory just like all the others. When it's time to use something else, finding it in a stat panel among all those potions will be difficult. Saving and loading a character with all those potions will take a long time, too. The solution to this is to use a simple grouping or stacking system. By combining like items and counting how many you have, you no longer have to keep dozens of separate objs.

To set this up we'll need a few things. First, every obj needs a var to tell how many there are, and whether it's groupable. The same var can do both jobs; if it's 0, it means this object can never be grouped. Then all you need are some utility procs to manage the items.

// built-in vars that shouldn't be considered when comparing objects
var/list/builtin=list(\
"count","vars",\
"overlays","underlays","contents","verbs",\
"name","suffix",\
"x","y","z","loc","pixel_x","pixel_y",\
null)

obj
var/count = 0 // 0 means not groupable; 1+ is groupable

proc/Update()
if(count)
// change suffix
suffix = (count>1) ? "[count]x" : null
// consider changing name to a plural here too

// tell if two items are alike
proc/IsAlike(obj/O)
if(!O || type != O.type || !count || !O.count || \
contents.len || O.contents.len) return 0
for(var/V in vars)
if(vars[V] != O.vars[V])
if(V in builtin) continue
return 0
return 1

// return the new obj in case it combines with another one
proc/MoveTo(atom/container)
if(count)
for(var/obj/O in container)
if(O != src && O.IsAlike(src))
O.count += count
O.Update()
loc = null // let this auto-delete
return O
loc = container
return src

// split off an obj and return the new one
proc/Split(n)
if(!count || n >= count || contents.len) return src
if(n <= 0) return null
count -= n
Update()
var/obj/O = new type(loc)
for(var/V in vars)
if(vars[V] != initial(vars[V]))
if(V in builtin) continue
// copy non-tmp lists
if(issaved(V) && istype(vars[V], /list))
var/list/L = vars[V]
O.vars[V] = L.Copy()
else O.vars[V] = vars[V]
O.count = n
O.Update()
return O

With this system in place, all you need are a few custom verbs for manipulating multiple items. For example, you might want a player to be able to drop just a few of their items.

obj/item
verb/Drop(n = (count || null) as null|num)
set src in usr
if(!n || n <= 0) n = 1
else n = round(n, 1) // don't allow sneaky decimals
if(!count)
loc = usr.loc
usr << "You drop [src]."
return
if(n >= count)
MoveTo(usr.loc)
usr << "You drop [count] [src]."
return
var/obj/O = Split(n)
O.MoveTo(usr.loc)
usr << "You drop [n] [src]."

Well, that wasn't so terrible. If you want to pluralize words, then you'll probably want to use [Pluralize(n)] (or count instead of n) instead of just [src] in a few places; we'll get to that proc shortly. But for now, what happens if you want to use one of those many items you've grouped together? Well, that's pretty easy actually.

obj/item/potion
count = 1 // groupable item

proc/Effect(mob/affected, form)
// form=null or 0 for drinking
// form=1 might be when splashed, or 2 as vapor...

verb/Drink()
set src in usr
usr << "You drink \a [src]."
Effect(usr)
if(--count <= 0) del(src)
Update()

For situations where you want a good plural word, you need to set up just a few vars: base_name, and if necessary, base_plural. You need base_plural only for words that don't fit the usual rules, like "deer" or "mice". For most words, TextPlural() will pluralize a word nicely.

proc/TextPlural(base_name, base_plural)
. = base_plural
if(!.)
. = base_name
var/l = length(.)
if(l < 2) return . + "'s"
var/ch = text2ascii(., l) & 223
switch(ch)
if(83) // S
return . + "es"
if(72) // H
ch = text2ascii(., l-1) & 223
// CH, SH
if(ch==67 || ch==83) return . + "es"
if(89) // Y
ch = text2ascii(., l-1) & 223
if(ch==65 || ch==69 || ch==73 || ch==79 || ch==85) return . + "s"
return copytext(., 1, l) + "ies"
if(90) // Z
ch = text2ascii(., l-1) & 223
if(ch==65 || ch==69 || ch==73 || ch==79 || ch==85) return . + "zes"
return . + "es"
. += "s"

obj
var/base_name
var/base_plural

proc/Pluralize(n = count)
return (count && n != 1) ? TextPlural(base_name, base_plural) : base_name

proc/Update()
if(count)
// change suffix
suffix = (count>1) ? "[count]x" : null
// change name
name = Pluralize()

And that's about all there is to making items groupable. It's a lot easier than it sounds. The trick is remembering to use the utility procs Split(), MoveTo(), and Update() as needed.

And So On

As you've seen, there are a variety of techniques for reducing the load on BYOND. Some of these even have extra benefits in presentation, like the item grouping system. The key is to remember that BYOND's resources aren't infinite, and conserving them where possible makes sense. Sometimes it's a matter of using fewer lists or combining multiple lists into just one. Other times you may need to save a few objs. And sometimes it's just a matter of saving time, and not running a zillion procs at once when you could run maybe just 25% of them. If you're planning a big game, you need to be prepared to handle big numbers of things. These are just a few of the techniques that can make all the difference between a crashy laggy experience and an awesome epic.

So essentially this article can be summed up as:

1. Don't abuse lists. If they're not needed, don't create them, and when they're done being used, set them to null again.

2. Don't have things happening when no one is there to appreciate them.

3. Don't create a hundred individual objects when you can have one object with a variable saying that there are a hundred of it.
Also:

4. Whenever possible, let the garbage collector delete stuff naturally by letting the references run out instead of using del(object).
Good stuff.

Another space saver could be using a library like SwapMaps.
ah,this is my alltime favorite BScape articles
I was unaware of this article :O

I like it a lot! :D
Lummox - How did you learn to code so good? Havent u made a game yet?

O>O

Hmmm... I was directed here, it's interesting, but sadly, I need to use them 1000 mobs running around like insane idiots killing each other.
Ganing, how you apply these principles depends on your project. If you do need 1000 active mobs in one place, you can take simple steps to be sure they don't slow things down too much. If they're bent on killing each other, you can have them try to lock on to a target within a short range instead of looking at the whole area, and then maybe do the whole area as a fallback. You could also have AI only active part of the time, and the rest of the time have it in a "dumb" mode where it just moves toward a target till it's interrupted.

Basically any operation you have that has O(n**2) complexity (like looping through each mob, and then having each one loop through all other mobs to find a target) is going to be very bad at n=1000 compared to n=10. If it's as frenzied as you say, you can really dumb down the AI quite a lot when n is high and no one will be able to tell the difference; gradually you could transition to smarter units as their numbers thin out. O(n**2) algorithms are sometimes impossible to avoid, though most often they're just the easiest way to do things. So choosing a relatively dumb algorithm when n is a high number can reduce your complexity as far as O(n).
Wow, takes a master to show me how inferior I am to programming. I got pretty lost in all that. But from what I think you said is have it so that they don't look in wide ranges, where there will be many mobs visible. Am I correct? I've thought about lowering the range for awhile, but it's already at three, I figured I would try to find a way to make it look for certain NPCs by using list. Such as


var/list/L = list()
L = [var/mob/NPCs/Shu_Soldier,var/mob/NPCs/Shu_Soldier]
for(L in view(3, src))

Not sure if that's correct way of doing it or not. But yea, something based off that.
Perhaps you should just take what he said apart until you understand it. :)