Code to read Tibia 11 collections (skills, server info, etc)

[blackd]

Ok, I just finished another important piece of this big puzzle of Tibia 11.

Below I am posting my highly optimized VB6 function to read Tibia full tibia collection (Qt5 structure).
It is almost as fast as reading a classic list of items.



Public Sub ReadTibia11CollectionMIN(ByRef pid As Long, adrPath As AddressPath, _
ByRef dict As Scripting.Dictionary)

Dim adrCOLLECTION_START As Long
Dim totalItems As Long
Dim adrSTARTER_ITEM As Long
Dim maxDepth As Long
Dim p0, p1, p2 As Long
Dim item As Variant
Dim iterCount As Long
Dim c0, c1, c2 As Long
Dim adrRoot As Long
iterCount = 0
Set dict = New Scripting.Dictionary
adrCOLLECTION_START = ReadCurrentAddress(pid, adrPath, -1, False)
totalItems = QMemory_Read4Bytes(pid, adrCOLLECTION_START + 4)
If (totalItems = 0) Then
Exit Sub
End If
maxDepth = totalItems
adrSTARTER_ITEM = QMemory_Read4Bytes(pid, adrCOLLECTION_START)
adrRoot = adrSTARTER_ITEM
p0 = QMemory_Read4Bytes(pid, adrSTARTER_ITEM)
p1 = QMemory_Read4Bytes(pid, adrSTARTER_ITEM + 4)
p2 = QMemory_Read4Bytes(pid, adrSTARTER_ITEM + 8)
c0 = fillCollectionDictionaryMIN(pid, p0, adrSTARTER_ITEM, dict, 0, maxDepth, adrRoot)
c1 = fillCollectionDictionaryMIN(pid, p1, adrSTARTER_ITEM, dict, 0, maxDepth, adrRoot)
c2 = fillCollectionDictionaryMIN(pid, p2, adrSTARTER_ITEM, dict, 0, maxDepth, adrRoot)
iterCount = c0 + c1 + c2
Debug.Print "Collection size " & CStr(totalItems) & " took " & CStr(iterCount) & " iterations"
' For Each item In dict
' Debug.Print CStr(item) & " (" & CStr(Hex(item)) & ") found at " & CStr(Hex(dict(item)))
' Next item
End Sub

Private Function fillCollectionDictionaryMIN(ByRef pid As Long, ByVal adrCurrentItem As Long, _
ByVal adrPrev As Long, _
ByRef dict As Scripting.Dictionary, _
ByVal currentDepth As Long, _
ByRef maxDepth As Long, ByRef adrRoot As Long) As Long
On Error GoTo gotErr
Dim id As Long
Dim c0, c1, c2 As Long
Dim Count As Long
Count = 1
id = QMemory_Read4Bytes(pid, adrCurrentItem + &H10)
If (dict.Exists(id) = False) Then
dict(id) = adrCurrentItem
If (currentDepth < maxDepth) Then
Dim p0, p1, p2 As Long
p0 = QMemory_Read4Bytes(pid, adrCurrentItem)
p1 = QMemory_Read4Bytes(pid, adrCurrentItem + 4)
p2 = QMemory_Read4Bytes(pid, adrCurrentItem + 8)
If Not ((p0 = adrPrev) Or (p0 = adrRoot)) Then
c0 = fillCollectionDictionaryMIN(pid, p0, adrCurrentItem, dict, currentDepth + 1, maxDepth, adrRoot)
Count = Count + c0
End If
If Not ((p1 = adrPrev) Or (p1 = adrRoot)) Then
c1 = fillCollectionDictionaryMIN(pid, p1, adrCurrentItem, dict, currentDepth + 1, maxDepth, adrRoot)
Count = Count + c1
End If
If Not ((p2 = adrPrev) Or (p2 = adrRoot)) Then
c2 = fillCollectionDictionaryMIN(pid, p2, adrCurrentItem, dict, currentDepth + 1, maxDepth, adrRoot)
Count = Count + c2
End If
End If
End If
fillCollectionDictionaryMIN = Count
Exit Function
gotErr:
fillCollectionDictionaryMIN = 0
Debug.Print ("Something failed: " + Err.Description)
End Function

