java - 我的 A* 寻路实现有问题吗？

标签 java libgdx path-finding a-star

因此，我尝试在 LibGDX 中实现 A* 寻路算法，以便了解它的工作原理。我的实现基于这篇文章: < Link >

目前，我已经获得了计算路径的算法，如果目标不可访问，甚至将路径返回为不存在，但是如果有墙壁部分阻挡目标，则找到的路径所采用的路线确实不寻常正如您在这里看到的:

PathFinding Problem

所以我想找出我的实现出了什么问题，看看为什么封闭列表会生成这样的路径，或者我是否遗漏了一个步骤。

这些是 PathFinder 类中的变量:

public class PathFinder {
private Array<Array<GridNode>> grid = new Array<Array<GridNode>>();
private Array<GridNode> openPath = new Array<GridNode>();
private Array<GridNode> closedPath = new Array<GridNode>();
private int GridX, GridY;
private int StartX = -1, StartY = -1;
private int EndX = -1, EndY = -1;

public static int Found = 1;
public static int NonExistant = 2;

这是 PathFinder 类中的路径查找代码:

public int findPath()
{
    //Clear current path
    openPath.clear();
    closedPath.clear();
    
    //Reset all F, G and H values to 0
    for (int y = 0; y < grid.size; y++)
    {
        for (int x = 0; x < grid.get(y).size; x++)
        {
            grid.get(y).get(x).Reset();
        }
    }
    
    //If no Start or End nodes have been set, quit the findPath.
    if (StartX == -1 || StartY == -1 || EndX == -1 || EndY == -1)
    {
        return NonExistant;
    }
    else if (StartX == EndX && StartY == EndY) // If Start = End, return found.
    {
        return Found;
    }
    else
    {
        openPath.add(grid.get(StartY).get(StartX)); //Add Start node to open
        SetOpenList(StartX, StartY); //Set neighbours.
        
        closedPath.add(grid.get(StartY).get(StartX)); //Add Start node to closed.
        openPath.removeValue(grid.get(StartY).get(StartX),true); //Remove Start Node from open.
        
        while (closedPath.get(closedPath.size - 1) != grid.get(EndY).get(EndX))
        {
            //Set Neighbours for parent
            SetOpenList(closedPath.get(closedPath.size-1).X/GridX, closedPath.get(closedPath.size-1).Y/GridY);
            
            if (openPath.size != 0)
            {
                int bestF = 10000;
                int bestFIndex = -1;
                
                //Get node with lowest F in open.
                for (int i = 0; i < openPath.size; i++)
                {
                    if (openPath.get(i).F < bestF)
                    {
                        bestF = openPath.get(i).F;
                        bestFIndex = i;
                    }
                }
                
                if (bestFIndex != -1)
                {
                    closedPath.add(openPath.get(bestFIndex)); //Add node to closed list
                    openPath.removeIndex(bestFIndex); //remove from open list
                }
                else
                    return NonExistant;
            }
            else
            {
                return NonExistant;
            }
        }
    }
    
    return Found;
}

public void CompareParentwithOpen(GridNode Parent, GridNode Open)
{
    //If the G value of open is smaller than the G value in Parent, recalculate F, G and H.
    if (Open.G < Parent.G)
    {
        openPath.get(
                openPath.indexOf(Open, true)).CalculateNode(
                        Parent, 
                        grid.get(StartY).get(StartX), 
                        grid.get(EndY).get(EndX));
    }
}

public void SetOpenList(int X, int Y)
{
    //Check position of X and Y to avoid IndexOutofBounds.
    Boolean ignoreLeft = (X - 1 < 0);
    Boolean ignoreRight = (X + 1 >= grid.get(Y).size);
    Boolean ignoreUp = (Y - 1 < 0);
    Boolean ignoreDown = (Y + 1 >= grid.size);
    
    tempOpen = new Array<GridNode>();
    
    //For each check, if the checked grid is not an unpassable type and not in the closed list, continute checking.
    //If checked grid is already in Open List, go to Compare parent with open.
    if (!ignoreLeft && !ignoreUp)
    {
        if (grid.get(Y-1).get(X-1).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y-1).get(X-1), true))
        {
            if (!(openPath.contains(grid.get(Y-1).get(X-1), true) || openPath.contains(grid.get(Y-1).get(X-1), false)))
            {
                grid.get(Y-1).get(X-1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y-1).get(X-1));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y-1).get(X-1), true)));
            }
        }
    }
    
    if (!ignoreUp)
    {
        if (grid.get(Y-1).get(X).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y-1).get(X), true))
        {
            if (!(openPath.contains(grid.get(Y-1).get(X), true) || openPath.contains(grid.get(Y-1).get(X), false)))
            {
                grid.get(Y-1).get(X).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y-1).get(X));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y-1).get(X), true)));
            }
        }
    }
    
    if (!ignoreRight && !ignoreUp)
    {
        if (grid.get(Y-1).get(X+1).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y-1).get(X+1), true))
        {
            if (!(openPath.contains(grid.get(Y-1).get(X+1), true) || openPath.contains(grid.get(Y-1).get(X+1), false)))
            {
                grid.get(Y-1).get(X+1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y-1).get(X+1));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y-1).get(X+1), true)));
            }
        }
    }
    
    if (!ignoreLeft)
    {
        if (grid.get(Y).get(X-1).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y).get(X-1), true))
        {
            if (!(openPath.contains(grid.get(Y).get(X-1), true) || openPath.contains(grid.get(Y).get(X-1), false)))
            {
                grid.get(Y).get(X-1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y).get(X-1));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y).get(X-1), true)));
            }
        }
    }
    
    if (!ignoreRight)
    {
        if (grid.get(Y).get(X+1).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y).get(X+1), true))
        {
            if (!(openPath.contains(grid.get(Y).get(X+1), true) || openPath.contains(grid.get(Y).get(X+1), false)))
            {
                grid.get(Y).get(X+1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y).get(X+1));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y).get(X+1), true)));
            }
        }
    }
    
    if (!ignoreLeft && !ignoreDown)
    {
        if (grid.get(Y+1).get(X-1).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y+1).get(X-1), true))
        {
            if (!(openPath.contains(grid.get(Y+1).get(X-1), true) || openPath.contains(grid.get(Y+1).get(X-1), false)))
            {
                grid.get(Y+1).get(X-1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y+1).get(X-1));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y+1).get(X-1), true)));
            }
        }
    }
    
    if (!ignoreDown)
    {
        if (grid.get(Y+1).get(X).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y+1).get(X), true))
        {
            if (!(openPath.contains(grid.get(Y+1).get(X), true) || openPath.contains(grid.get(Y+1).get(X), false)))
            {
                grid.get(Y+1).get(X).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y+1).get(X));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y+1).get(X), true)));
            }
        }
    }
    
    if (!ignoreRight && !ignoreDown)
    {
        if (grid.get(Y+1).get(X+1).type != GridNode.GridType.UNPASSABLE && 
                !closedPath.contains(grid.get(Y+1).get(X+1), true))
        {
            if (!(openPath.contains(grid.get(Y+1).get(X+1), true) || openPath.contains(grid.get(Y+1).get(X+1), false)))
            {
                grid.get(Y+1).get(X+1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX));
                openPath.add(grid.get(Y+1).get(X+1));
            }
            else
            {
                CompareParentwithOpen(grid.get(Y).get(X), 
                        openPath.get(openPath.indexOf(grid.get(Y+1).get(X+1), true)));
            }
        }
    }
    
    for (GridNode c : closedPath) //incase any nodes in closed are in open, remove closed nodes.
    {
        openPath.removeValue(c, true);
    }
}

public void SetGridNode(int screenX, int screenY, GridNode.GridType Type)
{
    int pointX = (int)(screenX/GridX);
    int pointY = (int)(screenY/GridY);
    
    if (pointY >= 0 && pointY < grid.size)
    {
        if (pointX >=0 && pointX < grid.get(pointY).size)
        {
            if (Type == GridNode.GridType.START || Type == GridNode.GridType.END)
            {
                for (int y = 0; y < grid.size; y++)
                {
                    for (int x = 0; x < grid.get(y).size; x++)
                    {
                        if (grid.get(y).get(x).type == Type)
                        {
                            if (Type == GridNode.GridType.START)
                            {
                                StartX = -1;
                                StartY = -1;
                            }
                            else if (Type == GridNode.GridType.END)
                            {
                                EndX = -1;
                                EndY = -1;
                            }
                            
                            grid.get(y).get(x).type = GridNode.GridType.NONE;
                        }
                    }
                }
            }
            
            if (grid.get(pointY).get(pointX).type == Type)
                grid.get(pointY).get(pointX).type = GridNode.GridType.NONE;
            else
            {
                if (Type == GridNode.GridType.START)
                {
                    StartX = pointX;
                    StartY = pointY;
                }
                else if (Type == GridNode.GridType.END)
                {
                    EndX = pointX;
                    EndY = pointY;
                }
                
                grid.get(pointY).get(pointX).type = Type;
            }
        }
    }
}

public Array<GridNode> GetPath()
{
    return closedPath;
}

这些是 GridNode 类中的变量:

public class GridNode {
public int X = 0, Y = 0;
public int Width = 10, Height = 10;
public GridType type = GridType.NONE;
public int F = 0, G = 0, H = 0;

public static enum GridType
{
    NONE,
    UNPASSABLE,
    START,
    END
}

下面是计算 GridNode 类中的 F、G 和 H 值的代码:

public void CalculateNode(GridNode Parent, GridNode Start, GridNode End)
{
    if (Parent != null)
    {
        if (Math.abs(X - Parent.X) != 0 &&
                Math.abs(Y - Parent.Y) != 0)
        {
            G = Parent.G + 14;
        }
        else
        {
            G = Parent.G + 10;
        }
        
        H = (int)((Math.abs(X-End.X)/Width) + (Math.abs(Y - End.Y)/Height)) * 10;
        
        /*int xDistance = (Math.abs(X-End.X)/Width);
        int yDistance = (Math.abs(Y - End.Y)/Height);
        
        if (xDistance > yDistance)
            H = 14*yDistance + 10*(xDistance-yDistance);
        else
            H = 14*xDistance + 10*(yDistance-xDistance);*/
        
        F = G + H;
    }
}

public void Reset()
{
    F = G = H = 0;
}

最佳答案

在 Twitter 上的 @KommaKameleon 的帮助下发现了该问题。您可以查看GitHub Repo完整的工作代码。

问题是我遵循了上面的所有步骤。除了最后一步之外的所有步骤，这需要您通过每个节点的父节点从终点到起点。

因此，我所做的就是在 GridNode 类中添加一个 GridNode 变量来存储计算 F、G 和 H 时使用的父节点。 

public class GridNode {
public float X = 0, Y = 0;
public int Width = 10, Height = 10;
public GridType type = GridType.NONE;
public float F = 0, G = 0, H = 0;
public GridNode Parent = null;
...

public void CalculateNode(GridNode Parent, GridNode Start, GridNode End)
{
    this.Parent = Parent;

    if (Parent != null)
    {
...

然后在 findPath() 方法中，在 while 循环之后，我执行了另一个 while 循环来设置一个名为 FinalPath 的新数组属性:

private Array<GridNode> finalPath = new Array<GridNode>();

这是我用来从终点到起点遍历每个父级的算法。 (其中 End 节点位于 closePath 数组的最后一个元素中)

GridNode g = closedPath.peek();
finalPath.add(g);

while (g != grid.get(StartY).get(StartX))
{
    g = g.Parent;
    finalPath.add(g);
}

finalPath.reverse();

关于java - 我的 A* 寻路实现有问题吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21991668/

上一篇：java - 字节数组到位图不显示Java Android

下一篇：java - MergeEventListener 中的 Hibernate 原始状态

相关文章：

java - 将 Java 字符串数组或 JSON 字符串转换为 Javascript 数组(Parse.com Cloud Code 和 Mandrill)

java - Hadoop 映射器 : lines vs files

java - Libgdx 如何阻止和解除阻止游戏关卡？

Floyd Warshall 算法的 Java 实现

java - 设备中的应用名称

java - 使用 LibGDX.scene2d 中的输入进行错误条件检查

ios - 将 sqlite 数据库用于 iOS (robovm) 与 libgdx

path-finding - 寻找移动目标的路径

algorithm - 通过连接的组件找到一条路径，其中每个顶点都被恰好访问一次

java - ssh 私钥/公钥认证示例

©2024 IT工具网  联系我们