加快Dijkstra

Question

嗨，我写了一个小的Dijkstra实现，用于在我们基于平铺的游戏中查找路径。问题是，如果有10个敌人使用这个算法找到目标的最短路径(目前主要用于巡逻)，那么游戏就会变得相当滞后。特别是因为游戏应该在Android智能手机上运行。到目前为止，我试着加快这件事的速度：

1.将通过边连接的节点数量限制为一个固定的数目，这意味着只需执行N个步骤，直到超过initializeEgdes方法。这导致了一些丑陋的行为，并不是所有的巡警都被处决了，因为有些地方太长了。

2.以每一个敌人在自己的线程中计算其最短路径的方式，将Dijkstra的执行进行了并行化。这里的问题是，我对线程不太熟悉，也没有把这个想法带入运行状态(我的敌人没有移动)

我认为关于限制处理nodeConnections数量的第一个想法可能会产生相当大的影响，但我找不到一个好的规则什么时候加入处理。

public class Dijkstra {

PathNode[][] allNodes;
TiledMap tiledMap;

public Dijkstra(TiledMap sourceMap) {
    tiledMap = sourceMap;
    generateAllNodes();
}


/**
 * Node that virtualises an actual unit on gameboard, currently a tile.
 *
 * @author Lucas
 */
public class PathNode {
    boolean walkable = true;
    float x = 0;
    float y = 0;
    public final static float width = 32;
    public final static float height = 32;
    DijkstraNode myDijstraNode;

    public PathNode(int xpos, int ypos) {
        x = width * xpos;
        y = height * ypos;
        myDijstraNode = new DijkstraNode(this);
    }
}

/**
 * Node used for the Dijkstra methodes.
 *
 * @author Lucas
 */
public class DijkstraNode implements Comparable<DijkstraNode> {
    PathNode correspondingNode;
    double minDistance = Double.POSITIVE_INFINITY;
    DijkstraNode previous;
    Edge[] adjacencies;

    public DijkstraNode(PathNode myNode) {
        correspondingNode = myNode;
    }

    @Override
    public String toString() {
        return "TILE[" + correspondingNode.x / PathNode.width + "][" + correspondingNode.y / PathNode.height + "]";
    }


    @Override
    public int compareTo(DijkstraNode arg0) {
        // TODO Auto-generated method stub
        return Double.compare(minDistance, arg0.minDistance);
    }

    public void resetNode()
    {
        minDistance= Double.POSITIVE_INFINITY;
        adjacencies=null;
        previous=null;
    }
}

/**
 * An Edge between two dijkstraNodes
 *
 * @author Lucas
 */
class Edge {
    public final DijkstraNode target;
    public final double weight;

    public Edge(DijkstraNode argTarget, double argWeight) {
        target = argTarget;
        weight = argWeight;
    }
}


private List<DijkstraNode> getNeighbours(DijkstraNode u) {

    List<DijkstraNode> neighbours = new ArrayList<DijkstraNode>();

    float originX, originY;
    originX = u.correspondingNode.x / PathNode.width;
    originY = u.correspondingNode.y / PathNode.height;
    TiledMapTileLayer tl = (TiledMapTileLayer) tiledMap.getLayers().get(
            "main_background");
    //Left
    //Checks if the calculated field is still in allNodes
    if (Math.signum(originX - 1) == 1 && allNodes[(int) originY][(int) (originX - 1)].walkable) {
        neighbours.add(allNodes[(int) originY][(int) (originX - 1)].myDijstraNode);
    }
    //Right
    if ((originX + 1) < tl.getWidth() && allNodes[(int) originY][(int) (originX + 1)].walkable) {
        neighbours.add(allNodes[(int) originY][(int) (originX + 1)].myDijstraNode);
    }
    //Up
    if (originY + 1 < tl.getHeight() && allNodes[(int) originY + 1][(int) (originX)].walkable) {
        neighbours.add(allNodes[(int) originY + 1][(int) (originX)].myDijstraNode);
    }
    //Down
    if (Math.signum(originY - 1) == 1 && allNodes[(int) originY - 1][(int) (originX)].walkable) {
        neighbours.add(allNodes[(int) originY - 1][(int) (originX)].myDijstraNode);
    }
    return neighbours;

}

public DijkstraNode getDijkstraNode(com.hhn.liberation.logic.units.Enemy objectToMove) {
    DijkstraNode startNode = null;
    startNode=getDijkstraNode(new Vector2(objectToMove.getX(),objectToMove.getY()));
    return startNode;
}


//Dijkstra Methoden gefunden auf http://www.algolist.com/code/java/Dijkstra%27s_algorithm
public static List<DijkstraNode> getShortestPathTo(DijkstraNode target) {
    List<DijkstraNode> path = new ArrayList<DijkstraNode>();
    for (DijkstraNode vertex = target; vertex != null; vertex = vertex.previous)
        path.add(vertex);
    Collections.reverse(path);
    return path;
}

public static void computePaths(DijkstraNode source) {
    source.minDistance = 0.;
    PriorityQueue<DijkstraNode> vertexQueue = new PriorityQueue<DijkstraNode>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        DijkstraNode u = vertexQueue.poll();

        // Visit each edge exiting u
        for (Edge e : u.adjacencies) {
            DijkstraNode v = e.target;
            double weight = e.weight;
            double distanceThroughU = u.minDistance + weight;
            if (distanceThroughU < v.minDistance) {
                vertexQueue.remove(v);
                v.minDistance = distanceThroughU;
                v.previous = u;
                vertexQueue.add(v);
            }
        }
    }
}
//Ende Dijkstra Methoden