[blackd]

And today I finally finished my function to find a collection item by KEY, supposing that this Qt5 collection will not have 2 items with same key. It would be possible in Qt5, but we should not see that case in any Tibia collection.

My current search is optimized enough to search any KEY with few iterations. However, I am sure it could improved up to x2 faster by someone with better knowledge about this Qt5 structure. It looks like a very complex red-black binary tree.



Public Function FindCollectionItemByKey(ByRef pid As Long, adrPath As AddressPath, ByRef keyToSearch As Long) As Long
Dim res As Long
Dim adrCOLLECTION_START As Long
Dim totalItems As Long
Dim pLeft As Long
Dim pRight As Long
Dim val0 As Long
Dim val1 As Long
Dim val2 As Long
Dim maxDepth As Long
Dim adrSTARTER_ITEM As Long
Dim p(5) As Long
Dim isGoal As Boolean
Dim isFail As Boolean
Dim currentDepth As Long
Const rootval As Long = -1
currentDepth = 1
adrCOLLECTION_START = ReadCurrentAddress(pid, adrPath, -1, False)
totalItems = QMemory_Read4Bytes(pid, adrCOLLECTION_START + 4)
If (totalItems = 0) Then
FindCollectionItemByKey = -1
Exit Function
End If
maxDepth = 1 + (totalItems / 2)
adrSTARTER_ITEM = QMemory_Read4Bytes(pid, adrCOLLECTION_START)
p(0) = QMemory_Read4Bytes(pid, adrSTARTER_ITEM)
p(1) = QMemory_Read4Bytes(pid, adrSTARTER_ITEM + 4)
p(2) = QMemory_Read4Bytes(pid, adrSTARTER_ITEM + 8)
p(3) = p(0)
p(4) = p(1)
p(5) = p(2)
q_nextIteration pid, adrSTARTER_ITEM, keyToSearch, p, pLeft, pRight, isGoal, isFail
If (isGoal) Then
res = pLeft
End If
If (isFail) Then
currentDepth = maxDepth + 1
End If
If (isGoal = False) And (isFail = False) Then
'Debug.Print "..."
Do
currentDepth = currentDepth + 1
p(0) = QMemory_Read4Bytes(pid, pLeft)
p(1) = QMemory_Read4Bytes(pid, pLeft + 4)
p(2) = QMemory_Read4Bytes(pid, pLeft + 8)
p(3) = QMemory_Read4Bytes(pid, pRight)
p(4) = QMemory_Read4Bytes(pid, pRight + 4)
p(5) = QMemory_Read4Bytes(pid, pRight + 8)
q_nextIteration pid, adrSTARTER_ITEM, keyToSearch, p, pLeft, pRight, isGoal, isFail
If (isGoal) Then
res = pLeft
Exit Do
End If
If (isFail) Then
currentDepth = maxDepth + 1
Exit Do
End If
' Debug.Print "..."
Loop Until currentDepth > maxDepth
End If
If (currentDepth > maxDepth) Then
' Debug.Print "WARNING at FindCollectionItemByKey: Key not found (With size=" & CStr(totalItems) & ") Key = " & CStr(keyToSearch) & " (" & CStr(Hex(keyToSearch)) & ")"
FindCollectionItemByKey = -1
Else
' Debug.Print "(With size=" & CStr(totalItems) & ") Key " & CStr(keyToSearch) & " (" & CStr(Hex(keyToSearch)) & ") found after " & CStr(currentDepth) & " iterations at " & CStr(Hex(res))
FindCollectionItemByKey = res
End If
End Function

