Using Binary Trees And Linked Lists To Represent Group Hierarchy

Disclaimer

Note: This page represents an idea for a proposed way of coding some particular functionality/behavior in UnrealScript. It does not represent the way that UT/UT2003/UT2004 actually do things in the normal game engine.

Introduction

I was thinking of way to construct classes that could behave with other classes in a group fasion. I came across the idea of using the C++ ideas of binary trees and linked lists to get the job done. It may be put to good use in forming a hierarchy among classes. It allows us to form "groups" of classes with parents,children, heads, and tails, which can later be used to construct "group" behaviour. Now, linked lists and binary trees can be used, but I feel it depends on the complexity of ones groups. For those of you who don't know of linked lists or binary trees, below is an overview of the linked list and the binary tree idea.

Linked Lists

A linked list is basically a list of chunks of data linked together. Each "chunk" of data is known as a node. Each node contains some data and some form of "linking" itself to another node. In C++, usually each node has some data, and a pointer to another node. This form is knows as a singly-linked list. Some linked lists have nodes with pointers to the the next node, and the previous node in the list. These types of lists are known as doubly-linked lists. Each list has a head, and a tail. The head being the first node in the list, and the tail being the last node in the lists. Linked lists are an effective way of storing complex datatypes in an array-like structure.

Generally, a linked list is used when an array-type structure is needed but the final size of the array is not known, or, elements within the array are often moved, added, and removed. Linked lists are generally un-ordered although elements can be efficiently sorted into position as they are added to the list.

Binary Trees

Binary trees are ways of storing data in hierarchial structure composed of nodes (elements of the structure that have children) and leaves (elements of the structure that have no children). A binary tree has a parent node, and two child nodes.

Large trees can be constructed by having contain more node elements than leaf elements – imagine having several layers of nodes with child nodes. This provides a good foundation for searching and finding positional status (if the nodes and leaves are ordered).

Unreal Examples

The Linked List Example

Say I wanted to create a group of skaarj that had a hierarchy with a leader and a general. I would need two classes, List, and ListNode. List could contain a ListNode head, a ListNode tail, and a name listName. ListNode could contain an instance of a scripted pawn called _skaarj, lowerSkaarj, and higherSkaarj.

class List extends ScriptedPawn;

//global variables

var() ListNode head;
var() ListNode tail;
var() string   listName;

The head could be the leader of the pack, and the tail could be the last person in the pack, it is irrelevant, but for this example, that will be true.

class ListNode extends List;

//global variables

var() Skaarj _skaarj;  //the data
var() Skaarj lowerSkaarj; //the previous monster
var() Skaarj higherSkaarj; //the next monster

This node forms a doubly linked list. We will have to modify the skaarj class a little to include a list if in a group. So lets do that:

class Skaarj extends ScriptedPawn;

//added variable
var() List group;

Now we could form a hierarchy by creating a List of Skaarj. Say I created a map and in it I have six skaarj: Larry, George, Matt, Jack, Tarquin, and Mychaeel. All six skaarj have a group since we just added it above. I will now create a list.

class SkaarjGroup extends List;

listName = "SkaarjGroup1"; 

Now that the list is created we can add the six skaarj to it.

var ListNode LN_Larry;
var ListNode LN_George;
var ListNode LN_Jack;
var ListNode LN_Tarquin;
var ListNode LN_Mychaeel;
var ListNode LN_Matt;

Larry.group = SkaarjGroup;
George.group = SkaarjGroup;
Jack.group = SkaarjGroup;
Tarquin.group = SkaarjGroup;
Mychaeel.group = SkaarjGroup;
Matt.group = SkaarjGroup;

LN_Larry._skaarj = Larry;
LN_George._skaarj= George;
LN_Jack._skaarj = Jack;
LN_Tarquin._skaarj = Tarquin;
LN_Mychaeel._skaarj = Mychaeel;
LN_Matt._skaarj = Matt;

SkaarjGroup.head = LN_Larry;
SkaarjGroup.tail = LN_Matt;

