Transcript Binary Search Trees in UT

Sega 500
More Data Structures
Binary Search Trees
Jeff “Ezeikeil” Giles
[email protected]
http://gamestudies.cdis.org/~jgiles
OK,

We’ve looked at how to build a linked list
in UT and used it for you observer…Works
pretty good too.
Today

We’re going to expand on this concept by
building a (hopefully) useful and more
efficient data structure.

The Binary Search Tree…
But First…


Why are we talking about this kind of
thing? This is a mod class.
Aren’t there storage containers built in?
Well, sorta…
What UT has already…

Currently, there are 2 methods to store
“generic” list-type data in UT.



There is a ListItem class
And there are Dynamic Arrays.
Both of these have their place, but may
not be exactly what we want.
What UT has already…

We’ll give them a quick look in a second.

The second reason for this lesson is that,
as you already well know, UT does things
differently.

Trying to build efficient data structures in a
pointerless environment is different.
What UT has already…

Not to mention that it is quite conceivable
that you may need to store and access a
large number of objects in your mod in a
timely manner.
UT’s List Item

This is the basic doubly linked list.

It is derived off of the Object class which
implies that it could be rather useful and
fairly generic.
UT’s List Item

And it comes with all sorts of useful
functions:






AddElement
AddSortedElement
FindItem
DeleteElement
MoveElementUp
MoveElementDown
UT’s List Item

Really nice to have all these built in sort
and find functions.

However, if you do a find all for these in
files, you’ll be hard pressed to find them
anywhere but in the GUI class.
UT’s List Item

Here’s why…
var String
var String
var bool

Tag;
// sorted element
Data;
// saved data
bJustMoved; // if the map was just
// moved, keep it selected
It’s only useful for storing strings…
UT’s List Item

Now if it weren’t for that…it’d be almost
useful…

However, this class is still a great
reference on how to build a list structure in
UT.
Give it a boo…
UT’s Dynamic Array’s

The Dynamic arrays are a bit more useful
and fully supported buy UT2003.

However, their functionality is a bit limited
and very linear.
Here’s what they have to offer:
UT’s Dynamic Array’s

The type can be any of the built-in or selfdefined types (structs, enums, classes)
and declaration is:
var array<Material> Skins;
Array keyword
Type
Name
UT’s Dynamic Array’s

To access elements of the array, just use
the [ ] operators.

The array also comes with some built in
functionality.
UT’s Dynamic Array’s

Length


Returns the number of elements in the array. (Similar
to ArrayCount(ArrayName) for static arrays.) You can
change this property to add or remove elements from
the array. Only use the = operator for doing this, any
other (like e.g. +=) will not work and might even crash
the game.
Increasing the length adds empty elements at the end
of the array while preserving the existing elements.
Decreasing the length removes only the last elements
without changing the other ones.
UT’s Dynamic Array’s

Remove(position, number)

Removes number elements from the array,
starting at position. All elements before
position and from position+number on are not
changed, but the element indices change, i.e.
the element formerly accessed through
ArrayName[position+number] is accessed
through ArrayName[position] after the
removing.
UT’s Dynamic Array’s

Insert(position, number)

Inserts number elements into the array at
position. The indices of the following elements
are increased by number in order to make
room for the new elements.
UT’s Dynamic Array’s

Thus it’s basic functionality more closely
resembles the basic functionality of the
STL Vector class in C++.
UT’s Dynamic Array’s


If you write to an array element that
doesn't exist (yet) because the array is too
short, the array will automatically increase
its length.
All new elements inserted between the
former end of the array and the element
you are writing to are initialized with their
respective null element
UT’s Dynamic Array’s

If you read an array element that doesn't
exist because it's beyond the array's
length, you'll get a null value.
UT’s Dynamic Array’s

Now, everyone here is a fairly smart
cookie, so I don’t think I need to
demonstrate the usage of these
things…It’s pretty straight forward…

But I do have couple of words of caution
on using these…
UT’s Dynamic Array’s

The big one:
Dynamic arrays can't be replicated!

So you’ll have to find a way around that
problem if you use them.
UT’s Dynamic Array’s

Next, you can use the config keyword with
them no problem at all.

However, if you do, just remember that
EVERY element in the array will be saved
to file and reloaded with each execution of
your program.
UT’s Dynamic Array’s

Hence, if you not judicious in your use of
Insert and Remove operations, you can
end up with a REALLY big ini file REALLY
easily.
Big ‘O’

