Как использовать результат алгоритма A * для 2D-игры? - PullRequest
Новая
       23

Как использовать результат алгоритма A * для 2D-игры?

1 голос
/ 26 октября 2019

Я делаю свою первую попытку ввести поиск пути в одной из моих игр. До сих пор я реализовал алгоритм 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;

Так как я впервые делаю поиск пути для игры, я могу подойти к этому неправильно, хотя я не уверен.

...