Drop the bugs documented as fixed. File was last changed in Empire 2,
so these have been fixed for a while...
Remaining bugs:
The classification scheme used by report is dumb.
It still is.
You can make a sector temporarily useless by filling up all its
fields with delivery and distribution information. This is useful
when an enemy is trying to capture the sector (his mil don't have
room to move in :-) You have to halt some of the deliveries or
distributions to make room for the military to move in. (Mostly
fixed by changing the number of available fields)
Fixed since 4.2.14 eliminated `variables'. Delete.
Warehouses can't distribute all commodities simultaneously, due to
limited fields for this information. This becomes a problem if
you have a countrywide network of warehouses distributing to each
other. (Mostly fixed by changing the number of available fields)
Fixed since 4.2.14 eliminated `variables'. Delete.
You can sometimes move small quantities of certain items from
warehouses at no mobility cost, even into mountains (this is my
favorite bug, I'd hate to see it fixed :-)
Feature; delete.
Guerrillas don't seem to carry the plague.
They still don't.
You can sometimes trick someone into paying a huge price for
commodities by changing the price suddenly. Therefore one should
always check prices when buying commodities.
You can't increase prices anymore. Delete.
When two countries are attacking each other simultaneously, you
can sometimes move into a sector he is in the process of
attacking. If you get the timing right, he will take the sector
but you will get it back, along with all his military.
Can't reproduce; delete.
If a plane is out to trade, and gets shot down, it can still be
bought until the next update. If another country builds a new
plane that gets the number of the plane that was shot down, the
new plane will go on the trading market automatically. Then if
that plane is bought, the money goes to the country whose plane
was shot down, not the country that built the plane. I stole
numerous planes (including nuclear missiles :-) this way (by
deliberately putting low numbered planes up for trade, then having
them shot down).
Planes on a trading block can't get shot down, because they can't fly.
They can get destroyed on the ground, though. A new plane with the
same number still goes on the market automatically. Same for ships,
land units and nukes. check_trade() deletes a trade when the object's
owner changed. Reword the paragraph accordingly.
If a plane has negative mobility, then gets traded, mobility goes to 0.
Still correct.
Firing on sectors with land-locked sunken ships does strange
things.
Can't reproduce; delete.
If two countries are cooperating, its possible to raid an enemy
airport and steal the planes by putting them out to trade.
Still correct.
You can also strip enemy sectors of commodities using "sell", if
you have military control temporarily.
Requires mobility now. Delete.
One can make work go back to 100 everywhere in a country by moving
all civil- ians in low-work sectors onto a bridge, then collapsing
the bridge. Work then goes to 100 at the next update, if you
leave some mil in the vacated sectors. Or you can move mil out
too, letting the sector ownership change to the Deity, then move
back in from a 100% working sector, and work goes immediately to
100.
Feature; delete.
Two cooperative countries can move commodities around at no
mobility cost using the market.
Still correct.
You can collapse enemy bridges by making a lightning raid on his
bridgeheads and redesignating them, even if you only hold the
bridgehead for a short time. (In this games, bridges work
differently, see info build, info bridges")
Still correct. The parenthesis is cryptic, though; delete it.
You can map out enemy territory by raiding his radar stations.
Feature; delete.
Condition checking is very treacherous. Global commands with
conditions are unreliable. I never figured out exactly what was
wrong, although I think your method of putting conditions towards
the front of the line helped sometimes.
Can't reproduce; delete.
You can have more than 26 ships in a fleet, but only the first 26
will move when you navigate the fleet (I think 26 is the right
number, but I'm not cer- tain. It might be 32).
Can't reproduce; delete.
"Look" only spots subs (from destroyers) at a certain distance.
If you are too close you won't see them (unless you are in the
same sector).
Can't reproduce; delete.
You can only fly as many planes on a mission as you can fit on the
command line (so low numbered planes have an advantage this way).
USE WINGS
The real issue here is truncation of long input lines. Replace.
When a sector has a visible ship, radar doesn't show whether the
sector is land or sea, just the ship. This has interesting
possibilities for exploita- tion (like land-locking a battleship
in your capital in order to deceive the enemy :-)
Feature; delete.
I don't think you can land planes on a land-locked aircraft
carrier anymore.
Yes, you can. Is that good or bad? Anyway, delete.
Its common to mistakenly set the price of a plane or ship
incorrectly so one should check trade after using set.
Pilot error; delete.
The "must be accepted by" date on offered loans is bogus.
Why is it bogus? The date looks good to me. The offer expires at
that time. Delete.
buy() reads the lot, prompts for input, then writes back the lot,
triggering a generation oops. Any updates made by other threads while
buy() waits for input are wiped out, triggering a seqno mismatch oops.
Since commodities are taken from the seller when he puts them on the
market, and given to the buyer when the trade executes, the wiped out
lot's seller loses his goods without compensation, the other seller
gets to keep his goods, and the buyer receives their duplicates.
This can be abused by two conspiring countries to duplicate
commodities. The seller puts them on the market (say 100 gold bars).
The buyer starts a buy command, and waits at its last prompt for the
lot to be replaced. The seller takes them off the market (possible,
since there's no bid, yet), and sells something else (say one food)
quickly enough to get the same lot number assigned. The buyer then
completes the buy command. The seller loses one food, the buyer gains
100 gold bars.
Replaces a partial fix from v4.0.1, which only caught lots gone away,
not lots replaced by new ones.
Fix setsector and setres not to wipe out concurrent updates
setsector() reads the sector, prompts for input, then writes back the
sector, triggering a generation oops. Any updates made by other
threads while setsector() waits for input are wiped out, triggering a
seqno mismatch oops.
They can still get split by output arriving between two reads from
input, but that's unavoidable, because the client is designed to read
and write big chunks, not lines.
give() reads the sector, prompts for input, updates the sector and
writes it back, triggering a generation oops. Any updates made by
other threads during the yield are wiped out, triggering a seqno
mismatch oops.
Make generation numbers catch more potential yields on input
getstarg(), snxtitem() and snxtsct() can yield the processor, because
they call getstring(). But only for null or empty arguments. For
other arguments, we should call ef_make_stale(), to catch errors.
Problem: if a caller never passes null or empty arguments, it may rely
on these functions not yielding. We'd get false positives. In
general, we can't know whether that's the case. But we do know in the
common special case of player arguments. Call ef_make_stale() for
those.
Without ARG1, display_region_map() formats a rectangular area around
CURX,CURY, so it can use do_map(). Ugly, and duplicates some
unit_map() functionality.
Factor snxtsct_around() out of unit_map(). Inline do_map() into
display_region_map(), so we can use snxtsct_around().
Don't mess with player->condarg. Leftover from when we abused map()
here.
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.