I am now more acquainted with Lua syntax. I looked at the the Locator in broader context
there is a global table of historical figures which is indexed and assumed to be ordered by unitID in ascending order, e.g.:
index | Historical Figure (as object)
0 | unit42
1 | unit56
2 | unit215
3 | unit418
... | ...
354624 | unit678954
Each unit object in this table has an attribute .id, that's one of the game-internal attributes of the unit class, I presume.
Locator is a class (or table, in Lua terms) which serves two purposes:
1. Given an index in the table of historical figures, it can find access the corresponding historical figure and lookup its id. The method (or function) doing this is called
id_of.
This method is undefined by default, so every time the Locator class is instantiated, this method has to be defined like this:
id_of =
(function (index)
return df.global.world.history.figures [index].id
end)
2. Given a game-internal unit id, it can find the unit with this unit id in the table of historical figures and return the index under which it can be found there. The method doing this is called
index_of. Nah, that would make the code more readable, let's call it
locate instead.
The
locate method uses some sort of searching algorithm which I assume is pretty quick in searching in a list where the the historical figures are sorted by their ids in an ascending order. When I was trying to perform this method myself to see how its searching algorithm actually works,
I think I have found a bug. It seems that it cannot handle the case where it is supposed to find and return the index of the very first historical figure in the list (index 0).
Let's shorten our list of global historical figures to only two members (count = 2):
index | Historical Figure (as object)
0 | unit205
1 | unit408
I'll now run through the locate function:
function Locator:locate (id, count)
local bottom = 0
local top = count - 1
local step
local index
while true do
step = top - bottom
if step == 0 then
return -1 -- Not found
end
if step % 2 == 1 then
step = step + 1
end
step = math.floor (step / 2)
index = bottom + step
if self.id_of (index) < id then
bottom = index
elseif self.id_of (index) > id then
if top == index then
return -1 -- Not found
end
top = index
else
return index
end
end
end
When we call hf_locator:locate(205, 2), the initial values are:
id = 205
count = 2
bottom = 0
top = 1
the the loop starts:
step = 1 // (top - bottom)
step % 2 == 1 is true, that's why:
step = 2 (step + 1)
step = 1 (math.floor (step / 2))
index = 1 (bottom + step)
self.id_of(index) < id is false, skipping this if, executing elseif
elseif self.id_of(index) > id is true, executing the if body:
if top == index is true (1 == 1), executing the if body:
return -1, returning -1 index not found. (
which is wrong, it should have found it and return 0)
Once the loop progresses to the point where top search limit is reduced to 1, the function only checks the unitID, and if it is not the unit we are looking for, it returns -1 forgetting to look at the one last remaining place in the list, index 0.