Since the last devlog there were 5 commits between 2019/03/08 and 2019/03/13, totaling 56 commits. I have worked 20 hours during this period, bringing the total to 142 hours. Yes, this devlog is released over a year late.

Playing fetch is fun, but lack of pathfinding turns minor obstacles into insurmountable ones. So I went down the rabbit hole studying how to implement one.

Tiled based games (which this is) often use a simple A* algorithm to search through the tiles. That is pretty easy to implement and works well, but if you remember the first GIF I showed back in the first devlog, you might notice the character is able to walk around the sign post much closer than just a whole tile size away. That’s because I’m not using a simple walkable/non-walkable tiles collision system.

On top of having more complex collision shapes, I also wanted entities to move naturally towards the target, not from tile to tile. This is achieved by using a navigation mesh. With this approach, I can still use A* to look for paths between two points, but the path will be based on arbitrary convex polygons, not fixed-sized tiles. This can also be faster than tile-based approach, as there’s less nodes to search through.

First problem to solve was generating the navigation mesh. I didn’t want to create one manually, as that would be error-prone and a lot of tedious work. I assumed this would be simple and went into it pretty naively – by cutting out collision rectangles.

Turns out it’s not that simple. This would generate a lot of thin slices. Determining if an entity fits through would also be non-trivial. I thought about optimizing it, but trying to avoid reinventing the wheel, I turned to google for some proper research. Turns out this is quite a big topic, but I found an approach I liked a lot, called Funnel Algorithm. I’m not sure who came up with it first, but a very good resource I found is a thesis called Efficient Triangulation-Based Pathfinding by Douglas Jon Demyen.

I didn’t read it all, as a lot of the math concepts would take me too long to properly understand. But the algorithm itself seemed doable. Everything needed was described in the thesis. While it all seemed simple in principle, it wasn’t a trivial topic once I started thinking about implementation. From generating a triangle mesh, finding a path through the triangles, optimizing it for straight lines and avoiding cutting corners, it added up to quite a task. I estimated it would take me at least a month to implement (looking back, I think it would take longer).

Luckily, there were some implementations of the necessary parts in the open source world. I tried looking for some good-enough looking resources that wouldn’t be horrible to port to Haxe, and to my surprise I found a library implementing it all in a nice package. Enter hxDaedalus.

It’s a mess mesh! It all turned out great and I got it working in a day. Now we can play proper fetch: