Difference between revisions of "Linked list"

Latest revision as of 14:49, 27 July 2009

A linked list is a data structure consisting of a sequence of values, where each element in the list not only holds the data, but also a reference to the next element in the list.

A linked list containing integer values.

See linked list for a more general introduction to linked lists.

Linked list examples in UnrealScript[edit]

The linked lists used in UnrealScript are usually simply-linked linear lists, as opposed to circular and/or doubly- or multiply-linked lists. Also the lists or list nodes in UnrealScript linked lists usually aren't explicitly encapsulated in special objects, but instead are created implicitly through properties in the objects contained in the list. The first such object is usually referenced directly in another object.

Linked lists in UnrealScript are sometimes a bit difficult to explain, as the property pointing to the first or next item in the list often has a name that is similar or identical to the type of objects in the list. For example, the inventory item list is created through a property of type Inventory with the name Inventory. Don't get the type and name of variables confused here.

Inventory list[edit]

Probably one of the most important linked lists in UnrealScript is the Inventory^{(RTNP, U1, UT, U2, U2XMP, UE2Runtime, UT2003, UT2004, UDK, UT3)} item list. In Unreal Engine 1 and 2 games it is built via the Actor.Inventory property. In theory this means any Actor can have an Inventory list, but practically the Inventory property is only used by Pawns and Inventory items to create the list.

An inventory list in UT, starting at a Pawn and containing a Flak Cannon, its ammo and a body armor.

Unreal Engine 3 changed the layout of the inventory list a bit. Pawns now have a special InventoryManager^{(UDK, UT3)} object, which holds a reference to the first item in the inventory list via its InventoryChain property. The Inventory property is declared in the Inventory class now, so "universal" inventory lists are no longer possible.

In either case the inventory list is a replicated linked list, which means its start and link properties are replicated.

Mutator lists[edit]

Another very important linked list is the Mutator^{(RTNP, U1, UT, U2, U2XMP, UE2Runtime, UT2003, UT2004, UDK, UT3)} chain and the related GameRules^{(U2, U2XMP, UE2Runtime, UT2003, UT2004, UT3)} chain. In UT there are even four different Mutator chains, the "main" mutators list, damage mutators, message mutators and HUD mutators. Except for the HUD mutators list, all mutator and gamerules lists are serverside-only.

The main mutators list starts with the BaseMutator property of the GameInfo^{(RTNP, U1, UT, U2, U2XMP, UE2Runtime, UT2003, UT2004, UDK, UT3)} and continues via the Mutator.NextMutator property. In earlier engine generations you can assume the mutator list to contain at least one entry during the game, but starting with Unreal Engine 3 the mutator list can also be completely empty.

Similarly, UT's damage and message mutator lists start with GameInfo.DamageMutator and GameInfo.MessageMutator respectively and continue with the Mutator.NextDamageMutator and Mutator.NextMessageMutator properties. Later engine generations combined these into the separate GameRules class. The GameRules list starts at GameInfo.GameRulesModifiers and continues via the GameRules.NextGameRules property.

HUD mutators are a bit tricky. Technically they are a clientside linked list starting at HUD.HUDMutator and continuing via the Mutator.NextHUDMutator property. Two problems make them harder to use, though. One is the lack of a standard registering method and standard PostRender() implementation. The other, more critical is an implementation inconsistency in the Relic mutators. These use the incompatible chaining property HUDMutator.NextRHUDMutator. If that wasn't bad enough, the HUDMutator's registering method also destroys any previously existing chain built on the Mutator.NextHUDMutator property! (See Legacy:Relics Patch for an attempt to fix this incompatibility at least for the standard Relic mutators.)

Controller, Pawn and NavigationPoint lists[edit]

In Unreal Engine 1 games, all Pawns are automatically added to a linked list starting at the LevelInfo.PawnList property, which is accessible from all actors via Level.PawnList and continues via the Pawn.NextPawn property. Similarly Unreal Engine 2 games maintain a Controller list (but no Pawn list) via LevelInfo.ControllerList and Controller.NextController. Unreal Engine 3 games maintain both a Controller and a Pawn list via WorldInfo.ControllerList and WorldInfo.PawnList respectively.

All Unreal Engine games maintain a list of NavigationPoints via the LevelInfo/WorldInfo.NavigationPointList and NavigationPoint.NextNavigationPoint properties.

Iterating over linked lists[edit]

To iterate over all items in a typical UnrealScript linked list, use the following for loop:

local ListItemType Item;
 
for (Item = FirstListItem; Item != None; Item = Item.NextItem) {
  // process the current list item
}

Here ListItemType is the type of items making up the list, FirstListItem stands for an expression that returns the first item in the linked list and Item.NextItem stands for an expression that returns the item in the list following the current item.

Sometimes you may want to delete items from a linked list while iterating over the list. In this case the above scheme will not work correctly. A more robust way to iterate in such cases looks as follows:

local ListItemType Item, Next;
 
for (Item = FirstListItem; Item != None; Item = Next) {
  Next = Item.NextItem;
  // process the current list item
}

Here the next item is determined before processing (and potentially deleting) the current item.

Using built-in iterator functions[edit]

Unreal Engine 3 provides iterator functions for many built-in linked list, for example InventoryManager.InventoryActors() and WorldInfo.AllPawns()/AllControllers(). So, in order to iterate over all weapons in a Pawn's inventory, you would use the following foreach loop:

local Weapon W;
 
foreach thePawn.InvManager.InventoryActors(class'Weapon', W) {
  // process this weapon
}

Earlier Unreal Engine generations require you to modify the original for loop:

local Inventory Inv;
local Weapon W;
 
for (Inv = thePawn.Inventory; Inv != None; Inv = Inv.Inventory) {
  W = Weapon(Inv);
  if (W != None) {
    // process this weapon
  }
}

In Unreal Engine 3 the iteration steps and the checked typecasting can be performed in fast native code by using the iterator functions mentioned above. In fact, the Controller and NavigationPoint lists can only be accessed via the iterator functions because they are built from private variables.

Building linked lists[edit]

You already know how to iterate over existing items in a linked list, but how do you add new items to it? Well, basically there are three different positions in a list where an item can be added:

1. as new first item,
2. at the end of the list or
3. somewhere in the middle of the list, potentially after a specific other item.

If the list is empty, the second option collapses into the first option and the third option no longer applies.

The first option is the easiest:

NewItem.NextItem = FirstListItem;
FirstListItem = NewItem;

Basically the previously first list item becomes the successor of the new item and the new item becomes the new first item of the list. This is how almost all linked lists in UnrealScript are used, although it's not very replication-friendly as clients might temporarily see only the new item in the list if the "link properties" are replicated instead of being built clientsidely.

Adding new items to the end of the list is a bit more complicated unless you remember the last element in a separate variable, but it is much more robust in the case of replicated linked lists:

local ListItemType Item;
 
if (FirstListItem == None) {
  FirstListItem = NewItem;
}
else {
  for (Item = FirstListItem; Item != None; Item = Item.NextItem) {
    if (Item.NextItem == None) {
      // found last item
      Item.NextItem = NewItem;
      break;
    }
  }
}

Note that you need to catch the special case where FirstListItem == None (i.e. the list is empty) because the for loop can't cover this case.

The third option, inserting a new item after a given item is as simple as the first option:

NewItem.NextItem = GivenItem.NextItem;
GivenItem.NextItem = NewItem;

One very important thing to keep in mind when using these schemes is that every item can only be added to a list if it is not already in that or in any other list! Checking other lists is virtually impossible, you can only make sure an item is only added to a list if it was just created or removed from a list.

Another considerable issue with regard to building a linked list, by appending new elements on the end of the list, is the 250 calls restriction. That is, when adding new elements by passing the new element through the whole list, by calling an "add" function on the first element, which passes the new element to the next etc.., until the last element assigns the new element as its next element, the game will throw a "Infinite Script Recursion (250 calls) detected" General Protection Fault on your screen. This will happen from the moment it wants to add the 250th element, thus, resulting in a sum of 250 recursive calls of the "Add" function.

In short, to benefit the replication surplus of adding elements to the end of a linked list,either use an iterating function in the base object, or keep a pointing variable to the last element of the list and use that one instead to add the new element directly to the end. Make sure the function responsible for removing elements from the list, will update this variable if it's pointing to the element being removed, before removing the element.

Removing list items[edit]

The previous section outlined how to build a linked list, but sometimes you need to remove items from he list without breaking it. Take the inventory list example from the top of the page and imagine the player throws away his Flak Cannon. The Flak Cannon must be properly removed from the inventory chain, otherwise Bad Things might happen. Similarly, if a player leaves the game, the player's Controller and/or Pawn must be removed from their corresponding lists.

To remove an item from a simply-linked linear list, one must consider two cases:

1. The item is the first in the list or
2. the item is at some later point in the list.

The following removal scheme accounts for both cases:

local ListItemType Item;
 
if (ItemToRemove == FirstListItem) {
  // item is first in list
  FirstListItem = ItemToRemove.NextItem;
  ItemToRemove.NextItem = None; // important: unlink the remaining list from the item!
}
else {
  // item is somewhere else (or not at all) in the list
  for (Item = FirstListItem; Item != None && Item.NextItem != None; Item = Item.NextItem) {
    if (Item.NextItem == ItemToRemove) {
      // found the item, unlink it from the list
      Item.NextItem = ItemToRemove.NextItem;
      ItemToRemove.NextItem = None; // important: unlink the remaining list from the item!
      break; // item can be in the list only once
    }
  }
}