A* 寻路算法运行速度极慢 [英] A* Path finding algorithm running extremely slow
本文介绍了A* 寻路算法运行速度极慢的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我目前正在开发我的第一款安卓游戏，也是我第一次创建 a* 寻路算法.这是一款2d游戏.我已经创建了一个包含该算法的敌人(即，它每帧运行一次)并且将性能从 60fps 降低到 1-2 fps.显然有些事情是非常错误的，我曾尝试在网上寻找解决方案，但还没有找到答案.这是我的寻路课程:
I am currently working on my first game for android, and my first time creating an a* path finding algorithm. It is a 2d game. I have created one enemy containing this algorithm (ie. It is being ran once every frame) and it slows down performance from 60fps to 1-2 fps. Obviously something is horribly wrong, I have tried looking online for solutions but have yet to find an answer. Here are my pathfinding classes:
package com.frog8fly.nunca;
导入 com.badlogic.gdx.utils.Array;
import com.badlogic.gdx.utils.Array;
导入 java.util.Comparator;
import java.util.Comparator;
公共类寻路{
private static Node[][] grid;
private static NodeComparator nodeComparator;
static{
nodeComparator = new NodeComparator();
}
public static class NodeComparator implements Comparator<Node> {
@Override
public int compare(Node node1, Node node2) {
if(node1.F > node2.F){
return 1;
}
else if(node1.F < node2.F){
return -1;
}
else{
return 0;
}
}
}
public static Array<Node> findPath(Node start, Node finish, Node[][] _grid) {
Array<Node> path = new Array<Node>();
Array<Node> openList = new Array<Node>();
Array<Node> closedList = new Array<Node>();
grid = _grid;
Node currentNode = start;
currentNode.parent = null;
currentNode.G = 0;
currentNode.H = getHeuristic(currentNode, finish);
openList.add(currentNode);
System.out.println("PATHFINDING STARTED ||| startPos : " + start.position + " finishPos : " + finish.position);
while (openList.size > 0) {
//Sorts open nodes lowest F value to heighest
openList.sort(nodeComparator);
currentNode = openList.first();
//If path is found, return
if (currentNode == finish) {
System.out.println("PATH FOUND...RETURNING -gat5");
return constructPath(currentNode);
}
openList.removeValue(currentNode, true);
closedList.add(currentNode);
int counter = 0;
for (Node neighbor : getNeighbors(currentNode)) {
if (!closedList.contains(neighbor, true)) { //If neighbor not in closed list
if(neighbor != null) { //If neighbor not wall
if(counter == 4){
counter++;
}
int movementCost = checkMovementCost(counter);
if (openList.contains(neighbor, true)) {
if (currentNode.G + movementCost < neighbor.G) {
neighbor.parent = currentNode;
}
} else {
openList.add(neighbor);
neighbor.parent = currentNode;
neighbor.H = getHeuristic(currentNode, finish);
neighbor.G = neighbor.parent.G + movementCost;
}
counter++;
}
}
}
}
System.out.println("NO PATH FOUND RETURNING...");
path.add(start);
return path;
}
private static int checkMovementCost(int neighbor) {
int movementCost = 0;
switch (neighbor) {
//Diagonal
case 0:
case 2:
case 6:
case 8:
movementCost = 16;
break;
//Not Diagonal
case 1:
case 3:
case 5:
case 7:
movementCost = 10;
break;
}
return movementCost;
}
public static Array<Node> constructPath(Node finish) {
Array<Node> pathNodes = new Array<Node>();
Node currentNode = finish;
pathNodes.add(currentNode);
while (currentNode.parent != null) {
currentNode = currentNode.parent;
pathNodes.add(currentNode);
System.out.println("Anotha");
}
pathNodes.reverse();
return pathNodes;
}
private static float getHeuristic(Node start, Node finish){
int H = 0;
System.out.println(start.position);
System.out.println(finish.position);
H += Math.abs(start.position.x - finish.position.x);
H += Math.abs(start.position.y - finish.position.y);
return H;
}
private static Array<Node> getNeighbors(Node node){
Array<Node> neighbors = new Array<Node>();
int x = (int)node.position.x;
int y = (int)node.position.y;
if(x - 1 > 0 && x - 1 < grid.length && y + 1 < grid.length && y + 1 > 0){
neighbors.add(grid[x - 1][y + 1]);
}
else{
neighbors.add(null);
}
if(x > 0 && x < grid.length && y + 1 < grid.length && y + 1 > 0){
neighbors.add(grid[x][y + 1]);
}
else{
neighbors.add(null);
}
if(x + 1 > 0 && x + 1 < grid.length && y + 1 < grid.length && y + 1 > 0){
neighbors.add(grid[x + 1][y + 1]);
}
else{
neighbors.add(null);
}
if(x - 1 > 0 && x - 1 < grid.length && y < grid.length && y > 0){
neighbors.add(grid[x - 1][y]);
}
else{
neighbors.add(null);
}
if(x > 0 && x < grid.length && y < grid.length && y > 0){
neighbors.add(grid[x][y]);
}
else{
neighbors.add(null);
}
if(x + 1 > 0 && x + 1 < grid.length && y < grid.length && y > 0){
neighbors.add(grid[x + 1][y]);
}
else{
neighbors.add(null);
}
if(x - 1 > 0 && x - 1 < grid.length && y - 1 < grid.length && y - 1> 0){
neighbors.add(grid[x - 1][y - 1]);
}
else{
neighbors.add(null);
}
if(x > 0 && x < grid.length && y - 1 < grid.length && y - 1 > 0){
neighbors.add(grid[x][y - 1]);
}
else{
neighbors.add(null);
}
if(x + 1 > 0 && x + 1 < grid.length && y - 1 < grid.length && y - 1 > 0){
neighbors.add(grid[x + 1][y - 1]);
}
else{
neighbors.add(null);
}
for(Node nodee : neighbors){
if(node.position != null){
}
}
return neighbors;
}
}
还有我的 Node 类:
And my Node class:
package com.frog8fly.nunca;
import com.badlogic.gdx.math.Vector2;
public class Node{
public Node parent;
public Vector2 position;
public float G, H, F;
public Node(Vector2 position){
this.position = position;
this.position.x = (int)Math.floor(this.position.x);
this.position.y = (int)Math.floor(this.position.y);
}
}
推荐答案
你的启发式函数是错误的.我相信你想要:
You're heuristic function is wrong. I believe you want:
H += Math.abs(start.position.x - finish.position.x);
H += Math.abs(start.position.y - finish.position.y);
使用不正确的启发式方法肯定会降低 A* 搜索的速度，因为它基本上会将其减少为广度优先搜索.
Having an incorrect heuristic could definitely slow down A* search to a crawl since it basically reduces it to breadth first search.
这篇关于A* 寻路算法运行速度极慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