Private Sub q_nextIteration(ByRef pid As Long, ByRef adrSTARTER_ITEM As Long, _
ByRef keyToSearch As Long, ByRef p() As Long, _
ByRef pLeft As Long, ByRef pRight As Long, _
ByRef isGoal As Boolean, ByRef isFail As Boolean)
Const rootval_min As Long = -2147483648#
Const rootval_max As Long = 2147483647
Dim val_min(5) As Long
Dim val_max(5) As Long
Dim best_min_v As Long
Dim best_min_i As Long
Dim best_max_v As Long
Dim best_max_i As Long
Dim i As Long
isGoal = False
isFail = False
best_min_i = 0
best_min_v = rootval_min
best_max_i = 0
best_max_v = rootval_max
For i = 0 To 5
If (p(i) = adrSTARTER_ITEM) Then
val_min(i) = rootval_min
val_max(i) = rootval_max
Else
val_min(i) = QMemory_Read4Bytes(pid, p(i) + &H10)
val_max(i) = val_min(i)
End If
Next i
'Debug.Print "q_nextIteration options: " & CStr(val(0)) & "," & CStr(val(1)) & "," & CStr(val(2)) & "," & CStr(val(3)) & "," & CStr(val(4)) & "," & CStr(val(5))
For i = 0 To 5
If (val_min(i) = keyToSearch) Then
' Debug.Print "Goal found at q_nextIteration p(" & CStr(i) & ")"
isGoal = True
pLeft = p(i)
pRight = p(i)
Exit Sub
End If
' Pick best left
If (val_min(i) > best_min_v) And (val_min(i) <= keyToSearch) Then
best_min_v = val_min(i)
best_min_i = i
End If
' Pick best right
If (val_max(i) < best_max_v) And (val_max(i) >= keyToSearch) Then
best_max_v = val_max(i)
best_max_i = i
End If
Next i
pLeft = p(best_min_i)
pRight = p(best_max_i)
'Debug.Print "Next iteration will search between " & CStr(val_min(best_min_i)) & " and " & CStr(val_max(best_max_i))
If (val_min(best_min_i) > keyToSearch) Or (val_max(best_max_i) < keyToSearch) Then
isFail = True
End If
End Sub

[Mahatesh]

Can you please give a short explanation of the algorithm, for the less VB-inclined?

[blackd]

I wrote my functions based on some facts I discovered:
- This structure seems to use some kind of red black logic. Each node have color Red, Black or Special. The logic is somehow related in the logic that you might have to follow for the optimal algorithm. I don't fully understand this so my algorithm will analyze ALL the possible logic decisions in each iteration.
- The starter item is special. It does not contain data. It only contains 3 pointers and the Special color flag.
- ALL the items have 3 pointers. P0, P1 and P2.
- For all the items (except MAYBE for the starter item) the meaning of each pointer will be different (maybe depending color and/or iteration step?) And -whatever is the logic behind this hell- I know that each pointer should take one of the following roles: LEFT, RIGHT and PARENT.
- The PARENT pointer will point to the previous collection item. This is an interesting fact when you only want to gather full collection because in that case you only want to follow LEFT and RIGHT, avoiding parents and avoiding items that you already gathered. However, we should not discard PARENT when searching for a key. Sometimes following parent is the fastest step.
- The tree is somehow sorted in LEFT - RIGHT. The only special case seems to be the starter item.
- In the starter item I think you can read pointers as LEFT, MIDDLE and RIGHT. When searching a key you should start choosing the 2 pointers that better fit for your key. Then, in each iteration, you should try to obtain a smaller interval, you should decide the best pointer that follow to each of them, always keeping your goal key between LEFT and RIGHT, and choosing best pointer option depending their pointed item key values. You should consider that the key value of the root item is SPECIAL (min or max value depending if you are checking best left or best right). You should consider the value of each pointer as the key of the item it is pointing.

[Mahatesh]

