12 years agoCompile-time option to use A* for distribution pathfind-test
Markus Armbruster [Sat, 5 Mar 2011 15:05:26 +0000 (16:05 +0100)]
Compile-time option to use A* for distribution

Just for benchmarking.

12 years agoMerge branch 'pathfind-astar' into pathfind-test
Markus Armbruster [Tue, 12 Apr 2011 20:29:40 +0000 (22:29 +0200)]
Merge branch 'pathfind-astar' into pathfind-test

12 years agoGeneralize new path finder to A* pathfind-astar
Markus Armbruster [Sat, 5 Mar 2011 15:04:17 +0000 (16:04 +0100)]
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.

12 years agoCover sea & air in new path finder's regression test-bed
Markus Armbruster [Sat, 26 Feb 2011 15:54:40 +0000 (16:54 +0100)]
Cover sea & air in new path finder's regression test-bed

Make TEST_PATH_FIND cover sea & air paths in addition to land paths.

12 years agoCompile-time option to switch off "multiple paths same source"
Markus Armbruster [Mon, 21 Feb 2011 22:52:42 +0000 (23:52 +0100)]
Compile-time option to switch off "multiple paths same source"

Just to facilitate benchmarking.

12 years agoRegression test-bed for new path finder
Markus Armbruster [Thu, 17 Mar 2011 03:26:45 +0000 (04:26 +0100)]
Regression test-bed for new path finder

Define TEST_PATH_FIND to run both the new and the old code, and verify
they yield the same path costs.

12 years agoMerge branch 'pathfind' into pathfind-test
Markus Armbruster [Tue, 12 Apr 2011 20:07:10 +0000 (22:07 +0200)]
Merge branch 'pathfind' into pathfind-test


modified:   include/path.h
modified:   include/prototypes.h
modified:   src/lib/update/finish.c

12 years agoMerge branch 'old-astar' into pathfind-test
Markus Armbruster [Tue, 12 Apr 2011 19:56:08 +0000 (21:56 +0200)]
Merge branch 'old-astar' into pathfind-test

12 years agoUse the new path finder for sea & air, drop bestownedpath()
Markus Armbruster [Tue, 22 Feb 2011 06:18:41 +0000 (07:18 +0100)]
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.

12 years agoCompute distribution paths center by center
Markus Armbruster [Mon, 21 Feb 2011 22:13:07 +0000 (23:13 +0100)]
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.

12 years agoExploit fast "multiple paths from same source" in distribution
Markus Armbruster [Mon, 21 Feb 2011 21:22:54 +0000 (22:22 +0100)]
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

Allocates four bytes per sector, actually uses only the first 4*n
bytes, where n is the number of distributing sectors.

12 years agoNew path_find_visualize(), to aid debugging
Markus Armbruster [Mon, 21 Feb 2011 21:49:44 +0000 (22:49 +0100)]
New path_find_visualize(), to aid debugging

12 years agoAdd performance statistics to path finder
Markus Armbruster [Mon, 21 Feb 2011 21:30:41 +0000 (22:30 +0100)]
Add performance statistics to path finder

New function path_find_print_stats() prints a few numbers of interest
when compiled with PATH_FIND_STATS defined.

12 years agoOptimize Dijkstra's inner loop for hex maps
Markus Armbruster [Sat, 26 Feb 2011 16:40:13 +0000 (17:40 +0100)]
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.

12 years agoUse the new path finder for land paths, drop old A*
Markus Armbruster [Sat, 26 Feb 2011 15:06:09 +0000 (16:06 +0100)]
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.

12 years agoNew path finder
Markus Armbruster [Mon, 21 Feb 2011 19:38:09 +0000 (20:38 +0100)]
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

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

[*] To fully exploit Dijkstra's "many paths" capability, we need to
compute distribution paths in distribution center order.

12 years agoSpeed up A* neighbor cache hits old-astar
Markus Armbruster [Thu, 24 Feb 2011 18:29:33 +0000 (19:29 +0100)]
Speed up A* neighbor cache hits

