Changeset - r12987:a96aecf2b6ea
Parent rev.
Child rev.
[Not reviewed]
master
0 3 0
rubidium - 15 years ago 2009-09-09 21:01:45
rubidium@openttd.org
(svn r17491) -Fix [FS#3188]: road vehicles could get lost when the prelimiary destination (for the pathfinder heuristics) is unreachable.
3 files changed with 139 insertions and 16 deletions:
src/roadveh_cmd.cpp
2
16
src/yapf/yapf.h
9
src/yapf/yapf_road.cpp
128
0 comments (0 inline, 0 general)
src/roadveh_cmd.cpp
➞
Show inline comments
 
@@ -689,22 +689,8 @@ TileIndex RoadVehicle::GetOrderStationLo
 
{
 
	if (station == this->last_station_visited) this->last_station_visited = INVALID_STATION;
 

			




	
	
	
		
 
	TileIndex dest = INVALID_TILE;

			




	
	
	
		
 
	const RoadStop *rs = Station::Get(station)->GetPrimaryRoadStop(this);

			




	
	
	
		
 
	if (rs != NULL) {

			




	
	
	
		
 
		uint mindist = UINT_MAX;

			




	
	
	
		
 

			




	
	
	
		
 
		for (; rs != NULL; rs = rs->GetNextRoadStop(this)) {

			




	
	
	
		
 
			uint dist = DistanceManhattan(this->tile, rs->xy);

			




	
	
	
		
 

			




	
	
	
		
 
			if (dist < mindist) {

			




	
	
	
		
 
				mindist = dist;

			




	
	
	
		
 
				dest = rs->xy;

			




	
	
	
		
 
			}

			




	
	
	
		
 
		}

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	if (dest != INVALID_TILE) {

			




	
	
	
		
 
	TileIndex dest;

			




	
	
	
		
 
	if (YapfFindNearestRoadVehicleCompatibleStop(this, station, &dest)) {

			




	
	
	
		
 
		return dest;

			




	
	
	
		
 
	} else {

			




	
	
	
		
 
		/* There is no stop left at the station, so don't even TRY to go there */

			




        

    


    
    

    

        

                

                    src/yapf/yapf.h
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -15,6 +15,7 @@

			




	
	
	
		
 
#include "../debug.h"

			




	
	
	
		
 
#include "../depot_type.h"

			




	
	
	
		
 
#include "../direction_type.h"

			




	
	
	
		
 
#include "../station_type.h"

			




	
	
	
		
 
#include "../pbs.h"

			




	
	
	
		
 

			




	
	
	
		
 
/** Finds the best path for given ship.

			




	
	
		
 
@@ -53,6 +54,14 @@ Trackdir YapfChooseRailTrack(const Vehic

			




	
	
	
		
 
 */

			




	
	
	
		
 
uint YapfRoadVehDistanceToTile(const Vehicle *v, TileIndex tile);

			




	
	
	
		
 

			




	
	
	
		
 
/** Used to determinine the closest reachable compatible road stop for a given vehicle.

			




	
	
	
		
 
 * @param v            vehicle that needs to go to the road stop

			




	
	
	
		
 
 * @param station      the station the road stop must belong to

			




	
	
	
		
 
 * @param stop_tile    receives the stop tile if a stop was found

			




	
	
	
		
 
 * @return             true if stop was found.

			




	
	
	
		
 
 */

			




	
	
	
		
 
bool YapfFindNearestRoadVehicleCompatibleStop(const RoadVehicle *v, StationID station, TileIndex *stop_tile);

			




	
	
	
		
 

			




	
	
	
		
 
/** Used when user sends road vehicle to the nearest depot or if road vehicle needs servicing.

			




	
	
	
		
 
 * @param v            vehicle that needs to go to some depot

			




	
	
	
		
 
 * @param max_distance max distance (number of track tiles) from the current vehicle position

			




        

    


    
    

    

        

                

                    src/yapf/yapf_road.cpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -12,6 +12,9 @@

			




	
	
	
		
 
#include "../stdafx.h"

			




	
	
	
		
 
#include "../depot_base.h"

			




	
	
	
		
 
#include "../roadveh.h"

			




	
	
	
		
 
#include "../roadstop_base.h"

			




	
	
	
		
 
#include "../cargotype.h"

			




	
	
	
		
 
#include "../newgrf_cargo.h"

			




	
	
	
		
 

			




	
	
	
		
 
#include "yapf.hpp"

			




	
	
	
		
 
#include "yapf_node_road.hpp"

			




	
	
		
 
@@ -186,6 +189,78 @@ public:

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
template <class Types>

			




	
	
	
		
 
class CYapfDestinationAnyRoadVehicleCompatibleStopOfGivenStationT

			




	
	
	
		
 
{

			




	
	
	
		
 
public:

			




	
	
	
		
 
	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)

			




	
	
	
		
 
	typedef typename Types::TrackFollower TrackFollower;

			




	
	
	
		
 
	typedef typename Types::NodeList::Titem Node;        ///< this will be our node type

			




	
	
	
		
 
	typedef typename Node::Key Key;                      ///< key to hash tables

			




	
	
	
		
 

			




	
	
	
		
 
	TileIndex      m_destTile;

			




	
	
	
		
 
	StationID      m_dest_station;

			




	
	
	
		
 
	bool           m_bus;

			




	
	
	
		
 
	bool           m_non_artic;

			




	
	
	
		
 

			




	
	
	
		
 
	/** to access inherited path finder */

			




	
	
	
		
 
	Tpf& Yapf()

			




	
	
	
		
 
	{

			




	
	
	
		
 
		return *static_cast<Tpf*>(this);

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	void SetDestination(const RoadVehicle *v, StationID sid, TileIndex destTile)

			




	
	
	
		
 
	{

			




	
	
	
		
 
		m_dest_station = sid;

			




	
	
	
		
 
		m_destTile     = destTile;

			




	
	
	
		
 
		m_bus          = IsCargoInClass(v->cargo_type, CC_PASSENGERS);

			




	
	
	
		
 
		m_non_artic    = !v->HasArticulatedPart();

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	/** Called by YAPF to detect if node ends in the desired destination */

			




	
	
	
		
 
	FORCEINLINE bool PfDetectDestination(Node& n)

			




	
	
	
		
 
	{

			




	
	
	
		
 
		return PfDetectDestinationTile(n.m_segment_last_tile, INVALID_TRACKDIR);

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	FORCEINLINE bool PfDetectDestinationTile(TileIndex tile, Trackdir trackdir)

			




	
	
	
		
 
	{

			




	
	
	
		
 
		return

			




	
	
	
		
 
			IsTileType(tile, MP_STATION) &&

			




	
	
	
		
 
			GetStationIndex(tile) == m_dest_station &&

			




	
	
	
		
 
			(m_bus ? IsBusStop(tile) : IsTruckStop(tile)) &&

			




	
	
	
		
 
			(m_non_artic || IsDriveThroughStopTile(tile));

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	/** Called by YAPF to calculate cost estimate. Calculates distance to the destination

			




	
	
	
		
 
	 *  adds it to the actual cost from origin and stores the sum to the Node::m_estimate */

			




	
	
	
		
 
	FORCEINLINE bool PfCalcEstimate(Node& n)

			




	
	
	
		
 
	{

			




	
	
	
		
 
		static const int dg_dir_to_x_offs[] = {-1, 0, 1, 0};

			




	
	
	
		
 
		static const int dg_dir_to_y_offs[] = {0, 1, 0, -1};

			




	
	
	
		
 
		if (PfDetectDestination(n)) {

			




	
	
	
		
 
			n.m_estimate = n.m_cost;

			




	
	
	
		
 
			return true;

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		TileIndex tile = n.m_segment_last_tile;

			




	
	
	
		
 
		DiagDirection exitdir = TrackdirToExitdir(n.m_segment_last_td);

			




	
	
	
		
 
		int x1 = 2 * TileX(tile) + dg_dir_to_x_offs[(int)exitdir];

			




	
	
	
		
 
		int y1 = 2 * TileY(tile) + dg_dir_to_y_offs[(int)exitdir];

			




	
	
	
		
 
		int x2 = 2 * TileX(m_destTile);

			




	
	
	
		
 
		int y2 = 2 * TileY(m_destTile);

			




	
	
	
		
 
		int dx = abs(x1 - x2);

			




	
	
	
		
 
		int dy = abs(y1 - y2);

			




	
	
	
		
 
		int dmin = min(dx, dy);

			




	
	
	
		
 
		int dxy = abs(dx - dy);

			




	
	
	
		
 
		int d = dmin * YAPF_TILE_CORNER_LENGTH + (dxy - 1) * (YAPF_TILE_LENGTH / 2);

			




	
	
	
		
 
		n.m_estimate = n.m_cost + d;

			




	
	
	
		
 
		assert(n.m_estimate >= n.m_parent->m_estimate);

			




	
	
	
		
 
		return true;

			




	
	
	
		
 
	}

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
template <class Types>

			




	
	
	
		
 
class CYapfDestinationTileRoadT

			




	
	
	
		
 
{

			




	
	
	
		
 
public:

			




	
	
		
 
@@ -414,6 +489,30 @@ public:

			




	
	
	
		
 
		*depot_tile = n->m_segment_last_tile;

			




	
	
	
		
 
		return true;

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	static bool stFindNearestRoadVehicleCompatibleStop(const RoadVehicle *v, TileIndex tile, TileIndex destTile, Trackdir td, StationID sid, TileIndex *stop_tile)

			




	
	
	
		
 
	{

			




	
	
	
		
 
		Tpf pf;

			




	
	
	
		
 
		return pf.FindNearestRoadVehicleCompatibleStop(v, tile, destTile, td, sid, stop_tile);

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	FORCEINLINE bool FindNearestRoadVehicleCompatibleStop(const RoadVehicle *v, TileIndex tile, TileIndex destTile, Trackdir td, StationID sid, TileIndex *stop_tile)

			




	
	
	
		
 
	{

			




	
	
	
		
 
		/* set origin and destination nodes */

			




	
	
	
		
 
		Yapf().SetOrigin(tile, TrackdirToTrackdirBits(td));

			




	
	
	
		
 
		Yapf().SetDestination(v, sid, destTile);

			




	
	
	
		
 

			




	
	
	
		
 
		/* find the best path */

			




	
	
	
		
 
		bool bFound = Yapf().FindPath(v);

			




	
	
	
		
 
		if (!bFound) return false;

			




	
	
	
		
 

			




	
	
	
		
 
		/* some path found

			




	
	
	
		
 
		 * get found depot tile */

			




	
	
	
		
 
		const Node *n = Yapf().GetBestNode();

			




	
	
	
		
 

			




	
	
	
		
 
		*stop_tile = n->m_segment_last_tile;

			




	
	
	
		
 
		return true;

			




	
	
	
		
 
	}

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
template <class Tpf_, class Tnode_list, template <class Types> class Tdestination>

			




	
	
		
 
@@ -438,6 +537,9 @@ struct CYapfRoad2         : CYapfT<CYapf

			




	
	
	
		
 
struct CYapfRoadAnyDepot1 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot1, CRoadNodeListTrackDir, CYapfDestinationAnyDepotRoadT> > {};

			




	
	
	
		
 
struct CYapfRoadAnyDepot2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyDepot2, CRoadNodeListExitDir , CYapfDestinationAnyDepotRoadT> > {};

			




	
	
	
		
 

			




	
	
	
		
 
struct CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation1 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation1, CRoadNodeListTrackDir, CYapfDestinationAnyRoadVehicleCompatibleStopOfGivenStationT> > {};

			




	
	
	
		
 
struct CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation2 : CYapfT<CYapfRoad_TypesT<CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation2, CRoadNodeListExitDir , CYapfDestinationAnyRoadVehicleCompatibleStopOfGivenStationT> > {};

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
Trackdir YapfChooseRoadTrack(const Vehicle *v, TileIndex tile, DiagDirection enterdir)

			




	
	
	
		
 
{

			




	
	
		
 
@@ -504,3 +606,29 @@ bool YapfFindNearestRoadDepot(const Vehi

			




	
	
	
		
 
	bool ret = pfnFindNearestDepot(v, tile, trackdir, max_distance, depot_tile);

			




	
	
	
		
 
	return ret;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
bool YapfFindNearestRoadVehicleCompatibleStop(const RoadVehicle *v, StationID station, TileIndex *stop_tile)

			




	
	
	
		
 
{

			




	
	
	
		
 
	*stop_tile = INVALID_TILE;

			




	
	
	
		
 

			




	
	
	
		
 
	const RoadStop *rs = Station::Get(station)->GetPrimaryRoadStop(v);

			




	
	
	
		
 
	if (rs == NULL) return false;

			




	
	
	
		
 

			




	
	
	
		
 
	TileIndex tile = v->tile;

			




	
	
	
		
 
	Trackdir trackdir = v->GetVehicleTrackdir();

			




	
	
	
		
 
	if ((TrackStatusToTrackdirBits(GetTileTrackStatus(tile, TRANSPORT_ROAD, RoadVehicle::From(v)->compatible_roadtypes)) & TrackdirToTrackdirBits(trackdir)) == 0) {

			




	
	
	
		
 
		return false;

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	/* default is YAPF type 2 */

			




	
	
	
		
 
	typedef bool (*PfnFindNearestRoadVehicleCompatibleStop)(const RoadVehicle*, TileIndex, TileIndex, Trackdir, StationID, TileIndex*);

			




	
	
	
		
 
	PfnFindNearestRoadVehicleCompatibleStop pfnFindNearestRoadVehicleCompatibleStop = &CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation2::stFindNearestRoadVehicleCompatibleStop;

			




	
	
	
		
 

			




	
	
	
		
 
	/* check if non-default YAPF type should be used */

			




	
	
	
		
 
	if (_settings_game.pf.yapf.disable_node_optimization) {

			




	
	
	
		
 
		pfnFindNearestRoadVehicleCompatibleStop = &CYapfRoadAnyRoadVehicleCompatibleStopOfGivenStation1::stFindNearestRoadVehicleCompatibleStop; // Trackdir, allow 90-deg

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	bool ret = pfnFindNearestRoadVehicleCompatibleStop(v, tile, rs->xy, trackdir, station, stop_tile);

			




	
	
	
		
 
	return ret;

			




	
	
	
		
 
}

			




        

    



    


    



    



      

      





    
    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