Changeset - r9804:b9d32bdb8da7
Parent rev.
Child rev.
[Not reviewed]
master
0 2 0
rubidium - 16 years ago 2008-08-02 22:52:22
rubidium@openttd.org
(svn r13946) -Add [YAPP]: Implement track reserving for NPF as well. (michi_cc)
2 files changed with 87 insertions and 6 deletions:
src/npf.cpp
82
5
src/npf.h
5
1
0 comments (0 inline, 0 general)
src/npf.cpp
➞
Show inline comments
 
@@ -441,9 +441,48 @@ static int32 NPFFindStationOrTile(AyStar
 
	}
 
}
 

			




	
	
	
		
 
/* To be called when current contains the (shortest route to) the target node.

			




	
	
	
		
 
/**

			




	
	
	
		
 
 * Find the node containing the first signal on the path.

			




	
	
	
		
 
 *

			




	
	
	
		
 
 * If the first signal is on the very first two tiles of the path,

			




	
	
	
		
 
 * the second signal is returnd. If no suitable signal is present, the

			




	
	
	
		
 
 * last node of the path is returned.

			




	
	
	
		
 
 */

			




	
	
	
		
 
static const PathNode* FindSafePosition(PathNode *path, const Vehicle *v)

			




	
	
	
		
 
{

			




	
	
	
		
 
	/* If there is no signal, reserve the whole path. */

			




	
	
	
		
 
	PathNode *sig = path;

			




	
	
	
		
 

			




	
	
	
		
 
	for(; path->parent != NULL; path = path->parent) {

			




	
	
	
		
 
		if (IsSafeWaitingPosition(v, path->node.tile, (Trackdir)path->node.direction, true, _settings_game.pf.forbid_90_deg)) {

			




	
	
	
		
 
			sig = path;

			




	
	
	
		
 
		}

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	return sig;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/**

			




	
	
	
		
 
 * Lift the reservation of the tiles from @p start till @p end, excluding @p end itself.

			




	
	
	
		
 
 */

			




	
	
	
		
 
static void ClearPathReservation(const PathNode *start, const PathNode *end)

			




	
	
	
		
 
{

			




	
	
	
		
 
	bool first_run = true;

			




	
	
	
		
 
	for (; start != end; start = start->parent) {

			




	
	
	
		
 
		if (IsRailwayStationTile(start->node.tile) && first_run) {

			




	
	
	
		
 
			SetRailwayStationPlatformReservation(start->node.tile, TrackdirToExitdir((Trackdir)start->node.direction), false);

			




	
	
	
		
 
		} else {

			




	
	
	
		
 
			UnreserveRailTrack(start->node.tile, TrackdirToTrack((Trackdir)start->node.direction));

			




	
	
	
		
 
		}

			




	
	
	
		
 
		first_run = false;

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/**

			




	
	
	
		
 
 * To be called when @p current contains the (shortest route to) the target node.

			




	
	
	
		
 
 * Will fill the contents of the NPFFoundTargetData using

			




	
	
	
		
 
 * AyStarNode[NPF_TRACKDIR_CHOICE].

			




	
	
	
		
 
 * AyStarNode[NPF_TRACKDIR_CHOICE]. If requested, path reservation

			




	
	
	
		
 
 * is done here.

			




	
	
	
		
 
 */

			




	
	
	
		
 
static void NPFSaveTargetData(AyStar* as, OpenListNode* current)

			




	
	
	
		
 
{

			




	
	
		
 
@@ -452,6 +491,40 @@ static void NPFSaveTargetData(AyStar* as

			




	
	
	
		
 
	ftd->best_path_dist = current->g;

			




	
	
	
		
 
	ftd->best_bird_dist = 0;

			




	
	
	
		
 
	ftd->node = current->path.node;

			




	
	
	
		
 
	ftd->res_okay = false;

			




	
	
	
		
 

			




	
	
	
		
 
	if (as->user_target != NULL && ((NPFFindStationOrTileData*)as->user_target)->reserve_path && as->user_data[NPF_TYPE] == TRANSPORT_RAIL) {

			




	
	
	
		
 
		/* Path reservation is requested. */

			




	
	
	
		
 
		const Vehicle  *v = ((NPFFindStationOrTileData*)as->user_target)->v;

			




	
	
	
		
 

			




	
	
	
		
 
		const PathNode *target = FindSafePosition(&current->path, v);

			




	
	
	
		
 
		ftd->node = target->node;

			




	
	
	
		
 

			




	
	
	
		
 
		/* If the target is a station skip to platform end. */

			




	
	
	
		
 
		if (IsRailwayStationTile(target->node.tile)) {

			




	
	
	
		
 
			DiagDirection dir = TrackdirToExitdir((Trackdir)target->node.direction);

			




	
	
	
		
 
			uint len = GetStationByTile(target->node.tile)->GetPlatformLength(target->node.tile, dir);

			




	
	
	
		
 
			TileIndex end_tile = TILE_ADD(target->node.tile, (len - 1) * TileOffsByDiagDir(dir));

			




	
	
	
		
 

			




	
	
	
		
 
			/* Update only end tile, trackdir of a station stays the same. */

			




	
	
	
		
 
			ftd->node.tile = end_tile;

			




	
	
	
		
 
			if (!IsWaitingPositionFree(v, end_tile, (Trackdir)target->node.direction, _settings_game.pf.forbid_90_deg)) return;

			




	
	
	
		
 
			SetRailwayStationPlatformReservation(target->node.tile, dir, true);

			




	
	
	
		
 
			SetRailwayStationReservation(target->node.tile, false);

			




	
	
	
		
 
		} else {

			




	
	
	
		
 
			if (!IsWaitingPositionFree(v, target->node.tile, (Trackdir)target->node.direction, _settings_game.pf.forbid_90_deg)) return;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		for (const PathNode *cur = target; cur->parent != NULL; cur = cur->parent) {

			




	
	
	
		
 
			if (!TryReserveRailTrack(cur->node.tile, TrackdirToTrack((Trackdir)cur->node.direction))) {

			




	
	
	
		
 
				/* Reservation failed, undo. */

			




	
	
	
		
 
				ClearPathReservation(target, cur);

			




	
	
	
		
 
				return;

			




	
	
	
		
 
			}

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		ftd->res_okay = true;

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/**

			




	
	
		
 
@@ -782,7 +855,9 @@ static NPFFoundTargetData NPFRouteIntern

			




	
	
	
		
 
	/* Initialize result */

			




	
	
	
		
 
	result.best_bird_dist = (uint)-1;

			




	
	
	
		
 
	result.best_path_dist = (uint)-1;

			




	
	
	
		
 
	result.best_trackdir = INVALID_TRACKDIR;

			




	
	
	
		
 
	result.best_trackdir  = INVALID_TRACKDIR;

			




	
	
	
		
 
	result.node.tile      = INVALID_TILE;

			




	
	
	
		
 
	result.res_okay       = false;

			




	
	
	
		
 
	_npf_aystar.user_path = &result;

			




	
	
	
		
 

			




	
	
	
		
 
	/* Initialize target */

			




	
	
		
 
@@ -868,7 +943,7 @@ NPFFoundTargetData NPFRouteToDepotTrialE

			




	
	
	
		
 
	 */

			




	
	
	
		
 
	Queue depots;

			




	
	
	
		
 
	int r;

			




	
	
	
		
 
	NPFFoundTargetData best_result = {(uint)-1, (uint)-1, INVALID_TRACKDIR, {INVALID_TILE, 0, {0, 0}}};

			




	
	
	
		
 
	NPFFoundTargetData best_result = {(uint)-1, (uint)-1, INVALID_TRACKDIR, {INVALID_TILE, 0, {0, 0}}, false};

			




	
	
	
		
 
	NPFFoundTargetData result;

			




	
	
	
		
 
	NPFFindStationOrTileData target;

			




	
	
	
		
 
	AyStarNode start;

			




	
	
		
 
@@ -973,7 +1048,7 @@ void InitializeNPF()

			




	
	
	
		
 
	_npf_aystar.max_search_nodes = _settings_game.pf.npf.npf_max_search_nodes;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v)

			




	
	
	
		
 
void NPFFillWithOrderData(NPFFindStationOrTileData *fstd, Vehicle *v, bool reserve_path)

			




	
	
	
		
 
{

			




	
	
	
		
 
	/* 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,

			




	
	
		
 
@@ -989,4 +1064,6 @@ void NPFFillWithOrderData(NPFFindStation

			




	
	
	
		
 
		fstd->dest_coords = v->dest_tile;

			




	
	
	
		
 
		fstd->station_index = INVALID_STATION;

			




	
	
	
		
 
	}

			




	
	
	
		
 
	fstd->reserve_path = reserve_path;

			




	
	
	
		
 
	fstd->v = v;

			




	
	
	
		
 
}

			




        

    


    
    

    

        

                

                    src/npf.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -45,6 +45,8 @@ enum {

			




	
	
	
		
 
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

			




	
	
	
		
 
	const Vehicle* v;        ///< The vehicle we are pathfinding for

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
/* Indices into AyStar.userdata[] */

			




	
	
		
 
@@ -67,6 +69,7 @@ enum NPFNodeFlag {

			




	
	
	
		
 
	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

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
/* Meant to be stored in AyStar.userpath */

			




	
	
		
 
@@ -75,6 +78,7 @@ struct NPFFoundTargetData {

			




	
	
	
		
 
	uint best_path_dist;    ///< The shortest path. Is (uint)-1 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! */

			




	
	
		
 
@@ -105,7 +109,7 @@ NPFFoundTargetData NPFRouteToDepotBreadt

			




	
	
	
		
 
 * 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, Vehicle* v);

			




	
	
	
		
 
void NPFFillWithOrderData(NPFFindStationOrTileData *fstd, Vehicle *v, bool reserve_path = false);

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
/*

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: code.theleruby.com-48
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support