struct sctstr members sct_x, sct_y are normalized, no need to
normalize them again.

The neighbor cache now speeds up distribution path assembly by about
10% without the path cache, and by about 5% with the path cache.

12 years agoPermit disabling of A* neighbor cache at compile-time
Markus Armbruster [Sun, 20 Feb 2011 07:43:44 +0000 (08:43 +0100)]
Permit disabling of A* neighbor cache at compile-time

Mostly to measure its effectiveness.  Compile with
AS_NO_NEIGHBOR_CACHE defined to disable it.

The neighbor cache turns out to be useless in my tests: it eats memory
without speeding up the update's distribution path assembly.

12 years agoPermit disabling of A* path cache at compile-time
Markus Armbruster [Sat, 19 Feb 2011 14:00:03 +0000 (15:00 +0100)]
Permit disabling of A* path cache at compile-time

Mostly to measure its effectiveness.  Compile with AS_NO_PATH_CACHE
defined to disable it.

Turns out the path cache is quite effective.  For my continental test
case (Hvy Metal 2 updates), it reduces the number of searches by a
factor of 18.5, speeding up distribution path assembly by a factor of
7.  The price is memory: it uses 135 times more memory than the A*
library.  For my island test case (Hvy Plastic 2 updates), I get 4
times search reduction, 3.5 times faster distribution path assembly,
36 times more memory.

12 years agoFix when best_path() prints A* performance statistics
Markus Armbruster [Sat, 19 Feb 2011 12:50:10 +0000 (13:50 +0100)]
Fix when best_path() prints A* performance statistics

Print them when A* actually runs, not when best_path() finds a path.
Statistics for unsuccessful runs were lost, and old statistics were
printed for path cache hits.

12 years agoA* path and neighbor cache performance statistics
Markus Armbruster [Sat, 19 Feb 2011 12:19:27 +0000 (13:19 +0100)]
A* path and neighbor cache performance statistics

as_clear_cachepath() now prints cache hits, misses, number of entries,
and memory use to stderr, when compiled with AS_STATS defined.

12 years agoMore precise and complete A* performance statistics
Markus Armbruster [Sat, 19 Feb 2011 09:47:32 +0000 (10:47 +0100)]
More precise and complete A* performance statistics

Memory usage didn't include path (adp->path), neighbor cache
(adp->neighbor_coords, adp->neighbor_nodes), and the hash table

While there, print path length.

To get A* statistics on stderr, compile with AS_STATS defined.

12 years agoClean up A* sector cache leftovers
Markus Armbruster [Fri, 18 Feb 2011 19:08:26 +0000 (20:08 +0100)]
Clean up A* sector cache leftovers

The sector cache was disabled in v4.2.2, and dropped in commit
8f40f5ad, v4.2.20.  A bit of cache statistics code was left behind.
Remove it.

12 years agoLicense upgrade to GPL version 3 or later
Markus Armbruster [Mon, 21 Feb 2011 18:37:40 +0000 (19:37 +0100)]
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.

12 years agoDocument buffer overrun for long land paths
Markus Armbruster [Sun, 20 Mar 2011 09:06:33 +0000 (10:06 +0100)]
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

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.

12 years agoRemove pointless check for sea from finish_sects()
Markus Armbruster [Fri, 25 Feb 2011 18:45:46 +0000 (19:45 +0100)]
Remove pointless check for sea from finish_sects()

Checking "sea or unowned" is pointless, because sea is always unowned.

12 years agoOptimize assemble_dist_paths() for foreign distribution center
Markus Armbruster [Fri, 25 Feb 2011 18:40:08 +0000 (19:40 +0100)]
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.

12 years agoOptimize dodistribute() for sectors with no distribution center
Markus Armbruster [Fri, 25 Feb 2011 07:08:05 +0000 (08:08 +0100)]
Optimize dodistribute() for sectors with no distribution center

import_cost is now -1 in that case, so checking that suffices.

