Physics & AI

This year, each of us got to pick our specializations. As I'm interested in collaborating more high-level in the future with designers as a gameplay programmer, I chose the module which comes closest to that: Physics & AI.

Coincidentally, this module also turned out to be the easiest of the 3. While graphics programmers were struggling to draw a triangle on the screen, and engine programmers needed  to figure out how to even compile their codebase in the first place, we lucky physics & AI programmers already had an engine and a renderer to work with.

This made especially the first few weeks quite comfortable, and left me with time left over to spend on extra challenges. While this was not my first time encountering pathfinding algorithms, I do not believe I have properly implemented an A* algorithm myself before. Still, that was not challenging enough, so I decided to look into C++ templates and create my own data structure: a Fibonnacci Heap. Fibonnacci Heaps are particularly good to use as priority queues for an A*-algorithm because peeking the minimum element, inserting a new element, and updating the key of an existing element all happen in O(1) time. Only extracting the minimum is in O(log n) because the heap needs to be fixed up. I will not delve into more details here, but this video covers the topic excellently.

Was it necessary to implement a Fibonnacci Heap? Not at all; there was no performance bottleneck at my path finding. If I were to profile my current implementation against one where I'm making use of an std::priority_queue, I would not be surprised to find that the priority queue is more efficient for any practically-sized navmesh graph.

Anyway, after implementing A* search, navmesh generation (well, the CDT library did most of the work), and path following, it was time to focus on physics. This is when I really got to work with the ECS framework of the library I was using. This was my first time working with an ECS really, and I have noticed its advantages. It is actually surprisingly easy to work with once you understand the basic syntax and underlying architecture. I created a separate navigation system for my pathfinding, and a physics system for updating my game objects' positions and velocities through forces, and handling collisions between objects.

What I was most looking forward to was the last two weeks, in which we could implement some gameplay features. I added basic bullets and mines with custom collisions that destroy other agents like everyone else, but on top of that, I liked the idea of having a destructible environment. While I didn't have the time or scope to get into voronoi fracturing, I did make it so mines exploding would push obstacles away, which then in turn updated the underlying navmesh. To make it look a little more realistic, I then also implemented polygon-polygon collisions (so obstacles could push each other), rotational physics, and some damping element (proper friction also fell out of scope).

All in all, I'm quite happy with the end result. I was able to explore technical challenges, as well as design my own features to some extent. The design itself was quite limited though, it was mostly just about adding a cool feature or two. In the end, it is really just a physics simulation rather than a proper game. There's no end goal or progression, and there isn't even a menu. Still, I learned a lot, and compared to last year, I felt I had some more freedom for my own features, which I'm sure will continue being the case this year.