<div dir="ltr"><div class="gmail_default" style="font-family:monospace">Hello Amber Dev Team,<br><br>I just wanted to share my experience with some of the new/preview Amber features such as Sealed Types, Data-Oriented Programming, and Pattern-Matching. Specifically, I wanted to show how things turned out when I used them in a project. This project was built from the ground up to use all of the Amber features from Java 20 (and prior) to their fullest extent. If you want an in-depth look at the project itself, here is a link to the GitHub project. If you clone it, you can run it right now using Java 21 + preview features.<br><br><a href="https://github.com/davidalayachew/HelltakerPathFinder/tree/a5c8757425c468288a2021e533ac31958f89360f">https://github.com/davidalayachew/HelltakerPathFinder/tree/a5c8757425c468288a2021e533ac31958f89360f</a><br><br>The project I built is essentially a Path Finding Algorithm, built for the video game Helltaker (free on Steam if you want to understand the code a little better, but Content Warning -- Occult/Violence/Lewd).<br><br>The project is functionally complete, except for the DLC. Other than that, I am just adding performance improvements. For example, I am in the middle of adding parallelism to the search algorithm. Please ignore the CompletableFuture::completedStage calls in the code, those are placeholder for actual parallelism soon to come later.<br><br>Here is a link to a rundown of the game's mechanics [1].<br><br>On to the code.<br><br>I already had a lot of practice using Sealed Types and Data-Oriented Programming [2], so I took my lessons learned from that to make this project work better than last time. To avoid spending all of my time repeating myself from last time, let me quickly sum up the parts that were the same as last time.<br><br>* Sealed types, records, and switch expressions make refactoring easy and borderline painless. I am still in shock and awe about how quickly I can uproot and replace entire sections of my code base with very little effort. And the error messages point me to exactly what needs to change, leading me down the right path like guard rails, as opposed to being thrown around to different solutions like a pinball machine.</div><div class="gmail_default" style="font-family:monospace"><br></div><div class="gmail_default" style="font-family:monospace">* Converting untyped data into typed data still feels frustrating and difficult. I was able to bypass most of it this time around because, thankfully, this project had very little conversion (whereas my previous project [2] was completely built around that concept)<br><br>On to the new stuff.<br><br>This time around, I added pattern matching to my code. Specifically, record patterns and switch patterns. These 2 features were critical to this project's success because, this time around, I had a very complex hierarchy of types that was not only wide, but deep.<br><br>For example, I made a sealed interface Cell [3] to model the state of each Cell on my grid. Then, I broke that down into more sealed interfaces, records, and enums. Since all elements of this structure were either sealed, a record, or an enum, that meant that my domain of possible types (and thus, solutions) was very bounded. That boundedness made reasoning about my domain much easier.<br><br>And it's a good thing it was easy because the possible number of states I had to reason through was extremely large.<br><br>For example, when building the actual path finding algorithm, I needed to exhaustively handle all possible states that my cells could be. And worse yet, I need to pattern match not just on where the player is, but on the 2 steps in front of them. So I need to exhaustively pattern match on 3 cells, 2 of which have a complex hierarchy of possible states they can be in. Thankfully, sealed interfaces and pattern-matching made this much easier.<br><br>Here is a direct link to the path-finding algorithm itself ([4] and [5]). I'd specifically like to focus on [5].<br><br>Lines 501, 502, and 503 of [5] hold the first, second, and third cells mentioned in the paragraph above. And then 506 onwards is the exhaustive pattern match on all possible states for those 3 cells. I nested switch expressions and used record patterns to handle the branching logic efficiently.</div><div class="gmail_default" style="font-family:monospace"><br></div><div class="gmail_default" style="font-family:monospace">It ended up being a >60 line switch expression.</div><div class="gmail_default" style="font-family:monospace"><br></div><div class="gmail_default" style="font-family:monospace">Trying to do this with if statements instead would have been prohibitively verbose. In fact, for fun, I tried to recreate this same logic in a couple of different ways. Here is the result [6], and compare it to [7]. I don't know what you think, but for me, if I had to write code like [6], I would switch to a different language. I know because I actually tried a very similar project to this in Java, and I had to put it down because I couldn't fit all of the info in my head. Funnily enough, I had the idea for this HelltakerPathFinder back before I knew what pattern matching in Java was. I remember thinking to myself that trying to solve this problem in Java would have been too painful and difficult, and that I should probably use Haskell or JavaScript instead.<br><br>This segues very nicely into my next point. Not only did switch patterns and record patterns allow me to write code that would have been too difficult for me previously, it also freed up my mind to focus on significantly harder problems.<br><br>I set a standard for myself when making this project -- I wanted my algorithm to "beat" the entire game in under 60 seconds. However, early on in the project, I ran into several performance issues. The first level alone was taking minutes to calculate instead of seconds.<br><br>Because my code was so simple and easy to follow along, I was able to use process of elimination and identify the only possible places that inefficiencies could exist. More specifically, because most of my code was so simple and straightforward to follow, I quickly realized that the only problem was that my algorithm was not being intelligent enough.<br><br>Because of that, I was able to make a focused effort on a bunch of different optimization strategies, such as prioritizing directions by likeliness to succeed, distance to the goal, obstacles in the way, etc. None of those strategies ended up bearing any fruit, but they led me to the real solution - short circuiting.<br><br>So then, I tried to short circuit to failure whenever the player was too far from the goal ("as the crow flies") [9]. That gave a significant boost in performance, such that my first level completed in 20 seconds. However, most of the other levels still took over 60 seconds to run each. I needed all 9 levels COMBINED to run under 60 seconds, so again, not good enough.<br><br>After more struggling, I realized that I needed to keep a history of the paths I was taking in order to more intelligently short circuit.<br><br>I tried to save my steps and then tried failing if I retread a cell on the grid, but that didn't work because some puzzles actually require you to retread your steps<br><br>And then I got hit with a flash of brilliance -- if I want to track my steps across the board, I should keep track of the state of the entire board. Meaning, I decided to create a java.util.Map where my key was the entire state of the board for my current attempt (including player location), and the value was the number of steps left on my current attempt. My recursive algorithm was already using immutable copies of the board, so I just passed in a mutable Map, used Map::merge to compare the current path I was on to what was contained within my map, and if the map had an entry, I checked to see if the number of steps left was greater than what was recorded on the map. If the map's value was smaller, I could safely assume that the path I was taking could be short circuited, and I could stop traveling down this branch because all paths from it were guaranteed to be inefficient.</div><div class="gmail_default" style="font-family:monospace"><br></div><div class="gmail_default" style="font-family:monospace">Here is the strategy -- [10] and [11].</div><div class="gmail_default" style="font-family:monospace"><br></div><div class="gmail_default" style="font-family:monospace">I
 remember laughing to myself incredulously when I first thought of it. 
After all, Map keys should be small and simple, like Strings, or tiny 
data aggregations. Not a 2 dimensional List of a very complex data type. And worse yet, my value was a singular Integer. This entire structure was backwards and off. When I tried running it, I thought "Surely this is a terrible idea that shouldn't work."<div class="gmail_default" style="font-family:monospace"><br></div><div class="gmail_default" style="font-family:monospace">Immediately, most of my computation times dropped to less than 1 second. And the most difficult level of the bunch (Chapter 9) only took 15 seconds to complete. Not only was I able to beat the entire game in under 60 seconds, I was able to beat it in under 23 seconds -- less than half the time I had aimed for.</div><br>SUCCESS<br><br>In conclusion, these new Amber features have helped me to solve problems that were previously out of reach. I have tried many times to solve this exact type of problem, but I previously wasn't able to because I was too busy trying to manage things like exhaustiveness and maintainability in my head while I was also trying to optimize the code. Since switch patterns and record patterns allowed me to dissolve away most of the needless complexity, I was able to solve problems I previously would have used other languages for. And even if I had used Haskell or JavaScript, I never would have been able to come up with that short circuiting strategy of carrying the entirety of my board state as keys of a map lol. And with the exception of the data conversion point mentioned very early on, there was really no negatives or downside -- Amber features just felt like a straight improvement of what I was doing before.</div><div><br></div><div><br></div><div class="gmail_default" style="font-family:monospace">Thank you all for your time!<br>David Alayachew<br><br>[1]=<a href="https://github.com/davidalayachew/HelltakerPathFinder#readme">https://github.com/davidalayachew/HelltakerPathFinder#readme</a><br>[2]=<a href="https://mail.openjdk.org/pipermail/amber-dev/2022-September/007456.html">https://mail.openjdk.org/pipermail/amber-dev/2022-September/007456.html</a><br>[3]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Cell.java">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Cell.java</a><br>[4]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L69">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L69</a><br>[5]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Board.java#L487">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Board.java#L487</a><br>[6]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/potential_alternatives.txt">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/potential_alternatives.txt</a><br>[7]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Board.java#L505">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Board.java#L505</a><br>[8]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L112">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L112</a><br>[9]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L95">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L95</a><br>[10]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L102">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L102</a><br>[11]=<a href="https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L196">https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L196</a></div></div>