2026-01-03
13:12:43, atom feed.
This week I implemented A* and added support for multiplate enemies to the game.
Here is the commit log for this week's work.
2025-12-27
feat: separate min_heap out of heap impl; add max_heap; add tests
2025-12-27
feat: implementation of A*; access violation in min heap at runtime
2025-12-29
fix: don't attempt min/max_heapify if the heap is empty
2025-12-29
feat: get A* pathfinding working; enemy now chases player
2025-12-30
fix: default to random enemy movement if pathfinding fails
2025-12-30
feat: extend neighbors to include diagonals in pathfinding
2025-12-31
feat: use our own arena for storage in pathfinding
2025-12-31
feat: support multiple enemies: state, pathfinding, rendering
I implemented A* using a priority queue which you can achieve by using a min heap. After implementing the heap itself, in separate files I implemented a min and max heap interface over the data structure. The max heap was just for fun.
The pathfinding signature first looked like this.
path_to :: (
m: Map,
from: Math.Vector2f,
to: Math.Vector2f,
_: *Arena.Arena
) -> Math.Vector2f;
Even though we build a full path from from to to, we only return the next
step from from toward to, since that is all we need from the callsite at
this time. I also thought to use my own arena allocator for the data structures
required in the algorithm, but at first I just used Jai's temp allocator via the
Jai context.
My first pass through A* always assumed we could find a path from one point to another, but this is not necessarily the case. I modified my game map to include a small region enclosed by collision tiles and hard-coded my test enemy's spawn position inside the region. My pathfinding implementation predictably failed, so to fix it, I also tracked whether pathfinding succeeded and returned a flag indicating so.
The final signature looks like this.
next_step_toward :: (
m: Map,
from: Math.Vector2f,
to: Math.Vector2f
) -> dst_reached bool, Math.Vector2f;
You'll notice the arena parameter is missing. However, I do use my own arenas
for all allocations in the implementation. My implementation uses my own
priority queue and also two hash tables, the latter coming from Jai libraries.
The Jai libraries allocate through the context, so I needed to implement a new
Allocator and context-compatible alloc procedure to provide my arena through
the context. Setting up the allocator looks like this:
pathfinding_arena: Arena.Arena;
pathfinding_arena_size :: 40 * (1 << 10); // 40 KiB.
pathfinding_arena.base = Arena.alloc(arena, pathfinding_arena_size);
assert(pathfinding_arena.base != null);
pathfinding_arena.size = pathfinding_arena_size;
pathfinding_allocator := Allocator.{
proc = Arena.jai_arena_allocator_proc,
data = cast(*void)*pathfinding_arena,
};
and the alloc procedure looks like this:
jai_arena_allocator_proc :: (
mode: Allocator_Mode,
size: s64,
old_size: s64,
old_memory: *void,
allocator_data: *void
) -> *void {
arena := cast(*Arena)allocator_data;
ret := null;
if #complete mode == {
case .ALLOCATE;
ret = cast(*void)alloc(arena, cast(u64)size);
if ret == null {
print(
"%:%: arena out of memory\n",
#location().fully_pathed_filename,
#location().line_number);
}
case .RESIZE;
ret = cast(*void)realloc(
arena, cast(*u8)old_memory, cast(u64)old_size, cast(u64)size);
if ret == null {
print("failed to resize with arena allocator\n");
}
case .FREE;
// Do nothing.
case .STARTUP;
assert(false, "attempted startup with arena allocator\n");
case .SHUTDOWN;
assert(false, "attempted shutdown with arena allocator\n");
case .THREAD_START;
assert(false, "attempted thread-start with arena allocator\n");
case .THREAD_STOP;
assert(false, "attempted thread-stop with arena allocator\n");
case .CREATE_HEAP;
assert(false, "attempted create-heap with arena allocator\n");
case .DESTROY_HEAP;
assert(false, "attempted destroy-heap with arena allocator\n");
case .IS_THIS_YOURS;
assert(false, "attempted is-this-yours with arena allocator\n");
case .CAPS;
assert(false, "attempted caps with arena allocator\n");
}
return ret;
}
Before looping over each enemy, I create the pathfinding arena once, and then
I set it on the context (,, allocator=pathfinding_allocator) when calling into
next_step_toward. When the call returns, I reset the arena. This way we only
path the memory cost of a single pathfinding attempt but perform pathfinding n
times. The 40 KiB was determined empirically and will likely need to grow. The
reason the required size is so large for such a small map is explained by the
case .FREE; portion of the allocator function above. As the pathfinding
frontier explores more territory, the hash tables dynamically grow their backing
storage, doubling the backing storage each time. However, I'm not reusing any
memory in my simple arena. Depending on the size and complexity of my maps in
the future, I may want to switch to a more sophisticated allocator. Jai does
provide one or two implementations that I believe can be backed by a
caller-configured memory pool (the implementation of the pool is also provided
with Jai).
As noted in the commit log, when pathfinding does fail, I just default to random movement for the entity it failed for. So, the enemy I force-spawned in the constrained area just moved around randomly.
Initially I did pathfinding only in the cardinal directions, but then I also added diagonals. The cost for moving in any direction is the same currently, but I have an additional heuristic which computes the Manhattan distance between some point on the frontier and the destination, and so this is what has the algorithm prefer diagonal movement over moving in cardinal directions when appropriate. Without this, the player can outrun the enemies by just moving diagonally.
Finally, to fuzz test the implementation of pathfinding more quickly and to make sure I wasn't leaking any memory, I hacked in multiple enemies into the game state.
Here is a video of the pathfinding algorithm and multiple-enemy support in action.
Last week I mentioned that I started live-streaming coding. The VODs are typically available for about 7 days after the stream, but I otherwise lose them. They are also filled with lots of less interesting segments such as me weighing whether to do this or that, me debugging something, or me just playing with designs and experimenting. (If you show up live, feel free to say hi or ask questions. I've had some fun conversations already!) Toward a more permanent log of the journey and more concise summaries of the progress along the way, I started editing the VODs and uploading them to YouTube. The videos are still on the order of tens of minutes, but if you want a digest, please check these out.
With the number of platforms I'm active on growing, I also updated this website to add links to these socials on the footer of all pages with the exception of the landing page which has its own styling.
Next week will be about entity-component-systems (ECS).