My experience building a path-finding algorithm using Amber

Wed Apr 26 07:02:53 UTC 2023

Hello Amber Dev Team,

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.

https://github.com/davidalayachew/HelltakerPathFinder/tree/a5c8757425c468288a2021e533ac31958f89360f

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).

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.

Here is a link to a rundown of the game's mechanics [1].

On to the code.

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.

* 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.

* 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)

On to the new stuff.

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.

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.

And it's a good thing it was easy because the possible number of states I
had to reason through was extremely large.

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.

Here is a direct link to the path-finding algorithm itself ([4] and [5]).
I'd specifically like to focus on [5].

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.

It ended up being a >60 line switch expression.

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.

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.

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.

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.

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.

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.

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.

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

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.

Here is the strategy -- [10] and [11].

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."

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.

SUCCESS

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.

Thank you all for your time!
David Alayachew

[1]=https://github.com/davidalayachew/HelltakerPathFinder#readme
[2]=https://mail.openjdk.org/pipermail/amber-dev/2022-September/007456.html
[3]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Cell.java
[4]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L69
[5]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Board.java#L487
[6]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/potential_alternatives.txt
[7]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Board.java#L505
[8]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L112
[9]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L95
[10]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L102
[11]=
https://github.com/davidalayachew/HelltakerPathFinder/blob/main/Helltaker/Main.java#L196
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/amber-dev/attachments/20230426/4f74182a/attachment-0001.htm>