spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

#include "AStar.h"

int main() {
    AStar *star = new AStar();
    star->findPath();
    star->print();
    delete star;

    cin.get();
    return 0;
}

C-/C++-Quelltext

#ifndef ASTAR_H
#define ASTAR_H

#include "NodeMap.h"
#include <iostream>
#include <set>
#include <list>

using namespace std;

struct ANodePtrComp{
    bool operator()(const Node* n1, const Node* n2) const  { return n1->getF() < n2->getF(); }
};

class AStar
{
public:
    AStar();
    ~AStar();

    void print();

    void findPath();

    

private:
    void addNodeToOpenList(Node* node);

    Node* getLastNodeFromOpenList();
    void eraseNodeFromOpenList(Node* node);

    void print(Node* node);
    void updateNode(int i, float g, Node* n);
private:
    NodeMap* nodeMap;

    multiset<Node*, ANodePtrComp> openList; //easy way!
};

#endif

C-/C++-Quelltext

#include "AStar.h"


AStar::AStar(){
    nodeMap = new NodeMap(9,5);
    nodeMap->initialize();
    nodeMap->setStartPoint(0,0);
    nodeMap->setEndPoint(8,4);
}

AStar::~AStar(){
    delete nodeMap;
    nodeMap = 0;
}

void AStar::print(){
    print(nodeMap->getCurrentEndPoint());
    cout << "\nFinal way." << endl;
    nodeMap->print();
    cin.get();
}

void AStar::print(Node* node){
    
    cout << "x: "
    << node->getPosition().x << " "
    << "y: "
    << node->getPosition().y << endl;

    if(!node->isStartNode() && node->getParentNode() != 0){
        node->setAsFinalWaypoint();
        print(node->getParentNode());
    }
}

void AStar::findPath(){
    bool found = 0;
    Node* startNode = nodeMap->getCurrentStartPoint();
    Node* endNode = nodeMap->getCurrentEndPoint();
    
    //1. add start node to open list
    addNodeToOpenList(startNode);

    do{ 
        nodeMap->print();
        
        //2. remove start node from open list and close it
        Node *currentNode = getLastNodeFromOpenList();
        currentNode->setIsClosed();

        //3. analyse all neighbors
        for(int i=0;i<8; i++){
            Node *node = nodeMap->getNeighborFromNode(currentNode->getPosition(),static_cast<NodeMap::Neighbors>(i));

            if(node == 0 || node->isClosed() || !node->isWalkable()) continue;

            float g = currentNode->getG() + nodeMap->calculateDistance(currentNode->getPosition(),node->getPosition());
            float h = nodeMap->calculateDistance(node->getPosition(), endNode->getPosition());

            if(!node->isOpen()){
                node->setParentNode(currentNode);
                node->setG(g);
            } else if (g < node->getG()){
                eraseNodeFromOpenList(node);
                node->setParentNode(currentNode);
                node->setG(g);
            }

            node->setH(h);
            node->calculateF();
            addNodeToOpenList(node);

            if(currentNode->isEndNode()){ //strike
                found = true;
            }
        }
    }
    while (found != true && openList.size() != 0);
}

void AStar::addNodeToOpenList(Node* node){
    node->setIsOpen();
    openList.insert(node);
}

void AStar::eraseNodeFromOpenList(Node* node){
    set<Node*>::iterator it;
    it=openList.find(node);
    openList.erase(it);
}

Node* AStar::getLastNodeFromOpenList(){
    set<Node*>::iterator it;
    Node* n;
    //get the first node from open list
    it=openList.begin();
    n = *it;

    //remove it
    openList.erase(it);
    return n;
}

C-/C++-Quelltext

#ifndef NODE_H
#define NODE_H

struct Position{
    int x;
    int y;
};

class Node {
public:
    /*-- mothods --*/
    void calculateF();

