标签: a-star

我已经在C#中成功实现了A*pathfinding,但它很慢,我不明白为什么.我甚至尝试不对openNodes列表进行排序,但它仍然是相同的.

地图是80x80,有10-11个节点.

我从维基百科那里拿了伪代码

这是我的实施:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; …

嘿,我是AI学生,我会尝试我的作业,即实现A*算法,以便遍历图表.我使用c ++代码,我现在所做的是代码,它只是一个Graph类+插入和顶点函数.但现在我对如何定义成本函数感到困惑(f = h(n)+ g(n))...

任何代码参考或解释A*如何适用于图表将有助于我.我在google中找到的是关于通过*进行寻路,它与遍历图没有任何关系.

#include <iostream>
using namespace std;

class Graph;
class node {
    friend class Graph;
private:
    char data;
    int cost;
    node *next;
    node *vlist;
    bool goal;
    bool visited;
public:
    node(char d,int c, bool g){
        cost = c;
        goal = g;
        next = NULL;
        data = d;
        vlist = NULL;
        visited = false;
    }
};

class Graph {
private:
    node *Headnodes;
    char n;
public:
    Graph ()
    {
        Headnodes = NULL;
    }
    void InsertVertex(char n, int c, bool …

我试图让一个敌人节点跟随C#中的玩家节点使用A*算法.我已阅读教程并下载了一些C#exmaples.我的A*算法现在已达到一定程度.它将在开放空间中跟随玩家,但在尝试追踪对象时遇到障碍.

因此,当我的算法检查并向最低F值方向移动时,它可能会遇到一个死胡同,此时它需要向后回溯它的步骤,但它不能,因为我的代码告诉它先前检查过节点已关闭且无法移动到,因此它会卡住.

如何重新计算一个封闭的节点,告诉我的算法可以以这种方式返回.

此外,如果我确实告诉我的算法重新开始,那么什么是阻止它再回到AGAIN到它刚刚来的更好的节点; 有效地在两个节点之间反复回归.

我看到它应该能够检查关闭列表中的节点并确定它在这个特定路径上是否更好,但我不确定如何完成.

我正在使用的启发式方法.

G = Math.Abs(StartNodeX - TargetNodeX) + Math.Abs(StartNodeY - TargetNodeY)

H = Math.Abs(CurrentNodeX - TargetNodeX) + Math.Abs(CurrentNodeY - CurrentNodeY)

F = G + H

伪码.

1. 将所有相邻节点添加到打开列表
2. 检查所有这些节点的最低F分数,并将该节点添加到最佳路径列表
3. 将所有选中的节点添加到"关闭列表"(它们都已经过检查,不想再次检查)
4. 重复直到达到目标
5. 沿最佳路径方向移动敌人1节点
6. 重复一遍

计划在2D RTS上工作,我试图了解Astar是如何工作的.实际上,我发现文章解释了如何优化Astar与二进制堆的耦合,以及利用Path对称性的算法,如Jump Poin Search算法.我试图实现跳转点搜索,它运行正常.我甚至用MovingAI的地图做了一些基准测试.

然而,有一个问题.允许对角线移动时,一切运行正常.禁用时,不返回任何路径...

它可能与我实现它的方式有关,然后我都在问......一般来说,你如何要求算法(JPS)搜索仅涉及直线移动(不是对角移动)的路径才能达到目标？

如何使用A star算法查找前100条最短路径？

我正面临一个问题,我必须使用A*来搜索地图,并且此地图中有多个目标可供使用.我的目标是扩展地图中的最少节点,任何关于如何为这个A*算法设计启发式的想法？谢谢

有人有一个简单和/或直观的解释,为什么你必须在A*中使用一个可接受的启发式,以及为什么你"应该"使用一致的启发式？

今天在课堂上,我的教授向我们介绍了可接受的启发式方法,并指出它们保证了A*算法的最优性.

我让他用一个极端的例子解释它,使其显而易见,但他不能.

有人可以帮忙吗？

我正在使用这个A星(A*)Pathfinder.java在Android地图应用中计算和生成我的路线. https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java

当我使用A星的Pathfinder.java来计算地图中从一个点到另一个点的路线时,地图的大小很大,尺寸大约为8000x8000.

A星探路者计算1乘1并用于大地图(8000x8000),性能/计算速度相当低/慢(效率不高).我试图将计算增加到100乘以100,它工作正常,但绘制的路径路径在曲线上不平滑.

无论如何使用A星算法或任何其他建议来改善路线计算性能来解决问题？我需要帮助才能解决问题.

我的a*算法并不总是采用最短的路径.

在这张图片中,机器人必须穿过黑色方块,河流和树木都是障碍物.黑线是它所采用的路径,显然不是最短的路径,因为它不应该浸入.

http://imgur.com/GBoq9py

这是我的代码*和我正在使用的启发式:

def HeuristicCostEstimate(start, goal):
    (x1, y1) = start
    (x2, y2) = goal
    return abs(x1 - x2) + abs(y1 - y2)

def AStar(grid, start, goal):
    entry = 1
    openSet = []
    heappush(openSet,(1, entry, start))
    cameFrom = {}
    currentCost = {}
    cameFrom[tuple(start)] = None
    currentCost[tuple(start)] = 0
    while not openSet == []:
        current = heappop(openSet)[2]
        print(current)
        if current == goal:
            break

        for next in grid.Neighbours(current):
            newCost = currentCost[tuple(current)] + grid.Cost(current, next)
            if tuple(next) not in currentCost or newCost < …