Esoteric Update #287 - Return Of The Cat: Long Update

I'm finally back. I didn't really plan to spend a week in the hospital, much less two. Unfortunately, this did impact my ability to do any work over the last three weeks, in total (because I was already falling very ill before I ended up hospitalised). Still, I'll try to go over what I've done, or at least some of the more interesting parts of it.

Despite what I wrote above, this update will be longer than usual, and the most interesting developments are at the bottom.

1) Engine optimisations and changes

I've optimised some base functionalities in the engine to be more memory efficient while also improving the functionality of the grammar parser, addressing some long-standing issues with it that dated back to the very inception of this project. I also implemented a few additional API tokens to make iterators better accessible from the level of the grammar language and cooperate with the [>_] token.

Furthermore, I looked at the custom distribution code I had for the Gauss and Beta distributions, decided to add a Gamma distribution, and did so. Distributions, in this case, refer to random variables or approaches to getting random values. The simplest continuous distribution is the Uniform distribution, from which we draw any number between the two closed bounds (often 0 and 1) with the same probability. The Gauss distribution, on the other hand, clusters its values around a mean; getting a value lesser than or greater than the mean is equally probable, but it is more likely to get a value closer to the mean over one that is further away. This property makes the distribution a valuable tool for constructing various random models, like those used in procedural generation. For example, if you wanted to assign a random height to a person, it would be better to draw that height from a normal distribution with a mean equal to the average height of a person rather than to do so uniformly. Unfortunately, the issue with the Gauss distribution is that it has no upper or lower limit. While the probability drops the further away from the mean we go, it's still possible to draw a height that makes someone a giant... or worse, a negative height!

So, while the Gauss distribution is open on both sides, Beta is closed on both sides, and Gamma is open on one side. Overall, the three of them are a kind of complete set with similar properties and applications. Unfortunately, the Beta and Gamma distributions have somewhat heavy and ugly code. This unfortunate fact is a mathematical necessity and is not something I can do anything about. However, I could implement limited Beta and Gamma distributions, which work based on integer parameters but are easier (and thus much faster) to calculate. In the process, I've also added the Exponential distribution, which is required for the calculations.

(Gamma Distribution for various parameters. Source: Wikipedia - Gamma Distribution.)

2) Bugfixes and UI

I did some bug fixing with some older code, specifically with how things work for the Minesweeper game; it turned out that some changes along the way slightly broke its interface, so I tidied that up. In the process, I bumped into the concept of real-time gameplay segments, which we implemented a while ago but were never communicated well in the game itself. I fixed that, gave it a UI and tutorialised it.

3) Epitrochoids/hypotrochoids, a.k.a. spirographs

I once started working on code to draw epitrochoids and hypotrochoids, or otherwise, what's known as spirographs (after the toy). I finished it. It's just a toy for making decorations and magic circles.

4) Numerical methods

Because I was reading about/dabbling in some simulations and AI, I needed to implement a few numerical methods to know if I could feasibly continue working with these ideas. I've implemented numerical integration and numerical derivation. It's not as good as analytical integration/derivation, but it does the job well enough.

The implementation is based on specialised iterators in the scripting language, allowing for much flexibility in defining the integrated/derived function.

I might revisit this later, as some work I've been doing with the AI suggests I still need a few other tools. At the very least, I've refreshed my memory on topics such as Gibbs Sampling, Markov Chains, Monte Carlo Methods and a few other related issues.

5) Artificial Intelligence

I've also been working on implementing some common AI solutions/patterns and giving them my own spin. There are three crucial components here: Goal Oriented Action Planning, Behaviour Trees and Utility AI. The intent here is to combine these three elements into a single AI that can control the actions of our NPCs. Do note that these are traditional white-box AI, not Machine Learning approaches. They require a good deal of engagement from the developer to set up, but I prefer white-box solutions.

(Please also note that this doesn't mean we're scrapping any of the AI methods we've developed before. It's more so that they can very much function within this framework. Many of our prior approaches were written to solve particular issues in decision-making, inference, classification, machine learning, etc. These methods can still be used for those tasks and will do better than this general scheme.)

As the concept goes, GOAP allows an NPC to form longer-term plans. Steps of these plans can then be handed off to BTs that can implement the various phases in more detail. At the same time, UAI adds some dynamism and immediate responsiveness to the system, particularly when applied to dynamic structural nodes within a BT. Thus, all these methods come together to emphasise their strengths while reinforcing each system's weak points.

Let's break this down going bottom-up.

5a) Utility AI

Known primarily from The Sims, though they do make their way into other games too, even some FPS titles, Utility AI is a simple system that assigns priorities to specific actions available to the agent based on an evaluation function. In such a system, the agent will choose the action with the highest associated value. While not a very refined method of coming to a decision, it is very reactive and dynamic (given it is set up correctly).

