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.
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.
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.
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.
Relations checking with getrel() often needs a special case for "is
same country". If you forget, you get behavior appropriate for a
neutral foreign country, which is usually very wrong (see commit
16c68eb4 for an example).
Unlike getrel(), relations_with() considers countries allied to
themselves. Less dangerous. In fact, allied behavior is typically
just right, so the special case isn't even needed.
SLOW_WAR has issues:
* The check whether the attacker old-owns the attacked sector is
broken, because att_abort() uses sect.sct_oldown uninitialized.
Spotted by the Clang Static Analyzer.
* Its implementation in setrel() is somewhat scary. It's actually
okay, because that part of setrel() only runs within decl(). Other
callers don't reach it: update_main() because player->god != 0
there, and the rest because they never pass a rel < HOSTILE.
* Documentation is a bit vague.
SLOW_WAR hasn't been used in a public game in years. Fixing it is not
worth it, so remove it instead.
struct trdstr members trd_x, trd_y are used only for teleporting
trades. For others, trad() wrote garbage coordinates to the trade
file. They weren't used except by xdump. Fortunately, even there
they're visible only to deities.
Write invalid coordinates instead. Do that in set() as well, so that
coordinates are valid only when we have a teleport destination.
Spotted by the Clang Static Analyzer.
take_def() and ask_move_in() printed both to the current player and to
land unit owner. Their use of prcom() and xyas() looked particularly
suspicious: they used the current player, then printed the result to
the land unit owner. Fortunately, current player and land unit owner
are the same, since even even deities can't attack with foreign land
units. Normalize to current player for consistency.
Switch get_ototal(), get_oland(), kill_land() and move_in_land() to
current player as well.
Local analysis can now easily find out what's up. Before,
whole-program analysis was required. The Clang Static Analyzer
complained about code that is actually fine.
Oops when a stale copy is written back, i.e. the processor was yielded
since the copy was made. Such bugs are difficult to spot. Sequence
numbers catch them when they do actual harm (they also catch different
bugs). Generation numbers catch them even when they don't.
New ef_generation to count generations. Call new ef_make_stale() to
increment it whenever the processor may be yielded.
New struct emptypedstr member generation. To conserve space, make it
a bit-field of twelve bits, i.e. generations are only recorded modulo
2^12. Make sure all members of unit empobj_storage share it. It is
only used in copies; its value on disk and in the cache is
meaningless. Copies with generation other than ef_generation are
stale. Stale copies that are a multiple of 2^12 generations old can't
be detected, but that is sufficiently improbable.
Set generation to ef_generation by calling new ef_mark_fresh() when
making copies in ef_read() and ef_blank(). nav_ship() and
fltp_to_list() make copies without going through ef_read(), and
therefore need to call ef_mark_fresh() as well. Also call it in
obj_changed() to make check_sect_ok() & friends freshen their argument
when it is unchanged.
New must_be_fresh() oopses when its argument is stale. Call it in
ef_write() to catch write back of stale copies.
Store them and ef_type in bit-fields.
Allocate eight bits for ef_type. Values range from 0 to EF_GAME
(currently 16), so this is plenty.
Allocate twelve bits for sequence numbers. Sequence number mismatches
are now missed when the numbers are equal modulo 2^12. Still
sufficiently improbable.
Common machines store the bit-fields in a 32 bit word. There are
twelve bits left in that word for future use. Total savings 16 bits,
which is exactly what the previous commit spent on wider uids on
common machines.
Before, they were stored as short. Wider uids use more space, but the
next commit will recover it by narrowing other members.
The use of short has always limited the number of ships, planes, land
units and nukes to SHRT_MAX (commonly 32768). Only the most extreme
games ever came close.
Commit 49780e2c (v4.3.12) added struct sctstr member sct_uid to make
struct empobj member uid work for sectors. This made the limit apply
to sectors as well. We've had games with more than 32768 sectors.
Member nws_uid is unused since the commit before previous. Remove it.
Member nws_seqno is of marginal value, because we write news only
through ncache[], and thus aren't prone to the errors sequence numbers
can catch. Remove it.
Make timestamp selector virtual, computing nws_when + nws_duration,
and remove member nws_timestamp. Impact:
* In ncache(), the removed timestamp equals nws_when + nws_duration,
both for new news and updated news. No change.
* delete_old_news() becomes invisible. Before, its move of unexpired
news to the beginning of the news file touched all the timestamps.
That was unwanted, because the move does not change news, only their
storage. Improvement.
* empdump no longer flags the imported news changed via the timestamp.
This is somewhat unfortunate. Document as bug.
With these members removed, struct nwsstr no longer matches struct
emptypedstr, so clear news table flag EFF_TYPED and remove union
empobj_storage member news. This loses the automatic maintenance of
member ef_type via struct emptypedstr. Remove ef_type as well.
This shrinks struct nwsstr from 20 to 12 bytes on common 32 bit
machines, and from 32 to 16 bytes on common 64 bit machines. Since
the server doesn't map the whole news file (EFF_MAP is off), this
reduces I/O, while the table's memory use remains the same.
Historical note: struct nwsstr is now pretty much what it was back in
BSD Empire 1.1. Members ef_type and nws_uid go back to Empire 3 (for
C_SYNC?). v4.3.12 added member nws_timestamp, which doubled the size
on common 64 bit machines. v4.3.15 added nws_seqno.
struct lndstr member lnd_flags is a leftover from Empire3's C_SYNC,
which was ripped out in 4.0.0.
struct lonstr member l_sel, struct nuk_str members nuk_ship, nuk_land,
and struct trtstr member trt_bond have been there basically forever
without any use.
Collateral damage was disabled, because after msl_hit() reported a
miss, the missile may or may not have reached the target.
Fix by splitting msl_launch() off msl_hit().
Drop the disabled collateral damage code for sector targets, because
sectors can't be missed. Enable it for ships and land units.
Since msl_launch() returns whether the missile is sub-launched, drop
launch_missile() parameter sublaunch, and simplify its caller.
Keep only the common part in msl_intercept(), and give it internal
linkage. Wrap new msl_abm_intercept() and msl_asat_intercept() around
it. They are simpler to use.
