Pathfinding and unit interaction (PUI) is a subsystem in the game responsible for most of the unit movements and interactions.
Great thing about OOP is that smaller tasks inner workings can be tightly wrapped and hid from higher level task. In RTS games units are controlled on a high level of abstraction – Player or AI usually tells them to go from A to B or chase another unit C, without giving specific instruction on how to walk around each tree on the route or what to do if there’s another unit blocking the way. All those details are handled by PUI. Firstly the Pathfinding finds a route from A to B, using various approaches (tilebased or navmeshes or whatever). Then there’s route following and obstacles handling, static like trees and stones, or dynamic like other units. Static obstacle handling is relatively easy – try to walk around it and if failed – rebuild the route. Unit Interaction is trickier, since it’s responsible for dealing with other units, taking into account their state and goals. Sometimes units can just exchange places, sometimes pushed, sometimes wait (and sometimes fought 😉
Our old approach used an in-house tile-based PUI. Units behaved much like chess pieces, without being able to do anything while moving from one tile to another. Drawbacks of the old approach are many. Altogether they all result in clunky unit movement, where units would waste time and feel unresponsive to a player. That was okay for late 90s, when PCs were weak, algorithms scarce and player interaction with the games user-interface was still largely unexplored area.
RVO2 (https://gamma.cs.unc.edu/RVO2/) caught my attention a couple of years ago. Full title is “Reciprocal Collision Avoidance for Real-Time Multi-Agent Simulation”. It’s surprisingly efficient at handling hundreds of actors seemingly effortlessly. For a test I even have ported it to Delphi from C#.
RVO2 has a couple downsides however. It’s focused on unit avoidance, meaning that the rest of the navigation and interaction should be done outside of it (building navmes, doing pathfinding, resolving jams, etc.) It’s free only for non-commercial use, which is fine at the moment, but might be a problem later on (commercial license starts at $500). There are no updates since 2011.
Googling for alternatives revealed there are few. Some are pricey, some are no longer maintained. But there’s one that is a perfect fit with only a tiny bit of a flaw for our project  – Recast & Detour, which is also referenced as RecastNavigation (https://github.com/memononen/recastnavigation). The tiny flaw is the language it is written in – over 1 Mb of code in C++. All of that had to be ported to Delphi if we want to take advantage from RN in our game (or wrapping the code into DLL, which is equally troublesome and debug-unfriendly). Luckily RDC does not use any advanced C++ stuff and does things straight and simple.
Progress is slow because of the vast amount of code and my unfamiliarity with C++ (which is improving). I’m trying to keep the codes as similar as possible, for the ease of bugtracking and updates that might happen in RN master branch.
At the moment I have ported around a half of the RN to Delphi.
Once it’s done I’m planning to upload it to GitHub as port of the original RN. I estimate it will take another few months to complete and rig with our game.
