java - 将 A* 路径查找更改为 HPA* - Java

Question

我已经为一个简单的基于 2d 网格的游戏实现了 A* 算法。然而，该算法使游戏速度减慢很多，我最近了解了 HPA*，它旨在尝试在一定程度上解决这个问题。

我确实找不到任何对我有用的编码示例，因为我正在使用 Java 进行编码，而且我对从哪里开始调整我的初始代码有点困惑。

我的代码如下，如果有人想看的话。我真的只是想以某种方式调整代码，以便将路径分割成网格，这样我就可以计算出一条大约 5 个方格长度的路径，而不是一条 20 个方格长并减慢游戏速度的路径。

  if (shortestPath == null) {

     openLocations.add(playerLocation);

        // While the goal has not been found yet
        while (openLocations.size() != 0 || pathFound != true) {
            // get the first node from the open list
            Node current = openLocations.get(0);
            shortestPath = reconstructPath(current);

            // check if current node is the goal node
            if (current.getX() == goalLocation.getX()
                    && current.getY() == goalLocation.getY()
                    //|| shortestPath.getWayPointPath().size() > GameInfo.getPathLength() + GameInfo.getPathCounter()
                    //|| shortestPath.getWayPointPath().size() >= 5
                    ) {
                shortestPath = reconstructPath(current);
                pathFound = true;

                for(Node node: shortestPath.getWayPointPath())
                 totalClosedLocations.add(node);

                // path has been found
                break;
            }

            // move current node to the already searched (closed) list
            openLocations.remove(current);
            closedLocations.add(current);

            // set the current nodes neighbours
            current = setNeighbours(current);

            // Now it's time to go through all of the current nodes
            // neighbours and see if they should be the next step
            for (Node neighbor : current.getNeighborList()) {
                boolean neighborIsBetter;

                // if we have already searched this Node, don't bother and
                // continue to the next one
                if (closedLocations.contains(neighbor)) {
                    continue;
                }

                boolean found = false;
                for (Node neighbournode : closedLocations) {
                    if (neighbournode.getX() == neighbor.getX()
                            && neighbournode.getY() == neighbor.getY()) {
                        found = true;
                        continue;
                    }
                }

                if (found)
                    continue;

                Node movable = new Node(neighbor.getX(), neighbor.getY(), 
                        neighbor.getCategory(), neighbor.getItype(), neighbor.getId());

                if (grid[movable.getX()][movable.getY()].size() > 0) {
                    // check to make sure that the square is not of category
                    // 4(immovable object) or category 3(enemy)
                    if ((grid[movable.getX()][movable.getY()].get(0).category == 4 && grid[movable
                            .getX()][movable.getY()].get(0).itype == 0)
                            && grid[movable.getX()][movable.getY()].get(0).obsID != goalLocation.getId()
                            ) {
                        // You cannot move on this square
                        neighbor.setMoveable(false);
                    } else {
                        // You can move on this square. Set parent location
                        // as the players current position.
                        movable.setParent(playerLocation);
                    }
                }

                // also just continue if the neighbor is an obstacle
                if (neighbor.getMoveable()) {

                    // calculate how long the path is if we choose this
                    // neighbor
                    // as the next step in the path
                    float neighborDistanceFromStart = (current
                            .getDistanceFromStart() + getDistanceBetween(
                            current, neighbor));

                    // add neighbor to the open list if it is not there
                    if (!openLocations.contains(neighbor)) {
                        openLocations.add(neighbor);
                        neighborIsBetter = true;
                        // if neighbor is closer to start it could also be
                        // better
                    } else if (neighborDistanceFromStart < current
                            .getDistanceFromStart()) {
                        neighborIsBetter = true;
                    } else {
                        neighborIsBetter = false;
                    }
                    // set neighbors parameters if it is better
                    if (neighborIsBetter) {
                        neighbor.setParent(current);
                        neighbor.setDistanceFromStart(neighborDistanceFromStart);
                        neighbor.setHeuristicDistanceFromGoal(heuristicStar
                                .getEstimatedDistanceToGoal(
                                        neighbor.getX(), neighbor.getY(),
                                        goalLocation.getX(),
                                        goalLocation.getY()));
                    }
                }

            }
        }

        System.out.println("====================");
    }

Answer 1

比方说:你实现了一个类似爬行的游戏，有一个迷宫、英雄和很多怪物......

英雄移动后，怪物会转动，它们可能会移动，朝英雄移动(a*星)。我猜你每次都会计算每个怪物的路径？!？正确的？好吧，那么有些事情就很不对劲了:

让每个怪物保持自己的路线。如果怪物距离很远，你不必搜索最短路径，因为即使你的英雄移动了，最短路径也基本上是相同的(只有最后几步不同)。然后，如果怪物移动了 10 圈，你可以重新计算路径。这样你就可以将计算时间加快 10 倍 - 考虑到较长的路径比较短的路径花费更多的时间，你可以做更多的优化

如果距离较远，可以每5步重新计算一次路径，也许如果它真的很接近，则需要每回合重新计算路径，但不用担心......如果它是一条短路径，则不需要太多时间来计算!

抱歉 - 未添加代码...

好吧，让我们继续:这是一个简单的迷宫/ map :

你从上/左开始，想要走到最后(不是 A，不是 B，你想要走到最后!)...

如果你不计算整个路径，你将永远找不到路，因为所有其他路径似乎都更短，尤其是当你在搜索中使用启发式方法时!!!

所以 - 没有办法不进行完整路径搜索!

优化:查找邻居通常是一个瓶颈:当您创建字段时，为每个字段设置邻居!

public class Test {

    public Field[][] field;
    public void doSomeTest(){

        field = new Field[25][25]
        MazeGenerator.createMaze(field); //this makes your map = this sets the fields passable or not
        for (int dy == 0; dy < 25; dy ++){
            for (int dx == 0; dx < 25; dx ++){
                createNeighbours(field[dx][dy]);                    
            }
        }

    }

    public void createNeigbours(Field f){

        //north
        if (isPassable(f.xpos, f.ypos-1) f.neighbours.add(field[xpos][ypos-1]); 

        //east
        if (isPassable(f.xpos+1, f.ypos) f.neighbours.add(field[xpos+1][ypos]);

        //south
        if (isPassable(f.xpos, f.ypos+1) f.neighbours.add(field[xpos][ypos+1]);

        //west
        if (isPassable(f.xpos-1, f.ypos) f.neighbours.add(field[xpos-1][ypos]);

    }

    public boolean isPassable(int xpos, int ypos){

        if (xpos <= 0) return false; //outside [maybe you even have a border, then xpos <= 1
        if (ypos <= 0) return false; //outside
        if (xpos >= Map.width) return false; //outside
        if (ypos >= Map.height) return false; //outside
        if (field[xpos][ypos].isBlocked) return false; //blocked

        return true;
    }
}

public class Field{

    public final int xpos;
    public final int ypos;
    public boolean isBlocked = false; // this makes your map

    public ArrayList<Field> neigbours = new ArrayList<Field>();

    public Field(int xpos, int ypos){
        this.xpos = xpos;
        this.ypos = ypos;
    }

    public List<Field> getNeighbours(){
        return neigbours ;
    }
}

上面的代码仅解释了如何在创建字段时创建邻居...但是如果扩展节点(a*)，您可以非常快地获得邻居并且无需计算时间(想想您创建对象的频率在您的代码中)