Generalize new path finder to A* A* is only usable for a single path, except with a heuristic function returning always zero, which turns it into Dijkstra's algorithm. Distribution uses it that way, because it needs to find multiple paths from the same source as efficiently as possible. Only the other uses of path search can profit from A*'s superior efficiency. I feel the extra complexity is not justified. Besides, it slows down distribution path assembly a bit, which is the only case where efficiency really matters. Let's stick to Dijkstra's for now.
Use the new path finder for sea & air, drop bestownedpath() bestownedpath() is a rather simple-minded breadth-first search. It's slower than the new path finder, and maintaining it in addition to the new path finder makes no sense.
Compute distribution paths center by center This way, we compute all distribution paths from the same center in one go, and thus fully exploit the fast multiple paths from same source capability of Dijkstra's algorithm. Sorting by dist center increases the average length of runs from 4.5 to 73 for my continental test case, and from 3 to 10 for my island test case. Compared to the commit before the previous one, distribution path assembly runs more than 40 times faster for my continental test case, and more than 5 times faster for my island test case. The new path finder now runs my continental test case more than 30 times faster than the old A*, and the island test case more than 6 times, in a fraction of the memory. This makes the continental updates run 3.5 times faster, and the island updates 6% faster. Distribution path assembly no longer dominates the continental update's run time: it takes less than 10% instead of more than 70%. In a sense, this is the path cache done right.
Exploit fast "multiple paths from same source" in distribution Dijkstra's algorithm can find multiple paths from the same source. This is much faster than starting from scratch for every path. Make distribution path assembly work that way. This speeds up runs of distributions to the same center. The next commit will reorder path searches to maximize the length of these runs. It also has benchmark results. Allocates four bytes per sector, actually uses only the first 4*n bytes, where n is the number of distributing sectors.
Optimize Dijkstra's inner loop for hex maps Because the cost to enter a sector is independent of the direction of entry, we visit sectors at most once. Exploit that. Beware: this is not the case for A*. Pitfall for any future generalization to A*. Speeds up distribution path assembly by 35-40% in my tests.
Use the new path finder for land paths, drop old A* This gets rid of the memory leak mentioned in the previous commit. To get rid of the buffer overruns for long paths mentioned in the previous commit, make BestLandPath() fail when path length exceeds 1023 characters. assemble_dist_paths() and move_ground() pass buffers with a different size. Eliminate assemble_dist_paths()'s buffer. Update now works regardless of distribution distance (the distribute command still limits to 1023, to be fixed in a later commit). Enlarge move_ground()'s buffers. Doubles the length of paths accepted by explore, move, and transport. I use two test cases to benchmark the path finders: "continental" (Hvy Metal 2 updates) and "island" (Hvy Plastic 2 updates). The new path finder runs my tests around 3-4 times faster than the old A* without its caches. That's enough to meet its cached performance for "island", but it's only half as fast for "continental". Not for long; big speedups are coming.
New path finder We've been using Phil Lapsley's A* library to find land paths since Chainsaw 3. It's reasonably general, and uses relatively complex data structures to conserve memory. Unfortunately, it occasionally leaks a bit of memory (see commit 86a187c0), and is unsafe for long paths (see commit e30dc417). To speed it up, v4.2.2 added two caches: the neighbor cache and the path cache. The neighbor cache attempts to speed up lookup of adjacent sectors. It allocates 6 pointers per sector for that. In my tests, this is more, sometimes much more memory than the A* library uses. See commit 7edcd3ea on branch old-astar for its (modest) performance impact. The path cache attempts to speed up the update's computation of distribution path costs. There, A* runs many times. Each run finds many shortest paths, of which only the one asked for is returned. The path cache saves all of them, so that when one of them is needed later, we can get it from the path cache instead of running A* again. The cache is quite effective, but a bit of a memory hog (see commit a02d3e9f on branch old-astar). I'm pretty sure I could speed up the path cache even more by reducing its excessive memory consumption --- why store paths when we're only interested in cost? But that's a bad idea, because the path cache itself is a bad idea. Finding many shortest paths from the same source has a well-known efficient and simple solution: Dijkstra's algorithm[*]. A* is an extension of Dijkstra's algorithm. It computes a *single* path faster than Dijkstra's. But it can't compute *many* shortest paths from the same source as efficiently as Dijkstra's. I could try to modify Phil's code to make it compute many shortest paths from the same source efficiently: turn A* into its special case Dijkstra's algorithm (at least for distribution path assembly), then generalize it to the many paths problem. Of course, I'd also have to track down its memory allocation bugs, and make it safe for long paths. Instead, I'm replacing it. This commit is the first step: a rather unsophisticated implementation of Dijkstra's algorithm specialized to hex maps. It works with simple data structures: an array for the hex map (16 bytes per sector), and a binary heap for the priority queue (16 bytes per sector, most of it never touched). This is more memory than Phil's A* uses, but much less than Phil's A* with v4.2.2's caches. [*] To fully exploit Dijkstra's "many paths" capability, we need to compute distribution paths in distribution center order.
License upgrade to GPL version 3 or later Why upgrade? I'm not a lawyer, but here's my take on the differences to version 2: * Software patents: better protection against abuse of patents to prevent users from exercising the rights under the GPL. I doubt we'll get hit with a patent suit, but it's a good move just on general principles. * License compatibility: compatible with more free licenses, i.e. can "steal" more free software for use in Empire. I don't expect to steal much, but it's nice to have the option. * Definition of "source code": modernization of some details for today's networked world, to make it easier to distribute the software. Not really relevant to us now, as we normally distribute full source code. * Tivoization: this is about putting GPL-licensed software in hardware, then make the hardware refuse to run modified software. "Neat" trick to effectively deny its users their rights under the GPL. Abuse was "pioneered" by TiVo (popular digital video recorders). GPLv3 forbids it. Unlikely to become a problem for us. * Internationalization: more careful wording, to harden the license outside the US. The lawyers tell us it better be done that way. * License violations: friendlier way to deal with license violations. This has come out of past experience enforcing the GPL. * Additional permissions: Probably not relevant to us. Also include myself in the list of principal authors.
Document buffer overrun for long land paths BestLandPath(), BestDistPath() and best_path() are unsafe by design: they take a path[] argument without a size, and blindly assume there's enough space. When that's wrong, bp_path() overruns the caller's buffer. move_ground() and assemble_dist_paths() provide space for 512 characters. best(), dist(), path(), att_reacting_units(), s_commod() and do_unit_move() provide space for 1024 characters. A malicious player can arrange paths longer than that, but it takes a lot of land. BestAirPath() and BestShipPath() also take a path[] argument without a size, but they're actually safe: bestownedpath() writes at most 100 (MAXROUTE) characters, perform_mission_bomb() provides space for 512, sorde(), getpath(), do_unit_move() and nav_ship() for 1024.
Fix assemble_dist_paths()'s recovery from invalid dist center The recovery avoided crashing here, but left the path costs undefined. If they happend to be non-negative, dodistribute() still crashed. Set the costs to -1 to avoid that. While there, oops on invalid distribution center.
Speed up export cost calculation in assemble_dist_paths() Import and export paths enter the same sectors, except for the last one. Compute export cost from import cost instead of reverting the import path. Do it in dodistribute(), so that we need to store only import costs.