A*路径搜索问题的处理(Java)
创始人
2024-07-21 11:40:55
0

A路径搜索是一种常用的寻路算法,可以在图形化地图中找到最短路径。以下是一个用Java实现A路径搜索的示例代码:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Node implements Comparable {
    int x, y;
    int g, h;
    Node parent;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int f() {
        return g + h;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.f(), other.f());
    }
}

public class AStarPathfinding {
    private int[][] map;
    private int startX, startY;
    private int targetX, targetY;
    private List openList;
    private List closedList;

    public AStarPathfinding(int[][] map, int startX, int startY, int targetX, int targetY) {
        this.map = map;
        this.startX = startX;
        this.startY = startY;
        this.targetX = targetX;
        this.targetY = targetY;
        this.openList = new ArrayList<>();
        this.closedList = new ArrayList<>();
    }

    public List findPath() {
        Node startNode = new Node(startX, startY);
        Node targetNode = new Node(targetX, targetY);
        openList.add(startNode);

        while (!openList.isEmpty()) {
            Node currentNode = openList.remove(0);
            closedList.add(currentNode);

            if (currentNode.x == targetX && currentNode.y == targetY) {
                return reconstructPath(currentNode);
            }

            List neighbors = getNeighbors(currentNode);
            for (Node neighbor : neighbors) {
                if (closedList.contains(neighbor)) {
                    continue;
                }

                int cost = currentNode.g + 1;
                boolean isBetter = false;

                if (!openList.contains(neighbor)) {
                    openList.add(neighbor);
                    neighbor.h = heuristic(neighbor, targetNode);
                    isBetter = true;
                } else if (cost < neighbor.g) {
                    isBetter = true;
                }

                if (isBetter) {
                    neighbor.parent = currentNode;
                    neighbor.g = cost;
                }
            }

            Collections.sort(openList);
        }

        return null;
    }

    private List getNeighbors(Node node) {
        List neighbors = new ArrayList<>();
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int neighborX = node.x + dir[0];
            int neighborY = node.y + dir[1];

            if (isValidCoordinate(neighborX, neighborY) && map[neighborX][neighborY] == 0) {
                neighbors.add(new Node(neighborX, neighborY));
            }
        }

        return neighbors;
    }

    private boolean isValidCoordinate(int x, int y) {
        return x >= 0 && x < map.length && y >= 0 && y < map[0].length;
    }

    private int heuristic(Node node1, Node node2) {
        return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);
    }

    private List reconstructPath(Node node) {
        List path = new ArrayList<>();
        Node currentNode = node;

        while (currentNode != null) {
            path.add(currentNode);
            currentNode = currentNode.parent;
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        int[][] map = {
                {0, 0, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0},
        };
        int startX = 0, startY = 0;
        int targetX = 3, targetY = 4;

        AStarPathfinding pathfinding = new AStarPathfinding(map, startX, startY, targetX, targetY);
        List path = pathfinding.findPath();

        if (path != null) {
            for (Node node : path) {
                System.out.println("(" + node.x + ", " + node.y + ")");
            }
        } else {
            System.out.println("No path found");
        }
    }
}

上述代码实现了一个简单的A*路径搜索算

相关内容

热门资讯

安装了Anaconda之后找不... 在安装Anaconda后,如果找不到Jupyter Notebook,可以尝试以下解决方法:检查环境...
安装安卓应用时出现“Play ... 在安装安卓应用时出现“Play Protect 警告弹窗”的原因是Google Play Prote...
iwatch怎么连接安卓系统,... 你有没有想过,那款时尚又实用的iWatch,竟然只能和iPhone好上好?别急,今天就来给你揭秘,怎...
vivo安卓系统取消更新系统,... 亲爱的vivo手机用户们,你们是不是也遇到了这样的烦恼:手机里突然冒出一个更新提示,点开一看,哇,新...
安卓系统怎么连不上carlif... 安卓系统无法连接CarLife的原因及解决方法随着智能手机的普及,CarLife这一车载互联功能为驾...
避免在粘贴双引号时向VS 20... 在粘贴双引号时向VS 2022添加反斜杠的问题通常是由于编辑器的自动转义功能引起的。为了避免这个问题...
安装apache-beam==... 出现此错误可能是因为用户的Python版本太低,而apache-beam==2.34.0需要更高的P...
iqoo安卓14系统怎么升级系... 亲爱的iQOO手机用户们,是不是觉得你的手机系统有点儿落伍了呢?别急,今天就来手把手教你如何升级到最...
Android Recycle... 要在Android RecyclerView中实现滑动卡片效果,可以按照以下步骤进行操作:首先,在项...
oppo手机安卓系统换成苹果系... OPPO手机安卓系统换成苹果系统:现实吗?如何操作?随着智能手机市场的不断发展,用户对于手机系统的需...