Java 类com.badlogic.gdx.utils.BinaryHeap 实例源码

public static Grid2D.Coordinate selectMoveTarget(Creature creature, Array<Grid2D.Coordinate> coordinates, CellValueCalculator calculator) {
    BinaryHeap<Node> heap = new BinaryHeap<Node>(9, true);
    for (Grid2D.Coordinate c : coordinates) {
        float value = calculator.getValue(creature, c.x(), c.y());
        heap.add(new Node(c.x(), c.y(), value));
    }

    if (heap.size == 0)
        return new Grid2D.Coordinate(creature.getX(), creature.getY());
    Node node = heap.peek();
    return new Grid2D.Coordinate(node.x, node.y);
}

public static <T> T selectBest(Array<T> elements, Function<T, Float> calc) {
    BinaryHeap<TypedNode<T>> heap = new BinaryHeap<TypedNode<T>>(9, true);
    for (T t : elements) {
        float value = calc.apply(t);
        heap.add(new TypedNode<T>(t, value));
    }
    if (heap.size == 0)
        return elements.first();
    return heap.peek().t;
}

@SuppressWarnings("unchecked")
public IndexedAStarPathFinder (IndexedGraph<N> graph, boolean calculateMetrics) {
    this.graph = graph;
    this.nodeRecords = (NodeRecord<N>[])new NodeRecord[graph.getNodeCount()];
    this.openList = new BinaryHeap<NodeRecord<N>>();
    if (calculateMetrics) this.metrics = new Metrics();
}

@SuppressWarnings("unchecked")
public IndexedAStarPathFinder (IndexedGraph<N> graph, boolean calculateMetrics) {
    this.graph = graph;
    this.nodeRecords = (NodeRecord<N>[])new NodeRecord[graph.getNodeCount()];
    this.openList = new BinaryHeap<NodeRecord<N>>();
    if (calculateMetrics) this.metrics = new Metrics();
}

@SuppressWarnings("unchecked")
public OptimizedPathFinder(OptimizedGraph<N> graph) {
    this.graph = graph;
    this.nodeRecords = (NodeRecord<N>[]) new NodeRecord[graph.getNodeCount()];
    this.openList = new BinaryHeap<>();
}

@Override
public boolean findPath (Object mover, N startNode, N targetNode, NavPath<N> out) {
    this.mover = mover;
    distance = 0;

    if (isBlocked(targetNode, targetNode)) return false;

    checkedID++;
    if (checkedID < 0) checkedID = 1;

    BinaryHeap<AStarAlgoData> openList = this.openList;
    AStarHeuristicCalculator<N> heuristicCalculator = this.heuristicCalculator;
    int maxSearchDistance = this.maxSearchDistance;

    openList.clear();
    addToOpenList(getAlgoData(startNode));
    getAlgoData(targetNode);

    AStarAlgoData currentData = null;
    int maxDepth = 0;
    while (maxDepth < maxSearchDistance && openList.size != 0) {
        AStarAlgoData lastData = currentData;
        currentData = openList.pop();
        currentData.open = false;
        distance = currentData.depth;
        currentData.closed = true;

        if (currentData.node == targetNode && lastData != null && !isBlocked(lastData.node, targetNode)) break;

        float currentCost = currentData.cost;
        for (N neighborNode : currentData.node.neighbors) {
            AStarAlgoData neighborData = getAlgoData(neighborNode);
            if (!isBlocked(currentData.node, neighborNode)) {
                sourceNodeInContext = startNode;
                float nextStepCost = currentCost + graph.getCost(this, neighborNode);
                if (nextStepCost < neighborData.cost) {
                    if (neighborData.open) {
                        openList.remove(neighborData);
                        neighborData.open = false;
                    }
                    neighborData.closed = false;
                }
                if (!neighborData.open && !neighborData.closed) {
                    neighborData.cost = nextStepCost;
                    neighborData.heuristic = heuristicCalculator.getCost(this, mover, neighborNode, targetNode);
                    neighborData.depth = currentData.depth + 1;
                    neighborNode.parent = currentData.node;
                    maxDepth = Math.max(maxDepth, neighborData.depth);
                    addToOpenList(neighborData);
                }
            }
        }
    }

    boolean pathFound = targetNode.parent != null;
    if (pathFound) out.fill(startNode, targetNode);
    return pathFound;
}