This morning I plan to continue working on my vision of a small number of tiny objects collaborating to track along a path.
Where were we? I just have to open the script and run the tests and the broken one that I left yesterday reminds me:
[05:23] Bezier 2025-05-24: test_d_bezier: <400.00000, 400.00000, 0.00000> was expected to be <700.00000, 400.00000, 0.00000> ()
[05:23] Bezier 2025-05-24: Tests: Pass 19, Fail 1
Ah, right. That’s this test:
function Tests:test_d_bezier()
local p0 = vector(400, 400, 0)
local p1 = vector(500, 500, 0)
local p2 = vector(600, 500, 0)
local p3 = vector(700, 400, 0)
local b = Bezier(p0, p1, p2, p3)
local len = b:compute_length(8)
local db = D_Bezier(b)
self:assert_equals(db:at(0), b:at(0))
self:assert_equals(db:at(len), b:at(1))
end
The failure is on the second assertion, where the D_Bezier should discover that we have asked for the furthest point (its total length) of its saved path, and return the value at t=1.
We could fake that result but I think what we’ll try is to build up the array of metatables that the D-Bezier will use to approximate t values, and use it. Here’s the class now:
D_Bezier = class()
function D_Bezier:init(bezier)
self.bezier = bezier
self.waypoints = self:make_waypoints()
end
function D_Bezier:at(distance)
local t = self:find_t(distance)
return self.bezier:at(t)
end
function D_Bezier:make_waypoints()
return {}
end
function D_Bezier:find_t(distance)
for _, wp in ipairs(self.waypoints) do
if wp:contains(distance) then
return wp:evaluate(distance)
end
end
return 0
end
We’re good to go except that we don’t have any waypoints to search. I need to think about what the waypoints really need to contain. They are defined like this:
WayPoint = class()
function WayPoint:init(min_d, max_d, min_t, max_t)
self.min_d = min_d
self.max_d = max_d
self.min_t = min_t
self.max_t = max_t
self.length = max_d - min_d
self.delta_t = max_t - min_t
end
We’re going to generate segments of uniform t-values for a fixed number of intervals, say 8. We want the min_t, max_t to go
(0, 1/8), (1/8, 2/8), (2/8, 3/8)
and the min_d, max_d to go
(0, len1), (len1, len2), (len2, len3)
That’s a bit tricky to build. I’ll probably try it a few different ways.
Yucch! This was harder than I wanted it to be. I want a test for the method I just slammed together, at least a printing one.
I’ll spare you the code, here are the five waypoints I first compute with 4 intervals:
[06:01] Bezier 2025-05-24: wp: 0, 0 0, 0
[06:01] Bezier 2025-05-24: wp: 0, 93.75 0, 0.25
[06:01] Bezier 2025-05-24: wp: 93.75, 261.45509338378906 0.25, 0.5
[06:01] Bezier 2025-05-24: wp: 261.45509338378906, 493.3797912597656 0.5, 0.75
[06:01] Bezier 2025-05-24: wp: 493.3797912597656, 793.3797912597656 0.75, 1
The t-intervals are incrementing but the first one is wrong. And while there are 5 points measured, there are only 4 waypoints. Curse that whole attempt, I’ll erase it and do again.
OK, I have a printout that I somewhat believe:
[06:30] Bezier 2025-05-24: length(4) 342.116455078125
[06:30] Bezier 2025-05-24: WP 0, 93.75, 0, 0.25
[06:30] Bezier 2025-05-24: WP 93.75, 171.0582275390625, 0.25, 0.5
[06:30] Bezier 2025-05-24: WP 171.0582275390625, 248.366455078125, 0.5, 0.75
[06:30] Bezier 2025-05-24: WP 248.366455078125, 342.116455078125, 0.75, 1
[06:30] Bezier 2025-05-24: test_d_bezier: <400.00000, 400.00000, 0.00000> was expected to be <700.00000, 400.00000, 0.00000> ()
[06:30] Bezier 2025-05-24: Tests: Pass 19, Fail 1
I am printing each WayPoint as I create it. The min_t and max_t are incrementing 0.25 as expected (intervals is 4). The min_d and max_d values are incrementing by amounts that make sense, and I’ve printed the differences and they look good. I think this part works. Let’s fix up the D_Bezier computation to try to get our correct answer.
Hmm … It looks like it should nearly be working but I think I see the problem.
function D_Bezier:at(distance)
local t = self:find_t(distance)
return self.bezier:at(t)
end
function D_Bezier:find_t(distance)
for _, wp in ipairs(self.waypoints) do
if wp:contains(distance) then
return wp:evaluate(distance)
end
end
return 0
end
if the loop terminates, we have run off the end of the distance tables. We should return 1, not 0 in that case, at least as a first cut at the behavior we want.
With a one in place there, the test passes. An issue is that I have pinned the length calculation that I use to 8 and currently, for testing convenience, the D_Bezier only computes four waypoints, which is pretty weak.
For fun and learning, I’ll print the estimated lengths at various intervals:
4 342.116455078125
8 343.7848892211914
16 344.1999168395996
32 344.3035430908203
64 344.3294343948364
128 344.3359127044678
1024 344.3380494713783
Tests: Pass 20, Fail 0
At 8 intervals, our error is about 0.61, which is less than 0.2 percent. It is about a half-meter off over 344 meters. I still think we can live with 8 intervals but we can go to any number we desire at any point.
However, I pretty much hate this code:
function D_Bezier:make_waypoints(intervals)
local wps = {}
local min_d = 0
local min_t = 0
local min_pos = self.bezier:at(min_t)
for i = 1, intervals do
local max_t = i/intervals -- 1/8, 2/8
local max_pos = self.bezier:at(max_t)
local span = vector.magnitude(max_pos-min_pos)
local max_d = min_d + span
wp = WayPoint(min_d, max_d, min_t, max_t)
table.insert(wps, WayPoint(min_d, max_d, min_t, max_t))
min_t = max_t
min_d = max_d
min_pos = max_pos
end
return wps
end
I’m inclined to improve that code, but our tests for waypoints are pretty weak just now, really only the one that is checking the endpoints. So let’s do this: I’ll make a copy of this method, which I do have confidence in, and write a test that compares the output of both approaches.
function Tests:test_waypoint_refactoring()
local p0 = vector(400, 400, 0)
local p1 = vector(500, 500, 0)
local p2 = vector(600, 500, 0)
local p3 = vector(700, 400, 0)
local b = Bezier(p0, p1, p2, p3)
local db = D_Bezier(b)
wp_good = db:make_waypoints(8)
wp_refac = db:make_waypoints_refactored(8)
for i, wpg in ipairs(wp_good) do
wpr = wp_refac[i]
self:assert_equals(wpr.min_d, wpg.min_d)
self:assert_equals(wpr.max_d, wpg.max_d)
self:assert_equals(wpr.min_t, wpg.min_t)
self:assert_equals(wpr.max_t, wpg.max_t)
end
end
Now I can make changes and be confident that they work (in the sense that they do not change the result).
This isn’t much better:
function D_Bezier:make_waypoints_refactored(intervals)
local wps = {}
local min_d = 0
for i = 1, intervals do
local min_t = (i-1)/intervals
local min_pos = self.bezier:at(min_t)
local max_t = i/intervals -- 1/8, 2/8
local max_pos = self.bezier:at(max_t)
local span = vector.magnitude(max_pos-min_pos)
local max_d = min_d + span
wp = WayPoint(min_d, max_d, min_t, max_t)
table.insert(wps, WayPoint(min_d, max_d, min_t, max_t))
min_d = max_d
end
return wps
end
It’s a little more compact but less efficient, as it computes things twice rather than remembering them.
I think there is probably some clever way with an iterator but I’m not ready for that after messing around this long.
Let’s call this a wrap: we’ve made some progress.
I think it’s good: we have moved from not having a way to compute waypoints to having a way. It’s not a great way but one is a lot larger than zero when it comes to ways to do things. We have a test in place that will even let us refactor our scheme, or we could use it to write a whole new scheme.
Was I off my game today? Was the problem a little harder than I thought? Was the desired output too complicated to do in one go?
Doesn’t matter: it is what it is. We made progress, we learned things, and tomorrow is another day. Celebrate the small win and kiss the difficulties up to heaven. Or elsewhere, your choice.
Time for a nice break and we’ll hit it again later, or tomorrow.
Safe paths!
0/8 p0 1/8 p1 2/8 p2
1/8 p1 2/8 p2 3/8 p3
Couldn’t we just quickly produce what we need from those two rows? I think maybe we could. I’ll try it next time, unless I get an even better-seeming idea.