I have some issues with some of your points. Referring back to linky-link (http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html?graph=digraph%20%7B%0A%20%20%20%20A%20%5 Blabel%3D%22root%5B0101%5D%22%5D%3B%0A%20%20%20%20 B%20%5Blabel%3D%2256030737%5B0000%5D%22%5D%3B%0A%2 0%20%20%20C%20%5Blabel%3D%221074154386%5B0001%5D%2 2%5D%3B%0A%20%20%20%20D%20%5Blabel%3D%221074201871 %5B0001%5D%22%5D%3B%0A%20%20%20%20E%20%5Blabel%3D% 221073741884%5B0001%5D%22%5D%3B%0A%20%20%20%20F%20 %5Blabel%3D%221073742123%5B0001%5D%22%5D%3B%0A%20% 20%20%20G%20%5Blabel%3D%221074159815%5B0001%5D%22% 5D%3B%0A%20%20%20%20H%20%5Blabel%3D%221074181788%5 B0000%5D%22%5D%3B%0A%09I%20%5Blabel%3D%22107374188 5%5B0000%5D%22%5D%3B%0A%09J%20%5Blabel%3D%22107374 1920%5B0000%5D%22%5D%3B%0A%09K%20%5Blabel%3D%22107 3742717%5B0000%5D%22%5D%3B%0A%09L%20%5Blabel%3D%22 1074158718%5B0000%5D%22%5D%3B%0A%09M%20%5Blabel%3D %221074160803%5B0001%5D%22%5D%3B%0A%09N%20%5Blabel %3D%221073741998%5B0001%5D%22%5D%3B%0A%09O%20%5Bla bel%3D%221073742314%5B0001%5D%22%5D%3B%0A%09P%20%5 Blabel%3D%221074153284%5B0001%5D%22%5D%3B%0A%09Q%2 0%5Blabel%3D%221074154701%5B0001%5D%22%5D%3B%0A%09 R%20%5Blabel%3D%221074159255%5B0001%5D%22%5D%3B%0A %09S%20%5Blabel%3D%221074164080%5B0000%5D%22%5D%3B %0A%09T%20%5Blabel%3D%221073741964%5B0000%5D%22%5D %3B%0A%09U%20%5Blabel%3D%221073742136%5B0000%5D%22 %5D%3B%0A%09V%20%5Blabel%3D%221073742489%5B0000%5D %22%5D%3B%0A%09W%20%5Blabel%3D%221074153415%5B0000 %5D%22%5D%3B%0A%09X%20%5Blabel%3D%221074154564%5B0 000%5D%22%5D%3B%0A%09Y%20%5Blabel%3D%221074154871% 5B0000%5D%22%5D%3B%0A%0A%20%20%20%20A%20-%3E%20B%20%5Blabel%3D%22p0%22%5D%3B%0A%09A%20-%3E%20C%20%5Blabel%3D%22p1%22%5D%3B%0A%09A%20-%3E%20D%20%5Blabel%3D%22p2%22%5D%3B%0A%09B%20-%3E%20A%20%5Blabel%3D%22p0%22%5D%3B%0A%09B%20-%3E%20E%20%5Blabel%3D%22p1%22%5D%3B%0A%09B%20-%3E%20A%20%5Blabel%3D%22p2%22%5D%3B%0A%09C%20-%3E%20F%20%5Blabel%3D%22p0%22%5D%3B%0A%09C%20-%3E%20G%20%5Blabel%3D%22p2%22%5D%3B%0A%09D%20-%3E%20H%20%5Blabel%3D%22p1%22%5D%3B%0A%09E%20-%3E%20I%20%5Blabel%3D%22p2%22%5D%3B%0A%09F%20-%3E%20J%20%5Blabel%3D%22p0%22%5D%3B%0A%09F%20-%3E%20K%20%5Blabel%3D%22p2%22%5D%3B%0A%09G%20-%3E%20L%20%5Blabel%3D%22p0%22%5D%3B%0A%09G%20-%3E%20H%20%5Blabel%3D%22p2%22%5D%3B%0A%09H%20-%3E%20M%20%5Blabel%3D%22p0%22%5D%3B%0A%09J%20-%3E%20E%20%5Blabel%3D%22p0%22%5D%3B%0A%09J%20-%3E%20N%20%5Blabel%3D%22p2%22%5D%3B%0A%09K%20-%3E%20O%20%5Blabel%3D%22p0%22%5D%3B%0A%09K%20-%3E%20P%20%5Blabel%3D%22p2%22%5D%3B%0A%09L%20-%3E%20Q%20%5Blabel%3D%22p0%22%5D%3B%0A%09L%20-%3E%20R%20%5Blabel%3D%22p2%22%5D%3B%0A%09M%20-%3E%20S%20%5Blabel%3D%22p2%22%5D%3B%0A%09N%20-%3E%20T%20%5Blabel%3D%22p0%22%5D%3B%0A%09O%20-%3E%20U%20%5Blabel%3D%22p0%22%5D%3B%0A%09O%20-%3E%20V%20%5Blabel%3D%22p2%22%5D%3B%0A%09P%20-%3E%20W%20%5Blabel%3D%22p2%22%5D%3B%0A%09Q%20-%3E%20X%20%5Blabel%3D%22p0%22%5D%3B%0A%09Q%20-%3E%20Y%20%5Blabel%3D%22p2%22%5D%3B%0A%09%0A%09%0A %7D), which is a single example, and thus cannot tell us how EVERY case works, but can tell us if an algorithm is NOT RIGHT, here is some stuff I do not agree with:

-The PARENT pointer will point to the previous collection item -- this is NOT true for the special item's P0, since that is the MIN element in my example, and his P1 points to the SECOND SMALLEST item, meaning, his next item.
-Sometimes following parent is the fastest step -- while true for a small subset of items, in general this is bad practice. It is not worth following the parent if the item we want is not there, since it will lead to a full (O(log n)) search anyways. Until we understand the logic behind MAX and MIX's parents, I think this is a very wasteful step.


Another issue we might want to investigate- tibia caches battlelist entries. If I have your entry, and you log out, it will still be present in the structure. When you log back in, it will update the entry you had before. This means several things:
-We could use this info to avoid searching the tree altogether. Once you found an item, just store its address.
-We could view cached copies as "live" ones. This would throw off any logic that reads the battlelist to assume your surrounding.
And on this note, I could not identify any changes in a cached entry from a live one. I have no idea how tibia keeps track of them (to filter the battlelist UI), but the memory image of an entry (and its info block) stayed the exact same for several tests I ran.

[Sydek]

Hello,

Im trying to understand the algorithm and I have some questions that will clarify things alot, I hope its not a burden... Ive been dying to debug this code with hope to achieve deeper understanding.

1. What exactly is being returned out of [Public Function FindCollectionItemByKey] ? Do you think could post a representative short example of usage?

2. [Public Function ReadCurrentAddress] vs [QMemory_Read4Bytes] , does the first check the legacy client? Im confused on why use the first one.

Thanks hope not to bother too much and thanks for all.

[blackd]

There is no sense in a cache.
Collections should be fast enough, specially for Cipsoft code.
Visual battlelist might be independient but it gets data from the main battlelist. I am almost sure about it.
Battlelist keeps death creatures, but marks their entries with a special byte at the end of the usefull information block.
And of course I don’t know the exact algorithm but I am sure my functions are optimal besides the fact that each iteration takes probably x2 cpu instructions than the native algorithms. The O(thing) does not suffer at all because this.
About parents in each node: I only mean that each node A contains at least 1 pointer to P where P contains at least 1 pointer to A.

[blackd]

FindCollectionItemByKey returns the address of the start of the collection item block. You can look how they look in other threads

ReadCurrentAddress uses AddressPath and returns a final address only valid for your current instance of the tibia 11 client.

My other memory funcions just read final adress and return usefull values: numbers or strings.

[Sydek]

FindCollectionItemByKey returns the address of the start of the collection item block. You can look how they look in other threads

ReadCurrentAddress uses AddressPath and returns a final address only valid for your current instance of the tibia 11 client.

My other memory funcions just read final adress and return usefull values: numbers or strings.

Thanks , I managed to read the battle list, I did find x, y, z, hp and visible . I am having alot of trouble finding the values for outiftColors/outfit/mounts/ do you think its somehow encoded?

Is the outfit (the one on the battle list) a collection itself? or is it the protobuf number thing?


Thanks for all in advance.