    /*-- constructor and destructor --*/
    Node(float g, float h, bool start, bool end, Node* parentNode, Position position, bool walkable);
    virtual ~Node();
    Node(const Node& other);
    Node& operator=(const Node& other);

    /*-- get and set methods --*/
    void setParentNode(Node* node);
    Node* getParentNode();

    void setG(const float& g);
    void setH(const float& h);

    float const& getG() const;
    float const& getH() const;
    float const& getF() const;

    void setIsStartNode(const bool& start);
    void setIsEndNode(const bool& end);
    void setIsWalkable(const bool& walkable);
    void setIsOpen();
    void setIsClosed();

    bool const& isStartNode() const;
    bool const& isEndNode() const;
    bool const& isWalkable() const;
    bool const& isOpen() const;
    bool const& isClosed() const;
    bool const& isFinal() const;

    void setPosition(const struct Position& position);
    Position const& getPosition() const;

    void setSign(char* sign);

    char* getSign() const;

    void setAsFinalWaypoint();
protected:
private:
    bool isFinalWayNode;
    char* sign;

    float g;
    float h;
    float f;

    bool start;
    bool end;
    bool walkable;

    bool open;
    bool closed;

    Node* parentNode;
    Position position;
};

#endif // NODE_H

C-/C++-Quelltext

#include "Node.h"


/*-- mothods --*/

void Node::calculateF() {
    f = g + h;
}

/*-- constructor and destructor --*/
Node::Node(float g, float h, bool start, bool end, Node* parentNode, Position position, bool walkable):g(g),h(h),start(start), end(end),parentNode(parentNode), position(position), walkable(walkable) {
    open = 0;
    closed = 0;
    sign = ".";
    isFinalWayNode=false;
}

Node::~Node() {
}

Node::Node(const Node& other) {
    //copy ctor
}

Node& Node::operator=(const Node& rhs) {
    if (this == &rhs) return *this; // handle self assignment
    //assignment operator
    return *this;
}

/*-- get and set methods --*/

void Node::setParentNode(Node* node) {
    this->parentNode = node;
}

void Node::setAsFinalWaypoint(){
    isFinalWayNode = true;
}

bool const& Node::isFinal() const {
    return isFinalWayNode;
}

Node* Node::getParentNode(){
    return this->parentNode;
}

float const& Node::getG() const {
    return g;
}

float const& Node::getH() const {
    return h;
}

float const& Node::getF() const {
    return f;
}

void Node::setG(const float& g) {
    this->g = g;
}

void Node::setH(const float& h) {
    this->h = h;
}

void Node::setIsStartNode(const bool& start) {
    this->start=start;
}

void Node::setIsEndNode(const bool& end) {
    this->end = end;
}

bool const& Node::isStartNode() const {
    return start;
}

bool const& Node::isEndNode() const {
    return end;
}

void Node::setIsWalkable(const bool& walkable) {
    this->walkable = walkable;
}

bool const& Node::isWalkable() const {
    return walkable;
}

void Node::setPosition(const struct Position& position) {
    this->position = position;
}

Position const& Node::getPosition() const {
    return position;
}

void Node::setIsOpen() {
    this->closed = 0;
    this->open = 1;
}

void Node::setIsClosed() {
    this->open = 0;
    this->closed = 1;
}

bool const& Node::isOpen() const {
    return open;
}

bool const& Node::isClosed() const {
    return closed;
}

void Node::setSign(char* sign){
    this->sign = sign;
}

char* Node::getSign() const{
    return sign;
}

C-/C++-Quelltext

#ifndef NODEMAP_H
#define NODEMAP_H

#include "Node.h"

class NodeMap {


public:

    enum Neighbors{
        bottom,
        left,
        right,
        above,
        bottom_left,
        bottom_right,
        above_left,
        above_right
    };

    NodeMap(int width, int height);
    ~NodeMap();

    void initialize();
    void shutdown();
    void print();

    void setStartPoint(int x, int y);
    void setEndPoint(int x, int y);
    void setWalkable(int x, int y, bool able);

