Skip to content

Instantly share code, notes, and snippets.

@Rseding91

Rseding91/TrainPathFinder.cpp

Last active May 1, 2023 16:28
Show Gist options
  • Save Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 to your computer and use it in GitHub Desktop.
Save Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 to your computer and use it in GitHub Desktop.
Download ZIP
Factorio TrainPathFinder
Raw
TrainPathFinder.cpp
#include <Entity/Rail.hpp>
#include <Entity/RailSignalBase.hpp>
#include <Rail/RailBlock.hpp>
#include <Rail/RailPath.hpp>
#include <Rail/TrainPathFinder.hpp>
#include <Rail/RailSegment.hpp>
#include <Rail/RailUtil.hpp>
#include <Rail/Train.hpp>
#include <Util/Container/MinHeap.hpp>
#include <Log.hpp>
TrainPathFinderConstants TrainPathFinder::constants;
class TrainPathFinderNode : public MinHeap<TrainPathFinderNode>::ItemBase
{
public:
enum class Type {
Normal,
StartNodeFront,
StartNodeBack,
SingleSegmentMarker
};
TrainPathFinderNode() = default;
TrainPathFinderNode(RailSegment* segment,
RailDirection enterDirection,
const TrainPathFinderNode* cameFrom,
uint32_t blockDistanceFromStart,
bool setSeen,
InChainSignalSection inChainSignalSection)
: cameFrom(cameFrom)
, segment(segment)
, blockDistanceFromStart(blockDistanceFromStart)
, enterDirection(enterDirection)
, inChainSignalSection(inChainSignalSection)
{
if (setSeen && this->segment)
this->segment->setSeen(this->enterDirection, inChainSignalSection, this);
}
~TrainPathFinderNode()
{
if (this->segment)
{
this->segment->seenForwards = nullptr;
this->segment->seenBackwards = nullptr;
this->segment->seenForwardsInChainSequence = nullptr;
this->segment->seenBackwardsInChainSequence = nullptr;
this->segment->hasEnd = false;
}
}
bool operator<(const TrainPathFinderNode& other) const
{
assert(this->segment && other.segment);
if (this->segment != other.segment)
return this->segment->getID() < other.segment->getID();
if (this->enterDirection != other.enterDirection)
return this->enterDirection == RailDirection::Front && other.enterDirection == RailDirection::Back;
if (this->type != other.type)
return this->type < other.type;
assert(false);
return false;
}
public:
const TrainPathFinderNode* cameFrom = nullptr;
double costFromStart = 0;
double heuristicCostToEnd = 0;
/** This is the end at which we enter the segment. */
RailSegment* segment = nullptr;
// how many blocks are there between this node and start node
uint32_t blockDistanceFromStart = 0;
RailDirection enterDirection;
InChainSignalSection inChainSignalSection = InChainSignalSection::False;
Type type = Type::Normal;
};
class Data
{
public:
Data() = default;
Data(const Data&) = delete;
Data(Data&&) = delete;
Data& operator=(const Data&) = delete;
Data& operator=(Data&&) = delete;
~Data() = default;
MinHeap<TrainPathFinderNode> heap;
template<typename ... Ts>
TrainPathFinderNode* createNode(Ts&& ... values)
{
return new (this->nodeProvider.allocate())TrainPathFinderNode(std::forward<Ts>(values) ...);
}
private:
TypeAwareMemoryPool<TrainPathFinderNode, 24, BlockExpandMode::DuringAllocate> nodeProvider;
};
class TrainPathFinderHeuristic
{
public:
TrainPathFinderHeuristic() = delete;
TrainPathFinderHeuristic(const TrainPathFinder::Request& request);
~TrainPathFinderHeuristic() = default;
double costToEnd(const TrainPathFinderNode* node) const;
private:
std::vector<MapPosition> goals;
};
void TrainPathFinder::findPath(Request& request)
{
uint32_t endsFound = 0;
if (request.type == TrainPathRequestType::GetAccessibleStateOfAllEnds)
request.endAccessabilities.reset(new std::vector<char>(request.toEnds.size()));
Data pfData;
TrainPathFinderHeuristic heuristic(request);
// setup special node for single segment solution
RailEnd* bestSingleSegmentPathEnd = nullptr;
{
double bestSingleSegmentDistance = 0;
for (RailEnd& toEnd : request.toEnds)
{
// straight path to the front
if (request.allowPathWithinSegmentFront &&
request.fromEndFront.rail &&
toEnd.rail->segment == request.fromEndFront.rail->segment)
{
double currentDistance = 0;
if (TrainPathFinder::findPathWithinSegment(request.fromEndFront, toEnd, currentDistance))
{
if (request.type == TrainPathRequestType::GetAccessibleStateOfAllEnds &&
TrainPathFinder::constructPath(request, toEnd, nullptr, endsFound))
return;
if (bestSingleSegmentPathEnd == nullptr || currentDistance < bestSingleSegmentDistance)
{
bestSingleSegmentPathEnd = &toEnd;
bestSingleSegmentDistance = currentDistance;
}
}
}
// straight path to the back
if (request.allowPathWithinSegmentBack &&
request.fromEndBack.rail &&
toEnd.rail->segment == request.fromEndBack.rail->segment)
{
double currentDistance = 0;
if (TrainPathFinder::findPathWithinSegment(request.fromEndBack, toEnd, currentDistance))
{
if (request.type == TrainPathRequestType::GetAccessibleStateOfAllEnds &&
TrainPathFinder::constructPath(request, toEnd, nullptr, endsFound))
return;
if (bestSingleSegmentPathEnd == nullptr || currentDistance < bestSingleSegmentDistance)
{
bestSingleSegmentPathEnd = &toEnd;
bestSingleSegmentDistance = currentDistance;
}
}
}
}
if (bestSingleSegmentPathEnd && (request.type != TrainPathRequestType::GetAccessibleStateOfAllEnds))
{
// there exists single segment path. Create special node (marker) so this solution is returned only when all other (multi segment) paths are worse
TrainPathFinderNode* singleSegmentPathMarker = pfData.createNode(bestSingleSegmentPathEnd->rail->segment, RailDirection::Front/*dummy*/, nullptr, 0, false /* setSeen */, request.inChainSignalSection);
singleSegmentPathMarker->type = TrainPathFinderNode::Type::SingleSegmentMarker;
singleSegmentPathMarker->insertTo(pfData.heap, bestSingleSegmentDistance);
}
}
// init starting nodes
if (request.fromEndFront.rail)
{
bool isCycle;
double costFromStart = 0;
RailDirection leaveSegmentDirection = TrainPathFinder::calcLeaveSegmentDirection(request.fromEndFront.rail,
request.fromEndFront.direction,
isCycle,
costFromStart).opposite();
if (!isCycle || request.allowPathWithinSegmentFront == false)
{
RailSegment* segment = request.fromEndFront.rail->segment;
// not setting seen in the first segment, so we can pathfind to the same segment we started in
TrainPathFinderNode* startNodeFront = pfData.createNode(segment, leaveSegmentDirection, nullptr, 0, false /* setSeen */, request.inChainSignalSection);
startNodeFront->type = TrainPathFinderNode::Type::StartNodeFront;
startNodeFront->costFromStart = costFromStart;
startNodeFront->heuristicCostToEnd = heuristic.costToEnd(startNodeFront);
startNodeFront->insertTo(pfData.heap, startNodeFront->costFromStart + startNodeFront->heuristicCostToEnd);
}
}
if (request.fromEndBack.rail)
{
bool isCycle;
double costFromStart = 0;
RailDirection leaveSegmentDirection = TrainPathFinder::calcLeaveSegmentDirection(request.fromEndBack.rail,
request.fromEndBack.direction,
isCycle,
costFromStart).opposite();
if (!isCycle || request.allowPathWithinSegmentBack == false)
{
RailSegment* segment = request.fromEndBack.rail->segment;
// not setting seen in the first segment, so we can pathfind to the same segment we started in
TrainPathFinderNode* startNodeBack = pfData.createNode(segment, leaveSegmentDirection, nullptr, 0, false /* setSeen */, request.inChainSignalSection);
startNodeBack->type = TrainPathFinderNode::Type::StartNodeBack;
startNodeBack->costFromStart = costFromStart;
startNodeBack->heuristicCostToEnd = heuristic.costToEnd(startNodeBack);
startNodeBack->insertTo(pfData.heap, startNodeBack->costFromStart + startNodeBack->heuristicCostToEnd);
}
}
for (const RailEnd& toEnd : request.toEnds)
if (RailSegment* segmentWithEnd = toEnd.rail->segment)
{
// dummy node so when it is destroyed, it will clear hasEnd flag
(void)pfData.createNode(segmentWithEnd, RailDirection::Front, nullptr, 0, false /* setSeen */, InChainSignalSection::False);
segmentWithEnd->hasEnd = true;
}
std::vector<Pair<RailSegment*, RailDirection>> scratch;
scratch.reserve(3);
// main path finding logic
while (TrainPathFinderNode* currentNode = pfData.heap.pop_top())
{
RailSegment* currentSegment = currentNode->segment;
RailDirection currentLeaveDirection = currentNode->enterDirection.opposite();
if (currentSegment->hasEnd)
{
// found path check
if (currentNode->type == TrainPathFinderNode::Type::Normal)
{
// regular multi-segment path node. Check ends for possible path
assert(currentNode->cameFrom);
for (const RailEnd& toEnd : request.toEnds)
if (toEnd.rail->segment == currentSegment &&
TrainPathFinder::findPathWithinSegment(currentSegment, currentNode->enterDirection, toEnd) &&
TrainPathFinder::constructPath(request, toEnd, currentNode, endsFound))
return;
}
else if (currentNode->type == TrainPathFinderNode::Type::SingleSegmentMarker)
{
// special node that when reached, means that all other paths have worse cost than single segment
// solution that was already found. Use existing single segment solution instead
assert(bestSingleSegmentPathEnd);
if (TrainPathFinder::constructPath(request, *bestSingleSegmentPathEnd, nullptr, endsFound))
return;
continue; // never expand from this special node
}
}
InChainSignalSection inChainSignalSection = currentNode->inChainSignalSection;
if (!currentSegment->canEverLeaveSegment(currentLeaveDirection, &inChainSignalSection, request.train))
continue;
// expand neighbors
for (Pair<RailSegment*, RailDirection> neighbor : currentSegment->getSegmentsWithEnterDirections(currentLeaveDirection, scratch))
{
RailSegment *neighborSegment = neighbor.first;
RailDirection neighborEnterDirection = neighbor.second;
// one way segment
if (!neighborSegment->canEverEnterSegment(neighborEnterDirection, &inChainSignalSection, request.train))
continue;
TrainPathFinderNode* seenNode = nullptr;
if (neighborEnterDirection == RailDirection::Enum::Front)
if (inChainSignalSection == InChainSignalSection::False)
seenNode = neighborSegment->seenForwards;
else
seenNode = neighborSegment->seenForwardsInChainSequence;
else
if (inChainSignalSection == InChainSignalSection::False)
seenNode = neighborSegment->seenBackwards;
else
seenNode = neighborSegment->seenBackwardsInChainSequence;
double costFromStart = currentNode->costFromStart;
if (seenNode)
{
// node was already expanded (exists and is detached), no need to process this neighbor again
if (!seenNode->is_linked())
continue;
// early skip if existing path is better (same heuristic on both sides skipped)
if (seenNode->costFromStart <= costFromStart)
continue;
}
// Transition from currentSegment to neighbor penalties
RailSignalBase* neighborInSignal = neighborSegment->getSignalIn(neighborEnterDirection);
RailSignalBase* outSignal = currentSegment->getSignalOut(currentLeaveDirection);
if ((outSignal && (outSignal->getReservedByCircuitNetwork() || outSignal->getReserveForCircuitNetworkWhenPossible()))
|| (neighborInSignal && (neighborInSignal->getReservedByCircuitNetwork() || neighborInSignal->getReserveForCircuitNetworkWhenPossible())))
costFromStart += TrainPathFinder::constants.signalReservedByCircuitNetworkPenalty;
if (currentSegment->getStop(currentLeaveDirection) && currentNode->type == TrainPathFinderNode::Type::Normal)
costFromStart += TrainPathFinder::constants.trainStopPenalty;
if (neighborSegment->getStop(neighborEnterDirection))
costFromStart += TrainPathFinder::constants.trainStopPenalty;
// Add some cost to the path depending on what are the trains doing in the block
if (neighborSegment->getBlock() != currentSegment->getBlock())
{
for (auto& item : neighborSegment->getBlock()->getTrainsInBlock())
{
const Train* neighbourTrain = item.first;
if (neighbourTrain == request.train)
continue;
switch (neighbourTrain->getState())
{
case TrainState::WAIT_STATION:
costFromStart += TrainPathFinder::constants.trainInStationPenalty;
if (neighbourTrain->getTicksInStation() == uint32_t(-1))
costFromStart += TrainPathFinder::constants.trainInStationWithNoOtherValidStopsInSchedule;
break;
case TrainState::ARRIVE_STATION:
costFromStart += TrainPathFinder::constants.trainArrivingToStationPenalty;
break;
case TrainState::MANUAL_CONTROL:
if (neighbourTrain->getSpeed() == 0)
if (neighbourTrain->hasPassenger())
costFromStart += TrainPathFinder::constants.stoppedManuallyControlledTrainPenalty;
else
// The train is in manual mode with no passenger - it's not going to move any time soon.
costFromStart += TrainPathFinder::constants.stoppedManuallyControlledTrainWithoutPassengerPenalty;
break;
case TrainState::ARRIVE_SIGNAL:
costFromStart += TrainPathFinder::constants.trainArrivingToSignalPenalty;
break;
case TrainState::WAIT_SIGNAL:
costFromStart += neighbourTrain->getTicksWaitingAtSignal() * TrainPathFinder::constants.trainWaitingAtSignalTickMultiplierPenalty +
TrainPathFinder::constants.trainWaitingAtSignalPenalty;
break;
case TrainState::NO_PATH:
costFromStart += TrainPathFinder::constants.trainWithNoPathPenalty;
break;
default: break;
}
}
}
// Neighbor segment penalties
if (!neighborSegment->getBlock()->isFree(request.train))
costFromStart += (2 * neighborSegment->getLength()) / (currentNode->blockDistanceFromStart + 1);
costFromStart += neighborSegment->getLength();
// node expand/update
uint32_t newBlockDistanceFromStart = currentNode->blockDistanceFromStart;
if (currentSegment->getBlock() != neighborSegment->getBlock())
newBlockDistanceFromStart++;
if (seenNode)
{
// skip if existing path is better (same heuristic on both sides skipped)
if (seenNode->costFromStart <= costFromStart)
continue;
seenNode->cameFrom = currentNode;
seenNode->blockDistanceFromStart = newBlockDistanceFromStart;
seenNode->costFromStart = costFromStart;
seenNode->decreaseValue(seenNode->costFromStart + seenNode->heuristicCostToEnd);
}
else
{
TrainPathFinderNode* newNode = pfData.createNode(neighborSegment,
neighborEnterDirection,
currentNode,
newBlockDistanceFromStart,
true /* setSeen */,
inChainSignalSection);
newNode->costFromStart = costFromStart;
newNode->heuristicCostToEnd = heuristic.costToEnd(newNode);
newNode->insertTo(pfData.heap, newNode->costFromStart + newNode->heuristicCostToEnd);
}
}
}
// no path
}
TrainPathFinderHeuristic::TrainPathFinderHeuristic(const TrainPathFinder::Request& request)
{
this->goals.reserve(request.toEnds.size());
for (const RailEnd& toEnd : request.toEnds)
this->goals.push_back(toEnd.rail->getPosition(0.0, toEnd.direction));
}
double TrainPathFinderHeuristic::costToEnd(const TrainPathFinderNode* node) const
{
RailDirection leaveDirection = node->enterDirection.opposite();
Rail* lastRail = node->segment->getEndRail(leaveDirection);
RailDirection lastRailDirection = RailSegment::getEndRailDirectionTo(lastRail, leaveDirection);
MapPosition position = lastRail->getPosition(0.0, lastRailDirection);
double lowestDistanceSquared = std::numeric_limits<double>::infinity();
for (const MapPosition& goal : this->goals)
lowestDistanceSquared = std::min(lowestDistanceSquared, position.distanceSquared(goal));
return Math::sqrt(lowestDistanceSquared);
}
bool TrainPathFinder::constructPath(Request& request, const RailEnd& toEnd, const TrainPathFinderNode* lastNode, uint32_t& endsFound)
{
if (request.type == TrainPathRequestType::GetAccessibleStateOfAllEnds)
if (!(*request.endAccessabilities)[&toEnd - &request.toEnds[0]])
{
(*request.endAccessabilities)[&toEnd - &request.toEnds[0]] = true;
++endsFound;
return endsFound == request.endAccessabilities->size();
}
else
return false;
if (request.type == TrainPathRequestType::GetAccessibleStateOfAnyEnd)
{
request.someEndAccessible = true;
return true;
}
RailPathCollector pathCollector;
// when we encounter first rail from the opposite direction we are finished
RailEnd stopFront(request.fromEndFront.rail, request.fromEndFront.direction.opposite());
RailEnd stopBack(request.fromEndBack.rail, request.fromEndBack.direction.opposite());
bool stoppedAtFront;
// we go through the whole path backwards and in the end we will reverse it
// the reason for going backwards is that the nodes can be tracked from the end to the beginning only
// add rails from the last node
if (TrainPathFinder::addRailsToPath(toEnd.rail,
toEnd.direction.opposite(),
stopFront,
stopBack,
pathCollector,
stoppedAtFront,
lastNode == nullptr || lastNode->cameFrom == nullptr))
{
if (request.type == TrainPathRequestType::SimpleRailPath)
request.simpleRailPathResult.reset(pathCollector.convertToSimplePath(stoppedAtFront));
else
request.railPathResult.reset(pathCollector.convertToPath(stoppedAtFront));
return true;
}
// add rails from the intermediate segments
assert(lastNode);
const TrainPathFinderNode* node = lastNode->cameFrom;
while (node != nullptr)
{
// start from the rail at the end of the segment where we left the segment
Rail* lastRail = node->segment->getEndRail(node->enterDirection.opposite());
RailDirection goBackDirection = RailSegment::getEndRailDirectionTo(lastRail, node->enterDirection.opposite()).opposite();
if (TrainPathFinder::addRailsToPath(lastRail,
goBackDirection,
stopFront,
stopBack,
pathCollector,
stoppedAtFront,
node->cameFrom == nullptr))
{
if (request.type == TrainPathRequestType::SimpleRailPath)
request.simpleRailPathResult.reset(pathCollector.convertToSimplePath(stoppedAtFront));
else
request.railPathResult.reset(pathCollector.convertToPath(stoppedAtFront));
return true;
}
node = node->cameFrom;
}
LOG_AND_ABORT("Failed to construt path.");
}
bool TrainPathFinder::addRailsToPath(Rail* rail,
RailDirection direction,
const RailEnd& stopEndFront,
const RailEnd& stopEndBack,
RailPathCollector& pathCollector,
bool& stoppedAtFront,
bool isLastSegment)
{
Rail::PlainIterator it = Rail::PlainIterator(rail, direction);
while (!it.ended() &&
it.rail->segment == rail->segment &&
(!isLastSegment || it.rail != stopEndFront.rail || it.direction != stopEndFront.direction) &&
(!isLastSegment || it.rail != stopEndBack.rail || it.direction != stopEndBack.direction))
{
pathCollector.append(it.rail);
++it;
// Abort on intersection even if it goes into same segment. This is to not collect rails that are from
// other node as going in cycle would end where we started, not where node ends and path would not be contiguous
// when next node rails would be collected
if (it.rail && it.rail->connection(it.direction.opposite()).getConnectionCount() != 1)
return false;
}
if (!it.ended() && isLastSegment && it.rail == stopEndFront.rail && it.direction == stopEndFront.direction)
{
pathCollector.append(it.rail);
stoppedAtFront = true;
return true;
}
if (!it.ended() && isLastSegment && it.rail == stopEndBack.rail && it.direction == stopEndBack.direction)
{
pathCollector.append(it.rail);
stoppedAtFront = false;
return true;
}
return false;
}
RailDirection TrainPathFinder::calcLeaveSegmentDirection(Rail* rail,
RailDirection direction,
bool& isCycle,
double& distance)
{
Rail* last = rail;
Rail* firstEdgeRail = nullptr;
if (rail->segment->isEndRail(rail))
firstEdgeRail = rail;
Rail::PlainIterator it = ++Rail::PlainIterator(rail, direction);
while (!it.ended() &&
it.rail->segment == rail->segment)
{
last = it.rail;
++it;
distance += last->length();
// this covering a very special case, where we have a cycle with one extra junction
if (it.rail && it.rail->connection(it.direction.opposite()).getConnectionCount() != 1)
{
isCycle = false;
return last->segment->getSegmentEndDirection(last, direction);
}
if (firstEdgeRail == nullptr && rail->segment->isEndRail(last))
firstEdgeRail = last;
}
isCycle = it.isCycle();
assert(last->segment->isEndRail(last) || isCycle);
// when is a cycle the return value is not used anyway
if (isCycle)
return firstEdgeRail == rail->segment->getFrontRail() ? RailDirection::Front : RailDirection::Back;
return last->segment->getSegmentEndDirection(last, direction);
}
bool TrainPathFinder::findPathWithinSegment(const RailEnd& fromEnd, const RailEnd& toEnd, double& distance)
{
// simple case when the toRail is at the end
Rail::PlainIterator it = Rail::PlainIterator(fromEnd.rail, fromEnd.direction);
while (!it.ended() &&
it.rail->segment == fromEnd.rail->segment &&
(it.rail != toEnd.rail || it.direction != toEnd.direction))
{
distance += it.rail->length();
++it;
// wee need to avoid intersections even when it is the same segment, as the rails can be connected by a loop from the other side.
// the lack of intersection from the last rail to this one is already guarded by the Rail::PlainIterator::operator++,
// but there can be intersection that merges the two rails.
if (it.rail && it.rail->connection(it.direction.opposite()).getConnectionCount() != 1)
return false;
}
return (!it.ended() && it.rail == toEnd.rail && it.direction == toEnd.direction);
}
bool TrainPathFinder::findPathWithinSegment(RailSegment* segment, RailDirection enterDirection, const RailEnd& toEnd)
{
assert(segment == toEnd.rail->segment);
Rail* fromRail = segment->getEndRail(enterDirection);
RailDirection fromDirection = RailSegment::getEndRailDirectionTo(fromRail, enterDirection).opposite();
double distance = 0;
return TrainPathFinder::findPathWithinSegment(RailEnd(fromRail, fromDirection), toEnd, distance);
}
TrainPathFinder::Request::Request(TrainPathRequestType type,
const RailEnd& fromFront,
const RailEnd& fromBack,
std::vector<RailEnd>&& toEnds,
Train* train,
InChainSignalSection inChainSignalSection)
: fromEndFront(fromFront)
, fromEndBack(fromBack)
, toEnds(std::move(toEnds))
, train(train)
, type(type)
, inChainSignalSection(inChainSignalSection)
{}
TrainPathFinder::Request::Request(TrainPathRequestType type,
Train* from,
std::vector<RailEnd>&& toEnds,
InChainSignalSection inChainSignalSection,
SearchDirection searchDirection)
: fromEndFront(nullptr, RailDirection::Front) // these are assigned in the end
, fromEndBack(nullptr, RailDirection::Front)
, toEnds(std::move(toEnds))
, train(from)
, type(type)
, inChainSignalSection(inChainSignalSection)
{
Train::TrainEnd frontEnd = this->train->getFrontEnd();
Train::TrainEnd backEnd = this->train->getBackEnd();
Rail* frontRail;
Rail* backRail;
if (searchDirection == SearchDirection::RespectMovementDirection)
{
// the path is searched only in the direction of movement (or in both when stopped)
frontRail = this->train->getSpeed() >= 0 && !this->train->getFrontMovers().empty() ? frontEnd.getRail() : nullptr;
backRail = this->train->getSpeed() <= 0 && !this->train->getBackMovers().empty() ? backEnd.getRail() : nullptr;
}
else if (searchDirection == SearchDirection::AnyDirectionWithLocomotives)
{
frontRail = !this->train->getFrontMovers().empty() ? frontEnd.getRail() : nullptr;
backRail = !this->train->getBackMovers().empty() ? backEnd.getRail() : nullptr;
}
else
LOG_ENUM_AND_ABORT(searchDirection);
// for pathfinding the from direction is the outgoing direction from the rail
this->fromEndFront = RailEnd(frontRail, frontEnd.getFromDirection().opposite());
this->fromEndBack = RailEnd(backRail, backEnd.getFromDirection());
}
TrainPathFinder::Request::~Request() = default;
Raw
TrainPathFinder.hpp
#pragma once
#include <Rail/InChainSignalSection.hpp>
#include <Rail/RailEnd.hpp>
#include <Rail/TrainPathFinderConstants.hpp>
#include <Rail/TrainPathRequestType.hpp>
#include <Util/TypeAwareMemoryPool.hpp>
class RailPathCollector;
class RailPath;
class SimpleRailPath;
class RailSegment;
class Train;
class TrainPathFinderNode;
class TrainPathFinder
{
public:
enum class SearchDirection
{
RespectMovementDirection,
AnyDirectionWithLocomotives
};
class Request
{
public:
Request(TrainPathRequestType type,
const RailEnd& fromFront,
const RailEnd& fromBack,
std::vector<RailEnd>&& toEnds,
Train* train,
InChainSignalSection inChainSignalSection);
Request(TrainPathRequestType type,
Train* from,
std::vector<RailEnd>&& toEnds,
InChainSignalSection inChainSignalSection,
SearchDirection searchDirection);
~Request();
/** The are two possible starts because we can go from front or from the back of the train.
For the start direction is the outgoing direction. */
RailEnd fromEndFront;
RailEnd fromEndBack;
std::vector<RailEnd> toEnds; // For the goal direction is the outgoing direction as well.
Train* train;
TrainPathRequestType type;
// When true, the resulting path mustn't encounter closed signal until it reaches the chain signal sequence exit
InChainSignalSection inChainSignalSection = InChainSignalSection::False;
bool allowPathWithinSegmentFront = true; // the target stop is already on my rail, but the train is too far to be aligned,
// so I need to find a path around to re-approach the station
bool allowPathWithinSegmentBack = true;
std::unique_ptr<RailPath> railPathResult; // related to TrainPathRequestType::Normal
std::unique_ptr<SimpleRailPath> simpleRailPathResult; // related to TrainPathRequestType::SimpleRailPath
std::unique_ptr<std::vector<char>> endAccessabilities; //related to TrainPathRequestType::GetAccessibleStateOfAllEnds
bool someEndAccessible = false; // related to TrainPathRequestType::GetAccessibleStateOfAnyEnd
};
static void findPath(Request& request); // stores the result(s) into the request class depending on what is requested
private:
/** Searches for a path within the segment. */
static bool findPathWithinSegment(const RailEnd& fromEnd, const RailEnd& toEnd, double& distance);
/** Wrapper around previous function version. Transforms segmentStartEnd to rail and it inner direction. */
static bool findPathWithinSegment(RailSegment* segment, RailDirection enterDirection, const RailEnd& toEnd);
static bool constructPath(Request& request, const RailEnd& toEnd, const TrainPathFinderNode* lastNode, uint32_t& endsFound);
/** Helper function for path construction.
* @return true if hit the stopRail from the stopDirection */
static bool addRailsToPath(Rail* rail,
RailDirection direction,
const RailEnd& stopFront,
const RailEnd& stopBack,
RailPathCollector& pathCollector,
/** Whether we hit the stopRailFront or StopRailBack.*/
bool& stoppedAtFront,
bool isLastSegment);
/** If we start on rail and follow the direction at what segment direction will we leave the rail segment. */
static RailDirection calcLeaveSegmentDirection(Rail* rail, RailDirection direction, bool& isCycle, double& distance);
public:
static TrainPathFinderConstants constants; // these are copied from UtilityConstants on load for faster access
};
@BRNSystems
Copy link

Where is the part that chooses the optimal path to running the most players over?
(joke)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment