Dynamic Storage

Preamble note: Since OBSE (not to mention Pluggy) has added array manipulation to Oblivion script language, the implementation described in this article is only meaningful for modders that don't want to use OBSE in their mods.

Warning

This is a complicated and advanced subject. I will attempt to make it as straightforward as possible, but if you do not need the capability to store a previously undetermined number of items in a list, then consider whether you want to spend your time reading this tutorial. Programmers and experienced scripters may appreciate it merely on it's merit as clever code, but beginning scripters are likely to become confused and discouraged.

Introduction

In the Oblivion Scripting language, we have been provided with four variable types. Short, Long, Float, and Ref. There are no arrays or lists which allow us to store and easily access more than one element of a given data type. If I want to have a list of 5 numbers, I need to write code that looks like this

long number1
long number2
long number3
long number4
long number5
long sum

begin OnLoad

  set number1 to (GetAV Strength)
  set number2 to (GetAV Stealth)
  set number3 to (GetAV Health)
  set number4 to (GetAV Endurance)
  set number5 to (GetAV Agility)
  set sum to number1 + number2 + number3 + number4 + number5
  Message "The sum of your Strength, Stealth, Health, Endurance and Agility skills is %.0f", sum, 2
end

I can't imagine what you would do with this information, but that is the way it would have to be written. This is true if you plan to have three companions that follow the player around and you want to keep track of their references, or if you have a set of Actor references that surround the Player.

But wait, how do you handle that last case. Maybe I know I'm going to have 3 companions, but I can never be sure how many actors there will be surrounding the player. Sure I could make 10 referece variables and hope I have enough (forgetting of course that the code will end up being very ugly to check the references), but what if I have 15 actors around me and I REALLY needed the reference to and actor that didn't fit into my space? How do I solve that problem? That is what this article is here to address.

Linked Lists

In Computer Science, there are two major weed out concepts, Pointers, and Linked-Lists. People who have been chugging along without any trouble up until the point where these topics are brought up often times find themselves unable to understand these concepts. And as you find out after spending any time doing serious programming, they are essential basics.

Fortunately it may actually be easier to explain them in the context of Oblivion than in the context of C++. That's because there are direct examples in the Oblivion Scripting language and world that are easier to relate to.

The basic concept is this: 1) We define a new Base Object called a DSTDataNode (the DST stands for Dynamic Storage Tutorial and just helps us keep our scripts and object straight). I like to use the Null.nif or trigzone01.nif because they are invisible and there is no need to see our nodes (I'm going to call DSTDataNode objects nodes from now on to make things easier).

2) Every node is the same and has a script on it we'll call DSTDataNodeScript. That script looks like this:

  ref Child
  long Number

All this script does contain a reference to the node's child and a number to identify it. Now we're going to ignore some limitations of the scripting language right now for explaination purposes. To make my list I would write code that looks something like this (this script will not compile, but it is easier to understand the concept like this first, and then deal with reality).

ref Prev
ref Curr
ref Head
long count

begin GameMode
  if (count < 20)
    set Curr to PlaceAtMe DSTDataNode 1, 0, 0
    set Curr.Number to count
    set count to count + 1
    if (Prev != 0)
      set Prev.Child to Curr
    else
      set Head to Curr
    endif
    set Prev to Curr
  endif
end

So, if this code actually compiled, it would create a list with 20 elements, each element having a reference to the next element in the list, and since there has to be a front of the list, the first element's reference is stored in the Head reference variable. So if we write the list out starting from the head and using Node# where # is the Number stored in the node, we would see that the list looks like this: Head->Node0->Node1->Node2-> . . . ->Node18->Node19. Where -> is shorthand for "Has a reference to" so Head has a reference to Node0 who has a reference to Node1 and so on. If we wanted to print out the Number of every node in the list we would write that code like this (let's assume we have already built the list with Head as the first element):

Note that the above is just a simplified, conceptual code, as you cannot access script variables the way it is coded (set Curr.Number to count", etc). Check Linked List Tutorial for a more realistic approach.

long count
ref Curr

begin GameMode
  if (count < 20)
    if (count == 0)
      set Curr to Head
    else
      set Curr to Curr.Child
    endif
    Message "This is Node #%.0f", Curr.Number, 1
    set count to count + 1
  endif
end

The result of running that code would output

This is Node #0
This is Node #1
This is Node #2
.
.
.
This is Node #19

(where . . . means fill in all the missing lines from 3 to 18)

Compare that to the code with just five numbers and you can see how I printed 20 numbers with much less code and effort. It may have taken me 20 frames to do it, but it was far easier to do. That is the basic idea behind a linked list. You have an Object (or Node) that holds a pointer, or reference to another Object inside of it, and you create these Objects as you need them to store information. You'll notice all we stored was a number, but we can store several different things if we want to. We can also put items into the list so that they are in order or sorted.

Arrays

As a programmer, arrays are second nature to me, but since many people aren't programmers (go figure) they may not know what an Array is. For a good example of an array, think of a egg carton. It is a container than holds 12 eggs. Not only that, but I could say, give me the third egg in the second row and you would know which one I meant (Of course depending on which way the carton was facing, you might give me a different egg) So let's say we decide the row closest to the hinge (the place where the top joins with the bottom) is row 1, and the other row is row 2, then egg 2,6 would be egg furthest to the right in the row furthest from the hinge.

Arrays work basically like this. The only difference is that most languages have 0 based arrays, meaning that we would have rows 0 and 1 and the last egg in a row would be egg 5, not egg 6. Still, we would say that an egg carton is a 2x6 array of eggs.

What's the benefit of Arrays over linked lists? For one, I can tell you I want Egg(0, 4) and you can go straight to that egg without having to go to egg 0, then egg 1, then egg 2, then egg 3 and finally get to egg four. Second, sometimes it is easier to represent the world using an array because we could for instance create an array that is a 2D grid that represents the floor of a room. We could do the same with a list, but it would be more confusing.

One key thing about an Array though, is that we must know how many rows and columns there are, or we will try and read data that isn't in the array. If I ask you for Egg(2,3) you would either need to have a carton of 18 eggs, or you would look at me like I'm crazy and say "I can't give you that egg". Similarly Egg(0,7) doesn't exist. In a list, you just keep moving down the list until you find the node that matches your needs, and when you find the node with a Child == 0 then you say "I'm at the end of the list, there is no node that matches your request".

Implementation

Now that you've had your Linked List and Array primer, I'll give you two choices on what kind of list you want. There are some positives about both.

Linked List

A Linked List allows easy sorting and consistent and one at a time access. It is often easier to program around a linked-list because you know that you will always get one item back at a time, and the way Oblivion runs scripts, often times traversing an entire list still just takes one frame. Not only that, but we can make a list that acts like an array with easy index access. (Behind the scenes though, it is what we refer to as a List Traversal to get to the index you request) It is also very easy to remove items from lists. This is not so easy with an Array. Linked List Tutorial

Array

Arrays give you handy indexing so it is easy to get the item you want. In fact we can make a list that acts like an array in terms of indexing. But once you've gotten data into the array, you can change it, but erasing it is a very time consuming process (because we have to keep the indexes correct, that means everything after the affected index has to be adjusted to deal with the removed index). We can also set your array up so that it takes the exact same number of frames to get the first element as the 1000th element. There are some nice tricks we can play with arrays, but in general they are harder to understand (in Oblivion Scripting) because they rely on the idea of doing a lot of things to a lot of nodes at the same time. Array Tutorial