changeset 13857:19e881c1e87d draft

(svn r18386) -Codechange: make the NPF functions static and remove unused functions
author rubidium <rubidium@openttd.org>
date Wed, 02 Dec 2009 18:34:10 +0000
parents 8c8d1ebf7ae1
children 5cc78eb6c55c
files src/pathfinder/npf/npf.cpp src/pathfinder/npf/npf.h
diffstat 2 files changed, 87 insertions(+), 240 deletions(-) [+]
line wrap: on
line diff
--- a/src/pathfinder/npf/npf.cpp
+++ b/src/pathfinder/npf/npf.cpp
@@ -24,7 +24,60 @@
 #include "../../roadstop_base.h"
 #include "../pathfinder_func.h"
 #include "../pathfinder_type.h"
-#include "npf.h"
+#include "aystar.h"
+
+enum {
+	NPF_HASH_BITS = 12, ///< The size of the hash used in pathfinding. Just changing this value should be sufficient to change the hash size. Should be an even value.
+	/* Do no change below values */
+	NPF_HASH_SIZE = 1 << NPF_HASH_BITS,
+	NPF_HASH_HALFBITS = NPF_HASH_BITS / 2,
+	NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1
+};
+
+/* Meant to be stored in AyStar.targetdata */
+struct NPFFindStationOrTileData {
+	TileIndex dest_coords;    ///< An indication of where the station is, for heuristic purposes, or the target tile
+	StationID station_index;  ///< station index we're heading for, or INVALID_STATION when we're heading for a tile
+	bool reserve_path;        ///< Indicates whether the found path should be reserved
+	StationType station_type; ///< The type of station we're heading for
+	bool not_articulated;     ///< The (road) vehicle is not articulated
+	const Vehicle *v;         ///< The vehicle we are pathfinding for
+};
+
+/* Indices into AyStar.userdata[] */
+enum {
+	NPF_TYPE = 0,  ///< Contains a TransportTypes value
+	NPF_SUB_TYPE,  ///< Contains the sub transport type
+	NPF_OWNER,     ///< Contains an Owner value
+	NPF_RAILTYPES, ///< Contains a bitmask the compatible RailTypes of the engine when NPF_TYPE == TRANSPORT_RAIL. Unused otherwise.
+};
+
+/* Indices into AyStarNode.userdata[] */
+enum {
+	NPF_TRACKDIR_CHOICE = 0, ///< The trackdir chosen to get here
+	NPF_NODE_FLAGS,
+};
+
+/* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFGetBit() and NPFGetBit() to use them. */
+enum NPFNodeFlag {
+	NPF_FLAG_SEEN_SIGNAL,       ///< Used to mark that a signal was seen on the way, for rail only
+	NPF_FLAG_2ND_SIGNAL,        ///< Used to mark that two signals were seen, rail only
+	NPF_FLAG_3RD_SIGNAL,        ///< Used to mark that three signals were seen, rail only
+	NPF_FLAG_REVERSE,           ///< Used to mark that this node was reached from the second start node, if applicable
+	NPF_FLAG_LAST_SIGNAL_RED,   ///< Used to mark that the last signal on this path was red
+	NPF_FLAG_IGNORE_START_TILE, ///< Used to mark that the start tile is invalid, and searching should start from the second tile on
+	NPF_FLAG_TARGET_RESERVED,   ///< Used to mark that the possible reservation target is already reserved
+	NPF_FLAG_IGNORE_RESERVED,   ///< Used to mark that reserved tiles should be considered impassable
+};
+
+/* Meant to be stored in AyStar.userpath */
+struct NPFFoundTargetData {
+	uint best_bird_dist;    ///< The best heuristic found. Is 0 if the target was found
+	uint best_path_dist;    ///< The shortest path. Is UINT_MAX if no path is found
+	Trackdir best_trackdir; ///< The trackdir that leads to the shortest path/closest birds dist
+	AyStarNode node;        ///< The node within the target the search led us to
+	bool res_okay;          ///< True if a path reservation could be made
+};
 
 static AyStar _npf_aystar;
 
