寻路(待完成)

用C++实现寻路的几种方法。

地图

思前想后我决定用链表来存储地图,也就是用vector<int>按顺序存储地图的节点,由于地图一般是矩形的,知道高度与宽度后我们无需再存储位置信息,每个节点的内容可以是地形高度。用数组也是可以的,但栈中的数组需要确定大小,动态数组很好,但为了方便删除元素还是用效率低的vector容器吧。

points存储每个节点的高度,target存储目标节点的序号,landing存储登陆点的序号,width与length用于根据序号推算节点位置,height是寻路对象能够跨越的最大高度,track记录路径,find标记是否已到达所有终点。除了track与find,其余成员变量都要初始化。

class Graph{
 private:
  vector<int> points;
  vector<int> target;
  int landing;
  int width,length;
  int height;
  vector<int> track;
  bool find=false;
}

DFS

先写一个启动DFS的函数,用于未找到路径时输出结果。

    void startDFS()
    {
        DFS(this->landing);
        if (this->find == false)
        {
            cout << "未找到路径!" << endl;
        }

    }

DFS主函数检查周围的点是否已访问或符合规则,然后访问。访问后节点height被标记为-1,checkEnd用于判断是否已到达全部终点并修改find的值,checkNeighbor用于把将要访问的点放入neighbor。

    bool DFS(int start)
    {
        vector<int> neighbor;
        //如果已经找到那么结束
        if (this->find == true)
        {
            return false;
        }

        //如果已经访问过那么返回
        if (points[start]==-1)
        {
            return false;
        }
        else
        {
            points[start]=-1;
            track.push_back(start);
        }

        checkEnd(start);

        checkNeighbor(start, &neighbor);

        for (int i = 0; i < neighbor.size(); i++)
        {
            DFS(neighbor[i]);
        }
        track.pop_back(); //返回上级时弹出
    }

checkEnd函数:

    void checkEnd(int start)
    {
        for (int k = 0; k < target.size(); k++)
        {
            if (start == target[k])
            {
                cout << "经过了" << start << endl;
                target[k] = -1; //标记已到达
                bool visitedAll = true;
                for (int i = 0; i < target.size(); i++)
                {
                    if (target[i] != -1)
                    {
                        visitedAll = false;
                    }
                }
                if (visitedAll == true)
                {
                    cout << "已全部到达!" << endl;
                    this->find = true;
                    for (int i = 0; i < track.size(); i++)
                    {
                        cout <<"("<< track[i]/width <<","<<track[i]%width<<")"<< endl;
                    }
                }
            }
        }
    }

checkNeighbor函数,通过有关计算确定一个位置的上/下/左/右等位置是否存在节点。

    void checkNeighbor(int start, vector<int> *neighbor)
    {
        int leftTop = -1, top = -1, rightTop = -1, left = -1, right = -1, bottom = -1, leftBottom = -1, rightBottom = -1;
        bool hasLeft = false, hasRight = false, hasTop = false, hasBottom = false;

        if (start % width != 0)
        {
            hasLeft = true;
        }
        if ((start + 1) % width != 0)
        {
            hasRight = true;
        }
        if (start - width >= 0)
        {
            hasTop = true;
        }
        if (start + width < width * height)
        {
            hasBottom = true;
        }
        //8个方向的数组序号
        if (hasTop && hasLeft)
        {
            leftTop = start - width - 1;

            if (abs(points[start] - points[leftTop]) >= maxZ)
            {
                leftTop = -1;
            }
        }
        if (hasTop)
        {
            top = start - width;
            if (abs(points[start] - points[top]) >= maxZ)
            {
                top = -1;
            }
        }
        if (hasRight && hasTop)
        {
            rightTop = start - width + 1;
            if (abs(points[start] - points[rightTop]) >= maxZ)
            {
                rightTop = -1;
            }
        }
        if (hasLeft)
        {
            left = start - 1;
            if (abs(points[start] - points[left]) >= maxZ)
            {
                left = -1;
            }
        }
        if (hasRight)
        {
            right = start + 1;
            if (abs(points[start] - points[right]) >= maxZ)
            {
                right = -1;
            }
        }
        if (hasLeft && hasBottom)
        {
            leftBottom = start + width - 1;
            if (abs(points[start] - points[leftBottom]) >= maxZ)
            {
                leftBottom = -1;
            }
        }
        if (hasRight && hasBottom)
        {
            rightBottom = start + width + 1;
            if (abs(points[start] - points[rightBottom]) >= maxZ)
            {
                rightBottom = -1;
            }
        }
        if (hasBottom)
        {
            bottom = start + width;

            if (abs(points[start] - points[bottom]) >= maxZ)
            {
                
                bottom = -1;
            }
        }
        //添加到neighbor
        if (leftTop != -1)
        {
            //neighbor.push_back(&points[leftTop]);
            neighbor->push_back(leftTop);
        }
        if (top != -1)
        {
            //neighbor.push_back(&points[top]);
            neighbor->push_back(top);
        }
        if (rightTop != -1)
        {
           
            neighbor->push_back(rightTop);
        }
        if (left != -1)
        {
            
            neighbor->push_back(left);
        }
        if (right != -1)
        {
           
            neighbor->push_back(right);
        }
        if (leftBottom != -1)
        {
           
            neighbor->push_back(leftBottom);
        }
        if (bottom != -1)
        {
   
            neighbor->push_back(bottom);
        }
        if (rightBottom != -1)
        {
      
            neighbor->push_back(rightBottom);
        }
    }

BFS

虽然我把BFS遍历写出来了,但BFS不方便记录轨迹,因为访问元素是依次加入队列的,之间没有父子关系。如果要记录路径的话,需要知道路径上每个节点的父节点,也就是要形成一颗BFS树:每个节点都记录自己的父节点。

那么BFS记录轨迹的方法就是,将邻居节点加入队列时,节点信息要包括本节点,收集从队列中弹出的节点(收集访问过的节点,可以组织成一棵树),当找到终点时,反向寻找出发点。

A*

发表评论

电子邮件地址不会被公开。