Implementing Linked Lists
This tutorial demonstrates how to implement Linked lists in Papyrus.
Linked Lists are a powerful programming tool that can accomplish some tasks with ease that would otherwise be quite difficult.
They are a bit like the linked references you see in the Creation Kit, but more versatile, as they can be dynamically created, used, and then deleted when they have served your purposes.
Essentially, each element in a linked list has references to the Next reference, possibly the previous reference and often, as a timesaver, a reference to the first reference in the list.
Difficulties
Coding Linked Lists in Papyrus is not an easy task, as a number of things work against it.
The primary difficulty is that there is no way to make a new instance of a user created type without already having an instance of it “in hand” - You cannot call a function that returns an instance of it from an empty variable, for example:
Function MyLinkedListFunction
MyLinkedListType MyList = MyList.NewList()
; Do what you want
EndFunctionWill not work. You have to create a list element, in order to call the function that creates list elements. So just to use the above command, you need something more like:
GlobalVariableScript Property Gvar Auto
Function MyLinkedListFunction
if !Gvar.MyLinkedListTypeDummy ; At the start of any function wanting to use linked lists
Gvar.MyLinkedListDummy = Game.GetPlayer().PlaceAtMe(GVar.MyLinkedListDummyType,1)
; That's two globals - one for the type for creation, and one for storage of the dummy list item.
endif
; Then, and only then,
MyLinkedListType MyList = Gvar.MyLinkedListTypeDummy.NewList()
; Do what you want
EndFunctionBe sure to link the global variable script property up to the quest script you're using to store these variables.
Controller Objects
And remember, local variables are not persistent unless they're in a persistent object, so you will need to put your linked list control code on a control object...and make sure there's only one of them. That's ANOTHER global of course:
Scriptname MyLinkedListController
Function MyLinkedListFunction
if !Gvar.MyLinkedListTypeDummy ; At the start of any function wanting to use linked lists
; You'll want to replace Game.GetPlayer() with the Gvar.NodeSpawnPoint we define later.
Gvar.MyLinkedListDummy = Game.GetPlayer().PlaceAtMe(GVar.MyLinkedListDummyType,1)
endif
; Then, and only then,
MyLinkedListType MyList = Gvar.MyLinkedListTypeDummy.NewElement()
; Do what you want
EndFunction
Event OnInit()
if !Gvar.MyLLController
GVar.MyLLController = Self
RegisterForUpdate(10)
endif
EndEvent
Event OnUpdate()
; Periodic things you want to do with your lists here.
EndEvent
GlobalVariableScript Property Gvar AutoYou will need one controller for each different set of linked lists you need to use. Each set of lists might do something different on an update event, for example, and thus need separate OnUpdate events. For one set of lists that behaves differently in different circumstances, use states.
Linked List prototype script
OK, once you have your controller more or less set up, it's time to create the actual node types. Here is a bare-bones Linked List Script, implementing a doubly-linked list with references to the first element (anything that can lower the number of operations needed in Papyrus is a good thing.)
You'll most likely also want a spawn point for the list nodes other than the player, particularly if your list nodes are actual physical objects...that's another global variable you will need.
And if your list nodes are physical items, you can make a FormList of them so you can have them look different (make sure to attach this script to all of them, and assign the property for the global variables!) - Anything you can attach a script to can be a linked list node.
Take a Deep breath:
Scriptname LinkedList extends ObjectReference
{Controls to store data and control links for Linked Lists. Special LinkedList types should extend this}
import game
import utility
LinkedList property First Auto ; Reference to the First (Header)
LinkedList property Next Auto ; Reference to the Next Element.
LinkedList property Prev Auto ; Referebce to the previous element (Supports doubly-linked lists.)
Form Property Data Auto ; Reference to the Data Item for the node. Can be anything, the list doesn't care.
; Don't confuse the data reference with the list node, they are completely separate.
LinkedList Function MakeNewElement(int WhichType = -1)
if !Gvar.NodeSpawnPoint ; We haven't got a place to put node lists yet!
Gvar.NodeSpawnPoint = FindClosestReferenceOfTypeFromRef(Gvar.NodeSpawnPointType,Game.GetPlayer(),100000) ; Look for one.
if !Gvar.NodeSpawnPoint ; None in the cell!
Gvar.NodeSpawnPoint = Game.GetPlayer().PlaceAtMe(Gvar.NodeSpawnPointType,1,true) ; Emergency...make one!
endif
Wait(2.0) ; Give a new Spawn Point time to settle in as the link holder.
endif
if Gvar.NodeTypeList
if WhichType != -1 && WhichType <= Gvar.NodeTypeList.GetSize()
return (Gvar.NodeSpawnPoint.PlaceAtMe(Gvar.NodeTypeList.GetAt(WhichType - 1),1,true) as LinkedList)
else
return (Gvar.NodeSpawnPoint.PlaceAtMe(Gvar.NodeTypeList.GetAt(RandomInt(0,Gvar.NodeTypeList.GetSize() - 1)),1,true) as LinkedList)
endif
else
return (Gvar.NodeSpawnPoint.PlaceAtMe(Gvar.DefaultNodeType,1,true) as LinkedList)
endif
EndFunction
LinkedList Function NewList(form NewData, int Type = -1)
; Function to create a new list of a single element. Returns Reference to the element.
LinkedList FirstNode = MakeNewElement(Type)
FirstNode.Data = NewData
FirstNode.First = FirstNode
return FirstNode
Endfunction
LinkedList function AddNewElement(form NewData, int WhatNodeType = -1,Bool Append=false)
; Creates a new node holding the new data reference, and adds it to the List that called it.
LinkedList NewNode
NewNode = NewList(NewData,WhatNodeType)
NewNode.MoveToAnotherList(NewNode,self,Append) ; Insert NewNode into the list this was called from.
return Self ; Returns reference to the list.
Endfunction
; This next one may SEEM useless since you had a list and form reference already,
; but it is critical to be able to find out if a given reference is in a given list, and where the actual
; node is, in case you want to move it to another list, remove it from the list, or whatever.
; Again, don't confuse the node with the data...this only searches for the data node, not any data IN the node.
; You have to write your own functions to do that.
LinkedList function FindListNode(Form FindThis)
; Search the list for a data item reference matching FindThis. Returns a reference to the list element.
if First.Prev
; Debug.Notification("FindListNode: Bad First Link")
Self.FixFirsts() ; Need to do this in case something external messed up the reference to First.
endif
LinkedList CheckMe = First
While CheckMe
if CheckMe.Data == FindThis
return CheckMe
endif
CheckMe = Checkme.Next
Endwhile
Return None ; Not in this list.
Endfunction
int function CountList(); Returns a count of the number of elements in the list it is called on.
if First.Prev
; Debug.Notification("CountList: Bad First Link")
Self.FixFirsts() ; Need to do this in case something external messed up the reference to First.
endif
LinkedList Counter = First
int Quantity = 0
while Counter
Quantity += 1
Counter = Counter.Next
endwhile
return Quantity
Endfunction
LinkedList function FindElement(int N) ; Returns the Nth element of the list it is called on.
if N <= 0 ; If we were passed a zero or negative index
Debug.Trace("Passed a negative index ("+N+") in FindElement Function")
return None
else
if First.Prev
; Debug.Notification("FindElement: Bad First Link")
Self.FixFirsts() ; Need to do this in case something external messed up the reference to First.
endif
LinkedList FindMe = First
int Where = 1
while Where != N && FindMe
FindMe = FindMe.Next;
Where += 1
endwhile
if Where == N
return FindMe
else
Debug.Trace("Passed Index larger than list size in FindElement Function")
return None
endif
endif
Endfunction
LinkedList function PickRandom() ; Returns a reference to a random element from the list it is called on.
return FindElement(RandomInt(1,CountList()))
Endfunction
function swap(LinkedList A,LinkedList B) global
; swaps the data items of the two nodes, effectively swapping the nodes.
form HoldMe = A.Data
A.Data = B.Data ; Useful for sorting. Note you don't need to touch the prev and next references at all.
B.Data = HoldMe
endFunction
Function FixFirsts() ; used after activity that may alter the First node without fixing all of the references.
;Use this if you do any external manipulation.
LinkedList FixHere = Self
While FixHere.Prev
FixHere = FixHere.Prev
endwhile
FixHere.First = FixHere
While FixHere.Next
FixHere.Next.First = FixHere.First
FixHere = FixHere.Next
endwhile
EndFunction
; Here is a multi-use function. You can use it (as above) to insert a new element into a list,
; remove an element from a list, or move an element between lists.
function MoveToAnotherList(LinkedList FromList, LinkedList ToList,Bool Append=False)
; Moves element it was called on from list FromList to list ToList
if First.Prev
; Debug.Notification("MoveToAnotherList: Bad First Link")
Self.FixFirsts() ; Need to do this in case something external messed up the reference to First.
endif
if Self.First == FromList.First ; If this evaluates to False, the item wasn't in this list to begin with.
if !FromList.Next ; There is only one element in FromList - special case.
if ToList ; Last Element in previous list, New List has elements.
Self.First = ToList.First
if Append ; Put it at the end of the list, please.
LinkedList FindEnd = ToList.First
While FindEnd.Next
FindEnd = FindEnd.Next
endwhile
FindEnd.Next = Self
Self.Prev = FindEnd
else ; Don't care where it goes.
self.next = ToList.First.next ; Link to Next Element in new list.
self.prev = ToList.First; Link to header
if ToList.First.Next
ToList.First.Next.Prev = self ; Don't cut off the rest of ToList!
endif
ToList.First.Next = self
endif
FromList = None ; Make sure the previous list knows it's empty.
else ; Last element in previous list, first element in new list.
ToList = self
FromList = None
endif
elseif self == self.first ; Another Special case, need to swap nodes first.
Swap(Self,Self.Next) ; Put our data in the second node, and it's data here.
self.Next.MoveToAnotherList(FromList,ToList,Append) ; Take two, with self in the second slot this time.
; (Need to pass the same references in case one or the other gets changed in the move)
else
if ToList ; Last List has more than one element, New List has elements.
if Self.Next ; If there is a node after this one
Self.Next.Prev = self.Prev ; Link the next node's previous to it's new previous node.
endif
Self.Prev.Next = Self.Next
; Link the previous node's Next to our next. Self is now removed from it's old list.
if Append ; To the back of the line, you!
LinkedList FindEnd = ToList.First
While FindEnd.Next
FindEnd = FindEnd.Next
endwhile
FindEnd.Next = Self
Self.Prev = FindEnd
else
self.next = ToList.First.next ; Link to Next Element in new list.
self.prev = ToList.First; Link to header
if ToList.First.Next
ToList.First.Next.Prev = self ; Don't cut off the rest of ToList!
endif
ToList.First.Next = self
endif
self.First = Tolist.First
else ; Last list has more than one element, first element in new list.
if Self.Next ; If there is a node after this one
Self.Next.Prev = self.Prev
; Link the next node's previous to it's new previous node.
endif
Self.Prev.Next = Self.Next
; Link the previous node's Next to our next. Self is now removed from it's old list.
self.next = None ; No next item.
self.prev = None ; No Previous Item.
self.First = Self ; We are the header node of the new list.
ToList = self ; New List now refers to us.
endif
endif
else
; Debug.Notification("MoveToAnotherList: Item was not in FromList.")
endif
Endfunction
Event OnInit()
RegisterForUpdate(5000) ; Keep our data in existance until we are destroyed.
EndEvent
GlobalVariableScript Property Gvar AutoNode Spawn Point Wrapup
Notice how the spawn point code waits a bit before making the first node after creating a new spawn point?
Just to make sure your spawn point item is working, It needs some code on it like this:
Scriptname LinkedListNodeSpawnPointScript extends ObjectReference
Event OnInit()
if Gvar.NodeSpawnPoint ; Hey, there's one already!
self.Disable()
self.Delete()
else
RegisterForUpdate(5000) ; Keep our data in existance until we are destroyed.
moveto (MyFavoriteNodeSpawnPointLocation)
; Change to the default location of your choice...preferably in the cell you'll be using the linked lists in.
; Behind the statue of Wootamootazootagoota The Tense, or whatever.
Gvar.NodeSpawnPoint = self
endif
EndEvent
ObjectReference Property MyFavoriteSpawnPointLocation Auto
GlobalVariableScript Property Gvar AutoNote that you only need one NodeSpawnPoint, but can have multiple controller objects.
Here is a video, demonstrating a very simple use of Linked Lists: To simulate a 2-dimensional array of objectreferences.