MAJOR SUCCESS, MAJOR REFECTOR - MAY 2022

This is the month the roads and path finding begin coming together, extremely efficiently. I started the month off with beginning to implement road deletion. Unfortunately, all the work I did to finish up road placement/path tree creation did not consider a fundamental flaw: The graph was being created from the road graphics, not the other way around (as it should have been).

Suffice to say, adding the ability to delete roads with that flaw meant it was nearly impossible to do. Since this was two months ago, I have lost the details of this reality, so I'm not able to give the explanation the justice it deserves.

Having worked on the road/graph code all last month, it was fresh in my head. I began redesigning the road network code such that the graphics outputted to the game is based on an existing graph, not the other way around.

Technically, this work began the last week of April. After playing around with different hash table implementations, I finally discovered the most efficient solution I was looking for. Back in December I envisioned a way to store the path tree/graph in a vector while maintaining constant time access (like a hash table). The solution eluded me until this month. Since hash tables need to use pointers and need to store the hashes, this means it eats up a lot of RAM memory and takes more time to create the container. With vectors (i.e. arrays), the vector's index becomes the key I use, and the since the data is store contiguously in memory, only one pointer is needed to access the container (instead of a pointer for each key-value pair, IIRC). This cut the path tree creation time by 66% and the RAM memory requirements by 75%. That's HHUUGGEE!!!

How am I able to use a vector and still have constant time lookups? By using arithmetic. When a unit arrives at a node, it needs to know the next two nodes to path to (technically, the old second node is just pushed to the first). The nodes are stored in a hash table, and its position-index is the key. What I've done is assign an incremented index (starting at 0) to each node.

Since the unit needs to look at each node it paths to, I grab the ordered index too and use arithmetic to calculate the path tree's key (index position in the vector). Since each path tree for a pair of nodes takes N space (where N is the number of nodes in the graph), all I need to do is multiply the ordered index value by N (which points to the first element of the destination node group in the vector), then add the ordered index value of the start node, then multiply this whole value by the number of path storage slots assigned to each node (which for me is 2, since >99% of the time, there will be 2 or fewer possible turns to make at any node to continue on the shortest path to the units destination.

I further reduced the memory footprint by ~50% by changing the preference weights' types to shorts (2 bytes) from ints (4 bytes), then used efficient struct packing to make sure there were no unused bytes in the container.

After slogging through the graph rewrite, I have no regrets. The LOC needed in the graph-first code is 50% less than the graphics-first code. It was much easier to make the code scaleable so adding larger tiles and different road types in the future wont be a huge headache. Mid May I stopped working on the game for a week to look for a new place to live, which inevitably failed. So many people moved into my state during the pandemic that there are very few places on the market, and the rent is 50% more than pre-pandemic prices. The last feature I added at the end of the month was hot patching the game's art assets. I can now open up Asperite and modify the sprites, save the file, and they will immediately update in the game, live!

Published Date: 06/25/2022
Total Development Time: 6 months