12 years agoFix assemble_dist_paths()'s recovery from invalid dist center
Markus Armbruster [Fri, 25 Feb 2011 07:00:59 +0000 (08:00 +0100)]
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.

12 years agoSpeed up export cost calculation in assemble_dist_paths()
Markus Armbruster [Sat, 19 Feb 2011 07:21:33 +0000 (08:21 +0100)]
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.

12 years agoSupply charged mobility for backward path
Markus Armbruster [Fri, 18 Feb 2011 19:05:32 +0000 (20:05 +0100)]
Supply charged mobility for backward path

It used the path from supply recipient back to supply source.  Has
always been broken that way.

12 years agoDocument memory leak in as_search()
Markus Armbruster [Fri, 18 Feb 2011 18:10:28 +0000 (19:10 +0100)]
Document memory leak in as_search()

12 years agoMake bestpath work for deities in foreign land
Markus Armbruster [Fri, 18 Feb 2011 18:29:29 +0000 (19:29 +0100)]
Make bestpath work for deities in foreign land

Before, it only worked in land owned by the deity.

As always, paths can't cross international borders.

12 years agoMerge dodistribute() parameters dist_i_cost, dist_e_cost
Markus Armbruster [Fri, 18 Feb 2011 18:07:31 +0000 (19:07 +0100)]
Merge dodistribute() parameters dist_i_cost, dist_e_cost

Only one of them is used, depending on argument imex.  Replace them by
a single parameter path_cost.

12 years agoRemove dodistribute() parameter path
Markus Armbruster [Fri, 18 Feb 2011 18:01:25 +0000 (19:01 +0100)]
Remove dodistribute() parameter path

It was only used to see whether a path to the dist center exists.  Use
negative cost for that.

12 years agoSAVE_FINISH_PATHS hasn't been used since 4.2.2, remove it
Markus Armbruster [Fri, 18 Feb 2011 17:53:37 +0000 (18:53 +0100)]
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

12 years agoPrint distribution costs when compiled with DISTRIBUTE_DEBUG
Markus Armbruster [Fri, 25 Feb 2011 05:13:23 +0000 (06:13 +0100)]
Print distribution costs when compiled with DISTRIBUTE_DEBUG

12 years agoCollect path-related stuff in path.h
Markus Armbruster [Sun, 11 Jul 2010 09:30:02 +0000 (11:30 +0200)]
Collect path-related stuff in path.h

12 years agoLog distribution path assembly's CPU use (user and system time)
Markus Armbruster [Wed, 16 Mar 2011 17:25:18 +0000 (18:25 +0100)]
Log distribution path assembly's CPU use (user and system time)

12 years agoLog update's CPU use (user and system time)
Markus Armbruster [Wed, 16 Mar 2011 17:24:58 +0000 (18:24 +0100)]
Log update's CPU use (user and system time)

12 years agoFleshed out getrusage() stub for Windows
Ron Koenderink [Sat, 19 Mar 2011 22:05:35 +0000 (16:05 -0600)]
Fleshed out getrusage() stub for Windows

12 years agoProvide a getrusage() stub for Windows
Markus Armbruster [Wed, 16 Mar 2011 06:16:21 +0000 (07:16 +0100)]
Provide a getrusage() stub for Windows

12 years agoMake savecore mind available disk space
Markus Armbruster [Sun, 13 Mar 2011 13:23:13 +0000 (14:23 +0100)]
Make savecore mind available disk space

12 years agoMake savecore check core file is accessible
Markus Armbruster [Sun, 13 Mar 2011 13:22:30 +0000 (14:22 +0100)]
Make savecore check core file is accessible

12 years agoFix bitmap overruns when WORLD_X * WORLD_Y not a multiple of 16
Markus Armbruster [Mon, 28 Feb 2011 05:58:51 +0000 (06:58 +0100)]
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).

12 years agoFix pathrange()'s computation of the range's right limit
Markus Armbruster [Fri, 18 Feb 2011 18:36:55 +0000 (19:36 +0100)]
Fix pathrange()'s computation of the range's right limit

Because of the bug, the path command's maps weren't always fitted to
the path correctly.  Broken in commit 0f458d2c, v4.3.17

12 years agoLand units no longer hit allied mines
Markus Armbruster [Sun, 6 Feb 2011 15:28:12 +0000 (16:28 +0100)]
Land units no longer hit allied mines

12 years agoUse relations_with() in sendmessage()
Markus Armbruster [Sun, 6 Feb 2011 09:29:14 +0000 (10:29 +0100)]
Use relations_with() in sendmessage()

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.

12 years agoUse relations_with() for getrel(NP, THEM) where NP isn't THEM
Markus Armbruster [Sun, 6 Feb 2011 09:27:45 +0000 (10:27 +0100)]
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.

12 years agoUse relations_with() for US==THEM || getrel(NP, THEM)
Markus Armbruster [Sun, 6 Feb 2011 09:06:38 +0000 (10:06 +0100)]
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.

12 years agoUse relations_with() in unit_interdict()
Markus Armbruster [Tue, 1 Feb 2011 06:49:32 +0000 (07:49 +0100)]
Use relations_with() in unit_interdict()

No functional change, because the value of rel only matters when cn !=
victim, and then it's the same as before.

The new value of rel permits simplifying cn != victim && rel <=
NEUTRAL to just rel <= NEUTRAL

12 years agoUse relations_with() in owned_and_navigable()
Markus Armbruster [Sun, 30 Jan 2011 17:32:19 +0000 (18:32 +0100)]
Use relations_with() in owned_and_navigable()

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

* 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.

12 years agoUse relations_with() in getilists()
Markus Armbruster [Sun, 30 Jan 2011 16:37:36 +0000 (17:37 +0100)]
Use relations_with() in getilists()

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.

12 years agoUse relations_with() in nav_loadship()
Markus Armbruster [Sun, 30 Jan 2011 16:10:43 +0000 (17:10 +0100)]
Use relations_with() in nav_loadship()

No functional change, because the value of rel only matters when
sectp->sct_own != sp->shp_own, and then it's the same as before.

The new value of rel permits simplifying sectp->sct_own == sp->shp_own
|| rel >= FRIENDLY to just rel >= FRIENDLY.

12 years agoUse relations_with() in shp_fort_interdiction()
Markus Armbruster [Sun, 30 Jan 2011 15:39:38 +0000 (16:39 +0100)]
Use relations_with() in shp_fort_interdiction()

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

12 years agoUse relations_with() in lnd_mar_one_sector()
Markus Armbruster [Sun, 30 Jan 2011 15:31:02 +0000 (16:31 +0100)]
Use relations_with() in lnd_mar_one_sector()

No functional change, because the value of rel only matters when
sect.sct_own != actor, and then it's the same as before.

The new value of rel permits simplifying sect.sct_own != actor && rel
!= ALLIED to just rel != ALLIED.

12 years agoUse relations_with() in player_relstr()
Markus Armbruster [Sun, 30 Jan 2011 15:26:22 +0000 (16:26 +0100)]
Use relations_with() in player_relstr()

No functional change, because argument is never player->cnum.

12 years agoUse relations_with() for getrel(getnatp(US), THEM) where US!=THEM
Markus Armbruster [Sat, 29 Jan 2011 13:34:40 +0000 (14:34 +0100)]
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), sect.sct_own ==
player->cnum implies player->owner.  Conversely, !player->owner
implies sect.sct_own != player->cnum.  Similarly for getship(),
getplane() and nxtitem().

12 years agoUse relations_with() where its different value doesn't matter
Markus Armbruster [Sun, 30 Jan 2011 10:46:17 +0000 (11:46 +0100)]
Use relations_with() where its different value doesn't matter

Switching from getrel() to relations_with() can change the value from
NEUTRAL to ALLIED.  The change doesn't matter when the value's only
compared to HOSTILE, as both old and new value are greater than
HOSTILE.  Likewise for >= NEUTRAL.

