Factorio TrainPathFinder

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;

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
};

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