]> git.pond.sub.org Git - empserver/commit
Use the new path finder for land paths, drop old A*
authorMarkus Armbruster <armbru@pond.sub.org>
Sat, 26 Feb 2011 15:06:09 +0000 (16:06 +0100)
committerMarkus Armbruster <armbru@pond.sub.org>
Tue, 12 Apr 2011 19:48:58 +0000 (21:48 +0200)
commitffbbfcb25fd1e5ef1c03c0ece542c97f571ad51d
treeac5969998efc192a95aaae6dd4fd253355700340
parent90de24d038b01e0956ed91625f515ab66ac7677c
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.
19 files changed:
Make.mk
include/path.h
src/lib/as/COPYRIGHT [deleted file]
src/lib/as/README [deleted file]
src/lib/as/as.h [deleted file]
src/lib/as/as_cache.c [deleted file]
src/lib/as/as_costcomp.c [deleted file]
src/lib/as/as_delete.c [deleted file]
src/lib/as/as_extend.c [deleted file]
src/lib/as/as_hash.c [deleted file]
src/lib/as/as_init.c [deleted file]
src/lib/as/as_merge.c [deleted file]
src/lib/as/as_search.c [deleted file]
src/lib/as/as_stats.c [deleted file]
src/lib/as/as_winnow.c [deleted file]
src/lib/common/path.c
src/lib/common/pathfind.c
src/lib/subs/move.c
src/lib/update/finish.c