    Node* getNeighborFromNode(Position const& position,Neighbors neighbor);


    Node* getCurrentStartPoint();
    Node* getCurrentEndPoint();

    float calculateDistance(Position const& p1, Position const& p2);

private:
    Node* getNodeFromMap(int const &x, int const &y);
    
    int height;
    int width;
    int size;
    Node** nodes;

    Node* currentStartPoint;
    Node* currentEndPoint;
};

#endif

C-/C++-Quelltext

#include <iostream>
#include <vector>
#include <math.h>
#include "NodeMap.h"

using namespace std;

NodeMap::NodeMap(int width, int height){
    this->height=height;
    this->width=width;

    this->size = width * height;
}

NodeMap::~NodeMap(){
    shutdown();
}

/*
* This method creates a map like this.
* .........
* ....#....
* ..O.#.X..
* ....#....
* .........
*/
void NodeMap::initialize(){
    nodes = new Node*[size];

    //fill
    for(int i=0; i<height; i++) {
        for(int j=0; j<width; j++) {
            Position position;
            position.x = j;
            position.y = i;
            float g = 0;
            float h = 0.0f;
            nodes[width * i + j] = new Node(g, h, false, false, 0, position, true);
        }
    }

    //create wall
    for(int i=0; i<=3; i++){
        setWalkable(1,i,false);
    }

    for(int i=1; i<=4; i++){
        setWalkable(3,i,false);
    }

}

void NodeMap::shutdown(){
    //clean
    for(int i=0; i<size; i++) {
        delete nodes[i];
    }
    delete[] nodes;
}

void NodeMap::print(){
    
    for(int i=0; i<height; i++) {
        for(int j=0; j<width; j++) {
            if(j % width == 0){
                cout << endl;
            }

            if(nodes[width * i + j]->isStartNode()){
                cout << "O";
            }
            else if(nodes[width * i + j]->isEndNode()){
                cout << "X";
            }
            else if(!nodes[width * i + j]->isWalkable()){
                cout << "#";
            }
            else if(nodes[width * i + j]->isOpen())
            {
                cout << "+";
            }
            else if(nodes[width * i + j]->isFinal() && !nodes[width * i + j]->isEndNode())
            {
                cout << "w";
            }
            else if(nodes[width * i + j]->isClosed() && !nodes[width * i + j]->isEndNode())
            {
                cout << "-";
            }
            else{
                cout << nodes[width * i + j]->getSign();
            }
        }
    }

    cout << "\n" << endl;
}

/*
* This method return the neighbor from a specific node.
* In the case that a node is not walkable null will be returned as result.
*/
Node* NodeMap::getNeighborFromNode(Position const& position,Neighbors neighbor){
    const int *x;
    const int *y;

    x = &position.x;
    y = &position.y;

    switch(neighbor){
    /********
    * +++
    * +X+
    * +?+
    *********/
    case bottom:
        return getNodeFromMap(*x, *y - 1);
        break;

    /********
    * +++
    * +X+
    * ?++
    ********/
    case bottom_left:
        return getNodeFromMap(*x - 1, *y - 1);
        break;
    
    /********
    * +++
    * +X+
    * ++?
    ********/    
    case bottom_right:
        return getNodeFromMap(*x + 1, *y - 1);
        break;

    /********
    * +++
    * ?X+
    * +++
    ********/
    case left:
        return getNodeFromMap(*x - 1, *y);
        break;

    /********
    * +++
    * +X?
    * +++
    ********/ 
    case right:
        return getNodeFromMap(*x + 1, *y);
        break;
    
    /********
    * +?+
    * +X+
    * +++
    ********/
    case above:
        return getNodeFromMap(*x, *y + 1);
        break;
    
    /********
    * ?++
    * +X+
    * +++
    ********/
    case above_left:
        return getNodeFromMap(*x - 1, *y + 1);
        break;

    /********
    * ++?
    * +X+
    * +++
    ********/
    case above_right:
        return getNodeFromMap(*x + 1, *y + 1);
        break;

    default :
        return 0;
        break;
    };

    return 0;
}