12 years agoUse relations_with() for US==THEM || getrel(getnatp(US), THEM)
Markus Armbruster [Wed, 26 Jan 2011 18:41:28 +0000 (19:41 +0100)]
Use relations_with() for US==THEM || getrel(getnatp(US), THEM)

Replacing getrel(getnatp(US), THEM) by relations_with(US, THEM) makes
a difference only when US equals THEM.

Replace patterns like "us == them || getrel(getnatp(us), them)..." by
"relations_with(us, them)...".

12 years agoRearrange uses of getrel() slightly
Markus Armbruster [Sat, 29 Jan 2011 08:57:21 +0000 (09:57 +0100)]
Rearrange uses of getrel() slightly

Just to make the next few commits easier to review.

12 years agoEliminate a few pointless relations variables
Markus Armbruster [Sat, 29 Jan 2011 12:09:26 +0000 (13:09 +0100)]
Eliminate a few pointless relations variables

Just to make the next few commits easier to review.

12 years agoNew relations_with()
Markus Armbruster [Tue, 25 Jan 2011 19:13:41 +0000 (20:13 +0100)]
New relations_with()

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.

12 years agoPermit sharebmap with yourself
Markus Armbruster [Sun, 30 Jan 2011 17:37:02 +0000 (18:37 +0100)]
Permit sharebmap with yourself

Does nothing.  Before, it failed with a mildly bogus "does not have
friendly relations towards you" message.

12 years agoMake share_bmap() do nothing for sharing with oneself
Markus Armbruster [Wed, 19 Jan 2011 20:05:44 +0000 (21:05 +0100)]
Make share_bmap() do nothing for sharing with oneself

Before, it overwrote '?', '.', ' ' in the bmap with the capitalized
country letter, but only for sectors the player owns.  Pretty
harmless, just weird.  It can't happen currently, because sharebmap
with self fails with "does not have friendly relations towards you".

12 years agoPermit flash to yourself
Markus Armbruster [Sat, 5 Feb 2011 11:50:50 +0000 (12:50 +0100)]
Permit flash to yourself

Flashing yourself failed with a bogus "not logged on" message for
deities, and a mildly bogus "not a deity or friendly with us" message
for mortals.

Fix by simply permitting it.  Not terribly useful, except perhaps for
empire-hub users, but why not.

12 years agoDrop redundant chat(), sendmessage() parameter us
Markus Armbruster [Sat, 5 Feb 2011 11:48:10 +0000 (12:48 +0100)]
Drop redundant chat(), sendmessage() parameter us

It can't be anything but the current player.

12 years agoClean up confusing control flow in sendmessage()
Markus Armbruster [Sat, 5 Feb 2011 10:30:32 +0000 (11:30 +0100)]
Clean up confusing control flow in sendmessage()

The second patch hunk fixes a latent bug.  Before, rejected deity
flashes led to a bogus "not logged on" message, now they lead to a
"not accepting" message.  But deity flashes can't be rejected, so this
doesn't matter.

12 years agoOptimize sendmessage() use of getnatp()
Markus Armbruster [Sat, 5 Feb 2011 10:17:40 +0000 (11:17 +0100)]
Optimize sendmessage() use of getnatp()

Don't call it when its value must be TO anyway.

While there, oops when it fails instead of recovering silently.

12 years agoFix racy detection of ally rejecting flashes
Markus Armbruster [Sat, 5 Feb 2011 10:09:37 +0000 (11:09 +0100)]
Fix racy detection of ally rejecting flashes

sendmessage() checked NF_FLASH on two places: when deciding whether to
send the message, and later when telling the player why it didn't send
a flash.  This can race with the toggle command as follows: if a flash
could not be sent because the recipient's NF_FLASH was off, and the
recipient toggled it on before the flag was checked again, the flash
command claimed the sender wasn't logged on.

12 years agoChange flash not to print "Flash sent" for deities
Markus Armbruster [Sat, 5 Feb 2011 09:42:58 +0000 (10:42 +0100)]
Change flash not to print "Flash sent" for deities

