I think the Bezier class is quite close to what we need. L_Bezier seems like a valuable component, though I’m not certain of that. What I do not see is quite how to provide quite what the mover code really wants.
In essence, Valkyrie Transport vehicles move from one defined point in space to another. Many times per second they use their speed to come up with a small distance they will move in that small interval, and they ask for the point at that interval from where they are. A new point—and an associated rotation—comes back, and the vehicle moves to that new location.
Of course it isn’t quite that simple. If a vehicle has multiple “bogies”, offset from the center of the vehicle, we have to fetch two points and two rotations and then position the vehicle’s root in between those points, and we need to rotate the bogies separately, to line up with the track.
Of course it isn’t quite that simple. If a vehicle is following a leader, such as a car following a locomotive or another car, it needs to compute its positions and rotations as offset, along the track, from the leader. So it has to find out what distance the leader thinks it is at along the track, subtract or add its following distance, and base its own calculations on that.
Of course it isn’t quite that simple. There are a few different ways that a path can be represented, as a Bezier curve, as a collection of points and rotations, or other such schemes. And most of the code needs to be agnostic as to just how the path is actually represented.
Of course it isn’t quite that simple, but that will suffice to frame the issue that I what to think about today:
How can we define a code interface between a vehicle and a path so as to accommodate all the various path definitions on one side, and all the various needs on the other?
The path-side code needs to be fast, because it is exercised many times per second. It will not help to shift performance concerns to the moving code: they are in the same object. Most important for the moving code: it can differ in how the path is set up, but should not differ in how the path is used, to allow us to use the code in all our vehicles.
In our current code, version eleven or something, vehicles know their “distance” along the path. So the prime mover adds a bit to the distance and uses that to get its new position and rotation. All the other calculations use that distance, plus or minus a bit. All the communication with the path is in terms of distance from some arbitrary zero.
I think we’ll probably continue to use that scheme, since the position of a bogie or follower is easily expressed in terms of the distance: just add or subtract how far behind it is supposed to be. But there might be a decent alternative. My job, at this stage, defined by me, is to think about and explore alternatives.
Suppose that when a vehicle connected to a path it was given a little object, containing, among other things, the point and rotation where the vehicle was meant to be. When the vehicle wanted to move a bit it would send a message to that object, saying, oh, move_by:n_meters. And after it said that, magically the point and rotation in the object would be updated to the new point and rotation.
If it were that easy, then vehicles wouldn’t even be concerned with distance, just with speed, because when you call move_by, you use your speed, like always, to determine how much to move by, but you don’t have to update your distance, because magic.
Questions include:
On the face of it, yes, a little bit, one less thing to keep track of: distance. However, even if we do use distance, there is no reason why we couldn’t have a move_by method if we wanted one, Small advantage if any.
I think we could improve bogie handling. We might make the object that the vehicle talks to be some kind of table or list, and we would update all the points and rotations in the one call to move_by, and then the mover script would just use them instead of making multiple calls to the path, one for each bogie or other point needed.
This one is far less clear. Because a follower follows at some mostly-fixed distance behind the leader, it needs to have some solid value to relate its position to that of the leader. Currently we used distance along the track. If we don’t use distance at all, we would have to find another way for a follower to request a point at a known distance behind the leader. Any unique token would work, but it’s so much like distance that we might as well use distance.
Many of our paths are currently defined in fixed-length segments, so that accessing the point to move to is just an indexed lookup and a quick linear interpolation. But some are not. Those paths are typically defined by placing guides along the desired path. The vehicle senses those guides and calculates a smooth path between them, with the useful property that the path always goes through the guide. We use a Bezier curve to determine the path, which is why my current SLua efforts have focused on working with the Bezier.
As we’ve talked about here before, the main issue with a Bezier curve is that it is not indexed by distance. There is no expression that you can evaluate to find the point at distance d along a Bezier. To get an approximate point at distance d, we have to inch along the curve, estimating how far we have traveled until we get to d. Even with a known t-distance value, we still have to nudge along the curve to find d values near the known point. It’s slow.
That’s where the L_Bezier comes in: it is reasonably fast to create and very fast when it comes down to finding a point at a given distance. We search a small array for a value greater than the distance we want, and then interpolate between the preceding point and the one we just found. Much faster.
I am confident that Bezier plus L_Bezier is faster in the main loop than tracking a Bezier directly, and accept that this needs to be proven. For now, it seems to be a key advantage to the scheme.
As configured now, an L_Bezier object is a path that understands a distance index that starts at zero. Its name is perhaps misleading: we create them from a set of little Bezier curves, and we created those little Beziers by partitioning one large Bezier.
In my current moving test in Aditi, I have a simple figure-eight path. It is made up of four bezier curves, two for each half of the 8. We can picture the path as a straight line. Suppose each segment is of length 10. It might look like this:
|---B1---|---B2---|---B3---|---B4---|
0 10 20 30 40
To move along that path at some constant speed speed, on every timer tick, we might have code a bit like this:
dist = 0
ll.SettimerEvent(cycle)
function timer()
local point = path:at(dist)
move_to(point)
dist += speed
end
Our vehicle might be responsible setting distance back to zero as it wraps around, or the path:at might deal with the matter internally, Either way, it looks something like the above.
So what we have is four L_Beziers, each of which thinks it runs from zero to ten, and a vehicle that wants to travel from zero to forty, or perhaps zero to forty and beyond. How can we mate these up?
I can think of at least two ways:
Create a new object that holds a collection of L_Beziers and knows their lengths, so that when the vehicle asks for distance D, this new object fines the L_Bezier that contains that distance as seen from the outside and then subtracts the L_Bezier’s starting distance from D and lives the rest to the L_Bezier.
That is exactly what the L_Bezier object itself does. It knows the length of its segments and it finds the right one and then asks it for the in-between value. So we could jigger the L_Bezier to handle more than one big bezier internally. And we’d have to jigger it to deal with the duplicated endpoints between adjacent Beziers … wouldn’t we?
I hope it is clear why I reject #2. It takes a simple object with a simple function and misuses it to make it do something weird. Would it work? I am sure we could make it work. But I’d rather have two objects, or at least start that way.
It happens, conveniently, that an L_Bezier knows its total length. We can make use of that.
L_Bezier = class()
function L_Bezier:init(beziers)
self._points = self:_create_points(beziers)
self._lengths, self.length = self:_create_lengths(self._points)
end
We could write a test for our new object, if only we knew its name. It doesn’t need to be a kind of Bezier. I’m not even sure that L_Bezier is a kind of Bezier. The new object is a thing that finds an object in an array, based on an increasing value d that we think of as distance. It will return to us the object it finds, and the remaining part of the value d that hasn’t been consumed.
I think I’ll start with an inline test just to get a feel for how it’ll work. I come up with this after some fiddling:
function Tests:test_distance_finding()
local function find_in_list(d, list)
local total = 0
for _, pair in list do
if d <= pair[1] then
return d, pair[2]
end
d = d - pair[1]
end
return nil
end
local input = { {10, "a"}, {10, "b"}, {10, "c"}, {10, "d"}}
remainder, value = find_in_list(6, input)
self:assert_equals(remainder, 6)
self:assert_equals(value, "a")
remainder, value = find_in_list(27, input)
self:assert_equals(remainder, 7)
self:assert_equals(value, "c")
remainder, value = find_in_list(46, input)
self:assert_equals(remainder, nil)
self:assert_equals(value, nil)
end
My input, to me, is a bunch of lengths and paths, a b c d. To the find function, it’s just a pair of things, a number and something else. Now let’s make an object. We’ll call it DistanceFinder for now. I copy and modify that first test:
function Tests:test_distance_finder()
local input = { {10, "a"}, {10, "b"}, {10, "c"}, {10, "d"}}
local df = DistanceFinder(input)
remainder, value = df:find(6, input)
self:assert_equals(remainder, 6)
self:assert_equals(value, "a")
remainder, value = df:find(27, input)
self:assert_equals(remainder, 7)
self:assert_equals(value, "c")
remainder, value = df:find(46, input)
self:assert_equals(remainder, nil)
self:assert_equals(value, nil)
end
I need the class, of course.
function Tests:test_negative_mod()
local d = -1
local dmod = d%10
self:assert_equals(dmod, 9)
end
DistanceFinder = class()
function DistanceFinder:init(pairs)
self:check_pairs(pairs)
self._pairs = pairs
end
function DistanceFinder:check_pairs()
end
function DistanceFinder:find(d)
local total = 0
for _, pair in self._pairs do
if d <= pair[1] then
return d, pair[2]
end
d = d - pair[1]
end
return nil
end
That code passes the tests. I added the check_pairs with the intention of dong some verification on the format of the input. We’ll see whether we need it. To remind myself, I’ll write a test and ignore it,
function Tests:ignore_test_check_pairs()
-- create a DistanceFinder with bad input
end
I can already tell that this test result is not enough to nag me:
All Tests: Pass 852 Fail 0 Ignored 1. Tests:run_tests
It should turn red or something. I wonder if color works in Sublime Text’s build pane. We’ll leave that yak for later, but a quick search suggests that I can add a package and do it.
I want a different result, I think. I’d like the DistanceFinder to wrap around. Change the test:
remainder, value = df:find(46, input)
self:assert_equals(remainder, 6)
self:assert_equals(value, "a")
Fix DistanceFinder to know its total length.
DistanceFinder = class()
function DistanceFinder:init(pairs)
self._pairs = pairs
self:check_pairs(pairs)
end
function DistanceFinder:check_pairs()
self._total_length = 0
for _, pair in self._pairs do
self._total_length += pair[1]
end
end
function DistanceFinder:find(d)
d = d % self._total_length
local total = 0
for _, pair in self._pairs do
if d <= pair[1] then
return d, pair[2]
end
d = d - pair[1]
end
return nil
end
Made semi-good use of check_pairs. Needs improvement, but I think we have a useful start.
All this thinking and writing for a class with three simple methods? Yes. Why Because we have the time to do the thinking necessary to do the job well. We have been in SL for nearly twenty years and our vehicles have been moving most of that time. And, while we do not yet know what will come out of the SLua exercise, I’d like it to reflect my best work. We have, most likely, months before SLua appears on the live grid.
We have the time to learn and to create the best things we can think of. And those things? Well, we will surely improve upon them as time passes. We might as well give them the best start possible.
Until next time, I wish you safe paths!