One of the first things I did this month was a major change to the game's spatial partitioning. This code is used for broad phase collision detection, culling entities for rendering, querying tile data, and organizing the world into loadable "chunks". The approach I was using before this change was a simple sparse grid of fixed size. Entries could be added and removed by hashing their cell location(simply by dividing their location by the cell size and rounding down), and then looking up their cell from a hash table. This worked great in a lot of ways, since adding and removing was very fast. Unfortunately, using this approach, the code performing a query has to account for the largest entity in the game, since an entity is only added to a cell based on it's position, not it's size. An alternative is that each entity must be added to every cell that they touch, requiring extra logic during queries to ensure a set of unique entities are returned.
Ultimately I decided to change my approach. I had avoided doing this for a long time, and instead preferred to just tweak numbers to account for larger and larger entities. Eventually I decided I wanted a solution that works well for any entity size primarily, and quickly found BVHs:
I replaced my fixed cell size grid solution with a BVH and this solved all functional problems I was having with entity size. I had a bit of trouble implementing this at first, I haven't worked too much with tree data structures directly before. I didn't really get the idea of balancing the tree or the importance of deciding where to insert a leaf. With enough reading on the subject, and messing around with my implementation, I got it working at a reasonable speed. At some point in the future I intend to go back and work on making it better. Inserting is taking much longer than I'd like at the moment, even with a reasonable amount of objects.
Merging Tilemap Collisions
With either of these methods, I wanted to greatly reduce the amount of entities that were in the game. By far(probably up to 90%) the most spawned type of entity was tilemap collisions. The reason for this was their small size. Basically any tile placed on a tilemap can have a small 8px*8px(1m*1m) collision tile, usually a square or a triangle. Altogether this amounted to about 20,000 entities across the entire map, and the game's world isn't even close to being completed yet. My plan was to compose these into minimal convex pieces since I'm only using GJK for collision detection with them anyway, and I'm not relying on their current shape in any way.
First I grouped tiles based on whether they had connecting edges or not. This reduces the problem into only groups of tiles that are touching. Any tiles that aren't connected will never end up being part of the same convex shape.
Collision after composing tiles into concave pieces
This basically leaves us with some amount of separate groups of tile, or just a giant group of points. I wanted to create one giant concave pieces and reduce it from there, but I struggled to do this at first. I started by implementing this:
I found the results to not be precise enough. With k too low, it didn't include all points, and with k too high the shape became too smooth and not precise enough. I guess this isn't surprising since it's a general algorithm for any group of points in space, and by using it, I was basically just throwing away all the information I had about how these tiles connected together.
I gave up on the concave hull solution and managed to come up with something that worked on my own. The idea was to loop over all tiles and record which edges are shared. If an edge is shared by 2 or more tiles, it gets removed. This leaves only the points on the outside of the shape.
Shared edges are in red. Removing shared edges leaves us with just the points on the outside of the shape
Now that we've removed points inside the shape, we need to connect the points together in some way. To do this I used the fact that there are still duplicate points in the data where two edges connect. Since we've removed all inside edges, we can work out how edges should connect. If we have edge A, and edge B, and A's end point overlaps B's end point, we know that A is connected to B in that order. To connect the entire shape, we start with one of our edges from the last step and look for a connection based on what other edge overlaps it's end point. Once we've found that edge, we then find the edge which overlaps it's end point etc. Once we're back to the edge that we started on, we're done and the entire concave shape is connected, with colinear points. I removed colinear points by checking if the point is on the line created between it's previous and next points. This leaves us with a concave shape.
From here I tried a few things to create the convex pieces, but eventually just settled on ear clipping triangulation to reduce the shape to a set of triangles. Right now I still need to merge triangles into larger convex pieces, but overall this process works pretty well.
The final collision triangles
This has greatly reduced the amount of collision entities in the game. It took a long time to implement this entire process. The results are rather slow, but only needs to be done when saving a tilemap(takes about 2-3 seconds to save every tilemap in the game right now), and I'm perfectly happy with this. There is still tones of room for improvement with this implementation. One edge case worth noting is when tiles create a "ring". The process for connecting edges for the concave shape won't work if the shape has "holes" in it. This is avoidable by detecting that the tiles create a ring and treating at least one of them as a different group.
OpenGL optimisation and bug fixing
I spent a pretty large amount of time fixing bugs in and optimsing my OpenGL code. There were a few instances were I was relying on undefined behavior that worked on my Nvidia GPU, but not my Intel GPU. Also, the game was very very slow on my laptop due to rendering.
As I mention before in another update, lighting in Nirion was done while rendering objects. A uniform buffer was used to upload all light data, and then in an object's fragment shader it would loop over all lights and determine the final light colour. Since objects are sorted from back to front in Nirion, this means a pixel might be lit by several lights, several times and not even end up having any lighting effect on the final pixel. I decided to change lighting to be one post processing step at the end of the "layer", just blending with the final screen pixel. This has a few issues when mixed with alpha blending sprites, mainly due to normal mapping. After testing out a few things, I decided that normal maps weren't making a significant enough difference to the visual quality of the game and removed them entirely. Making this change, along with batching more things in general, rendering is now much, much faster on my laptop. I still have a long way to go with performance, but for now it's good enough.
I also performed some preprocessing on tilemaps to remove hidden and unnecessary tiles. I did this in the most naive way possible, looped over each cell and found the tile with the highest layer that did not have any transparent pixels or did not meet any special requirements(needed for collision or other metadata).
As you can see, unnecessary tiles below the grass and rocks have been removed. This would normally be too time consuming to remove by hand. This improved performance a bit, and reduced the amount of tiles on some tilemaps by about 25%.
Tilemap height generation
In Nirion the player can jump down walls and climb up stairs:
The sense of height is just an illusion created by the art, and the engine doesn't really understand that the player just jumped down a level. He just kept falling until he hit a tile where there wasn't a wall. This works pretty well besides a couple of scenarios. Bridges and firing over gaps.
My solution to this before was to have projectiles record whether or not they've crossed over a ledge(just the same collision entity that tells the player that they can jump off) and if they have, don't interact with anything until you cross back over a ledge pointing the other way. This was pretty messy and didn't work a lot of the time. What if the projectile passes over more than two ledges of the same direction in a row? What if you shoot a ledge at a 90 degree angle?
Bridges were handled by painting whether or not a tile was a bridge into tilemaps, and changing a flag on an entity depending on which type they were on. This had a lot of problems around where tiles changed from "bridge" to "not bridge". Overall it was not a good solution, and it was pretty time consuming to make bridges.
My solution to both of these issues was to precompute tile "heights" at build time and use this to determine which height an entity should be on.
Computed height visualisation
An entity can now just check which tile they're on, and determine from that which height they should be at. If they do this every frame however, bridges won't work since they will just select the height that is below the bridge(since a tile query only works in 2D and will ignore bridges). But, if an entity performs this check only when certain conditions are met, bridges can be supported as well.
The player will reevaluate his height only when doing any of these things:
- Falling down a "layer"
- Going up stairs
This means that the height the entity was at when entering a bridge will be maintained until one of these things happen. This is exactly what we want for a bridge, if we were above it, stay above it, and if we were below it, stay below it. Unfortunately, if an entity jumps down onto a bridge, they'll won't get the correct height. Right now I'm just trying to avoid this situation and it hasn't been a problem yet.
To solve the firing a projectile over a gap problem, I just ignore any interactions between entities that have a different height. Overall this approach works really well and allows me to build pretty complex environments using various heights.
Game and level design
For the past week or so I've been focusing on some game and level design. I've added some variety to combat in order to make it more interesting. Before, the player only have one attack per weapon, but now each weapon has a more power alternate attack that can be used on a cooldown:
Drill alt attack
Cannon alt attack
Hopefully these abilities will help make combat a little more interesting. The game isn't solely focused on combat though, so I don't think it needs to get too complex.
I've recently been trying to come up with more interesting level designs and puzzles. The Mines area mainly focuses on pushing around mine carts to solve puzzles. I've been playing around with what will hopefully be some interesting things to do with this idea.
That's most of what I've been doing for the past month or so. Right now I'm planning on doing a lot of level building to complete the first area of the game. Building these areas and making them look nice takes me hours, so I'm a bit worried about how much the entire game will add up to. I am hoping to get a demo released within the next couple of months still.
Let me know if you have any questions or just want me to go more in depth on anything. Thanks!
Also, since I haven't posted it in a blog post yet, here's the gameplay video from about a month ago: