(svn r1751) - Feature: New PathFinder (NPF).

	- Supports trains, road vehicles and ships.
	- Uses A* pathfinding (same codebase as the new ai).
	- Currently unlimited search depth, so might perform badly on large maps/networks (especially ships).
	- Will always find a route if there is one.
	- Allows custom penalties for obstacles to be set in openttd.cfg (npf_ values).
	- With NPF enabled, ships can have orders that are very far apart. Be careful, this will break (ships get lost) when the old pathfinder is used again.
- Feature: Disabling 90 degree turns for trains and ships.
	- Requires NPF to be enabled.
	- Ships and trains can no longer make weird 90 degree turns on tile borders.
- Codechange: Removed table/directions.h.
	- table/directions.h contained ugly static tables but was included more than once. The tables, along with a few new ones are in npf.[ch] now. Better suggestions for a location?
- Fix: Binary heap in queue.c did not allocate enough space, resulting in a segfault.
- Codechange: Rewritten FindFirstBit2x64, added KillFirstBit2x64.
- Codechange: Introduced constant INVALID_TILE, to replace the usage of 0 as an invalid tile. Also replaces TILE_WRAPPED.
- Codechange: Moved TileAddWrap() to map.[ch] 
- Add TileIndexDiffCByDir(), TileIndexDiffCByDir(). 
- Codechange: Moved IsTrainStationTile() to station.h
- Add: IsRoadStationTile() and GetRoadStationDir().

1 files changed, 21 insertions, 1 deletions

diff --git a/map.h b/map.h
index 605b89495..55704a555 100644
--- a/map.h
+++ b/map.h
@@ -35,7 +35,9 @@ uint ScaleByMapSize(uint); // Scale relative to the number of tiles
 uint ScaleByMapSize1D(uint); // Scale relative to the circumference of the map
 
 typedef uint32 TileIndex;
-
+enum {
+	INVALID_TILE = (uint32) -1
+};
 
 static inline uint TileX(TileIndex tile)
 {
@@ -71,6 +73,24 @@ static inline TileIndexDiff ToTileIndexDiff(TileIndexDiffC tidc)
 
 #define TILE_ADDXY(tile, x, y) TILE_ADD(tile, TILE_XY(x, y))
 
+uint TileAddWrap(TileIndex tile, int addx, int addy);
+
+static inline TileIndexDiffC TileIndexDiffCByDir(uint dir) {
+	extern const TileIndexDiffC _tileoffs_by_dir[4];
+	return _tileoffs_by_dir[dir];
+}
+
+/* Returns tile + the diff given in diff. If the result tile would end up
+ * outside of the map, INVALID_TILE is returned instead.
+ */
+static inline TileIndex AddTileIndexDiffCWrap(TileIndex tile, TileIndexDiffC diff) {
+	int x = TileX(tile) + diff.x;
+	int y = TileY(tile) + diff.y;
+	if (x < 0 || y < 0 || x > (int)MapMaxX() || y > (int)MapMaxY())
+		return INVALID_TILE;
+	else
+		return TILE_XY(x, y);
+}
 
 // Functions to calculate distances
 uint DistanceManhattan(TileIndex, TileIndex); // also known as L1-Norm