Update 6
Last update for 2019!
I've moved on to gameplay-related work (more on that next update), but for now I'd like to show you my progress on pathfinding. I.e, the problem of getting units from point A to point B without looking overly stupid. I'm not interested in doing anything revolutionary here, so I've followed the model they use in StarCraft 2 (see
this excellent presentation). Basically, it creates a triangle mesh that roughly matches the world geometry and then "walks" between triangles to find a path between two points. Here's how it looks in my testbed:
This is a top-down view of a "map" where the boxes with dark lines are impassable objects or walls. The green line shows the computed path between the start and end (green circles).
Tech stuff: I use Constrained Delaunay Triangulation to create the triangle mesh. This took a while to do, since all implementations assume that you have floating point values, and I wanted to do it with only integers (both for speed and for the lockstep network model). I then search for the path using A-star, and smoothen out the path using the Funnel algorithm. I've done some tweaks to the Funnel to allow for units that have a radius.
Here's how the navigation mesh is mapped to a simple ingame map:
The walls create impassable barriers and makes units navigate around them. I made a quick video to show how the navigation looks in action:
The big chunk of work missing in my implementation is all the steering algorithms needed to make units move around other units intelligently. For now, I don't even have unit-to-unit collisions. I'm hoping to make some interesting gameplay without having to delve deeper into that particular rabbit-hole, but we'll see where it goes.