Now for a dive back into the past…Big O
notation.

Which, as you recall is simply a method to
approximate the complexity / efficiency of
a computer algorithm, where only the most
rapidly increasing factor is shown.
Big ‘O’

This is where we see why a Binary Search
Tree (BST) is so cool for us right now…
Big ‘O’

If we look at either of the above methods,
the most efficient search we can possible
get is a linear search of order O(n).

E.g. we have to visit each element in
order. One after another, until we find the
one we are looking for.
Big ‘O’

As where a BST is usually much more
efficient. Particularly on large sets of data
where the efficiency is O(log2n).
Exponentially faster.

The worst case search for BST is of O(n)
(linear).
Why is are they so much faster?

In a nutshell, it boils down to sorting the
data and removing sets of it from the
search set with each test.
What’s going on?

I’m guessing that you’ve already seen
these in the data structures class, so I’m
not going to talk in detail about these.

Just a review.
What’s going on?


At their core, they are actually pretty
simple.
They are constructed from a node similar
to this
Data
Link
Lesser
Link
Greater
What’s going on?

The nodes are set up similarly to a doubly
linked list. They just point to different
things.

When the data is compared to this node, if
it is greater it is linked to the right,
otherwise the left.
What’s going on?

The effect this has on the data set is that
when we go back to get the data we’ve
stored, with each comparison, we are
effectively removing sets of data from the
search.

For example, if we have an efficient tree
with 200 unique elements in it, we can find
any one element in 8 steps.
What’s going on?

Doing the math, removing ½ at each
step:
1)
2)
3)
4)
5)
6)
7)
8)
200
100
50
25
12
6
3
1
For 200 elements, that’s 25 times
faster than a linear search
BST’s in UT

Now, isn’t that sweet?

So how do we go about building one?
BST’s in UT

The first thing that we have to realize is
that we are somewhat limited to what we
can do in UT.


It’s pointerless.
And it will work on either an object or one
specific default data type. Like we saw in the
ListItem class.
BST’s in UT



Unfortunately, as we discovered with the
observer, there are no truly “generic” data
types in unreal.
The best we get is an object, so this is
what well be working with.
Once again…my kingdom for a void
pointer or a typedef!
BST’s in UT

So getting down to it, here’s what’s
needed.


A Node Class
The BST class
BST’s in UT

The Node class is really simple, it’s just
our data structure.
class BSNode extends Object;
var string Key;
var object data;
var BSnode Greater, LesserEqual;
DefaultProperties
{}
BST’s in UT

var string Key


var object data;


Is simply our key to this specific node.
A handle to the data.
var BSnode Greater, LesserEqual;

Links to the other nodes.
BST’s in UT

Next step is to start the declaration of our
BSTree class
class BSTree extends Actor;
var private BSNode head;
var name dataType;
var int numelements;

Notice that the
head node is
private.
BST’s in UT

And now because I want this class to be
specific to ONE data type I initialize it like
so:
function InitTree( name type )
{
if(dataType=='')
{
dataType=type;
}
else
log("InitTree failed...already initialized");
}
BST’s in UT

I’m planning on using ‘name dataType’ to
screen out undesired types with this isa
operator…
BST’s in UT

Now this is where things start getting
hairy, adding nodes.

This is not a push stack, we are always
appending nodes to the end of the list, it’s
just a question of which branch.
BST’s in UT

Also, we need some method of retrieving
the data…a key if you will.

We’ll talk about how the key works in a
second, first that we need one and they
each one has to be unique.

For every object, one and only one key.
BST’s in UT

Thus we take this into consideration with
the add method. If one is provided, great.

Otherwise we generate one and return it.
It’s to users responsibility to keep track of
the key!
Just like a lock, the key opens it, the lock
provides no storage.

Adding data to BST’s
function string AddData(object obj, optional string key)
{
local BSNode stuff;
if(obj.isa(dataType))//includes children
{
stuff= new(none) Class'BSNode';

The newness here is how we are creating
our object.
new(none) Class'BSNode';
Adding data to BST’s




So why aren’t we spawning it?
Simple, it’s not an actor.
New(none) is an alternative method to creating
objects for UT.
The New keyword is used to create new objects
which are:


not a subclass of Actor and
not created within the context of an Unreal level
Adding data to BST’s

A word of warning on using the new
keyword in UT:


Creating actors with the New keyword causes
the game or UCC commanlets to crash.
Be careful when using the new keyword to
create objects as well as maintaining
references between Objects and Actors, as it
is very easy to cause crashes during
serialization if not used properly.
Adding data to BST’s

When dealing with Objects you must be
absolutely sure to clean up any references
between Actors and Objects, generally by
explicitly setting those references to None
where appropriate.
Adding data to BST’s

There is more functionality to be had on
using new, for now, this will suffice.

However, for more information, consult the
wiki:
http://wiki.beyondunreal.com/wiki/Creating_Actors_And_Objects
Adding data to BST’s

The rest of the function simply sets the
BSnode’s key to the one provided (or
generates one).

Once a key is selected, it’s added to the
tree with the AddTailNode method.
Adding data to BST’s
stuff.data=obj;
if(key!="")
stuff.key= key;
else
stuff.key=""$RandRange(1,99999);
AddTailNode(stuff);
return stuff.key;
}
else
log("InitTree---> invalid type");
return "";
Adding data to BST’s

Now for the AddTailNode method, another
dose of weirdness.
private function AddTailNode(BSNode node)

Yes, functions can be private.
Adding data to BST’s

The 1st thing was to determine if this is the
1st element in the tree.
local BSNode idx;
log("AddTailNode-->"@node.key);
if(head == none)
head=node;

No Biggie here…
Adding data to BST’s



Then we have a large else condition…
It’s inside this that we determine which
branch of the tree to follow.
So the tree will follow something like this:
Added
Head
Adding data to BST’s
idx=head
while( idx!=None )
{
if(idx.Key<node.key)
{
if(idx.Greater==none)
{
idx.Greater=node;
break; //end of tree
}
else
idx=idx.Greater;
}
Adding data to BST’s
else
{
if(idx.LesserEqual==none)
{
idx.LesserEqual=node;
break; //end of tree
}
else
idx=idx.LesserEqual;
}
//end the while loop
numelements++;
Adding data to BST’s

This function simply navigates from node
to node until it reaches the end of a
branch and then appends itself to it.
Adding data to BST’s

Ok, we’re going to backup to the AddData
for a second before we talk about how to
retrieve data.

Notice that the key parameter is in fact a
string.
String Operations

That’s right, we can do conditional
operations on strings
idx.Key<node.key

Yeah, it’s as handy as it sounds. Have a
look in the object class to checkout all
that we have available.
String Operations

This is just the conditionals, there’s a
whole bunch more to play with.
native(115) static final operator(24) bool
native(116) static final operator(24) bool
native(120) static final operator(24) bool
native(121) static final operator(24) bool
native(122) static final operator(24) bool
native(123) static final operator(26) bool
native(124) static final operator(24) bool
< ( string A, string B );
> ( string A, string B );
<= ( string A, string B );
>= ( string A, string B );
== ( string A, string B );
!= ( string A, string B );
~= ( string A, string B );
String Operations

This makes the key mechanism supremely
easy.

We’ll look at exactly how we use our keys
in a bit.

First, have a boo at how we are retrieving
data.
String Operations

But first, realize what we are doing here.
We are looking for a node that has a
matching key. We are not making any
comparison to the data.

Also, the mechanism to find this is
remarkably similar to The Addtailnode
method…
Getting data from BST’s

It’s here that we get the real pay off…
function object GetData(string searchKey)
{
local BSNode idx;
 Set a handle
local int count;
idx=head;
to the
head node and a key to
look for…
Getting data from BST’s
while( idx.Key != searchKey && idx != none)
{
if(idx.Key<searchKey)
idx=idx.Greater;
Where magic happens
else
idx=idx.LesserEqual;
count++;
if(idx==none)
log("FAILED--->NONE");
}
return idx.data; //return the data
Note: I’ve removed the logs
in the sample code
Getting data from BST’s

Because this method requires a key to
search for, it’s vitally important that the key
not be lost.

Other wise you loose all the benefits of the
BST in finding your data…
Removing data from BST’s

So the next natural question, is how to
remove data from the BST.

Well, the find part if this popNode method
is the same as the Get method. We’ve just
added some logic to relink the nodes.
Removing data from BST’s

But one thing to remember, because our
nodes are objects and not actors, we can’t
destroy them.

If you recall we have to remove all
referenced to the object so that garbage
collection will catch it.
Removing data from BST’s



So, because the find component is the
same, there’s no real need to talk too
much about it.
However, there is one difference.
We need to keep track of the last node we
visited so we can redirect the handles.
Removing data from BST’s
while( bsHandle.Key != searchKey && bsHandle != none)
{
lastVisited=bsHandle; //lag one behind

Nothing too fancy…
Removing data from BST’s

But once we find the node we’re looking
for, we bail out of the loop and
1) Redirect the nodes
//relink nodes
lastVisited.greater=bsHandle.Greater;
lastVisited.LesserEqual=bsHandle.LesserEqual;
toReturn=bsHandle.data;
Removing data from BST’s
2) Set all it’s references to none.
//bsHandle is severed from the tree so garbage
//collection will catch it.
bsHandle.Greater=none;
bsHandle.LesserEqual=none;
bsHandle=none;
Removing data from BST’s

And now to ensure proper cleanup, there
is one last thing to consider…

Removing all references to the head node.
Removing data from BST’s
event Destroyed()
{
head = NONE;
Super.Destroyed();
}

The tree itself is an actor so we can safely
call and override the destroy.
Using the BST’s

Right, now that we’ve got this wonderful
toy built, how do we use it?

Well, I’m just after a simple piece of test
data here. I just created a simple
gametype that just adds all the pawns to
the tree at the start of the game.
Using the BST’s

Now, this isn’t a particularly large data
set…max of 16…but it’s enough to show
that there are some significant speed
benefits from using a BST.

At the start match call, I just iterate over all
the pawns and stuff them into the BST.
Using the BST’s

Now, pawns come with some benefits
here. Especially because we are using
strings as our key into the BST.

Pawns have names… Names are strings.
Hmmmm!
Using the BST’s

This provides a really easy way for me to
track and retrieve pawns from the BST.

And yeah, I’m not considering the case of
duplicate names in this example. If a
name is duplicated the 1st one found will
be returned.
Using the BST’s


That being said…
My new gametype has an instance of a
BST.
var BSTree dataTree;
Using the BST’s

In the start match method, we create and
populated it:
function StartMatch()
{
local controller C;
local BSNode BS;
local string AA,BB;
local int ctr;
AA="alpha"; //test values
BB="Mike";
super.StartMatch();
dataTree = spawn(class'BSTree');
dataTree.InitTree( Level.ControllerList.pawn.Name);
Using the BST’s
//populate the BStree
for( C=Level.ControllerList;C!=None;C=C.NextController )
{
ctr++;
AA=dataTree.AddData(c.Pawn,
c.Pawn.PlayerReplicationInfo.PlayerName);
if(ctr==6)
BB=AA; //for pop node test
log("controller key--->"$AA);
}
dataTree.AddData(self);//add invalid data test
Using the BST’s
log("--->BREAK<-------");
//end node pop test
log("TEST 1 BEGIN");
log("getdata--->"$dataTree.getdata(AA));
log("getdata--->"$dataTree.PopNode(AA));
log("getdata--->"$dataTree.getdata(AA));
log("TEST 1 DONE ");
//mid node pop test
log("TEST 2 BEGIN");
log("getdata--->"$dataTree.getdata(BB));
log("getdata--->"$dataTree.PopNode(BB));
log("getdata--->"$dataTree.getdata(BB));
log("TEST 2 DONE ");
Using the BST’s

Now, give it a run and see what the log
says…

I know…sorry not very graphically exciting
today…
Using the BST’s

So when we run the
game and populate
the map with 12
bots…

Everything registers
fine.
Using the BST’s


The different data
types are not allowed
to be added to the
list.
Here I attempted to
add my gametype
//add invalid data test
dataTree.AddData(self);
Using the BST’s

And now retrieve data
sets one from the end
of the branches.

Notice that we iterate over 13 pieces of data and
find our target in 4 steps. (The end “none” node is
counted)
Using the BST’s


These logs are
expected. Generated
inside the tree…
Also out data is successfully popped from the list.
Using the BST’s

Test 2 checks against
data in the middle of
the list.

It’s found in 3 steps
also…

And performs as expected for the other logs
Using the BST’s

But do notice that,
once the data is
popped, the next
search takes 6 steps
to reach the end of a
branch.

Indicating a successful pop midway.
Et Voila!

There you have it, A BST data structure in
unreal script.

I hope you can see some of the possible
benefits from using this kind of thing.
Especially for large data sets…