Linked Lists (part 1)
This tutorial assumes you have read and understood the UnrealScript language reference by Tim Sweeney.
Linked list????
A linked list is precisely that; a list of objects linked together by a series of pointers to another object in that list. This allows for a near unlimited amount of objects to be connected; a worthy substitution for dynamic arrays (arrays of no defined size), which are not present in UnrealScript. This can be used for a variety of purposes; a player's inventory a history of messages, a bunch of pipebombs a player can detonate, or even simply have easier and quicker access to certain actors.
How a list is set up
A linked list requires two parts. A "base object" (note that this part, under strange circumstances, may be omitted) which has a pointer a member of the list (for the purpose of this tutorial: the first) and a pointer in EVERY list element to another element.
| Class ListElement expands object;Var ListElement Next; // the next list element. |
| Class SomeImportantActor expands actor;Var ListElement ListElement; // the first element in the list |
SomeImportantActor should be some critical actor in your mod. As an example, Unreal uses the LevelInfo to hold the pointer to the first Pawn and NavigationPoint in the PawnList and NavigationPointList, respectfully. The first inventory item of a player is connected by a pointer residing inside of that player. The Next pointer points to the next element of the list. The list terminates when Next==None.A third part of the list also exists; contents. This is simply whatever the list elements are supposed to do or store.
Navigating through a list
The easiest to move through the list is simply to use the For loop.
| // this is run inside the SomeImportantActor class.Local ListElement Element;For (Element=ListElement; Element!=none; Element=Element.Next) //here each element's variables can be read, edited, or have functions called on it. |
Note how the above works. First the temporary Element pointer is set to the base element. At the end of each loop, the Element pointer is set to its Next pointer. This continues until no more elements are present (i.e. the Element pointer equals None).
Adding to Lists
There are three ways of adding to a list; at the beginning, at the end, or in the middle.Note: In this example the ListElement class is only an object, but not an actor. If you make a subclass of actor then you should replace new (none) class'ListElement'; with spawn (class'ListElement');
Beginning:Simply instantiate an object, set its Next pointer to the current base (the ListElement pointer), and then set it as the base:
| TempElement=New (none) class'ListElement';TempElement.next=ListElement;ListElement=TempElement; |
End:There are two ways that a new element can be added at the end of a list.The loop method inside the SomeImportantActor:
| Local ListElement Element;Element=ListElement;While (Element.next!=none) Element=Element.next;Element.Next=new (none) class'ListElement'; |
Note that this loop terminates not when Element is none, but when an Element's next pointer is none. This allows a pointer to the last element of the list to exist when the loop has completed.
The "1337 function in each element" method:I do not know of the "official" name of this method. Nonetheless, this is the simpler method, which is used to add mutators. Remember that list elements are true objects and CAN have functions called on them. This allows for very simple code to exist.Inside SomeImportantActor:
| ListElement.AddElement(new (none) class'ListElement'); |
The class ListElement has the following function:
| Function AddElement (ListElement NewElement){ If (Next!=None) Next.AddElement(NewElement); Else Next=NewElement;} |
First a ListElement is instantiated. Then the ListElement's AddElement function is called with a pointer to the new ListElement. If there is another element in the list, it then calls the AddElement function on that element. Eventually, the end of the list is reached, where Next is none. Now Next is set to point to the new ListElement.
In the middle:Adding an element into the middle of any list obviously requires a pointer to the item one wishes to add after. Assume that Element is some element inside the list:
| TempElement=new class'listelement';TempElement.Next=Element.Next;Element.Next=TempElement; |
Again an element is created. Its Next var is set to whatever the Next var is of the element that this one is being added in front of. Finally, the element that is going to have the new element added after it has its Next var set to the new element.
Removing Items:
In the case of actor lists, it is not safe to simply destroy an actor that is part of the list (objects do not apply as they cannot be manually destroyed). This causes any list elements after it to become unlinked. To remove any list item (it is safe to do this in actor.destroyed()), one must do the following:
| // in the SomeImportantActor classFunction RemoveElement(ListElement Element){ Local ListElement List; If (Element==ListElement) Element=ListElement.Next; Else For (List=Element;List!=none;List=List.Next) If (List.Next==Element) { List.Next=Element.Next; Break; }} |
First and foremost, a check must be performed to see if the element to be removed is the base pointer. If it is, then the base is simply set to whatever that element's next is. Yet, if this is not the case, the code must go looking for that doomed object. A loop is performed which goes through all the elements. With each loop, it is checked temporary List pointer's Next pointer is the item that should be removed. If this is the case, that element's next pointer is set to the to-be-deleted element's next. The loop can then be terminated.
You can synthesize the above information to conduct some exciting list manipulation. For instance to move a list item, you can simply remove it and then insert it in the middle of something else.
Advanced Lists
The above is only the basics of how a list is constructed. Many other pointers however may exist in a list. For instance, a two-way list can be created by having each item not only have a pointer to the next, but also to the previous. There can also be a pointer in every element to the base or even to the end. While this does mean execution can be faster and frankly easier to set up, it does mean more needs to be done when adding or removing elements. Also note that more pointers allow greater flexibility. For instance, with a pointer to the first or previous element, this allows for the link to the list to be at any element, rather than the first. As an example, in Operation: Na Pali, the translator has a history of all previous messages. I simply have a pointer to the TranslatorHistoryList that holds the current message. If a user wishes to read older or newer messages, the pointer to the TranslatorHistoryList simply changes to the current pointer's Next or Prev pointers, respectfully. This allows for simple and fast executing code.Note: When variables exist that apply to the list as a whole, rather than a per element basis, they should be placed in the actor that links to the list or the first element. In the latter case, this often means having a pointer to the first element in all elements.
Existing Lists in Unreal Tournament
This part of the tutorial explains existing linked lists in Unreal Tournament.Actor listType of ListAll actors in Unreal are connected though a gigantic list (well it is actually a dynamic array, but to make life easier think of it as a list) that exists only in the native c++ code. Without this list, actors would be just plain old objects. The base of this "list" is actually the native level object (all actors have a pointer to this: Xlevel)Exists: On both client and server. When a client "receives" an actor, it is added and when its connection is closed (except with bnettemporary), it is removed.Adding to List: Spawning an actor automatically does this. It adds at the end of the list. Note that levelinfo is always the first actor.Removing from List: Destroying an actor automatically does this.Navigating the list: In the actor class, various "interators" exist. These allow you read the list in different ways. Simply use ForEach Interator_Function(params) to use them. ForEach acts much like a For Loop.
| AllActors ( class<actor> BaseClass, out actor Actor, optional name MatchTag ); |
Baseclass is the parent of classes you wish to look for. The actor pointer passed in the second parameter becomes the actor outputted. As the iterator functions are hard-coded into the compiler, you can have the actor pointer be of the BaseClass or any of its parents. Matchtag, if given, will only return actors, which have that tag. This will go through every actor in the level and is thus somewhat slow (this is not noticeable however unless it is called multiple times in one frame), and thus use it sparingly. If a more class specific list exists, such as that for pawns and navigation points (see below), use those instead. Note that if you wish to terminate the loop when a certain actor is returned, simply use break;
| ChildActors ( class<actor> BaseClass, out actor Actor ); |
The paramaters work the same as AllActors'. However, this only returns actors with their owner set to the class this is run on. It has the same speed hit as AllActors.
| BasedActors ( class<actor> BaseClass, out actor Actor ); |
Returns all actors that have this as a base. Same speed hit as AllActors.
| TouchingActors( class<actor> BaseClass, out actor Actor ); |
Returns all actors touching this one. This uses a special "collision hash" and thus is quite fast.
| TraceActors ( class<actor> BaseClass, out actor Actor, out vector HitLoc, out vector HitNorm, vector End, optional vector Start, optional vector Extent ); |
This is supposed to trace a line from Start to End and return all actors hit (executes as fast as a normal trace). However, this is not ever used by Epic in code and I recall of no one ever getting it to work right. I do not recommend using it.
| RadiusActors ( class<actor> BaseClass, out actor Actor, float Radius, optional vector Loc ); |
This returns all actors that are within radius units of Loc (or if it isn't given; then the actor's location). Same speed hit as AllActors().
| VisibleActors ( class<actor> BaseClass, out actor Actor, optional float Radius, optional vector Loc ); |
This is much like RadiusActors() only it also checks if an actor is visible from Loc. Same speed hit as AllActors.
| VisibleCollidingActors ( class<actor> BaseClass, out actor Actor, optional float Radius, optional vector Loc, optional bool bIgnoreHidden ); |
This only returns actors with bCollideActors as true. It uses the collision hash to check, and thus it is much faster than Allactors, in normal circumstances. If a very high radius is used (900 or so), then it becomes very slow, and VisibleActors should be used instead.
| ZoneInfo.ZoneActors( class<actor> BaseClass, out actor Actor ); |
Returns all actors inside that zone. Same speed hit as AllActors(). Go figure.
Inventory ListType of List: Standard one way linked list. Notice how it is defined in actor, and not in inventory. This is designed so other actors (pawns) can have a link to the base, while keeping the same pointer name.Exists: Server. On the client side however, it will only exist for the player being controlled and within his inventory. Other player's will not have an inventory list. Note that in very rare events, replication can come at a weird order and cause the inventory pointer of one item to point to an older one in the list. Thus when using this list client-side, you should have a check so that no more than 100 or so loops occur (to avoid infinite iterators).Adding to List: Call AddInventory() on the pawn you wish to add that inventory item to with that item in the parameters. It is then added to the beginning of the inventory list. This should only be done server-side. Note that inventory's GiveTo() automatically does this.Removing From List: Class DeleteInventory() on the pawn(owner) with the item you wish to delete in the parameters. Again, this should only be performed server-side. When an inventory item is destroyed, this automatically occurs (see Inventory.Destroyed()).Navigating the List: If you are only searching for one item of a certain class (not child classes!), you can simply call FindInventoryType on the pawn who owns the items. Yet to search through the entire list do the following:
| Local Inventory Inv;For (Inv=somepawn.Inventory;Inv!=none;Inv=Inv.Inventory) //do stuff here |
Pawn ListThis list is the reason I am writing this tutorial. I tire of seeing code that uses ForEach AllActors(class'pawn',p), when there is a much faster way this can be done.Type of List: Native controlled standard one way list linked by levelinfo.pawnlist.Exists: Server Side only at BeginPlay() in gameinfo. Thus, on a client or in a mutator (post/pre)BeginPlay(), you need to stick with AllActors(class'pawn',p)Adding to List: Simply call AddPawn() on the pawn. Note that pawn automatically does this in its PreBeginPlay() so you really do not need to worry about calling this. Adds to the end of the list.Removing from List: Call RemovePawn() on the pawn. This is automatically taken care of in Destroyed().Navigating the List: The list base is located in levelinfo. Simply call (in any actor):
| Local pawn p;For (p=level.pawnlist;p!=none;p=p.nextpawn) //do stuff |
Of course you can add whatever IsA checks and casting you need. (for instance if you are only looking for PlayerPawns, have underneath the For loop If (p.IsA('playerpawn')) )
Navigation Point ListType of List: Constant standard one way list linked by LevelInfo.NavigationPointListExists: Server-side only.Adding To list: Cannot be done. The list is generated upon building the paths in UnrealEd.Removing From List: Cannot be done.Navigating the List: Most likely you will use the navigation point list to find path nodes (a simple navpoint added by level authors). This allows you to spawn actors at many different locations in the map, and still have bots touch them. For instance, the relics mutator searches the Navigation Point list for pathnodes. Relics are then spawned at a random node. Like the pawn list, the base is in levelinfo.
| Local NavigationPoint np;For (np=level.NavigationPointList;np!=none;np=np.nextnavigationpoint) //do stuff |
Note that many other lists exist within navigation point. They are all used exclusively for AI navigation. Unless your name is Pfhoenix, they have no meaning.
Mutator List:The introduction of mutators in Unreal 2.24 was one of the best things ever done for mod makers. What makes mutators so powerful? The fact that they are linked lists. This allows many different mods to be run at once and change many different game elements.There are in fact 4 mutator lists in Unreal Tournament; the primary mutator list, damage mutators that only affect (Mutator)TakeDamage calls, message mutators that only affect messages (broadcast, broadcastlocalized, and player's talking), and finally HUD mutators that allow mutators to draw on the HUD.Type of List: All are standard one-way linked lists. HUD mutators are linked to by a HUD, and all others are linked by the gameinfo.Exists: Mutators normally (default) only exist server-side. However, the HUD mutators must be on the client (see below).Adding to List:Normal mutators:When a user selects start, UT opens a map with a special parameter:?mutator=MutatorPackage.MutatorClass, AnotherMutatorPackage.AnotherMutatorClass
The GameInfo's InitGame() is called when it is first spawned. First the Base Mutator (generally DmMutator) is spawned. From there the mutator options are parsed (this tutorial is not about string manipulation and Unreal URLs!), the mutator class dynamically loaded, then spawned, then finally added to the list:
| log("Add mutator "$LeftOpt);MClass = class<Mutator>(DynamicLoadObject(LeftOpt, class'Class')); BaseMutator.AddMutator(Spawn(MClass)); |
AddMutator() adds to the end of the list with the "1337 function" method described earlier in this tutorial. Now the mutator list is ready to receive notification of actor spawning, mutate commands, player respawnings, death notifications, and all those other wonderful events mutators receive from pawns and, more commonly, the gameinfo.
DamageMutators:To make a mutator be used as a damage mutator (it still has normal mutator functions!), simply call level.game.RegisterDamageMutator(MutatorToBeRegistered) The mutator will now receive notification whenever a pawn takes damage and can modify certain values.
MessageMutators:This is another specialized mutator, not unlike a damage mutator. Simply call level.game.RegisterMessageMutator(MutatorToBeRegistered) to be able to edit all of the wonderful messages. Incidentally, message mutators did not exist until UT version 4.13. They were created simply for support of Rocket Arena. They have also been beneficial in stopping message hacking. :p
HudMutators:I cannot even count the amount of times people have why their HUD mutator will not work in network play. What is the reason for this problem? It is quite simple; mutators exist only on the server, yet HUDS are client-side only. Epic's code makes it appear that you can simply call RegisterHUDMutator, which is untrue. The following is one way of adding a HudMutator on the client:
Step 1: In the default properties of your mutator, place the following:
| bAlwaysRelevant=TruebNetTemporary=TrueRemoteRole=Role_SimulatedProxy |
These values cause the mutator to be replicated to all clients, but the connection only stays open until the client has received the mutator. The mutator must also be a Simulated Proxy on the client for step 2 to work.Step 2: Now add the following code to your mutator:
| Simulated Function Tick(float delta){ If (level.netmode==NM_DedicatedServer | bHUDMutator) Disable('Tick'); Else RegisterHUDMutator();} |
Each frame, RegisterHUDMutator() is called. If it finds a PlayerPawn with a HUD (local player!), it will set that HUD's HUDMutator to this mutator (as well as preserve the list) and set bHUDMutator to true. If the mutator has already been registered or this is a dedicated server (no HUDs!), then tick () can be safely disabled.
On a final note, I ask that all mod makers who make use of HUDMutators to do the following:At the end of PostRender() in your HUDmutator, PLEASE add:
| If (NextHUDMutator!=none) NextHUDMutator.PostRender(canvas); |
For some dumb reason, Epic did not add that support to begin with. Without those lines, your mutator will be the only HUDmutator used. Other HUDMutators will not receive PostRender() calls, and thus not be able to display anything on screen.
Removing from List:No specialized functions exist to remove elements from mutator lists. Simply follow the removal model at the beginning of this tutorial.Navigating the List:Rarely will you ever need to iterate through the mutator list. All functions of mutators simply call that same function on the next mutator, returning a result if necessary. Yet if you wish to go through all mutators simply use:
| Local mutator m;For (m=level.game.Xmutator;m!=none;m=m.nextYmutator) //do stuff |
For normal mutator list:Replace the capital X with base and blank out the capital Y.Damage mutators:X=Damage, Y=DamageMessage Mutators:X=Message, Y=MessageHUD mutators:Replace level.game.Xmutator with SomePlayerPawnPointer.myhud.HUDMutator and Y with HUD.
Spawn Notification ListThis is a list of very powerful actors; SpawnNotifies. For more information read http://unreal.epicgames.com/UTMagic.html. Whenever an actor is spawned/received on a client, native code calls SpawnNotification(actor) on the LevelInfo.SpawnNotifyList Type: Standard one-way list linked by levelinfo.SpawnNotify.Exists: Server and client-side. Note however that SpawnNotifies manually add themselves on both server and client, rather than having the list replicated, as is the case with inventory.Adding to the List:SpawnNotify.PostBeginPlay() automatically adds to the beginning of the list.Removing from the List:SpawnNotify.Destroyed() automatically removes that SpawnNotify. Feel free to call Destroyed() yourself to remove a SpawnNotify from a list, for this does not actually destroy the actor.
Note: The entire spawn notification system can be temporary deactivated as follows:
| Local SpawnNotify Sn;Sn=level.SpawnNotify;Level.SpawnNotify=None;//do stuff here without worrying about Spawn Notifies.Level.SpawnNotify=Sn; |
Other cases of Linked Lists
InterpolationPoint: Uses a two-way list for interpolation of player locations and other properties between each point. While the list is created in unrealscript, that is as far as unrealscript handles it. Everything else is handled by native code.
Pbolt: Uses a standard one-way list that you will probably never need to touch. The plasma beam you see when alt firing the Pulse Gun is actually a linked list of Pbolt's. Unfortunately, the system wasn't written in the best way possible. Ideally, there should be a pointer to the StarterBolt in all beams. Variables only important to the beam as a whole (AccumulatedDamage, LastHitTime) are controlled in each beam, rather than only the list base. Thus when beams are destroyed, some of those values are lost, resulting in odd damage patterns.
Mover: Uses a one-way linked list that also has a pointer to the base. This is used for movers that follow other movers. Feel free to explore this code on your own.
Actor.Deleted: A list of actors that have been deleted and are awaiting garbage collection. This occurs when 128 actors are in the list. This is only used in Epic's native c++ code.
SavedMove: For player movement in a network environment, the client must save old moves to be sent later (to avoid overflowing the network and in cases of packet loss). The actual list is the standard one-way one, which carries move information. A playerpawn has pointers to the SavedMoves (the beginning of the SaveMove list), FreeMoves (a move that is "free"), and PendingMove (the next move to be sent to the server). Yet, this is a tutorial on lists, not something else. Study the SavedMove class and playerpawn.ReplicateMove() to learn more.
Menu.ParentMenu: This is simply a pointer to the previous green menu that showed. These "green menus" were used in Unreal I only. There is little need to understand how they work if you script in UT.
ListElement: This is a two-way list that was set up for use with the WebAdmin. It is a quite powerful method of storing data.
UwindowList: This is a very advanced list, which stores various data for the uWindow system.
UwindowWindow: All the menus seen in UT are actually stored with this complex list system.