Today's update is a terrain overhaul 🏝️
Since the start the islands have been generated by using polar coordinates to sample a simplex noise field, which is how they get their organic swooping shapes. Any sample below zero is considered "water" and does not contribute to an island. Any sample between zero and a low threshold is considered "beach" and will produce one of the heavy but moveable rocks at the edge of the islands. Any sample above the low threshold is considered a "landmass" and contributes to the static unmovable mass of an island.
Nice and simple. The next step is to tell the physics engine about these samples. In all the prototypes up to this point we just generated a separate physics circle for each sample point which is... as efficient as it sounds. This update was the one where I finally triangulated the samples into polygons for the physics engine, so we're running collisions against dozens of triangles instead of thousands of circles.
The process of turning sparse noise samples into polygons is pretty tricky! One of the benefits of working in JavaScript however is access to the sprawling ecosystem of libraries on npm which for the most part "just work" with my vite-based stack. In particular JavaScript has a lot of production-grade mapping and GIS libraries because of how prevalent web mapping is, and what I am doing to process my terrain is basically a baby version of geospatial analysis.
So the trick to turning islands into polygons is basically:
For clustering I used jDBSCAN, an implementation of the DBSCAN algorithm. For the concave hull I used concaveman, an implementation of this paper. For convex hull decomposition I used poly-decomp which matter.js supports natively.
The tricky bit is that for clusters that are big and full of deep "coves" concaveman would "give up" and just close them off.
The dots are noise field samples, the thick yellow line is the concave hull, the thin yellow lines are the convex hulls. You can see it mostly follows the noise field but bridges what would have been a little cove at the top right with a flat line.
concaveman has a concavity parameter to control this but the shapes quickly degenerate if you tweak it too hard. The solution I put in place instead is not perfect (the above image is from the final build) but pretty good nonetheless: Instead of clustering the whole terrain into separate islands and processing each island completely, I first collect the samples into rings based on the polar grid and then I cluster each ring on its own and proceed with everything else as before. That gives us multiple polygons per island, but each "chunk" is smaller and more broken up so there's a better chance we get a nicer hulls.
The dot colors correspond to the different clusters and you can see the ring shapes emerge in the thick yellow lines. This will all be covered by art in the final game but I think these debug graphics look so good 😭
This update also renders the steering offset as an orange line centered at the Orca -- something play testers have asked for!