astar.hpp

我自己编写的A*搜索算法

#ifndef ASTAR_HPP
#define ASTAR_HPP

#include <vector>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
    #include "MemCheck.h"
#endif

/*
Author : WB
*/
struct Point{
    int x;
    int y;
};


class AStar{
    struct ANode{
        int x, y;
        int id;
        ANode *parent;
        ANode *children[8];
        int f ,g ,h;
        int childNum;
    };
    typedef ANode * PNode;

	//优先队列里面的比较器
    struct littleCompare{
        littleCompare(const PNode &f) : first(f){}

        bool operator()(const PNode &second){
            return first->f < second->f;
        }
    private:
        const PNode first;
    };

	//自定义的一个简易的优先队列（以vector为实现基础）
    struct priorityQueue{
        PNode top(){
			if(container_.empty())
				return 0;
            return container_.front();
        }

        bool empty(){
            return container_.empty();
        }

        void pop(){
            container_.erase(container_.begin());
        }

        PNode contain(const int &id){
            for(std::vector<PNode>::iterator itr = container_.begin();
                itr != container_.end(); ++itr){
                    if((*itr)->id == id)
                        return *itr;
            }
            return 0;
        }

        void push(PNode p){
            std::vector<PNode>::iterator itr =
                std::find_if(container_.begin(), container_.end(), littleCompare(p));
            container_.insert(itr, p);
        }
        private:
        std::vector<PNode> container_;
    };

    typedef priorityQueue OpenTable;
    typedef std::vector<PNode> ClosedTable;

public:
    AStar(char *m, const int &rows, const int &cols);
    bool findPath(std::vector<Point>&);
    ~AStar();

private:
    AStar(const AStar&);
    AStar& operator=(const AStar&);
    void init();
    void findSourceAndDestination();
    void initStartPoint();
    int generateId(const int &, const int &) const;
    bool canAccess(const int &, const int &) const;
    PNode isInOpenTable(const int &);
    PNode isInClosedTable(const int &);
    void updateNodes(PNode);
	void reCombine(PNode, PNode);
    const char *map_;
    const int rows_, cols_;
    Point source_, destination_;
    OpenTable ot_;
    ClosedTable ct_;
};
#endif