Split with parse() and pass first two arguments instead of the raw
tail to the map() callback. Advantages:
* Consistent with do_unit_move().
* Does the right thing when the tail is just spaces. Before, the
spaces got passed to the map() callback, which complained about
syntax. Now, they are ignored. This is what the commit I just
reverted tried to fix.
* Works better when the tail splits into more than two arguments.
Except for explore_map(), which ignores the argument(s), the map()
callbacks use display_region_map(), which split the tail at the
first space, and complained about any spaces in the second part.
Now, display_region_map() takes two argument strings instead of a
single, unsplit argument string, and extra arguments get silently
ignored, as usual.
parse_map_flags() silently truncates map flags after the first 't' or
'r'. This makes it accept arguments "true" and "revert". However, it
also breaks the perfectly sensible argument "ts", which should show
ships just like "st", but doesn't.
info bmap & friends document arguments "true" and "revert", and also
suggest flags 't' and 'r'. What a mess.
Make argument "revert" a special case. Deprecate flag 'r', and clean
up truncation there.
Don't truncate after flag 't'. If any bad flags follow, ignore
everything after 't', but deprecate that usage.
Drop useless checks for player->aborted in draw_map()
player->aborted gets set when we get an interrupt or EOF cookie from
the player, when update or shutdown abort commands, and when we abort
an attack (not relevant here).
The checks are useless: player interrupt and EOF are checked
elsewhere, and update/shutdown can run only when we yield the
processor, which we never do (output doesn't yield because C_MOD is
set).
It misuses snxtsct() and snxtitem() to find out whether the first
argument looks like sectors or like ships, which doesn't work with a
bad conditional argument.
Not worth fixing now; it's been disabled since 4.0.1, and broken at
least since commit 2fc1e74a (v4.3.0) broke its sector/ship
disambiguation via third argument.
Fix do_map()'s misuse of snxtsct() for testing argument syntax
It assumes snxtsct() fails only when the argument can't be parsed. It
can also fail when the condition argument has errors. `map # ?xxx'
first complains about xxx, then maps around ship#0. Broken since
Chainsaw 2 introduced smap, pmap and lmap.
Use sarg_type() to recognize sectors vs. unit argument. `map # ?xxx'
now fails as it should.
Subtle side effect: do_map() no longer prompts for argument "",
because snxtsct() is now guarded by sarg_type(). Impact on callers:
* display_region_map() is not affected, because it never passes "".
* map() passes on "" arguments. Change it to prompt in that case.
Consistent with how other commands behave. No functional change.
* do_unit_move() passes on "" arguments. Keep it that way. This
changes navigate and march sub-commands 'M' and 'B' not to prompt
for "" arguments, which is consistent with sub-command 'm' of move,
test and transport.
snxtsct() and snxtitem() fail when the condition argument is bad.
satmap() didn't check for failure. Due to the way snxtsct() and
snxtitem() work, bad condition arguments were reported and otherwise
ignored.
Redundant information, but incredibly useful when you want to figure
out what happened without a (still nonexistent) journal replay tool.
The redundancy could help making a journal replay tool more robust.
To enable, set econfig key keep_journal to at least 2. Output events
are *not* flushed to disk immediately.
A deity can easily break BRIDGETOWERS by reducing etu_per_update
without compensating customization of buil_tower_bh,
rollover_avail_max or bridge span maxpop.
Document the issue in output of pconfig (which is installed as
$prefix/etc/empire/econfig).
To increase the chance deities actually read the documentation,
disable BRIDGETOWERS.
Reduce bridge tower materials from 400 to 300 hcms.
Bridge spans have been unable to produce enough avail for a tower with
default game configuration since we reduced their maximum population
in commit 6bbd7ffd, v4.3.6. This commit reduces required avail from
160 to 120, fixing the stock game: 100 civilians and 100 uws can make
that much in a 60 ETU update.
Fix march and navigate not to interpret coordinates as path
Destination arguments can be a path or sector coordinates.
do_unit_move() passes the argument buffer to unit_path() to convert
coordinates to a path. If unit_path() fails, do_unit_move() still
interprets the argument as path.
This is correct when unit_path() fails because the argument is not
coordinates. But it can also fail when it is coordinates, namely when
the destination isn't reachable, when the path to it is too long, or
when the ships or land units aren't together. Then do_unit_move()
interprets coordinates as path, and rejects them with "Legal
directions are:".
Except when a land unit's destination read from a march prompt isn't
reachable, because then unit_path() empties the argument buffer that
do_unit_move() uses.
Change unit_path() to succeed when the argument is not coordinates.
Make do_unit_move() discard the argument when unit_path() fails,
i.e. when it is bad coordinates. unit_path() emptying the argument no
longer has an effect, drop it.
Destinations are no longer treated as unreachable when the best path
is longer than 99 characters. Instead, consider up to 1023 characters
of the best path.
Don't claim the destination sector is unreachable when the best path
is longer than 99 characters or the complete path is longer than 1023
characters. Instead, report that the path is too long when the total
path is longer than 1023 characters.
Don't claim the destination sector is unreachable when the best path
is longer than 1023 characters for land units or 99 characters for
ships. Instead, report that the path is too long. Up the limit for
ships to 1023 characters.
Don't compute the distance from the path, use the path cost. The
actual path is no longer needed, and we can use path_find() instead of
BestShipPath().
Destinations are no longer treated as unreachable when the best path
is longer than 1023 characters.
Use path_find() directly where only cost is needed
dist(), att_reacting_units() and s_commod() are only interested in
cost, not the actual path. BestLandPath() and BestDistPath() compute
both cost and path. Use path_find() directly instead.
Destinations are no longer treated as unreachable when the best path
is longer than 1023 characters.
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.
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%.
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.
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.
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.
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.
Optimize assemble_dist_paths() for foreign distribution center
You can't distribute to a foreign sector. This case is relatively
rare. However, unsuccessful path search is relatively expensive, and
the extra check doesn't really slow down the common case.
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.
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.
SAVE_FINISH_PATHS hasn't been used since 4.2.2, remove it
Since 4.2.2, assemble_dist_paths() stores a dummy path instead of the
real path to the dist center. That's possible because distribution
doesn't actually use the path, only whether it exists.
The code to store and free the real path is still around, under #ifdef
SAVE_FINISH_PATHS. Remove it.
Fix bitmap overruns when WORLD_X * WORLD_Y not a multiple of 16
World-sized bitmaps were allocated with size WORLD_SZ() / 8, which
expands to (WORLD_X * WORLD_Y / 2) / 8. The divisions truncate unless
WORLD_X * WORLD_Y is a multiple of 16. The bitmaps were one byte too
small then. Bitmap overruns happen when:
* A lookout looks at one of the last sectors of the sector file.
Besides commands look and llook, this affects navigate and march
sub-command 'l'.
* Command spy spies into one of the last sectors of the sector file.
* A map or nmap (but not a bmap) shows one of the last sectors of the
sector file, or a sector that can see one of the last sectors
(visual range is two sectors at 100% efficiency). Besides commands
lmap, map, nmap, pmap, smap, this affects move and transport
sub-command 'm'.
Diagnosed with valgrind.
Already broken in BSD Empire 1.1 (bitmaps were on the stack then).
We know player != other. Because we can have only one player in state
PS_PLAYING per country, and we know other->state == PS_PLAYING, it
follows that player->cnum != other->cnum. Thus, no functional change.
Adds another call to getnatp() hidden in relations_with(), though.
Keeping that optimized isn't worth it.
Use relations_with() for getrel(NP, THEM) where NP isn't THEM
Replacing getrel(NP, THEM), where NP is known to be getnatp(US), by
relations_with(US, THEM) makes a difference only when US equals THEM.
Replace in places where it's obvious that they're not equal.
Adds a few calls to getnatp() hidden in relations_with(). Keeping
that optimized isn't worth it.
Use relations_with() for US==THEM || getrel(NP, THEM)
Replace patterns like "US == THEM || getrel(NP, THEM)...", where NP is
known to be getnatp(US), by "relations_with(US, THEM)...". No
functional change.
Adds a few calls to getnatp() hidden in relations_with(), though.
Keeping that optimized isn't worth it.
This removes a special case for POGO (#0). Before, unoccupied sectors
were treated as "own or allied" for POGO, but not for other deities.
Impact on callers:
* BestAirPath() is not affected, because the change is only reachable
with a non-null bigmap argument.
* sorde() and nav_ship() pass a non-zero ship owner. sorde() ensures
that itself, and prod_ship() does it for nav_ship().
* unit_path() passes the player number when called with a ship
argument, i.e. in the navigate command. Player number is zero for
POGO. Since deities can't navigate foreign ships, this can happen
only when POGO navigates dead ships. Yes, that's possible, needs
fixing.
* getpath() passes the player number (zero for POGO) when called with
argument P_SAILING, i.e. by the sail command.
Thus, the change makes navigate's and sail's path finding work for
POGO exactly like it does for other deities. That's fine.
No functional change, even though this changes rel[intruder] from
NEUTRAL to ALLIED. Uses of rel[]:
* getilists() and ac_encounter() compare rel[cn] to HOSTILE. No
change, because NEUTRAL and ALLIED are both greater than HOSTILE.
* ac_encounter() compares rel[cn] to ALLIED, but only when cn !=
plane_owner. Because it passes plane_owner as argument for
getilists() parameter intruder, rel[cn] can't refer to the changed
element of rel[] here.
The new value of rel[plane_owner] permits simplifying cn ==
plane_owner || rel[cn] == ALLIED to just rel[cn] == ALLIED.
No functional change, because the change affects only
notified[victim], which isn't used in the loop around
notify_coastguard(), and gets overwritten before the interdiction fire
loop.
Use relations_with() for getrel(getnatp(US), THEM) where US!=THEM
Replacing getrel(getnatp(US), THEM) by relations_with(US, THEM) makes
a difference only when US equals THEM. Replace in places where it's
obvious that they're not equal.
Note: getsect() sets player->owner to "player is god or owns this
sector". Thus, after getsect(..., §), sect.sct_own ==
player->cnum implies player->owner. Conversely, !player->owner
implies sect.sct_own != player->cnum. Similarly for getship(),
getplane() and nxtitem().
projects / empserver / log