LN_Larry.lowerSkaarj = LN_George;
LN_Larry.higherSkaarj = NULL;

LN_George.higherSkaarj = LN_Larry;
LN_George.lowerSkaarj = LN_Jack;

LN_Jack.higherSkaarj = LN_George;
LN_Jack.lowerSkaarj = LN_Tarquin;

LN_Tarquin.higherSkaarj = LN_Jack;
LN_Tarquin.lowerSkaarj = LN_Mychaeel;

LN_Mychaeel.higherSkaarj = LN_Tarquin;
LN_Mychaeel.lowerSkaarj = LN_Matt;

LN_Matt.higherSkaarj = LN_Mychaeel;
LN_Matt.lowerSkaarj = NULL;

Fairly pseudo assuming all this would be done in the map editor by the mapper, but that is what would be happening in code.

As you can see this sets up a hierarchy with Larry at the top, Matt at the bottom, and George, Jack, Tarquin, and Mychaeel down the list. With this you can setup different responsibilities and behaviour:

if(self = SkaarjGroup.head) {

//do stuff

}

The Binary Tree Example

Using the same group in the Linked List example, lets set it up using a binary tree structure. Lets first start out by creating a BinaryTree class:

class BinaryTree extends ScriptedPawn;

var(Tree) Skaarj parent;    // the parent
var(Tree) Skaarj childOne;  // the first child
var(Tree) Skaarj childTwo;  // the second child


}

Each instance of Binary tree will have parent skaarj, a 1st child skaarj, and a 2nd child skaarj.

Now, as if we were in the editor again, and had the six skaarj, we could set this up as so:

var BinaryTree Piece1;
var BinaryTree Piece2;
var BinaryTree Piece3;

Piece1.parent = Larry;
Piece1.childOne = George;
Piece1.childTwo = Jack;

Piece2.parent = Jack;
Piece2.childOne = Tarquin;
Piece2.childTwo = Mychaeel;

Piece3.parent = Mychaeel;
Piece3.childOne = Matt;
Piece3.childTwo = NULL;

Of course there are ways to get around the Piece idea, it's just much eaisier to understand when it's set up like this. We create 3 binary trees and construct a hierarchy from it.

Conclusion

Try it. It will only further your experiece.

C0ry

Questions?

email me.

fusion815@cox.net

Some thoughts

I didn't want to break your lovely example above with some unweildy hackings and slashings so I thought I'd comment here.

As far as I can tell you are attempting to construct a structre that will allow groups of objects (in this case enemies) to be handled with some sort of priority (superiority) order. Also, that the numbers of objects within these groups can change, or are not known. What is shown below is merely a suggested class definition. The benefit of abstracting the data elements from the actual list element (ListElement) class is that the code can then be re-used every other time you need similar functionality.

// I don't know if you can actually subclass from object - but this class needs to be as light as you can make it.
class ListElement extends Object;

var ListElement parent; // A pointer to the parent element of this object -- null if there isn't one.
var ListElement child; // A pointer to the _first_ child element of this object -- null if there isn't one.
var ListElement next; // A pointer to the next sibling element of this object -- null if there isn't one.
var ListElement prev; // A pointer to the previous element of this object -- null if there isn't one.

var Object data; // A pointer to the object containing the data to be held in the list -- null if there is no data.

// Functions to add, remove, and search for elements go here (see below for more info).

Probably the most vital functions needed within this class are the AddChild() and AddSibling(). These functions must set the parent attribute of the object correctly at the point it is inserted into the list. Personally, I'd have functions to handle just about every operation you can think of on the class simply because it allows the pointer manipulation to be hidden and held all in one place. It also means you can change the way in which the data is stored should you need to.

One thing I would note though. If you know you are going to have very few elements in a list (say less than 10) then consider using an array and handling the null pointers (assuming sparse population). It will be quicker – particularly if the data needs to be replicated to the client.

I think that's all from me.

---

Foogod: I added the disclaimer at the top, because the way these pages are linked from Artificial Intelligence could confuse some people into thinking this is an explanation of the way that the UT-based games actually do things.