Node* NodeMap::getNodeFromMap(int const &x, int const &y){
    if(x < 0 || y < 0 || x > width - 1 || y > height - 1){
        return 0;
    }
    return nodes[width * y + x];
}

float NodeMap::calculateDistance(Position const& p1, Position const& p2){
    //return 10 * (abs(p1.x - p2.x) + abs(p1.y - p2.y));

    float px = float(p2.x - p1.x);
    float py = float(p2.y - p1.y);

    return sqrt(px * px + py * py);

}

void NodeMap::setStartPoint(int x, int y){
    currentStartPoint = nodes[width * y + x];
    currentStartPoint->setIsStartNode(true);
}

void NodeMap::setEndPoint(int x, int y){
    currentEndPoint = nodes[width * y + x];
    currentEndPoint->setIsEndNode(true);
}

void NodeMap::setWalkable(int x, int y, bool able){
    nodes[width * y + x]->setIsWalkable(able);
}


Node* NodeMap::getCurrentStartPoint(){
    return currentStartPoint;
}

Node* NodeMap::getCurrentEndPoint(){
    return currentEndPoint;
}

Quellcode

O#.......
.#.#.....
.#.#.....
.#.#.....
...#....X


O#.......
+#.#.....
.#.#.....
.#.#.....
...#....X


O#.......
-#.#.....
+#.#.....
.#.#.....
...#....X


O#.......
-#.#.....
-#.#.....
+#.#.....
...#....X


O#.......
-#.#.....
-#.#.....
-#.#.....
++.#....X


O#.......
-#.#.....
-#.#.....
-#+#.....
+-+#....X


O#.......
-#.#.....
-#.#.....
-#+#.....
+--#....X


O#.......
-#.#.....
-#+#.....
-#-#.....
+--#....X


O#.......
-#.#.....
-#+#.....
-#-#.....
+--#....X


O#.......
-#.#.....
-#+#.....
-#-#.....
---#....X


O#.......
-#.#.....
-#+#.....
-#-#.....
---#....X


O#.......
-#+#.....
-#-#.....
-#-#.....
---#....X


O#.......
-#+#.....
-#-#.....
-#-#.....
---#....X


O#++.....
-#-#.....
-#-#.....
-#-#.....
---#....X


O#++.....
-#-#.....
-#-#.....
-#-#.....
---#....X


O#+-+....
-#-#+....
-#-#.....
-#-#.....
---#....X


O#+-+....
-#-#+....
-#-#.....
-#-#.....
---#....X


O#+-++...
-#-#-+...
-#-#++...
-#-#.....
---#....X


O#+-++...
-#-#-+...
-#-#++...
-#-#.....
---#....X


O#+-++...
-#-#-++..
-#-#+-+..
-#-#+++..
---#....X


O#+-++...
-#-#-++..
-#-#+-+..
-#-#+++..
---#....X


O#+-++...
-#-#-++..
-#-#+-++.
-#-#++-+.
---#.+++X


O#+-++...
-#-#-++..
-#-#+-++.
-#-#++-+.
---#.+++X


O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.+++X


O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X


O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X


O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X


O#+-++...
-#-#-++..
-#-#+-+++
-#-#++--+
---#.++-X

x: 8 y: 4
x: 7 y: 3
x: 6 y: 3
x: 5 y: 2
x: 4 y: 1
x: 3 y: 0
x: 2 y: 1
x: 2 y: 2
x: 2 y: 3
x: 1 y: 4
x: 0 y: 3
x: 0 y: 2
x: 0 y: 1
x: 0 y: 0

Final way.

O#+w++...
w#w#w++..
w#w#+w+++
w#w#++ww+
-w-#.++-X