public DijkstraNode getDijkstraNode(Vector2 target) {
    // TODO Auto-generated method stub
    for (int i = 0; i < allNodes.length; i++) {
        for (int k = 0; k < allNodes[i].length; k++) {
            PathNode currentNeigbour = allNodes[i][k];
            if (currentNeigbour.x <= target.x && currentNeigbour.x + PathNode.width >= target.x &&
                    currentNeigbour.y <= target.y && currentNeigbour.y + PathNode.height >= target.y) {
                return currentNeigbour.myDijstraNode;
            }
        }
    }
    return null;
}

private void generateAllNodes() {
    TiledMapTileLayer tl = (TiledMapTileLayer) tiledMap.getLayers().get("main_background");

    if(allNodes==null)
    {
        allNodes = new PathNode[tl.getHeight()][tl.getWidth()];
        for (int i = 0; i < tl.getHeight(); i++) {
            for (int k = 0; k < tl.getWidth(); k++) {
                allNodes[i][k] = new PathNode(k, i);
                //TODO use provided method in level?
//                checkForObjectCollision(enemy)
                allNodes[i][k].walkable = !Collider.doesCollideWithWall(new Collider(
                        allNodes[i][k]), tiledMap);
            }
        }
    }
    else
    {
        for (int i = 0; i < tl.getHeight(); i++) {
            for (int k = 0; k < tl.getWidth(); k++) {
                allNodes[i][k].myDijstraNode.resetNode();
            }
        }
    }

}


public void initialiseEdges(DijkstraNode startNode) {
    // TODO Auto-generated method stub
    DijkstraNode currentNode = startNode;

    Queue<DijkstraNode> neigbourQueue=new LinkedList<DijkstraNode>();
    neigbourQueue.offer(currentNode);



    while(!neigbourQueue.isEmpty())
    {
        List<DijkstraNode> newNeigbours=innerFunction(neigbourQueue.poll(),0);
        if(newNeigbours!=null)
        neigbourQueue.addAll(newNeigbours);
    }

}


private List<DijkstraNode> innerFunction(DijkstraNode currentNode, int depth) {
    if (currentNode.adjacencies != null) {
        return null;
    }
//        if(depth>15)
//        {
//            currentNode.adjacencies=new Edge[0];
//            return;
//        }

    List<DijkstraNode> neigbours = getNeighbours(currentNode);

    currentNode.adjacencies = new Edge[neigbours.size()];
    for (int i = 0; i < neigbours.size(); i++) {
        DijkstraNode currentNeigbour = neigbours.get(i);
        currentNode.adjacencies[i] = new Edge(currentNeigbour, 1);
    }
//        for (PathNode pt : neigbours) {
//            innerFunction(pt.myDijstraNode,depth+1);
//        }
    return neigbours;
}


}

Answer 1

既然你说这是一个基于平铺的游戏，我认为有效的路径在两个方向上都是可遍历的，其成本与方向无关(或者足够接近独立)。在这种情况下，你做的工作比你需要做的更多，如果你应用Dijkstra开始在每个敌人的位置。

相反，从目标开始，在Dijkstra的同一段中找到所有敌人的最短路径(即只有在找到每个敌人的路径后才终止)。这种方法最坏的情况是不依赖于敌人的数量。

Answer 2

有一个CodeReview论坛。首先，您可以忘记浮点，使用整数算法，例如使用距离的平方。

Math.signum(originX - 1) == 1 ⇔
⇔ originX - 1 > 0 ⇔
⇔ originX > 1

如果最大的8个邻居，则保留一个容量8：

List<DijkstraNode> neighbours = new ArrayList<DijkstraNode>(8);

您认为算法更具有决定性是正确的，但这太好了，不值得评论。

Answer 3

假设您有一个正常的gameloop，那么路径查找需要一个更新迭代是很正常的。我认为您在单独线程中执行此操作的解决方案是一个不错的解决方案。许多游戏都面临着这个问题，你不希望你的角色在计算寻路的过程中保持不变。您可以通过计算一个粗略的路径(可以在一个更新迭代中计算)来解决这个问题，如果您的字符能够开始沿着一个一般的好方向行走，那么您的字符就会有一点点运气，然后在正确的路径被完全计算之后，就可以选择正确的路径。有时，他们会走错方向几帧，然后转身，以获得充分计算的路径。

如果无法使线程解决方案工作，则可以在框架更新中执行Dijkstra计算的一部分，然后暂停、绘制和计算下一个更新帧中的下一个部分。