It's annoying.  It never did that for mortals.

12 years agoRemove pointless variables from setrel()
Markus Armbruster [Sat, 5 Feb 2011 09:18:30 +0000 (10:18 +0100)]
Remove pointless variables from setrel()

12 years agoMake setrel() refuse to change relations to self
Markus Armbruster [Sat, 5 Feb 2011 08:31:44 +0000 (09:31 +0100)]
Make setrel() refuse to change relations to self

No current caller actually attempts that, but let's make it obvious.

12 years agoChange setrel(), setcont(), setrej() to return void
Markus Armbruster [Sat, 5 Feb 2011 08:30:12 +0000 (09:30 +0100)]
Change setrel(), setcont(), setrej() to return void

Nobody cares for their value anyway.

12 years agoOops on invalid arguments in setrel(), setcont(), setrej()
Markus Armbruster [Sat, 5 Feb 2011 08:28:05 +0000 (09:28 +0100)]
Oops on invalid arguments in setrel(), setcont(), setrej()

Before, they recovered silently.

12 years agoUse feels_like_helping() in dosupport(), lnd_support()
Markus Armbruster [Mon, 31 Jan 2011 19:53:44 +0000 (20:53 +0100)]
Use feels_like_helping() in dosupport(), lnd_support()

feels_like_helping() case cn == foe is missing in the code it
replaces.  No difference in behavior, because:

* cn == foe && cn == friend can't happen.  Because you can't get into
  ground combat against yourself (assault, attack and paradrop don't
  let you), friend != foe for support.

* cn == foe && cn != friend behaves the same: no support.
  feels_like_helping() returns 0 because of the explicit case.  The
  replaced code doesn't support because cn can't be at war with

12 years agoFactor feels_like_helping() out of quiet_bigdef(), sd(), dd()
Markus Armbruster [Mon, 31 Jan 2011 19:46:53 +0000 (20:46 +0100)]
Factor feels_like_helping() out of quiet_bigdef(), sd(), dd()

12 years agoPlug memory leaks in mission execution code
Markus Armbruster [Mon, 31 Jan 2011 06:56:44 +0000 (07:56 +0100)]
Plug memory leaks in mission execution code

Mission execution first builds lists of eligible units, one list per
country.  These lists are passed to perform_mission() one by one,
where they get freed.


* unit_interdict() didn't pass the list for the submarine's owner, but
  build_mission_list_type() built one.  Any submarine movement within
  own submarine interdiction mission op areas leaked memory.

* dosupport() passed only lists for countries that actually support
  (ally at war with victim), but build_mission_list_type() built lists
  for all countries hostile to the victim.  Ground combat within
  support mission op areas countries that are hostile to one of the
  party without actually supporting the other leaked memory.

* perform_mission() failed to free missiles targeting units.

Fixing the latter is straightforward.

Fix the first two by deciding whether a country acts on a mission
trigger before building any lists, in ground_interdict(),
unit_interdict(), dosupport().  Remove the code dealing with that from
build_mission_list_type() and the loops around perform_mission().

12 years agoMove code from def_support(), off_support() to dosupport()
Markus Armbruster [Mon, 31 Jan 2011 19:02:23 +0000 (20:02 +0100)]
Move code from def_support(), off_support() to dosupport()

12 years agoEliminate nav_loadship() variables landown, shipown
Markus Armbruster [Sun, 30 Jan 2011 16:08:00 +0000 (17:08 +0100)]
Eliminate nav_loadship() variables landown, shipown

Code is clearer without them.  Works because load_it() never changes
ship or sector owner.

12 years agoDrop redundant nav_loadship() parameter cnum
Markus Armbruster [Sun, 30 Jan 2011 15:55:15 +0000 (16:55 +0100)]
Drop redundant nav_loadship() parameter cnum

12 years agoEliminate nav_ship() variable cnum
Markus Armbruster [Sun, 30 Jan 2011 15:54:19 +0000 (16:54 +0100)]
Eliminate nav_ship() variable cnum

Code is clearer without it.

