Let’s try our PathFinder on one of our linearized Beziers. That should tell us whether we’re on the right track. No pun intended.
Pathfinder’s job, in its at method, is to contain a number of paths (or other PathFinders) and given a distance D, find the element within itself that covers the distance D. It then sends at to that object, passing not D but the remaining distance after accounting for the distances covered by all the preceding items. Let me draw a picture:
PathFinder
|--------|------------|------|--------|
p1:10 p2:15 p3:5 p4:10
0-10 10-25 25-30 30-40
We have a PathFinder containing four paths of length 10, 15, 5, and 10. Since they are consecutive paths, the actual distance each covers starts wherever the previous one left off. So p2 covers distance 10-25, because p1 dealt with 0-10. And so on.
So when we ask for distance D = 33, PathFinder spins through the lengths of its contents, decrementing as it goes, 33-10 is 23, 23-15 is 8, 8-5 is 3 … the one to ask is p4 and we ask for distance d = 3`.
I am concerned this morning about two things, one not very concerning and the other slightly more so.
Not very concerning: the object PathFinder finds must be able to deal with a length and one way or another dig into itself to find someone to deal with it. An actual path of some kind, like an L_Bezier, linearized Bezier, knows how to do that. A Bezier, if we were to use one directly, would have to somehow approximate the length within itself. This is why we don’t use them.
A path represented as a series of fixed-distance points, stored in Link Set Data under the names “P00”, “P05”, “P10”, “P15”, … “P95”, “P100”, would use the input distance d to compute the key and fetch the data.
We do not care how a path does it, we only care that it does it somehow, consistently with the general rule, which is that given a distance d, it returns the point (and other information) for that distance.
Slightly more concerning: The PathFinder needs to know the length of each of the things underneath it. The question comes down to working out one or more ways to create and configure PathFinders—and their equivalents.
Equivalents, you ask? Yes. There will probably be more than one kind of PathFinder. I mentioned the one that covers a path stored in Link Set Data, and we have the one we’re working on here, that covers a set of linearized Beziers. There might be another for a path stored in memory. There might be one for a path computed as a series of lines and arcs. There could be any number of kinds of PathFinder, all following the same protocol so that the rest of our mover code can remain the same no matter what kind of path is underneath it.
This morning, let’s see about plugging some L_Bezier instances under our existing PathFinder. If it’s easy, we’ve learned that we’re probably on the right track. If it isn’t easy, we’ll learn why and figure out what to do about it.
We’ll write a test, of course. Let’s create a closed course of two Beziers, converted to L_Bezier. We’ll wind up with 16 L_Beziers, I think. And, as we do this, we will want to deal with going around and around and around, which is not handled yet.
Even the setup for this test is a bit monstrous, and I haven’t even build the PathFinder yet:
function Tests:test_pathfinder_l_bezier()
local p0 = vector(000, 100, 0)
local p1 = vector(100, 100, 0)
local p2 = vector(100, -100, 0)
local p3 = vector(000, -100, 0)
b1 = Bezier(p0, p1, p2, p3)
lb1 = b1:linearized(3)
p0 = vector( 000, -100, 0)
p1 = vector(-100, -100, 0)
p2 = vector(-100, 100, 0)
p4 = vector( 000, 100, 0)
b2 = Bezier(p1, p2, p3, p4)
lb2 = b2:linearized(3)
end
Now so far, the PathFinder just expects to get the right input table, with entries of a length and some other object, so we can build that table in the test, to learn what it’s like:
pathfinder_table = { {lb1.length, lb1}, {lb2.length, lb2}}
pathfinder = PathFinder(pathfinder_table)
self:assert_equals(lb1.length, 0)
I put the assertion in there so that I could check the form of the PathFinder. The length is about 280 and change. Makes sense since the control sides are each 100 so the length around the controls is 300 and the bezier is inside that.
Anyway we can check the PathFinder table as part of our test. But there’s no point: it’s just assigned in. We really want to know whether this actually works.
We can check the points returned against the original Beziers, but not easily, unless we add a feature to Bezier to return the point at a given distance. We can do that. Let’s make an assertion and make it work.
I just spent nearly an hour trying to find out why it wasn’t working. It turns out I had called L_Bezier:at with a typo in the parameter name, thus passing nil. Looking at the code, I just didn’t see it. Finally, after printing a lot of trace info, I noticed. Tedious. Takes the air out of one’s sails.
Arrgh, finding tiny errors in the test as well. I’m off my game, but I have it working. I’ll have a break and deal with cleaning up and explaining later. We have guests coming today anyway, I should tidy up the dust bunnies.
Let me review what I’ve done, it has been almost two full days since I looked at this code.
We have these tests, now all passing:
function Tests:test_composite_find()
local a = {10, 100} -- length, payload
local b = {10, 200}
local c = {20, 400}
local path = PathFinder({a, b, c})
self:assert_equals(path:_find(4), a[2])
self:assert_equals(path:_find(17), b[2])
self:assert_equals(path:_find(31), c[2])
end
function Tests:test_composite_at()
local Leaf = class()
function Leaf:init(len, lo, hi)
self.len = len
self.lo = lo
self.hi = hi
end
function Leaf:at(d)
local frac = d / self.len
return self.lo*(1-frac) + self.hi*frac
end
local a = {10, Leaf(10, 0, 100)} -- length, payload
local b = {10, Leaf(10, 100, 200)}
local c = {20, Leaf(20, 200, 400)}
local path = PathFinder({a, b, c})
self:assert_equals(path:at(4), 40) -- 0-100
self:assert_equals(path:at(17), 170) -- 100-200
self:assert_equals(path:at(31), 310) -- 200-400
end
function Tests:test_pathfinder_l_bezier()
local p0 = vector(000, 100, 0)
local p1 = vector(100, 100, 0)
local p2 = vector(100, -100, 0)
local p3 = vector(000, -100, 0)
b1 = Bezier(p0, p1, p2, p3)
lb1 = b1:linearized(3)
p0 = vector( 000, -100, 0)
p1 = vector(-100, -100, 0)
p2 = vector(-100, 100, 0)
p3 = vector( 000, 100, 0)
b2 = Bezier(p0, p1, p2, p3)
lb2 = b2:linearized(3)
local pathfinder_table = { {lb1.length, lb1}, {lb2.length, lb2}}
local pathfinder = PathFinder(pathfinder_table)
local half = lb1.length / 2
local near_side = pathfinder:at(half)
local b_near_side = b1:at(0.5)
local far_side = pathfinder:at(3*half)
local b_far_side = b2:at(0.5)
self:verify_vectors(near_side, b_near_side)
self:verify_vectors(far_side, b_far_side)
end
The first one wrote to test the find logic and the second to verify that we are returning the second component from the pairs in the object. The third test builds a PathFinder containing two Beziers and it verifies that it correctly finds a point on each Bezier, the two center points, which we can rely on mathematically to be at t = 0.5 on the contained Bezier.
Here is the PathFinder itself;
PathFinder = class()
function PathFinder:init(tab)
self._tab = tab
end
function PathFinder:at(distance)
local payload, refined_distance = self:_find(distance)
return payload:at(refined_distance)
end
function PathFinder:_find(distance)
for i, t in self._tab do
if distance < t[1] then
return t[2], distance
end
distance -= t[1]
end
return nil
end
Not too large, does just what we want it to do, so far. We find the payload item that matches the input distance, and call its at method, passing in the refined_distance, which is the remaining distance after all the preceding items have munched away the parts that they cover.
In principle, according to the “composite” pattern I’m trying to follow, one of two things can happen at this point.
If the payload is a “leaf” of the tree, like the L_Bezier that we’re using here, that object does whatever computation it does and returns the true at value.
But another possibility is that the payload could, in principle, be another non-leaf, such as another PathFinder, or any object following the rules. In that case, the non-leaf would do its lookup as usual, using the residual distance it was passed, and then find its payload and send it at.
So there are just two ways of implementing at in this scheme: you either return the actual value or values in the payload, or you are not a leaf and you search your contents and find a suitable item to send at to,
It’s at all the way down.
I have identified some issues that need to be settled, including:
There are nil returns when the PathFinder (and some other objects we have) cannot perform their function. Things will quickly break in that case but we should perhaps just assert an error right there.
We will want to return more than one payload item, and tests indicate that returning them as separate items rather than wrapping them in a table or object is notably faster. We’ll need to settle on way to do this.
We may need to return some kind of memory token to the SLRR mover, which does not have a fixed distance to increment. Or, possibly, we’ll figure out a way to let it use some distance surrogate that the mover and path-finders agree upon. Possibly the top-level path-finder can just start at an arbitrary distance value and work from that. Almost seems possible.
Many movers are cyclical and need to support modular arithmetic so that a mover can just keep on incrementing forever. There is the possibility of overflow, however. That’s why this is an issue, not an answer.
All components in the path-finding composite need to have a length that their parent can use to decide whether they are the one that contains the point we have in mind. I think that needs to be a function, not a value, although some path-finding pieces will just be returning a never-changing constant. We’ll do some caching.
What objects are, and are not, candidates to be part of the PathFinder family?
PathFinder is the main and possibly the only non-leaf element.
L_Bezier, the linearized Bezier, is a very good possibility for representing a path initially defined by a Bezier (or NURBS, if we were to support those). We use Beziers to define roller coasters and create them dynamically in SLRR, and we might wish to linearize them into L_Beziers. (I feel sure that we’ll do that for SLRR.)
FixedIntervalPath (current name, maybe needs a better one) represents a path each of whose nodes is separated by a constant distance. We use that kind of path extensively: most of our local trains use 0.5 meter fixed paths, and our roller coasters are currently represented that way.
We currently store most fixed interval paths in Link Set Data, which is mysteriously fast and capable of storing quite long paths. I think the question of array access, list access, LSD access, etc., will not affect the general path-finding design. Instead it will, I believe, just be a particular implementation of a leaf’s at behavior.
(That’s pretty much the whole point of the “composite” idea: it hides the details of how you do a thing, so long as you abide by the external expectations.)
Since I’ve written about three lines of code so far this morning, let’s provide a length function in our objects, to get that structure in place.
L_Bezier currently has a member variable length. We want a function instead. Changing this will perhaps break a test but that’s fine, it will show us where we need to change the assumptions. We start here:
function L_Bezier:init(beziers)
self._points = self:_create_points(beziers)
self._lengths, self.length = self:_create_lengths(self._points)
end
And do this …
function L_Bezier:init(beziers)
self._points = self:_create_points(beziers)
self._lengths, self._length = self:_create_lengths(self._points)
end
function L_Bezier:length()
return self._length
end
I considered checking _length in the length() function, but I think we’re safe as it stands. Test to see what breaks.
This code needed to call length rather than just fetch it:
local pathfinder_table = { {lb1:length(), lb1}, {lb2:length(), lb2}}
local pathfinder = PathFinder(pathfinder_table)
local half = lb1:length() / 2
There’s someone else unhappy. This test of DistanceFinder needed similar changes:
function Tests:test_incremental_add()
local df = DistanceFinder()
local b = self:sample_bezier()
local lb1 = b:linearized(3)
df:add(lb1:length(), lb1)
local lb2 = b:linearized(3)
df:add(lb1:length(), lb2)
local l2 = lb1:length()/2
local rem, val = df:find(l2)
self:assert_equals(rem, l2, "1")
self:assert_equals(val, lb1, "1")
rem, val = df:find(3*l2)
self:assert_equals(rem, l2, "2")
self:assert_equals(val, lb2, "2")
end
I think that DistanceFinder is right out anyway. It was an experiment to work with the trick of decrementing the distance we’re looking for as we search. I’ll commit the current code and then remove it and its tests. Git will save it for me in case I want it later.
Committed and pushed. Now remove the class. Run the tests, finding the ones that now fail. Remove those. Remove one of the ignored ones that is no longer applicable. Commit and push: removed DistanceFinder.
I mentioned the ignored test. There is one more test marked ignore:
function Tests:ignore_test_verify_bezier()
-- using tangent_at and de casteljau.
-- verify against the long-hand calculation?
end
Just an idea: we could verify the Bezier’s calculation by comparing the current algorithm, De Casteljau, against the longhand one with the squares and cubes. Or we could not: I’m sure it works. Would I bet my life on it? No, but then I never would. Might be worth doing.
Every time I run the tests I get a reminded of any tests marked ignore_:
All Tests: Pass 870 Fail 0 Ignored 1. Tests:run_tests
[Finished in 29ms]
I might install an extension to Sublime Text to put color in the console, and then I could change the text from red to yellow or green. That might be fun. Not a big payoff.
So we have made a bit of progress. Actually, despite that it’s just a little bit of code, I think this is a powerful idea that offers the prospect of helping use converge all the code into a central commons that contains most of the functionality, plus a few smaller optional bits to deal with the differences.
Meanwhile it keeps me off the streets. So that’s nice.
Safe paths!