Calculating the path of a hanging chain (In Minecraft)
It can be frustrating to build a smooth and natural looking curve in Minecraft. Many hours can be spent demolishing and rebuilding the same curve, attempting to find the perfect ratio of horizontal and vertical rate of change to give your grid of disconnected blocks the illusion of acting as a continuous line.
While in the depths of your block based aggravation, you might start to ask some questions. Surely this problem has been solved decades ago! Your computer calculates thousands of curves every second, and effortlessly displays them to you on a grid of pixels. It must be possible to implement the same thing in Minecraft without too much effort!
Bézier Curves
One of the most common ways you will find to render curves is through the use of Bézier curves. These curves are defined by a series of ”control points” which determine the shape of the curve. The simplest way to intuitively understand what is going on is to imagine an iterative interpolation process, starting with your initial control points, and progressively adding more points until the curve is defined. Of course, in practice some clever calculus is used to greatly reduce the number of required computations.
This process is possible to implement yourself, but it is obviously not what we are looking for. The process of constructing the curve has been abstracted into the process of choosing the correct control points, which is an even more frustrating and difficult task than what we originally set out to do! Look at the dozens of control points used to define a simple letter in an average font!
Equation for a hanging chain
Clearly we are going to need to use a different approach. The curves you attempt to build in Minecraft are not arbitrary. They are often built attempting to emulate gravity acting upon a physical object, such as a hanging rope bridge, or power lines. This type of curve, caused by a flexible object hanging under its own weight, is called a ’Catenary’, and can be described mathematically by the shockingly simple expression y = cosh(x). A completely unmodified hyperbolic cosine function! (other than some scaling and translation of course)
This fact is quite amazing and unbelievable when you first learn of it. You can, of course, walk through the entire derivation, balancing the forces acting upon an infinitesimally small section of chain and integrating, and watching as the hyperbolic cosine falls out. However, personally I find no satisfaction in these derivations and much prefer intuitive explanations that are unsound at best, and fundamentally wrong and misleading at worst. While researching this phenomenon I found exactly such an explanation.
To my knowledge. The Hyperbolic trig functions have little to no relation with the standard trig functions you know and love. The hyperbolic trig functions are actually at their core exponential functions in disguise, merely wrapped in trig terminology for mathematical convenience, as for whatever reason they act in a very similar way mathematically to the trig functions, following the same rules of integration and derivation, obeying the trig identities, etc.
So cosh(x) is Really defined as 
. The average of 2 opposing exponential
functions. In our context, it is easy to imagine each point the cable is hanging from
contributing an exponential amount of ’influence’ on the chain, hence the cosh(x)
relation. This description is most likely fundamentally flawed in some way, and
most likely breaks down in more complex cases, but it satisfies my intuition so it is the
explanation I choose to believe :ˆ).
Catenary math
So now we have an easy way to draw a curve. Given 2 points to hang from and a
string of length s, parameters easy for us to work with, we need to solve for the curve
of the form cosh(x). Thankfully, the Wikipedia page on catenary curves has done all
of the hard work for us! Given the scaled curve A ⋅ cosh
, there is only
one value of A such that the curve will go through our 2 points while still
having our specified length s:
As the article points out in the last line, it is not trivial to solve for A, and we have to solve it numerically. I am almost certain that the canonical way to solve this function in through the use of a Taylor series expansion. As it is a ’cosine’ function, I would not be surprised if you could even simplify the infinite series to solve it exactly rather than simply take an approximation (as all of the even and odd terms of the derivative of cosh(x) can be grouped together).
However it has been a long time since I have done serious calculus, and I am very lazy and don’t want to leave my mathematical comfort zone, or take the derivative of my function by hand more than once for that matter. With that in mind, I chose the much simpler Newton’s method to solve for a. This is a very easy numerical method to understand and implement. To find the zero of a function, You simply take a guess at a value, draw a line tangent to the curve, follow it until you cross 0, and use that value as your new guess. You do this until your guess is close enough to 0 for your liking.
Anyone who is still following along despite my lackluster math explanations probably has a pretty good grasp of what is going on, and are cringing pretty hard right now. For those of you who have not realized the problem with my approach, lets look at the shape of the graph we are solving, y = x sinh(c/x). (where c is an arbitrary constant)
This is basically the textbook example of a graph you should never even THINK about using Newtons’ method to solve. Why not? Well, let’s see what happens if we choose a random value for x1 that is larger than the solution.
As you can see, if the function has an asymptote like ours does, the method completely breaks down and will not converge properly. Of course, as we know the shape, we can simply always choose a small value as our initial guess, to the left of the asymptote, to avoid this.
But at small values, we are choosing a point near a vertical asymptote, meaning the value will bounce like this for dozens or even hundreds of iterations before converging at our answer! After realizing this I was very tempted to revisit the Taylor series approach... But on the other hand the Newtons’ method approach did eventually converge on the correct value... so it was good enough for me :ˆ). I did implement a basic sweep that will sweep through orders of magnitude so we don’t start with our initial guess too far to the left. So for example if f(100) is positive, but f(1000) is negative, we know our value is somewhere in that range, so we can start at x=100 rather than our blind starting guess of x=0.01 (As our blind initial guess must be very small to ensure it does not end up on the horizontal asymptote to the right). My program actually broke at high values of A before implementing this feature, as otherwise the initial change of guess was so small, it was within the programs’ set error tolerance, and the program assumed it had found the solution after a single iteration.
Now that we have our scaling factor, we have to translate our curve in space to hit
our 2 given points. in math terms, we have our equation A ⋅ cosh
, and we need to
translate it B units vertically and C units horizontally, making our final equation
A ⋅ cosh
+ B. With this equation of two unknown variables, and our two points
(x1,y1) and (x2,y2), we can use high school calculus to trivially solve for B and C.
(We do have to do another round of newtons method to solve the system of
equations, but I am not going to bore you with the process here, it’s nothing
new.)
And voila! We have solved for the equation of a chain hanging between 2 points! Right?
When all you have is a hammer...
Astute readers may have noticed a problem. Minecraft is in 3d space. We just solved for an equation of a curve in a 2d space. There are 2 options I know of available to us to rectify this problem.
- 1.
- Re-derive ALL of the math we just did in 3d space, as a parameterized function defined by fx(t), fy(t), and fz(t)
- 2.
- Use Linear Algebra to transform our points in 3d space onto a 2d plane, do our math, and transform the answer back.
It is probably much more elegant to do option (1), and you would probably arrive at a very beautiful and simple solution. However, parametrizing Wikipedia’s derivation in 3d is far above my mathematical abilities, especially compared to the alternative option, which I already know how to do, despite being more computationally expensive (A common pattern in my solutions)
We simply translate the points to the origin, rotate P2 about the Y axis so it lies entirely on the X-Y plane (ie. Z=0), do our previously stated math on the 2d XY plane, and then rotate and translate in reverse. OpenGL has all the required functions built in to do this easily. However as the rotation is so basic, it actually isn’t hard to come up with a simple function to do it yourself using basic trigonometry! This blog post is getting a bit too long for me to go off on that tangent. (see for yourself what happens when you place P1 at the origin, P2 on the radius of a circle with radius R, and draw a right triangle down to the X-axis, where you want your new point to end up.)
Now that we have our final equation, we need to convert our equation to blocks to place in Minecraft. In Computer Science this is called rasterization, and there are all kinds of very clever methods to do this without using too many calculations. However I am not a computer science student, and if you have been paying attention to my problem solving style, you can already guess exactly how we are going to solve this problem --- We calculate an arbitrarily large number of points on our line and round them to the nearest integer :ˆ)! Here are the final results in-game, adjusting the length of the chain in real time.
Results
Pretty cool right? As a closing note, to put into perspective just how stupidly powerful modern computers are: Due to my modding-api and general java incompetency, my program doesn’t actually save it’s state, and the entire process I have just outlined (and even more minecraft-centric calculations that I glossed over, including a very computationally expensive sort of the block list by distance-to-the-player for rendering purposes) is performed Every Single Frame. Despite this, the game still is easily running at 60fps. I do plan on making efficiency changes in the future, but for now I am just happy to have a working product!
Excited to play with this feature in game? Too bad! I am still working out the details on the minecraft-side of things, such as the GUI used to edit the curve, and block rendering/placement. It will be released in the next version of my ’Texturizer’ mod for v1.12 of minecraft, and later ported to either 1.16 or 1.18, whichever one is currently the current ’canonical’ modded version. Subscribe to my RSS feed for updates.
If you are one of the 0-3 people who have actually read this post, I really appreciate it! I would love to hear your feedback, but I haven’t quite worked out how to put comments on my webzone. I would put a basic one up myself, but I don’t trust you to not do any form-injection attacks :ˆ). I saw there is a free guestbook service out there, but It requires google tracking cookies, and not to mention javascript, so I am staying away from it for now.