We’d like to be able to write movers that can use any or all of our various path types—without changes.
We have paths represented in fixed-step intervals. We have paths expressed with Bezier curves. We will have paths made by chopping up beziers into convenient variable-length chunks. We will have paths made up of collections and combinations of those. We have paths stored in memory, stored in Link Set Data, or discovered as we drive.
Each of those has to be dealt with a little differently. And yet, we really only want the same thing from any of them: “Please give me the information corresponding to this distance D”. Today I propose to work on a few objects that will let us build up paths defined in any or all of these says, such that the code that uses the path need not know anything about the details of how the path is described.
In what follows, I have, I believe, a good handle on part of the problem, finding the information that corresponds to a given distance D. I am not sure, yet, what to do about our movers that want to think in terms of moving a specific small distance d from wherever they are. So I’ll simply defer that question until the rest of the solution becomes more clear, and then see how to fit the small-move idea into things.
From the viewpoint of a script that moves a vehicle, each request to the path returns some expected “payload”, typically a position along the path, and an associated angle, vector, or rotation that helps in positioning the vehicle.
From the viewpoint of the path itself, the payload is almost irrelevant. There might be some decoding at the very bottom, unpacking a data structure or some such thing, but basically the path’s sole concern is to find the payload that is associated with a given distance D.
Since any path storage mechanism we’re likely to use has finite capacity, and the distance D is a number with a fractional part, there will be some kind of interpolation. The path will have an exact payload at two distances Di and Dj, such that Di<=D<=Dj, and somewhere, the interpolation between those two needs to happen.
Presently, “somewhere” is down at the bottom. We’ll assume that, but it’s worth being aware that finding the two surrounding values, and interpolating between them, are two different notions and don’t necessarily belong in the same place. We’ll see what it looks like when we get there.
I am committed to finding a good design that can be well-expressed in the code. To do that, I try to hold on to my design ideas loosely, so that the code can help me decide where things belong and how they can be done. That’s what we’ll be doing here.
Since the bottom-level classes I’ve sketched so far all mostly respond to at: distance, I plan to have all the objects here respond to the at: message.
If the object in question actually knows how to produce the payload for the input distance, it will return that payload, in a form to be decided later.
If the object isn’t able to produce the payload, it will be an object that contains one or more objects, each representing some interval of distance, and the object’s job is to determine which of its children is the right one, and ask it to answer at: distance. The value of distance in that call will generally not be the the original input value. Why? Because, in essence, each segment of a path typically thinks of itself as starting at zero and covering some distance.
Suppose we have a curving closed path made up of five sub-paths, p1 through p5. Suppose the sub-paths are of length 10, 15, 20, 15, and 10. The total path length is 70. The individual paths deal with segments of that, like this:
| start | end | path |
|---|---|---|
| 0 | 10 | p1 |
| 10 | 25 | p2 |
| 25 | 45 | p3 |
| 45 | 60 | p4 |
| 60 | 70 | p5 |
So if we ask the table above for the payload at distance, oh, 51, the table should ask p4 for the value at 51-45, or 6. And that, my friends, is exactly what the object holding those five paths needs to do: find the right segment in itself, and ask the payload there for the payload at: the updated distance.
At the bottom, the payload is whatever we choose to carry so as to return the value or values we need. Above the bottom, the payload will be … another of whatever these things are.
It’s a tree, isn’t it? There are leaves, with result payloads, and intervening nodes, with payloads consisting of other nodes. It’s nodes all the way down. Better than elephants all the way down: far less messy.
There is a Gang of Four Design Pattern for this, and it is called Composite. Look that up if you care to. What we’ll be doing here will be a very slim version of the full pattern, because we don’t need much.
Of course, we’ll build this thing with tests. And I think we may nearly have all the things that we need already. We certainly have a variable length path, in the L_Bezier, and I think I have a fixed-length one in here somewhere, FixedIntervalPath. And there is this class:
DistanceFinder = class()
-- possible utility class?
-- implemented as proof of concept.
function DistanceFinder:init(pairs)
self._pairs = {}
self:_add_pairs(pairs or {})
end
function DistanceFinder._add_pairs(self: DistanceFinder, pairs)
self._total_length = 0
for _, pair in pairs do
self:add(pair[1], pair[2])
end
end
function DistanceFinder:add(length, obj)
table.insert(self._pairs, {length, obj})
self._total_length += length
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
I have no detailed recollection of just what I had in mind when I wrote that, other than to work with the concept of finding a thing at a given distance. We have similar code to the find method elsewhere, I think. Probably in L_Bezier. Yes:
L_Bezier = class()
function L_Bezier:_find_distance(d)
local remaining_distance = d
for i, len in self._lengths do
if remaining_distance < len then
return i, remaining_distance/len
end
remaining_distance -= len
end
return nil
end
The method above is used in L_Bezier like this:
function L_Bezier:point_at_distance(d, debug)
local idx, frac = self:_find_distance(d)
local p0 = self._points[idx-1]
local p1 = self._points[idx]
return p0*(1 - frac) + p1*frac
end
Here, we’re returning our actual payload, presently taken to be just the position interpolated between the two points we discovered.
I suggest that you skip down to A Round Tuit on first reading.
I mentioned above my concern about the guide-driven movers, which want to move some small distance d from wherever they were, rather than move to some defined distance D along a fixed path. I want to do a small experiment with functions that return multiple values.
function Tests:test_multi_return_ideas()
local function multi()
return 123, 456
end
local function insert_one()
return "hello", multi()
end
local function make_table()
local t = { multi() }
table.insert(t, "hello")
return table.unpack(t)
end
a, b, c = insert_one()
self:assert_equals(a, "hello")
self:assert_equals(b, 123)
self:assert_equals(c, 456)
a, b, c = make_table()
self:assert_equals(a, 123)
self:assert_equals(b, 456)
self:assert_equals(c, "hello")
end
Here are two ways of returning a multiple result with the property that the upper caller does not know how many values the lower function will return.
In insert_one we use the fact that when a function returns multiple values and is called last in an assignment, all the values are returned. If it is not the last, then only the first value is used. So we return our special “hello” at the beginning, and it will be followed by however many the lower function, multi returns.
In make_table, we package the multiple returns as a table inside our upper-level function, insert our value (wherever we want it, really) and then unpack to return the bunch.
I think I prefer the former approach, because the latter creates, inserts, unpacks and then drops a table, while the former just lets Lua do its own thing. With any luck at all, that will be much faster than creating, updating, unpacking, and destroying.
I did this just to get the irritating question out of my mind of how to return a value of distance if we need it. We can use the first scheme.
But I digress.
While DistanceFinder is close to what we need, I think we’ll create a new class here, even if we later repurpose DistanceFinder. I want to be able to think clearly about what is going on, and Distance Finder has more stuff in it than I’m ready to think about.
Let’s think of a test. I can’t think all the way to calling at on the leaves. Here’s what I have so far:
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
The _find method will just return the item corresponding to the input distance. We’ll have to work out the next steps. One little step at a time. No hurry, Janet, no hurry. Here’s PathFinder:
PathFinder = class()
function PathFinder:init(tab)
self._tab = tab
end
function PathFinder:_find(distance)
for i, t in self._tab do
if distance < t[1] then
return t[2]
end
distance -= t[1]
end
return nil
end
The test passes. Now that I have something concrete, it’s easier to think about.
What I would really like is that when we call at: on the pathfinder, we get back an interpolated result from the tables at the bottom. They presently don’t know how to do that. Let’s write the test anyway:
function Tests:test_composite_at()
local a = {10, 100} -- length, payload
local b = {10, 200}
local c = {20, 400}
local path = PathFinder({a, b, c})
self:assert_equals(path:at(4), 40)
self:assert_equals(path:at(17), 170)
self:assert_equals(path:at(31), 220)
end
I think those are the correct interpolated values that I want. If not, I’ll find out soon enough.
My intention is that our PathFinder will not know what is underneath it, but that it will merely call at on that object, passing in the remainder of distance that is covered by that item. We’ll want more info, since we’ll need both ends of the curve in order to interpolate.
(There are other ways, I suppose, but they would require us to manipulate the contents of the leaves and we want to be independent of that. We’ll see what it takes. I expect we’ll have to jostle things around a bit to get it right.
I come up with this:
function PathFinder:at(distance)
local refined_distance, payload = self:find(distance)
return payload:at(refined_distance)
end
I realized that the PathFinder is chopping down the distance, so that it needs to return the chopped value to be used at the next level down, in this case our input items. We’ll need to change some things around to make this even work.
That’s fine, we’re finding out way. A look at the actual code makes me want to return the distance last, not first, so I’ll change the at:
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
I expect my initial test to pass and the second one to fail for want of at on the tables. That is what happens:
Error: /Users/jr/Desktop/repo/bezier_dev.lua:453:
attempt to index number with 'at'. Tests:test_composite_at
OK, my leaf objects have to be smarter. In particular, I’m afraid they need to know their starting address as well as the ending one in their payload. That’s troubling, because in general they do not know that sort of thing.
This might be just an issue with how truly silly my a, b, c objects are.
I’ll create something a bit more robust, right in the test.
Ha. As expected, one of my test values is wrong. Test is:
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
The last test needed to check for 310, 200 + 11/20*200.
And the code:
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
The test is passing. So is the old one. There are things not to like.
However, I am tired, and it is time for a break. I try never to code when I’m tired, and I have nothing to write if I’m not coding. Well, a few notes:
I think the main thing that troubles me is that my Leaf object needed to know both its starting and ending values. I’ll think about that when next I work on this.
Let’s wrap this up here, the article is too long anyway, and start another tomorrow.
Safe paths!