@@ -39,6 +92,22 @@
 };
 
 /**
+ * Returns the current value of the given flag on the given AyStarNode.
+ */
+static inline bool NPFGetFlag(const AyStarNode *node, NPFNodeFlag flag)
+{
+	return HasBit(node->user_data[NPF_NODE_FLAGS], flag);
+}
+
+/**
+ * Sets the given flag on the given AyStarNode to the given value.
+ */
+static inline void NPFSetFlag(AyStarNode *node, NPFNodeFlag flag, bool value)
+{
+	SB(node->user_data[NPF_NODE_FLAGS], flag, 1, value);
+}
+
+/**
  * Calculates the minimum distance traveled to get from t0 to t1 when only
  * using tracks (ie, only making 45 degree turns). Returns the distance in the
  * NPF scale, ie the number of full tiles multiplied by NPF_TILE_LENGTH to
@@ -918,7 +987,10 @@
 	return result;
 }
 
-NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes)
+/* Will search as below, but with two start nodes, the second being the
+ * reverse. Look at the NPF_FLAG_REVERSE flag in the result node to see which
+ * direction was taken (NPFGetBit(result.node, NPF_FLAG_REVERSE)) */
+static NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes)
 {
 	AyStarNode start1;
 	AyStarNode start2;
@@ -935,12 +1007,22 @@
 	return NPFRouteInternal(&start1, ignore_start_tile1, (IsValidTile(tile2) ? &start2 : NULL), ignore_start_tile2, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, sub_type, owner, railtypes, 0);
 }
 
-NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes)
+/* Will search from the given tile and direction, for a route to the given
+ * station for the given transport type. See the declaration of
+ * NPFFoundTargetData above for the meaning of the result. */
+static NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes)
 {
 	return NPFRouteToStationOrTileTwoWay(tile, trackdir, ignore_start_tile, INVALID_TILE, INVALID_TRACKDIR, false, target, type, sub_type, owner, railtypes);
 }
 
-NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty)
+/* Search using breadth first. Good for little track choice and inaccurate
+ * heuristic, such as railway/road with two start nodes, the second being the reverse. Call
+ * NPFGetBit(result.node, NPF_FLAG_REVERSE) to see from which node the path
+ * orginated. All pathfs from the second node will have the given
+ * reverse_penalty applied (NPF_TILE_LENGTH is the equivalent of one full
+ * tile).
+ */
+static NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty)
 {
 	AyStarNode start1;
 	AyStarNode start2;
@@ -959,111 +1041,6 @@
 	return NPFRouteInternal(&start1, ignore_start_tile1, (IsValidTile(tile2) ? &start2 : NULL), ignore_start_tile2, NULL, NPFFindDepot, NPFCalcZero, type, sub_type, owner, railtypes, reverse_penalty);
 }
 
-NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes)
-{
-	return NPFRouteToDepotBreadthFirstTwoWay(tile, trackdir, ignore_start_tile, INVALID_TILE, INVALID_TRACKDIR, false, type, sub_type, owner, railtypes, 0);
-}
-
-NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes)
-{
-	/* Okay, what we're gonna do. First, we look at all depots, calculate
-	 * the manhatten distance to get to each depot. We then sort them by
-	 * distance. We start by trying to plan a route to the closest, then
-	 * the next closest, etc. We stop when the best route we have found so
-	 * far, is shorter than the manhattan distance. This will obviously
-	 * always find the closest depot. It will probably be most efficient
-	 * for ships, since the heuristic will not be to far off then. I hope.
-	 */
-	Queue depots;
-	int r;
-	NPFFoundTargetData best_result = {UINT_MAX, UINT_MAX, INVALID_TRACKDIR, {INVALID_TILE, INVALID_TRACKDIR, {0, 0}}, false};
-	NPFFoundTargetData result;
-	NPFFindStationOrTileData target;
-	AyStarNode start;
-	Depot *current;
-	Depot *depot;
-
-	init_InsSort(&depots);
-	/* Okay, let's find all depots that we can use first */
-	FOR_ALL_DEPOTS(depot) {
-		/* Check if this is really a valid depot, it is of the needed type and
-		 * owner */
-		if (IsDepotTypeTile(depot->xy, type) && IsTileOwner(depot->xy, owner))
-			/* If so, let's add it to the queue, sorted by distance */
-			depots.push(&depots, depot, DistanceManhattan(tile, depot->xy));
-	}
-
-	/* Now, let's initialise the aystar */
-
-	/* Initialize procs */
-	_npf_aystar.CalculateH = NPFCalcStationOrTileHeuristic;
-	_npf_aystar.EndNodeCheck = NPFFindStationOrTile;
-	_npf_aystar.FoundEndNode = NPFSaveTargetData;
-	_npf_aystar.GetNeighbours = NPFFollowTrack;
-	switch (type) {
-		default: NOT_REACHED();
-		case TRANSPORT_RAIL:  _npf_aystar.CalculateG = NPFRailPathCost;  break;
-		case TRANSPORT_ROAD:  _npf_aystar.CalculateG = NPFRoadPathCost;  break;
-		case TRANSPORT_WATER: _npf_aystar.CalculateG = NPFWaterPathCost; break;
-	}
-
-	/* Initialize target */
-	target.station_index = INVALID_STATION; // We will initialize dest_coords inside the loop below
-	_npf_aystar.user_target = &target;
-
-	/* Initialize user_data */
-	_npf_aystar.user_data[NPF_TYPE] = type;
-	_npf_aystar.user_data[NPF_SUB_TYPE] = sub_type;
-	_npf_aystar.user_data[NPF_OWNER] = owner;
-
-	/* Initialize Start Node */
-	start.tile = tile;
-	start.direction = trackdir; // We will initialize user_data inside the loop below
-
-	/* Initialize Result */
-	_npf_aystar.user_path = &result;
-	best_result.best_path_dist = UINT_MAX;
-	best_result.best_bird_dist = UINT_MAX;
-
-	/* Just iterate the depots in order of increasing distance */
-	while ((current = (Depot*)depots.pop(&depots))) {
-		/* Check to see if we already have a path shorter than this
-		 * depot's manhattan distance. HACK: We call DistanceManhattan
-		 * again, we should probably modify the queue to give us that
-		 * value... */
-		if ( DistanceManhattan(tile, current->xy * NPF_TILE_LENGTH) > best_result.best_path_dist)
-			break;
-
-		/* Initialize Start Node
-		 * We set this in case the target is also the start tile, we will just
-		 * return a not found then */
-		start.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR;
-		start.user_data[NPF_NODE_FLAGS] = 0;
-		NPFSetFlag(&start, NPF_FLAG_IGNORE_START_TILE, ignore_start_tile);
-		_npf_aystar.addstart(&_npf_aystar, &start, 0);
-
-		/* Initialize result */
-		result.best_bird_dist = UINT_MAX;
-		result.best_path_dist = UINT_MAX;
-		result.best_trackdir = INVALID_TRACKDIR;
-
-		/* Initialize target */
-		target.dest_coords = current->xy;
-
-		/* GO! */
-		r = AyStarMain_Main(&_npf_aystar);
-		assert(r != AYSTAR_STILL_BUSY);
-
-		/* This depot is closer */
-		if (result.best_path_dist < best_result.best_path_dist)
-			best_result = result;
-	}
-	if (result.best_bird_dist != 0) {
-		DEBUG(npf, 1, "Could not find route to any depot from tile 0x%X.", tile);
-	}
-	return best_result;
-}
-
 void InitializeNPF()
 {
 	static bool first_init = true;
@@ -1081,7 +1058,7 @@
 	_npf_aystar.max_search_nodes = _settings_game.pf.npf.npf_max_search_nodes;
 }
 
-void NPFFillWithOrderData(NPFFindStationOrTileData *fstd, const Vehicle *v, bool reserve_path)
+static void NPFFillWithOrderData(NPFFindStationOrTileData *fstd, const Vehicle *v, bool reserve_path = false)
 {
 	/* Ships don't really reach their stations, but the tile in front. So don't
 	 * save the station id for ships. For roadvehs we don't store it either,
deleted file mode 100644
--- a/src/pathfinder/npf/npf.h
+++ /dev/null
@@ -1,130 +0,0 @@
-/* $Id$ */
-
-/*
- * This file is part of OpenTTD.
- * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
- * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
- * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
- */
-
-/** @file npf.h New A* pathfinder. */
-
-#ifndef NPF_H
-#define NPF_H
-
-#include "aystar.h"
-#include "../../station_type.h"
-#include "../../rail_type.h"
-#include "../../company_type.h"
-#include "../../vehicle_type.h"
-#include "../../tile_type.h"
-#include "../../track_type.h"
-#include "../../core/bitmath_func.hpp"
-#include "../../transport_type.h"
-
-/* mowing grass */
-enum {
-	NPF_HASH_BITS = 12, ///< The size of the hash used in pathfinding. Just changing this value should be sufficient to change the hash size. Should be an even value.
-	/* Do no change below values */
-	NPF_HASH_SIZE = 1 << NPF_HASH_BITS,
-	NPF_HASH_HALFBITS = NPF_HASH_BITS / 2,
-	NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1
-};
-
-/* Meant to be stored in AyStar.targetdata */
-struct NPFFindStationOrTileData {
-	TileIndex dest_coords;    ///< An indication of where the station is, for heuristic purposes, or the target tile
-	StationID station_index;  ///< station index we're heading for, or INVALID_STATION when we're heading for a tile
-	bool reserve_path;        ///< Indicates whether the found path should be reserved
-	StationType station_type; ///< The type of station we're heading for
-	bool not_articulated;     ///< The (road) vehicle is not articulated
-	const Vehicle *v;         ///< The vehicle we are pathfinding for
-};
-
-/* Indices into AyStar.userdata[] */
-enum {
-	NPF_TYPE = 0,  ///< Contains a TransportTypes value
-	NPF_SUB_TYPE,  ///< Contains the sub transport type
-	NPF_OWNER,     ///< Contains an Owner value
-	NPF_RAILTYPES, ///< Contains a bitmask the compatible RailTypes of the engine when NPF_TYPE == TRANSPORT_RAIL. Unused otherwise.
-};
-
-/* Indices into AyStarNode.userdata[] */
-enum {
-	NPF_TRACKDIR_CHOICE = 0, ///< The trackdir chosen to get here
-	NPF_NODE_FLAGS,
-};
-
-/* Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFGetBit() and NPFGetBit() to use them. */
-enum NPFNodeFlag {
-	NPF_FLAG_SEEN_SIGNAL,       ///< Used to mark that a signal was seen on the way, for rail only
-	NPF_FLAG_2ND_SIGNAL,        ///< Used to mark that two signals were seen, rail only
-	NPF_FLAG_3RD_SIGNAL,        ///< Used to mark that three signals were seen, rail only
-	NPF_FLAG_REVERSE,           ///< Used to mark that this node was reached from the second start node, if applicable
-	NPF_FLAG_LAST_SIGNAL_RED,   ///< Used to mark that the last signal on this path was red
-	NPF_FLAG_IGNORE_START_TILE, ///< Used to mark that the start tile is invalid, and searching should start from the second tile on
-	NPF_FLAG_TARGET_RESERVED,   ///< Used to mark that the possible reservation target is already reserved
-	NPF_FLAG_IGNORE_RESERVED,   ///< Used to mark that reserved tiles should be considered impassable
-};
-
-/* Meant to be stored in AyStar.userpath */
-struct NPFFoundTargetData {
-	uint best_bird_dist;    ///< The best heuristic found. Is 0 if the target was found
-	uint best_path_dist;    ///< The shortest path. Is UINT_MAX if no path is found
-	Trackdir best_trackdir; ///< The trackdir that leads to the shortest path/closest birds dist
-	AyStarNode node;        ///< The node within the target the search led us to
-	bool res_okay;          ///< True if a path reservation could be made
-};
-
-/* These functions below are _not_ re-entrant, in favor of speed! */
-
-/* Will search from the given tile and direction, for a route to the given
- * station for the given transport type. See the declaration of
- * NPFFoundTargetData above for the meaning of the result. */
-NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes);
-
-/* Will search as above, but with two start nodes, the second being the
- * reverse. Look at the NPF_FLAG_REVERSE flag in the result node to see which
- * direction was taken (NPFGetBit(result.node, NPF_FLAG_REVERSE)) */
-NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, NPFFindStationOrTileData *target, TransportType type, uint sub_type, Owner owner, RailTypes railtypes);
-
-/* Will search a route to the closest depot. */
-
-/* Search using breadth first. Good for little track choice and inaccurate
- * heuristic, such as railway/road.*/
-NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes);
-/* Same as above but with two start nodes, the second being the reverse. Call
- * NPFGetBit(result.node, NPF_FLAG_REVERSE) to see from which node the path
- * orginated. All pathfs from the second node will have the given
- * reverse_penalty applied (NPF_TILE_LENGTH is the equivalent of one full
- * tile).
- */
-NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, bool ignore_start_tile1, TileIndex tile2, Trackdir trackdir2, bool ignore_start_tile2, TransportType type, uint sub_type, Owner owner, RailTypes railtypes, uint reverse_penalty);
-/* Search by trying each depot in order of Manhattan Distance. Good for lots
- * of choices and accurate heuristics, such as water. */
-NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, TransportType type, uint sub_type, Owner owner, RailTypes railtypes);
-
-void NPFFillWithOrderData(NPFFindStationOrTileData *fstd, const Vehicle *v, bool reserve_path = false);
-
-
-/*
- * Functions to manipulate the various NPF related flags on an AyStarNode.
- */
-
-/**
- * Returns the current value of the given flag on the given AyStarNode.
- */
-static inline bool NPFGetFlag(const AyStarNode *node, NPFNodeFlag flag)
-{
-	return HasBit(node->user_data[NPF_NODE_FLAGS], flag);
-}
-
-/**
- * Sets the given flag on the given AyStarNode to the given value.
- */
-static inline void NPFSetFlag(AyStarNode *node, NPFNodeFlag flag, bool value)
-{
-	SB(node->user_data[NPF_NODE_FLAGS], flag, 1, value);
-}
-
-#endif /* NPF_H */