java - 如何将 A* 算法的结果用于 2D 游戏？

Question

我正在第一次尝试在我的一个游戏中引入寻路。到目前为止，我已经实现了一个 A* 算法，它似乎可以正确地找到我根据打印语句设置到指定位置的墙周围的路径。但是，从我理解的方式来看，我用来生成路径的方法返回的是从目标到角色的路径，而不是相反。因此，我需要反转路径以使我的角色移动到指定位置（如果我理解正确的话）。我如何以最好的方式做到这一点？

探路者代码：

public class PathFinder
{
    public static Map<Location, Location> createPath(Location start, Location goal)
    {
        //A "Location" is a simple vector object that accepts an X and Y value.
        HashMap<Location, Location> locationParents = new HashMap<>();
        HashMap<Location, Integer> movementCosts = new HashMap<>();

        PriorityQueue frontier = new PriorityQueue();
        frontier.push(start, 0);

        locationParents.put(start, null);
        movementCosts.put(start, 0);

        //"While we have locations that we need to check in order to get a path"
        while(!frontier.isEmpty())
        {
            Location current = frontier.pop();

            //Break if we found the goal
            if(current.equals(goal))
                break;

            //Neighbours around a location are locations in all 8 directions next to it that are passable
            for(Location next : SquareGrid.getLocationNeighbours(current))
            {
                int newCost = movementCosts.get(current) + SquareGrid.getLocationCost(next);
                if(!movementCosts.containsKey(next) || newCost < movementCosts.get(next))
                {
                    movementCosts.put(next, newCost);
                    int priority = newCost + makeGuess(next, goal);
                    frontier.push(next, priority);
                    locationParents.put(next, current);
                }
            }
        }

        return locationParents;
    }

    private static int makeGuess(Location a, Location b)
    {
        return Math.abs(a.getX() - b.getX()) + Math.abs(a.getY() - b.getY());
    }

    private static class PriorityQueue
    {
        private LinkedList<LocationPair> elements = new LinkedList<>();

        public boolean isEmpty()
        {
            return elements.isEmpty();
        }

        public void push(Location loc, int cost)
        {
            elements.push(new LocationPair(loc, cost));
        }

        public Location pop()
        {
            int bestIndex = 0;

            for(int i = 0; i < elements.size(); i++)
            {
                if(elements.get(i).cost < elements.get(bestIndex).cost)
                    bestIndex = i;
            }

            return elements.remove(bestIndex).location;
        }

        private static class LocationPair
        {
            private final Location location;
            private final int cost;

            private LocationPair(Location location, int cost)
            {
                this.location = location;
                this.cost = cost;
            }
        }
    }
}

我希望角色类中的运动代码是这样的：

            Location currentPos = new Location(x, y);
            //Next position to move to
            Location nextPosition = targets.get(currentPos);

            xVel = Integer.compare(parentPos.getX(), currentPos.getX());
            yVel = Integer.compare(parentPos.getY(), currentPos.getY());

            x += xVel;
            y += yVel;

由于这是我第一次为游戏进行寻路，虽然我不确定，但我可能会错误地接近这个。

标签： javaa-stargame-ai