Last modified 3 years ago Last modified on 01/27/09 01:48:17

Existing path-finding

The current path-finding uses an A* algorithm with chunks of the map divided into "zones" with several "gateways" that connect them to each other. For travel over longer distances, the code first finds a path to the nearest relevant gateway, then uses existing paths between the gateways to send the droid to the right zone, then calculates a path from that gateway and to the final destination.

New path-finding

Requirements

Threading

For cleaner design and to make effective use of multiple CPUs, the design should be multithreaded, and scale with more threads for multiple cores.

Thus the path-finding code needs to:

  • live in a separate thread, decoupled from the rendering and game logic thread(s);
  • be built in such a way that it can easily be spread across multiple threads.

No zones or gateways

While a neat hack, it turned out to be very hard to make zones and gateways correctly on maps. Even Pumpkin could not do it right.

Thus the path-finding code needs to:

  • perform path-finding on a per-tile basis rather than a per-zone basis.

-> Zones also improve performance. Autodetecting zones might be an idea. --DevUrandom

Clean implementation

Code should be easy to maintain and understand.

Thus the path-finding code needs to:

  • be well-documented, i.e. have plenty of descriptive comments'.

Speed

Needs to be fast. Should handle a hundred path calculations per second. Probably needs aggressive cacheing.

Group moves

Since group movement is very frequently used, these should be optimized, and not run as many path-finding calls.

Thus the path-finding code needs to:

  • perform path-computations only once for a group of droids, rather than once for every droid in a group.
  • The route should be computed only for a single droid (i.e. the "master")
  • All other member droids of the group should then follow the "master"-droid

Different terrain

Different terrain types and slope angles give different movement speed for different propulsion methods, and the code should take that into account.

Design suggestion

We can cache path-finding calculations, so that units that need to go to the same destination from roughly the same source only have to "hook up" to the existing path using dijkstra's. This makes it easy to do group moves and multiple single moves. Also can use roughly the same destination, by doing dijkstra's from destination point. Just need to validate the path - assume that it is fastest for some time (5 of seconds or so) after having first been created, perhaps throw in obstacle avoidance using dijkstra's locally if obstructed. We need to take into account different movement/propulsion properties, eg wheel vs tracks vs hover. With group movement, movement speed/properties are specifically generalized, so this avoids this problem.

In order to avoid collisions with own (allied) units, path steps immediately in front of the unit should be reserved. Reserved tiles have a countdown, which adds to movement cost calculation of units trying to path-find their way through, and in any case they will not enter such tiles and will dijkstra their way out of them if standing on them. Should take into account the future path of the reservee, so that a units in its way are not pushed along the fast lane.

Since path-finding is really computationally intensive, and can easily be parallelized, it should use threads to utilize multiple cpu cores. The main thread should push jobs to work threads (1 + one per additional core over 2) when they are done to avoid having to use write locks anywhere. This means the path-finding code cannot process more than ( threads x game frames per second ) paths per second by design, but that is probably fine.

Procedure:

  • Start a dijkstra search from both source and destination points, alternating between them each step.
  • For each tile, check all cached paths with correct propulsion method, and see if one of their endpoints is equal to the just checked tile and the other endpoint is also checked on our other end. If so, first optimize the path found by moving from the endpoints down the path from each endpoint as long as this reduces its Manhattan distance and we do not move outside the checked area. Second, check if the new endpoints are closer in Manhattan distance to each other than our source and destination points. If so, use this path. If not, mark this path as checked and unusable for us this time.
  • If we did not find a cached path, eventually the two dijkstra searches will meet at some tile. Where it does, generate paths to from both endpoints and splice them to form an optimal, new path.

This design assumes that if an existing, valid and optimal path for a given propulsion has a closer Manhattan distance than our endpoints, it is also more optimal. This should be the case unless I have overlooked something.

Pathfinding in the different versions of Warzone 2100

2.1 path-finding and older

The current Warzone path-finding code is an A* that is split among game frames, so that one large path-finding job does not slow down the game. It tries to reuse existing paths if it finds one (not sure about the exact heuristic it uses). The map is split into a number of zones, each with a number of gateways to other zones. Paths are calculated between these zones, and when a droid calculates a non-trivial path, it calculates a path to its nearest gateway, then uses existing gateway paths to get to the destination zone, then calculates a path from the entry gateway to the destination point. Warzone does not take movement cost into account when deciding on the fastest path - movement cost depends on propulsion and angle of terrain.

A new path-finding code should:

  • Be fast (at least as fast as the current code)
  • Be maintainable (much more easy to bugfix and read than the current code)
  • Not use zones and gateways (too hard for mod/map makers, bad zone/gateway placement really hurt path-finding)

Idea space:

  • We can make much more efficient use of existing paths. We can search for the closest cached path in manhattan distance, and if close enough, do two dijkstra searches, one from start and one from destination, and continue until either 1) we find two ends of the path, or 2) the search spaces meet, in which case the closest existing path was not the best path between start and destination after all. This guarantees that we find the shortest path, as long as no path is shorter than manhattan distance (but this is not strictly speaking true for Warzone, since we can move diagonally).
  • We can assume that an existing path remains valid as shortest path for at least 2-3 seconds after they have been created, and can be reused with simple validity checking in that time frame.
  • In order to avoid collisions with own (allied) units, path steps immediately in front of the unit should be reserved. Reserved tiles have a countdown, which adds to movement cost calculation of units trying to path-find their way through, and in any case they will not enter such tiles and will dijkstra their way out of them if standing on them. Should take into account the future path of the reservee, so that a units in its way are not pushed along the fast lane.
  • For easy lookup in a path, each path could store a map of itself in a bitfield the size of the map.
  • Automatically generate the zones/gateways
  • Store for each block of 4x4 tiles the direction to go for every block on the map (will take 8MiB of memory on a 256x256 map). This will not take into account structures that were built.
  • Make units automatically go in formation when close to an unit traveling (partially) the same path. Calculate only one path for the entire formation, and change formation width to pass trough narrow passages.
  • In general: use the path of nearby units with approximately the same destination (or origin)

2.2 path-finding, and more recent

New in 2.2 is that the path-finding code is multi-threaded, and is no longer arbitrarily broken up into game frames. We also exploit a second (but not third etc yet) CPU, if available. We also no longer make use of gateways and zones. The path management code has become much leaner and cleaner.

The following things are low-hanging fruit to be fixed in regards to improving path-finding:

  • We should fix the bug thatmakes droids go in circles when pushed off their path (​GnaBug:12363)
  • We should improve the AI scripting so that it does not attempt to send droids where they cannot possibly go (eg over water).
  • Find some solution to the problem of droid collisions, because when they get into these mass-collisions they spend a lot of cpu trying to get out.
  • Fix the path recycling algorithm which may have been broken to some extend or another since forever.