Horizon::Zone::AStar::Generator Class Reference

#include <AStar.hpp>

Collaboration diagram for Horizon::Zone::AStar::Generator:

Public Member Functions
	Generator ()
	Generator (MapCoords worldSize_, CollisionDetectionFunction c, bool diagonal_movement=true, HeuristicFunction h=&Heuristic::manhattan)
void	setWorldSize (MapCoords worldSize_)
void	setCollisionDetectionFunction (CollisionDetectionFunction c)
void	setDiagonalMovement (bool enable_)
void	setHeuristic (const HeuristicFunction &heuristic_)
CoordinateList	findPath (MapCoords source_, MapCoords target_)

Static Private Member Functions
static std::shared_ptr< Node >	findNodeOnList (NodeSet &nodes_, MapCoords coordinates_)
static void	releaseNodes (NodeSet nodes_)

Private Attributes
HeuristicFunction	heuristic
CollisionDetectionFunction	check_collision
CoordinateList	direction
MapCoords	worldSize
uint32_t	directions {0}

Constructor & Destructor Documentation

Generator() [1/2]

Horizon::Zone::AStar::Generator::Generator ( )

inline

    {
        setDiagonalMovement(true);
        setHeuristic(&Heuristic::manhattan);
    }

References Horizon::Zone::AStar::Heuristic::manhattan(), setDiagonalMovement(), and setHeuristic().

Here is the call graph for this function:

Generator() [2/2]

Horizon::Zone::AStar::Generator::Generator ( MapCoords  worldSize_, CollisionDetectionFunction  c, bool  diagonal_movement = true, HeuristicFunction  h = &Heuristic::manhattan  )

inline

    {
        setWorldSize(worldSize_);
        setCollisionDetectionFunction(std::move(c));
        setDiagonalMovement(diagonal_movement);
        setHeuristic(h);
    }

References setCollisionDetectionFunction(), setDiagonalMovement(), setHeuristic(), and setWorldSize().

Here is the call graph for this function:

Member Function Documentation

findNodeOnList()

static std::shared_ptr< Node > Horizon::Zone::AStar::Generator::findNodeOnList ( NodeSet &  nodes_, MapCoords  coordinates_  )

inlinestaticprivate

    {
        for (auto node : nodes_) {
            if (node->coordinates == coordinates_) {
                return node;
            }
        }
        return nullptr;
    }

Referenced by findPath().

Here is the caller graph for this function:

findPath()

CoordinateList Horizon::Zone::AStar::Generator::findPath ( MapCoords  source_, MapCoords  target_  )

inline

    {
        CoordinateList path;
        std::shared_ptr<Node> current = nullptr;
        NodeSet openSet, closedSet;
        int searchStep = 0;
 
        openSet.reserve(20);
        closedSet.reserve(20);
        openSet.push_back(std::make_shared<Node>(source_));
 
        if (check_collision(target_.x(), target_.y()))
            return path;
 
        while (!openSet.empty() && searchStep < MAX_VIEW_RANGE) {
            auto current_it = openSet.begin();
            
            current = *current_it;
 
            for (auto it = openSet.begin(); it != openSet.end(); it++) {
                auto node = *it;
                if (node->getFScore() <= current->getFScore()) {
                    current = node;
                    current_it = it;
                }
            }
 
            if (current->coordinates == target_)
                break;
 
            closedSet.push_back(current);
            openSet.erase(current_it);
 
            for (uint32_t i = 0; i < directions; ++i) {
                MapCoords newCoordinates(current->coordinates + direction[i]);
 
                if (check_collision(newCoordinates.x(), newCoordinates.y()) 
                    || findNodeOnList(closedSet, newCoordinates)) {
                    continue;
                }
 
                newCoordinates.set_move_cost((i < 4) ? 10 : 14);
                uint32_t totalCost = current->G + newCoordinates.move_cost();
 
                std::shared_ptr<Node> successor = findNodeOnList(openSet, newCoordinates);
                if (successor == nullptr) {
                    successor = std::make_shared<Node>(newCoordinates, current);
                    successor->G = totalCost;
                    successor->H = heuristic(successor->coordinates, target_);
                    openSet.push_back(successor);
                } else if (totalCost < successor->G) {
                    successor->parent = current;
                    successor->G = totalCost;
                }
            }
 
            searchStep++;
        }
 
        while (current != nullptr) {
            path.push_back(current->coordinates);
            current = current->parent;
        }
 
        releaseNodes(openSet);
        releaseNodes(closedSet);
 
        return path;
    }

References check_collision, direction, directions, findNodeOnList(), heuristic, MAX_VIEW_RANGE, Coordinates< MAX_COORDINATES >::move_cost(), releaseNodes(), Coordinates< MAX_COORDINATES >::set_move_cost(), Coordinates< MAX_COORDINATES >::x(), and Coordinates< MAX_COORDINATES >::y().

Here is the call graph for this function:

releaseNodes()

static void Horizon::Zone::AStar::Generator::releaseNodes ( NodeSet  nodes_ )

inlinestaticprivate

    {
        for (auto it = nodes_.begin(); it != nodes_.end();) {
            it = nodes_.erase(it);
        }
    }

Referenced by findPath().

Here is the caller graph for this function:

setCollisionDetectionFunction()

void Horizon::Zone::AStar::Generator::setCollisionDetectionFunction ( CollisionDetectionFunction  c )

inline

{ check_collision = c; };

References check_collision.

Referenced by Generator().

Here is the caller graph for this function:

setDiagonalMovement()

void Horizon::Zone::AStar::Generator::setDiagonalMovement ( bool  enable_ )

inline

{ directions = (enable_ ? 8 : 4); }

Referenced by Generator().

Here is the caller graph for this function:

setHeuristic()

void Horizon::Zone::AStar::Generator::setHeuristic ( const HeuristicFunction &  heuristic_ )

inline

{ heuristic = [heuristic_](auto && PH1, auto && PH2) { return heuristic_(std::forward<decltype(PH1)>(PH1), std::forward<decltype(PH2)>(PH2)); }; }

References heuristic.

Referenced by BOOST_AUTO_TEST_CASE(), and Generator().

Here is the caller graph for this function:

setWorldSize()

void Horizon::Zone::AStar::Generator::setWorldSize ( MapCoords  worldSize_ )

inline

{ worldSize = worldSize_; }

References worldSize.

Referenced by Generator().

Here is the caller graph for this function:

Member Data Documentation

check_collision

CollisionDetectionFunction Horizon::Zone::AStar::Generator::check_collision

private

Referenced by findPath(), and setCollisionDetectionFunction().

direction

CoordinateList Horizon::Zone::AStar::Generator::direction

private

Initial value:

= {
        { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 },
        { -1, -1 }, { 1, 1 }, { -1, 1 }, { 1, -1 }
    }

Referenced by findPath().

directions

uint32_t Horizon::Zone::AStar::Generator::directions {0}

private

Referenced by findPath().

heuristic

HeuristicFunction Horizon::Zone::AStar::Generator::heuristic

private

Referenced by findPath(), and setHeuristic().

worldSize

MapCoords Horizon::Zone::AStar::Generator::worldSize

private

Referenced by setWorldSize().

---

The documentation for this class was generated from the following file:

• src/Server/Zone/Game/Map/Path/AStar.hpp