I have a rough idea of how we could improve this. But I can't tell how much slowdown it causes. Basically, I want to buid a "flow" map. Maybe at a reduced resolution to the main map, for performance reasons. So for every 2x2 cells, count the directions the units there want to travel. If there are multiple units going one way, going against the flow gets a penalty in the pathfinding code. The hope is that in typical choke points 2-4 tiles wide, the pathfinding will establish a "two way lane" of preferred travelling tiles just by chance. Or at least, some units might wait on one side letting the other pass through, instead of pushing from both sides until everything comes to a halt.
Alternatively, units that are blocked could in turn mark their tiles als blocked, or at least add a penalty to paths going through there, to encourage other units to use alternate routes.
But before starting on that, I first need to understand some details of how the pathfinding is used in warzone. Is there any documentation available? I know A* quite well, and I have the impression that the pathfinding code could be sped up with some of the newer approaches here (HPA* for example). There are some things in the pathfinding code that probably cause a lot of unneccessary exploration: any tile that is known to be in enemy sensor range gets a penalty factor of 5. Assuming that the sensor range is 10, and you order your units to attack an enemy unit, the A* code currently probably explores a radius of 5*10 into non-enemy territorium trying to find a way to sneak up to the enemy unit without going into this radius (which of course won't work). The problem is that the A* heuristic essentially assumes a flat, unthratened as-the-bird-flies path from any unexplored tile to the destination (unless someone comes up with a better admissible heuristic).
A two-way A* search might be possible to improve here, or the mentioned HPA* approach. HPA* offers also an interesting possibility: approximate the latter half of the path, and only compute the first part in detail. When reaching the end of the refined path, recompute. As the order might be canceled before that, it does save some computations.
Anyway, if we can get the pathfinding faster, it might free up enough resources to add these per-team flow fields, for example, to avoid traffic jams.
Anyone knows whether WZ currently does "steering" (in particular for fast units on hover and VTOL) or assumes that units follow a path on a tile-to-tile basis? There is an interesting framework called OpenSteer. I don't think we should use it in WZ, but it might be good to look at some of the behaviors and add some to WZ. See
http://www.youtube.com/watch?v=dKW-psERFGA
It may be desireable to e.g. use the leader pattern for commanders (except that actually his +x tiles waypoint could serve as a fake leader while he is not targeting an object). Constructor droids on hover should do the arrival behavior to not shoot past a construction site at high speed. Or flocking for group behaviour. We might even want VTOLs to instead of going straight at the target (then slowly turning around) to instead try to do a "fly by shooting", i.e. come in at an angle to pass enemy territory at maximum speed. Or if multiple targets are given, choose a path that attacks them in sequence at max speed. Right now, they would attack the first, turn around, attack it again until its down, then attack the next (just like regular units do). And VTOLs turning around in the range of AA usually means they're down before they get a second attack.
I havn't tried it in some time, I wonder how a fast hover unit goes around a 90° corner. Does it overshoot, or does it step out of the line slightly, then cut the corner tightly? Because the fastest way around a corner at high velocity often looks like this.
Code: Select all
Fast: Slow:
,-._ .._
/ -> | -->
/ +---- |+----
| |#### ||####
\ |#### ||####
||#### ||####
^|#### ^|####
contra principia negantem non est disputandum