2025-12-29

Here is the commit log from last week's work.

2025-12-23
feat: introduce default allocator replacement for context

2025-12-26
feat: introduce "standard library" (sl) with ring buffer and test

2025-12-26
feat: add heap data structure and min-heap procedures to sl

2025-12-27
feat: separate min_heap out of heap impl; add max_heap; add tests

The main focus this week was pathfinding, but I was also up to some other peripheral things as well.

Firstly, we have the introduction of a default allocator replacement for the Jai context. Jai passes around a special variable implicitly to each scope called the context. I think I discussed this earlier, but in short, the context has various useful properties on it such as the currently preferred logging function and the preferred default and temporary allocators. In my case, I want to avoid allocating using the default allocator. I also want to avoid allocating using the temp allocator as much as possible, but I'm less concerned about this because I clear its storage at the beginning of each frame. To catch usage of the default allocator, I implemented my own allocator which just assert(false, "[...]");s on any operation requested of it. I caught a few issues with this, mostly String.join calls, that I fixed using

String.join(...,, allocator=temp);

Note the ,, which is an operator in Jai which allows you to modify context properties at callsites for arbitrary functions. I would like to use my own temporary allocators provided through the most basic of arenas, but for Jai "standard library" things like this, it's easier to use Jai's temporary allocator. I could always implement the allocator interface for my arena and thus use my own backing memory pool, though. Probably a project for a later time.

Toward pathfinding, I have a simple grid map with uniform cost to move between squares. I recalled the standard A* algorithm for pathfinding in such situations. It's been over 10 years since I've dealt with A*, though, so I needed a refresher. I came across Red Blob Games. This blog and the author's few others linked from it are a wealth of information on algorithms for games, particularly top-down, 2D ones such as mine. I highly recommend checking the site out if you're interested in such.

I thought I was going to use a queue, and a ring buffer would work well here, so I implemented one. I followed a great tip from Juho Snellman on using only positive indicies (no forced wrap-around via %) and masking the indicies only when you need to look into the backing storage. Clever and neat.

Now, it turns out I actually wanted a priority queue, so for that I decided to use a min heap. To my knowledge, Jai does not provide a min heap, so I implemented one of those as well. To brush up on that, I referenced the classic Introduction to Data Structures and Alrogithms book. I had learned from this in college as well. After re-reading a very small portion of this recently, I admit I cannot recommend it. It does many things well, but I find it overreaches with its advice in places and also (probably accidentally) misrepresents some concepts by overfitting descriptions on very narrow use cases in specific languages, for example by calling the heap a region of garbage-collected storage. Anyway, it did the job.

I ultimately implemented a heap (heap.jai) and then implemented the min-heap and max-heap interfaces in respective files that both import heap.jai. I reintroduced my "sl" concept from when I was playing with data structure generation via the C preprocessor two or three weeks ago. I have a special file in the sl module called test.jai which provides a main function and imports all of the files in sl and tests their features. I have a build.jai file in sl that builds a binary from test.jai. Building and running the tests is a manual process, but I don't anticipate changing sl so frequently that I'll hurt for any automation, except that one time when I will probably change it, introduce a bug, and forget to run the tests haha.

I then got to implementing A*. The work is on a branch currently and will be the subject of this week's update.

I also started streaming livecoding (and some gaming) on Twitch, as noted in a previous post. The idea here is to maybe build even the smallest of audiences or at least presence in parallel with building the game instead of serializing the process. Presumably an audience takes just as long if not longer to build than the game itself, but what do I know--I'm totally new to this aspect!