The math for comparing the distances with squared values was incorrect - one can not calculate the difference with squared values. The way to do this without needing to calculate square root is to add the remaining length of the tunnel to the threshold, and square that sum. And then do the comparison. ('d11' is the threshold distance, 'd10a' is the remaining length.)
The pictures shown for "before" and "after" happen to show the effect of this fix. Unfortunately, this bug was the reason for only a minority of the artifacts.
This is merely a fine-tuning to compensate for the side-effect of the fix #3. In particular, the old buggy results seemed to cause some more (albeit non-tunnel -like) connectivity between tunnels. This fix #2 adds a little bit more branching in tunnels to get a little bit more tunnels, which in turn will increase a bit of connectivity.
Also, the diameter of the branches was always randomly between 4 and 5; now the diameters are based on the diameter of the parent tunnel, which makes the branch locations a tiny bit smoother (and allows the sub-branching to work more naturally).
"FIX #3" - the rest Originally, the optimization itself is not fully compatible with the way tunnels are branched. The branching draws two new random values from a shared PRNG. Depending on which chunk is being generated, one chunk might optimize (stop tracking) a tunnel before it gets to the branching point, so for that chunk, those two random values are not taken from the generator, leaving them to be used by some other branch/tunnel generated later by the algorithm. However, another chunk in different direction might not do that optimization, taking those random values right then, which causes the "same" later coming other branches/tunnels to get different random values from the sequence, thus generating different looking tunnels.
This is fixed by saving the PRNG before (possibly) starting to work with the branch tunnels, and using new PRNG (recursively) for the branch tunnels. Even small mistakes with this can cause visible artifacts (and often unvisible ones, unless using e.g. xray to see weird small misplaced tunnel bits here and there inside the rock). Note, the "saving" of the PRNG is done simply by not using it inside branch generation.
The (small?) problem with this fix is that the tunnel/cave systems will partially change. Some of the tunnels that would have existed before will not be there at all after the fix, and also there will be some new tunnels. A number of tunnels will be exactly as before (other than not having weird clipping at chunk borders). There is a way to fix this so that there is no changes before vs. after, but the fix is a bit complex and makes the code "ugly" for relatively rarely needed benefit (to be able to produce same world tunnels/caves again). Though such a fix might be handy if an existing world is expanded after this fix is part of the client/server doing the expansion.
Also, the various miscalculated paths for the same tunnel ended up producing partially clipped and short extra tunnels here and there, which increased connectivity between tunnels. The fix removes these extras. This is compensated with the fix #2. The connectivity might still be a little less than before, but this needs more of pure feeling-based testing. It should be quite trivial to simply add more tunnels if necessary.
Perhaps important side-effect of the changing tunnels is that dungeons (monster spawners) will not be produced in the same place as before the fix. One should assume they will be rolled in completely new places (even though one or two could be the same place as before. However, this affects players only if they think to recreate the world (with the same seed) or parts of the world (by removing chunks) and hoping to have the dungeons in the old locations. (That would include me, my main world had a nice triplet of dungeons aligned nicely above each other. However, I'll rather have nicer tunnels than few conveniently located dungeons.)
Details for the update to this bug/fix. (The main points are updated into the OP, and I will update the source code fixes later today).
After the first fixes, I found still some rare artifacts, so I took a better look at the problem. After lots of number-checking, I found out that the optimization in itself was correct (i.e. the threshold value which "made sense" but didn't seem to work), except for the way it handled the math with squared values. Fixing the math mistake alone handles the artifacts shown in the example pictures, but that alone is only about 1/4 of all the obvious visible artifacts. When disabling the optimization, no artifacts are found, though most of the tunnels will be quite a bit different. So, the problem is still somehow related to that optimization.
After quite some more testing things out, the real reason revealed to be the "Bug #3"! I.e. the way the optimization, tunnel branching, and random number generation happened to play with each other - not nicely.
I had to make some quite elaborate tweaks (including own random number generator which allowed to "replay" parts of the sequence) in order to see the difference in a controller way (i.e. tunnels would not change so much with "before" and "after" runs). However, the final fix is surprisingly simple.
The fix to the real problem changes large share of tunnels completely, but also makes them to be without artifacts and be more tunnel-like overall. The slightly lesser connectivity (it looks like there would be more rock and less tunnels in an area) was easy to compensate by increasing branching. Before, each tunnel would branch with a T-crossroads exactly once with branch diameters randomly between 4 to 5, and the branches themselves didn't branch more. I made the branch tunnel diameters to be based on the parent tunnel's diameter, and the possibly larger diameter allows branches themselves to branch again. This generates a little bit more tunnels in the same area and increases the connectivity, and it also makes the branch tunnel diameters to be more smoothly matched to the parent tunnels (although this latter thing is visible only with very large tunnels).
Source code snippets and other texts updated for the new and improved fixes. I do not think I'll do any more changes on this, except possibly to increase the amount of tunnels if the connectivity seems too low.
As a funny side-note... While doing test runs on the MCP decompiled and recompiled client, on one run something weird happened...
No frigging idea. I have not installed any skins, ever, on any version of the client, but that tree skin... Looks good, but.. how?!?
(And no, I'm not expecting any answers to that.. just have a smile at it.)
Hm I Want To Make A Endless age like minecraft But I Want it to be diffrent I'm thinking And I know It's gonna Have Something from like A diffrent game But Kinda Has Like Other Stuff Completely Diffrent I Got To think.
Maybe that is an unused sappling graphic. I have no idea all that stuff you are talking about except for "Cave" and "bug" and that you were trying to fix it. I have only coded a little bit in C years ago, and got a c or a d in my C++ class.