Let’s try a compact fast scheme to see what it’s like.
I think we can be confident that script memory will still be a limitation when SLua arrives on the main grid. We’re told that LL are allowing more memory in Alpha than they expect to when it goes live. And anyway, we’re here to try things and build up our chops for SLua, so we’ll try all kinds of weird things.
In general in a garbage-collected language like SLua, I was raised to feel pretty free to create small objects frequently. “Trust your garbage collector”, someone said. but even if that’s generally good advice, creating large collections of small objects can be undesirable.
It’s tricky to be sure. We may have to come up with some code that helps measure the sizes of things, Or, we can study the literature, ask our friends, and make our best guesses.
A path has the ability to accept a distance input and to provide a position vector, and a rotation (quaternion), telling a vehicle how to move that distance and position itself. I think it is best to think of the path itself as consisting of a data structure that only the path understands, and an associated function, at(distance), or some longer name, that returns the vector and rotation for the provided distance.
If all this thinking comes together as I expect it to, we’ll end up with a handful of ways to represent path data, each one implemented as a data type (class or equivalent) with a method at: (or some other consistent name that we might pick). Each of those path objects will then be able to be plugged in and used underneath any kind of vehicle, hiding most of the complexity away from other parts of the intricate machinery that makes up a vehicle’s scripts.
Today I want to experiment with paths where we have the path expressed in terms of a fixed distance between a point/rotation pair, with linear interpolation between the locations.
I propose to represent these paths in SLua arrays, packed up in pairs, position/rotation/position/rotation/etc. The object will know the fixed distance between those pairs, and that distance need not be an integer. We typically use 0.5 meters as the interval in our current systems.
One possibly important optimization could be to initialize our object to the exact length of the array it contains. SLua allocates arrays dynamically, and adding a lot of items creates and destroys increasingly large amount of storage and generally leaves the array with extra space in case of more adds. We’ll leave that alone for now but it could be important
Let’s write a test. Here’s a try:
function Tests:test_fixed_interval()
local p,r
data = {1,10, 2,20, 3,30, 4,40}
path = FixedIntervalPath(0.5, data)
p, r = path:at(0)
self:assert_equals(p, 1)
self:assert_equals(r, 10)
end
I’m trying to make my job easy but not stupidly easy. Here’s a class that with a fake calculation, just to get the test to pass:
FixedIntervalPath = class()
function FixedIntervalPath:init(interval, array)
self._interval = interval
self._data = array
end
function FixedIntervalPath:at(distance)
local index = 0
local at = 2*index+1
return self._data[at], self._data[at+1]
end
I’m glad I picked something easy and decided to fake it. The indexing of these things is going to be a bit odd, because of SLua starting table indices at 1. We could force our array to be zero-based, I suppose, but I think that only leads to confusion later. Anyway that test passes.
Let’s take a few more very small tests. First let’s find a different value in at an exact position, then work on the interpolation separately.
local data = {1,10, 2,20, 3,30, 4,40}
--
p, r = path:at(1)
self:assert_equals(p, 3)
self:assert_equals(r, 30)
The result should be 3,30, because our interval is 0.5, so zero is the 1 cell, 0.5 the 2 cell and 1.0 the 3 cell. This of course fails now since we only know one answer. Enhance the class:
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local at = 2*index+1
return self._data[at], self._data[at+1]
end
The cell we want is the integer part of distance/interval, so there we are.
Now an interpolation. (And then we need to think about the end of the list and wrapping around and negative indexes oh my.) I’m pretty sure this is right:
local data = {1,10, 2,20, 3,30, 4,40}
--
p, r = path:at(0.75)
self:assert_equals(p, 2.5)
self:assert_equals(r, 25)
We need the fraction and to use it in interpolation.
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local frac = distance/self._interval - index
local at = 2*index+1
local p1,r1 = self._data[at], self._data[at+1]
local p2,r2 = self._data[at+2], self._data[at+3]
local p = p1*(1-frac) + p2*frac
local r = r1*(1-frac) + r2*frac
return p, r
end
We just get the remainder, and the tests are all passing. So far so good.
I am concerned about what would happen if we gave this thing a distance less than zero or greater than whatever the outer limit is. There are a number of things we could do, including:
Since we often make closed paths, and since my sisters have a tendency to make trains that can back up into negative distance, I think option #3 is the right one for us.
So we want to force index into the range zero to the half-length of the array (since we have two items per entry. (Should we not make that a parameter on the constructor? Possibly.))
Add a couple of tests. First this:
function Tests:test_fixed_interval_range()
local p,r
local data = {1,10, 2,20, 3,30, 4,40}
-- 0 0.5 1.0 1.5
-- 2.0 2.5
local path = FixedIntervalPath(0.5, data)
p, r = path:at(2.25)
self:assert_equals(p, 1.5)
self:assert_equals(r, 15)
end
I put this in a separate Tests function both because it is a different kind of test than the preceding in-range ones, and because when it failed at first, I got a clear message about what test was failing.
Many of my betters would limit the number of assertions, or assertion cases, to one per test. I do not follow that guideline as well as I might.
This is the code that is passing all the tests:
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local frac = distance/self._interval - index
local at = (2*index)%(#self._data)+1
local p1,r1 = self._data[at], self._data[at+1]
local p2,r2 = self._data[at+2], self._data[at+3]
local p = p1*(1-frac) + p2*frac
local r = r1*(1-frac) + r2*frac
return p, r
end
It’s getting kind of complicated isn’t it? We’ll see what we can do about that when we have it working. I want to test a negative distance next.
local data = {1,10, 2,20, 3,30, 4,40}
-- 0 0.5 1.0 1.5
-- 2.0 2.5 3.0 3.5
-- -2.0 -1.5 -1.0 -0,5
p, r = path:at(-1.5)
self:assert_equals(p, 2)
self:assert_equals(r, 20)
Those indices under the data? Those are not there for you. They are for me. They are the equivalent of counting on my fingers, I guess. That test passes. Let’s try a fractional one,
p, r = path:at(-1.75)
self:assert_equals(p, 1.5)
self:assert_equals(r, 15)
That also passes. This is aided greatly by SLua’s sensible mod operator, %, which always returns a positive result.
One thing to be concerned about here is the length function in SLua, #. In Lua, # is not performant: it counts through the array. (I can’t believe they’d do this but all the documents say that they do.) So let’s save the length in the init.
Here’s our class now:
FixedIntervalPath = class()
function FixedIntervalPath:init(interval, array)
self._interval = interval
self._data = array
self._length = #array
end
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local frac = distance/self._interval - index
local at = (2*index)%(self._length)+1
local p1,r1 = self._data[at], self._data[at+1]
local p2,r2 = self._data[at+2], self._data[at+3]
local p = p1*(1-frac) + p2*frac
local r = r1*(1-frac) + r2*frac
return p, r
end
Let’s see if we can refactor that for a bit of clarity.
Add a lerp function to do the interpolation:
function FixedIntervalPath:lerp(v1, v2, f)
return v1*(1-f) + v2*f
end
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local frac = distance/self._interval - index
local at = (2*index)%(self._length)+1
local p1,r1 = self._data[at], self._data[at+1]
local p2,r2 = self._data[at+2], self._data[at+3]
local p = self:lerp(p1, p2, frac)
local r = self:lerp(r1, r2, frac)
return p, r
end
Inline the last three statements:
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local frac = distance/self._interval - index
local at = (2*index) % (self._length)+1
local p1,r1 = self._data[at], self._data[at+1]
local p2,r2 = self._data[at+2], self._data[at+3]
return self:lerp(p1, p2, frac), self:lerp(r1, r2, frac)
end
What else? I think I don’t like the name at for the index into data, especially inside a method named at. I think we might be able to handle the % differently, possibly earlier? Maybe not. We can return all four data values in one go, like this:
function FixedIntervalPath:data(index)
local d = self._data
return d[index+1], d[index+2], d[index+3], d[index+4]
end
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local frac = distance/self._interval - index
local at = (2*index) % (self._length)
local p1,r1, p2,r2 = self:data(at)
return self:lerp(p1, p2, frac), self:lerp(r1, r2, frac)
end
Notice that I packaged the irritating +1 inside the data method.
Having done that, I am inclined to do the lerp inside the data method. Why bring them out individually only to use them in pairs? That was a bit tricky: I had to reorder the indexing:
function FixedIntervalPath:lerp_pair(index, frac)
local d = self._data
return self:lerp(d[index+1], d[index+3], frac), self:lerp(d[index+2], d[index+4], frac)
end
function FixedIntervalPath:at(distance)
local index = (distance/self._interval)//1
local frac = distance/self._interval - index
local at = (2*index) % (self._length)
return self:lerp_pair(at, frac)
end
It remains to see about clarifying those first three lines in at, and maybe to rename the other methods with underbar to signify private methods.
I’ll try some renaming:
function FixedIntervalPath:at(distance)
local interval_index = (distance/self._interval)//1
local fractional_interval = distance/self._interval - interval_index
local strided_index = (2*interval_index) % (self._length)
return self:lerp_pair(strided_index, fractional_interval)
end
Let’s extract that whole mess to a method returning just what the final line wants.
function FixedIntervalPath:position_at(distance)
local interval_index = (distance/self._interval)//1
local fractional_interval = distance/self._interval - interval_index
local strided_index = (2*interval_index) % (self._length)
return strided_index, fractional_interval
end
function FixedIntervalPath:at(distance)
local data_index, fraction = self:position_at(distance)
return self:lerp_pair(data_index, fraction)
end
Tests have remained green throughout all this. Now at least we have all the badness in a single method, position_at.
I want to do one more thing: rename all the private methods to be private.
FixedIntervalPath = class()
function FixedIntervalPath:init(interval, array)
self._interval = interval
self._data = array
self._length = #array
end
function FixedIntervalPath:at(distance)
local data_index, fraction = self:_position_at(distance)
return self:_lerp_pair(data_index, fraction)
end
function FixedIntervalPath:_position_at(distance)
local interval_index = (distance/self._interval)//1
local fractional_interval = distance/self._interval - interval_index
local strided_index = (2*interval_index) % (self._length)
return strided_index, fractional_interval
end
function FixedIntervalPath:_lerp_pair(index, frac)
local d = self._data
return self:_lerp(d[index+1], d[index+3], frac), self:_lerp(d[index+2], d[index+4], frac)
end
function FixedIntervalPath:_lerp(v1, v2, f)
return v1*(1-f) + v2*f
end
One more tiny thing comes to mind. We’re computing 1-f twice. We could reduce that to once if we were to return two fractions from _position_at. Let’s do it to see how it feels:
function FixedIntervalPath:_lerp_pair(index, frac)
local d = self._data
local one_f = 1 - frac
return self:_lerp(d[index+1], d[index+3], frac, one_f), self:_lerp(d[index+2], d[index+4], frac, one_f)
end
function FixedIntervalPath:_lerp(v1, v2, f, one_f)
return v1*one_f + v2*f
end
That may have been two far but it does save half a zillion subtract operations as we follow the path.
Time to stop. Let’s assess:
We have a nice little object. We give it a fixed distance and an array of pairs and it maps distance values into those pairs, allowing wrap-around and negative distances. It has an easy setup and a single method at in use. It hides all the nastiness of subscripting and interpolating inside itself, and if and when we have to change its indexing or calculations, they are all in one place.
The position_at method is scary but, I am confident, correct. I’d like to make it less scary but at least now all the scary bits are in one method. Hm. I think this will help reduce the scary:
function FixedIntervalPath:_position_at(distance)
local interval_index = (distance/self._interval)//1
local strided_index = (2*interval_index) % (self._length)
local fractional_interval = distance/self._interval - interval_index
return strided_index, fractional_interval
end
I moved the strided_index calculation up one line. I think those first two lines are pretty clear. The third line is still weird. I just noticed the duplication in it. Let’s pull that out.
function FixedIntervalPath:_position_at(distance)
local intervals = distance/self._interval -- float
local interval_index = intervals//1 -- integer
local fractional_interval = intervals - interval_index
-- 0 <= f <= 1
local strided_index = (2*interval_index) % (self._length)
return strided_index, fractional_interval
end
I think that’s slightly better but I am not satisfied. I am, however, tired and done for the morning. I think we have the makings of a nice little object here.
Safe paths!