12 years agoOops on invalid actor and victim arguments in nreport()
Markus Armbruster [Sun, 30 Jan 2011 15:12:14 +0000 (16:12 +0100)]
Oops on invalid actor and victim arguments in nreport()

Replaces the existing, silent recovery from invalid victim argument.

12 years agoClean up use of current player in march code
Markus Armbruster [Sat, 29 Jan 2011 09:40:59 +0000 (10:40 +0100)]
Clean up use of current player in march code

lnd_mar() and lnd_mar_one_sector() take an actor argument.
Nevertheless, they sometimes used player->cnum.  Fortunately, they are
the same: all callers pass current player for actor.  Normalize to
actor for consistency.

12 years agoFix land unit attack mobility cost out of allied sectors
Markus Armbruster [Sun, 23 Jan 2011 18:39:48 +0000 (19:39 +0100)]
Fix land unit attack mobility cost out of allied sectors

Land units pay a mobility penalty when marching into a non-old-owned
sector without sector mobility, to slow them down in newly taken
sectors.  Attacking land units pay this penalty regardless of sector

When attacking out of an allied sector, the penalty was computed as if
the land unit was owned by that ally.  Attacking sectors old-owned by
that ally was too cheap, and taking back one's own was too expensive.

Broken since attacking land units pay the "newly taken" mobility
penalty: commit 2e693275, v4.3.6.

12 years agoFix attack when attacking sector gets taken by ally
Markus Armbruster [Thu, 20 Jan 2011 06:49:44 +0000 (07:49 +0100)]
Fix attack when attacking sector gets taken by ally

When an attacking sector got lost while the player was at a prompt,
and the new owner was allied to the player, the server got confused:

1. If the sector attacked with mil, the server let the ghost mil
attack, but not occupy.

2. If the sector was allied, the server reported the sector loss and
land units dropping out of the attack, but claimed the lost sector was

Fix 1. by dropping sectors from attack when they change owner away
from the player, regardless of relations.  Side effect: also drops any
surviving land units there.  Before, they dropped out only if the new
owner wasn't allied to the player.  That change's okay.

Fix 2. the obvious way: change the messages.

Broken in 4.0.0.

12 years agoFix trade ships to pay off in own harbor
Markus Armbruster [Sun, 16 Jan 2011 20:20:28 +0000 (21:20 +0100)]
Fix trade ships to pay off in own harbor

Broken in commit 3318e4e4, v4.3.17.

12 years agoRemove option SLOW_WAR
Markus Armbruster [Sun, 9 Jan 2011 18:03:38 +0000 (19:03 +0100)]
Remove option SLOW_WAR

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.

12 years agoFix nightly's sandbox cleanup not to hang when stdin is a tty
Markus Armbruster [Sat, 15 Jan 2011 13:39:30 +0000 (14:39 +0100)]
Fix nightly's sandbox cleanup not to hang when stdin is a tty

"rm -r" prompts for read-only files when stdin is a tty.  Probably
broken since we install builtin configuration read-only, in commit
b4161cd7, v4.3.0.

Move "done" message to the right place.  Broken in commit 70c03561,

12 years agoFix nightly's check for existing sandbox
Markus Armbruster [Sat, 15 Jan 2011 12:47:16 +0000 (13:47 +0100)]
Fix nightly's check for existing sandbox

Broken in commit 70c03561, v4.3.12.

12 years agoClean up a useless use of cat
Markus Armbruster [Sat, 15 Jan 2011 12:46:43 +0000 (13:46 +0100)]
Clean up a useless use of cat

12 years agoFix make clean to remove info.ps
Markus Armbruster [Sun, 15 Aug 2010 09:18:31 +0000 (11:18 +0200)]
Fix make clean to remove info.ps

Missed in commit 9067d7a4.

12 years agoFix sail command to support full path length
Markus Armbruster [Sun, 18 Jul 2010 16:16:01 +0000 (18:16 +0200)]
Fix sail command to support full path length

