Optimize Dijkstra's inner loop for hex maps
authorMarkus Armbruster <armbru@pond.sub.org>
Sat, 26 Feb 2011 16:40:13 +0000 (17:40 +0100)
committerMarkus Armbruster <armbru@pond.sub.org>
Tue, 12 Apr 2011 19:51:31 +0000 (21:51 +0200)
commitd7dccef3b113c05e457c936d691bb913d011ff4b
tree114b60ca6f2f2b61b54564a699cbc74257d1c14e
parentffbbfcb25fd1e5ef1c03c0ece542c97f571ad51d
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.
src/lib/common/pathfind.c