My spin on this method is combining it with Bayesian Networks, where the value associated with an action is the probability that a given variable in the network has in the posterior distribution. Instead of manually assigning polynomials to the actions, this approach draws the values from an assigned Bayesian Network, which is easier to conceptualise/understand and can be presented visually. Furthermore, interestingly, as Bayesian Networks are probabilistic, it places a hard cap on the values of the evaluation and thus makes values from different Networks comparable to each other (perhaps given some weighting attribute, but that is still much easier to handle than uncapped polynomials.

There might be more than can be done with Bayesian Networks, such as estimating the values for unknown variables, but at the moment, that's all I've implemented.

5b) Behaviour Trees

The standard AI model used by Unreal games, Behaviour Trees allow the programmer to define complex and flexible routines for the agents to follow. The system lacks the reactivity of Utility AI, and it doesn't have the long-term planning capabilities of GOAP, but it works very well in the middle layer. That is to say, when the agent already has a clear, immediate objective to work towards and is provided with a behaviour to do so.

I've put a few spins on Behavioural Trees. Apart from implementing the leaf, structural and decorator nodes commonly found in such systems, I've also implemented dynamic structural nodes that can use Utility AI to prioritise actions and... well...

The exact syntax that defines a Behavioural Tree can also be used to specify a more advanced form of a Decision Tree, and the nodes of both trees are cross-compatible so that they can be mixed. This feature becomes useful when a Behavioural Tree might need to run one of several sub-routines, and Decision Tree nodes can be used to (well) decide which one is most appropriate. This is not a crucial feature; it's a side effect of both implementations sharing the same syntax.

5c) Goal Oriented Action Planning

Sometimes, what an agent must do is not immediately apparent, and the agent needs to consider a longer course of action to let them realise that goal. Utility AI cannot do this, and Behaviour Trees can only accomplish this if the whole solution is encoded into the tree. This situation isn't the same as the tree needing to contain all possible atomic actions, but it is also a way of deciding in which order the actions are applied. The complexity explosion is quite severe!

To solve this, we use GOAP, a type of planner that, given a set of atomic actions and a representation of the world state, can figure out some way of approaching the problem step by step. While this style of AI is quite well known academically, deriving from the Stanford Research Institute Problem Solver, the specific application to video games made its debut in the video game FEAR, which also happens to be acclaimed for its intelligent and dangerous enemies.

Unfortunately, this AI was unsuitable for my scripting language, so... I implemented it as a C# library, something I made possible a while ago specifically for situations like this. The implementation itself was initially uneventful. I gave it the Stanford Monkey Problem to solve, and it worked fine, but then I started experimenting with making the problem more complicated, and things started getting pretty interesting.

In one of the tests, the monkey found a solution to the presented problem I didn't even think about, which was much better than the solution I devised on my own, requiring fewer actions and a less convoluted chain of events. But another test really got to me, where I made an error defining the problem and created a physics glitch in the model that the monkey then exploited. It involved the monkey getting on a box and moving it out from underneath itself but remaining elevated, clearly levitating in mid-air (most likely while t-posing menacingly and ook-ooking loudly, just to taunt me).

In any case, the tests went fine apart from one thing. There's a heuristic in the GOAP algorithm that aims to take it from a Dijkstra-equivalent graph search to an A*-equivalent. The issue is that the heuristic, as described, only works when the goal is defined in an overly verbose way. If the goal description is short (counting by the number of propositions used to express it), the heuristic does very little or nothing.

So, my input into this method is a custom heuristic based on favourable and unfavourable modifiers (for the Monkey Problem, this might be things like "it's good to be in the same location as a box", "it's great to hold a banana", "it's pointless to be in room B if there's nothing there", etc.), which guide the system to narrow down the number of states explored. This change made a huge difference when I added superfluous propositions and actions to the problem, reducing the time needed to find a solution by several orders of magnitude.

(Solving a slightly spicier version of the Stanford Monkey Problem, a hole separating locations A and C was added, as well as a ledge joining the two, with a box on top of it; the ledge can only be reached when standing on top of a box. For simplicity of representation, a location can contain only one box. To win, the monkey is required to hold the banana while standing on a box at location A)

(Solving standard Hanoi Tower puzzle with five levels.)

(Note: more information about the details can be found on our Discord.)

For the moment, the methods I've implemented got extensive unit testing, but not yet any integration tests. I'll try to get those done at some point in the near future, but I need to return to the problem of locks on doors, since that's still hanging from before I went to the hospital. Unfortunately, for assorted reasons, I just couldn't get to it when I was bedridden. I know it sounds strange, but being in the hospital isn't so bad for thinking and reading, yet it's awful for writing. This isn't for any particular psychological reasons but rather just from the physical practicality of the matter.