Off-by-one in cmd_sail_ship() chopped off the last character of
full-length sail paths.

12 years agoRemove unused plurize()
Markus Armbruster [Sun, 18 Jul 2010 13:14:41 +0000 (15:14 +0200)]
Remove unused plurize()

Unused since commit 44c36fa, v4.3.23.

12 years agoChange ioq_dequeue() to return void
Markus Armbruster [Sun, 29 Aug 2010 09:38:02 +0000 (11:38 +0200)]
Change ioq_dequeue() to return void

For symmetry with ioq_append().

12 years agoErr, the race in io_output() doesn't double-free
Markus Armbruster [Sun, 29 Aug 2010 09:31:02 +0000 (11:31 +0200)]
Err, the race in io_output() doesn't double-free

The previous commit's message claims the race can lead to duplicated
output, use after free, then double-free.  That's correct only up to
the use after free.  There is no double-free.

Heap corruption (double-free?) has been observed in Changeling,
though.  Player logged in (still in sanctuary), map #, crashed within
removecc()'s free(io->data).  Partial backtrace:

    raise () from /lib64/libc.so.6
    abort () from /lib64/libc.so.6
    __libc_message () from /lib64/libc.so.6
    malloc_printerr () from /lib64/libc.so.6
    removecc (ioq=0x251fd10, cc=468) at ../src/lib/gen/ioqueue.c:350
    ioq_dequeue (ioq=0x251fd10, cc=468) at ../src/lib/gen/ioqueue.c:135
    io_output (iop=0x251fc90, wait=1) at ../src/lib/empthread/io.c:231
    recvclient (cmd=0x258d8e0 "", size=1024) at ../src/lib/player/recvclient.c:82
    getcommand (combufp=0x2557068 "map #1") at ../src/lib/player/empdis.c:84

I haven't been able to reproduce.

To hopefully catch ioqueue going south earlier, make ioq_dequeue()
oops when it can't dequeue as many bytes as requested.

12 years agoFix race in io_output() that can lead to double-free
Markus Armbruster [Sun, 4 Jul 2010 15:30:33 +0000 (17:30 +0200)]
Fix race in io_output() that can lead to double-free

Move call of ioq_makeiov() to its use, because calling it before
empth_select() is racy, as follows.

Player thread flushes output by calling io_output(player->iop, 1).
io_output() sets up iov[] to point to queued output.  empth_select()
blocks on output.

Another thread sends a C_FLASH or C_INFORM message to this player.
This calls io_output(p->iop, 0).  The output file descriptor has
become writable since the player thread blocked on it, so some output
gets written and dequeued.

The player thread resumes, writes out iov[] and dequeues.  Any output
already written by the other thread gets duplicated.  If the other
thread's dequeue operation freed struct io buffers, there's use after
free followed by double-free.

12 years agoDocument xundump() memory leak more clearly
Markus Armbruster [Sun, 4 Jul 2010 15:30:03 +0000 (17:30 +0200)]
Document xundump() memory leak more clearly

12 years agoPlanes get to sweep and sonar only after flak and interception
Markus Armbruster [Sun, 27 Jun 2010 07:33:24 +0000 (09:33 +0200)]
Planes get to sweep and sonar only after flak and interception

If defenders get to shoot before bombs are dropped, they surely get to
shoot before time-consuming missions like sweep and sonar.

Sweep and sonar used to happen after air defense, but before flak and
interception.  Air defense existed from Chainsaw 3 to v4.3.19.

12 years agoNeater plane sonar contact output
Markus Armbruster [Sun, 18 Jul 2010 08:37:43 +0000 (10:37 +0200)]
Neater plane sonar contact output

plane_sona() prints an empty line to make sonar contacts stand out.
Move it so the contact is visually "attached" to the right sector,
like this:

    flying over sea at 15,-3
    Sonar contact in 15,-3
    sub #3 13,-3

    flying over sea at 13,-3


    flying over sea at 15,-3

    Sonar contact in 15,-3
    sb   submarine (#3) 13,-3
    flying over sea at 13,-3