实现的效果图

Screenshot_20181213-143828.jpeg

思路分析

根据启发算法理论 f(n) = g(n)+h(n); 其中，g(n)表示实际代价（即已经走过的路程），h(n)代表预估代价，因为使用的网格构造，所以使用曼哈顿距离公式，表示h(n)。

代码实现

数据结构（采用单向链表）

  public class Node implements Comparable<Node> {Coord coord;Node parent;int g; // G：是个精确的值，是起点到当前结点的代价int h; // H：是个估值，当前结点到目的结点的预计代价public Node(int x, int y) {    this.coord = new Coord(x,y);}public Node(int x, int y, Node parent, int h, int g) {    this.coord = new Coord(x,y);    this.parent = parent;    this.h = h;    this.g = g;}public Node getParent() {    return parent;}public void setParent(Node parent) {    this.parent = parent;}public int getH() {    return h;}public void setH(int h) {    this.h = h;}public int getG() {    return g;}public void setG(int g) {    this.g = g;}@Overridepublic int compareTo(@NonNull Node o) {    return g+h - (o.g+o.h);}@Overridepublic boolean equals(Object obj) {    Node node = (Node) obj;    return coord.x == node.coord.x && coord.y == node.coord.y;}

}

说明：

因为寻路需要通过一个点找周围最近的点，最终形成一条多段的线段，在数据结构中与单向链表吻合，故选择单向链表存储。compareTo方法是按f(n)大小排序。

核心代码思路

1.将起点加入开放列表
2.从开放列表中移除掉其中f(n)最小的一个Node，并将该节点加入到关闭列表
3.从该节点向附近扩展，假如符合条件，则加入到开放列表
4.重复23步骤直至终点与2步骤的节点重合

代码：

 public class Astart {   private int[][] map;   private int width;   private int height;    private Node start;   private Node end;   private PriorityQueue<Node> openList = new PriorityQueue<>();   private List<Node> closeList = new ArrayList<>();   public Astart(@NonNull int[][] map, @NonNull Node start, @NonNull Node end)         {    this.map = map;    this.start = start;    this.end = end;    height = map.length;    width = map[0].length;  }public Stack<Node> start() {    //将起点放入开放列表    openList.add(start);    while (!openList.isEmpty()) {        //将曼哈顿距离最近的点取出        Node node = openList.poll();        //将节点放入关闭列表中        System.out.println(node.coord);        closeList.add(node);        //假如取出来的最近的点为终点，结束循环        if (end.equals(node)) {            end = node;            break;        }        //将扩展的节点加入开放列表(朝八個方向)        addNeighborNode(node);    }    //把关闭列表选中    Node node = end;    //将数据依次放入栈实现链表倒序    Stack<Node> pathStack = new Stack<>();    while (node != null) {        pathStack.push(node);        node = node.parent;    }    return pathStack;}/** * 向八个方向扩展增加节点 * * @param node */private void addNeighborNode(Node node) {    Node left = new Node(node.coord.x - 1, node.coord.y);    left.setParent(node);    left.setG(generateG(left));    left.setH(generateH(left));    Node right = new Node(node.coord.x + 1, node.coord.y);    right.setParent(node);    right.setG(generateG(right));    right.setH(generateH(right));    Node top = new Node(node.coord.x, node.coord.y - 1);    top.setParent(node);    top.setG(generateG(top));    top.setH(generateH(top));    Node bottom = new Node(node.coord.x, node.coord.y + 1);    bottom.setParent(node);    bottom.setG(generateG(bottom));    bottom.setH(generateH(bottom));    Node leftTop = new Node(node.coord.x - 1, node.coord.y - 1);    leftTop.setParent(node);    leftTop.setG(generateG(leftTop));    leftTop.setH(generateH(leftTop));    Node leftBottom = new Node(node.coord.x - 1, node.coord.y +1);    leftBottom.setParent(node);    leftBottom.setG(generateG(leftBottom));    leftBottom.setH(generateH(leftBottom));    Node rightTop = new Node(node.coord.x + 1, node.coord.y - 1);    rightTop.setParent(node);    rightTop.setG(generateG(rightTop));    rightTop.setH(generateH(rightTop));    Node rightBottom = new Node(node.coord.x + 1, node.coord.y + 1);    rightBottom.setParent(node);    rightBottom.setG(generateG(rightBottom));    rightBottom.setH(generateH(rightBottom));    addNeighborSingleNode(left);    addNeighborSingleNode(right);    addNeighborSingleNode(top);    addNeighborSingleNode(bottom);    //        addNeighborSingleNode(leftTop);    //        addNeighborSingleNode(leftBottom);    //        addNeighborSingleNode(rightTop);    //        addNeighborSingleNode(rightBottom);}/** * 单独增加一个相邻节点 * * @param node */private void addNeighborSingleNode(Node node) {    if (canAdd(node)) {        openList.add(node);    }}private int generateG(Node node) {    if (node.parent != null) {        Node parent = node.parent;        int c = (Math.abs(start.coord.x - node.coord.x) + Math.abs(start.coord.y - node.coord.y))*100;        return parent.h + c;    }    return 0;}private int generateH(Node node) {    return Math.abs(end.coord.x - node.coord.x) + Math.abs(end.coord.y - node.coord.y)*100;}/** * 是否增加进开放列表 * * @param node * @return */private boolean canAdd(Node node) {    if (node == null || node.coord == null) {        return false;    }    int x = node.coord.x;    int y = node.coord.y;    //假如超过边界 false    if (x < 0 || x > width - 1) {        return false;    }    if (y < 0 || y > height - 1) {        return false;    }    //假如节点在地图上位墙壁 false    int mapPoint = map[y][x];    if ( mapPoint == MapUtils.WALL) {        return false;    }    //假如节点在开放列表或者者关闭列表中 false    if (openList.contains(node)) {        return false;    }    if (closeList.contains(node)) {        return false;    }    return true;}

界面代码

public class MainActivity extends AppCompatActivity {private Node start;private Node end;private ShowMapView showMapView;@Overrideprotected void onCreate(Bundle savedInstanceState) {    super.onCreate(savedInstanceState);    setContentView(R.layout.activity_main);    showMapView = findViewById(R.id.show);    showMapView.init(MapUtils.map, new ShowMapView.OnTouchListener() {        @Override        public void onTouchPoint(int type, int row, int col) {            if (type == 1) {                start = new Node(col, row);            } else {                end = new Node(col, row);            }        }    });}private void findWayAndDraw() {    if (start != null && end != null) {        Stack<Node> pathList = new Astart(MapUtils.map, start, end).start();        Path path = new Path();        path.moveTo(start.coord.x * 80 + 40, start.coord.y * 80 + 40);        while (!pathList.empty()) {            Node node = pathList.pop();            path.lineTo(node.coord.x * 80 + 40, node.coord.y * 80 + 40);        }        showMapView.setPath(path);    }}public void cal(View view) {    findWayAndDraw();}public void reset(View view) {    showMapView.reset();}}

布局文件

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"xmlns:app="http://schemas.android.com/apk/res-auto"xmlns:tools="http://schemas.android.com/tools"android:layout_width="match_parent"android:layout_height="match_parent"tools:context=".MainActivity"><com.example.n011210.findway.ShowMapView    android:id="@+id/show"    android:layout_width="match_parent"    android:layout_height="match_parent" /><Button    android:id="@+id/btn"    android:layout_width="wrap_content"    android:layout_height="wrap_content"    android:layout_alignParentBottom="true"    android:onClick="cal"    android:text="计算" /><Button    android:id="@+id/reset"    android:layout_width="wrap_content"    android:layout_height="wrap_content"    android:layout_alignParentBottom="true"    android:layout_toRightOf="@id/btn"    android:onClick="reset"    android:text="刷新" /> </RelativeLayout>

说明

ShowMapView为地图控件

   public class ShowMapView extends View {   private int touchFlag;   private int[][] map;   private Path path;     private OnTouchListener listener;  public ShowMapView(Context context) {      super(context);  }public ShowMapView(Context context, @Nullable AttributeSet attrs) {    super(context, attrs);}public ShowMapView(Context context, @Nullable AttributeSet attrs, int defStyleAttr) {    super(context, attrs, defStyleAttr);}public void init(int[][] map, OnTouchListener listener) {    this.map = map;    this.listener = listener;    invalidate();}public void setPath(Path path) {    this.path = path;    invalidate();}public void reset() {    touchFlag = 0;    for (int i = 0; i < map.length; i++) {        for (int j = 0; j < map[i].length; j++) {            if (map[i][j] == 2) {                map[i][j] = 0;            }        }    }    path.reset();    invalidate();}@Overridepublic boolean onTouchEvent(MotionEvent event) {    if (touchFlag >= 2) {        return super.onTouchEvent(event);    }    float x = event.getX();    float y = event.getY();    //每格地图大小为80*80,注意:数组和屏幕坐标X和Y相反    int row = (int) y / 80;    int col = (int) x / 80;    if (map[row][col] == 0) {        touchFlag++;        if (listener != null) {            listener.onTouchPoint(touchFlag, row, col);        }        map[row][col] = 2;    }    this.invalidate();    return super.onTouchEvent(event);}@Overrideprotected void onDraw(Canvas canvas) {    super.onDraw(canvas);    if (map == null) {        return;    }    Paint paint = new Paint();    paint.setAntiAlias(true);    paint.setColor(Color.BLUE);    paint.setStrokeWidth(5);    paint.setStyle(Paint.Style.STROKE);    for (int i = 0; i < map.length; i++) {        for (int j = 0; j < map[i].length; j++) {            if (map[i][j] == 0) {                Bitmap bm = BitmapFactory.decodeResource(this.getResources(), R.drawable.route);                canvas.drawBitmap(bm, j * 80, i * 80, paint);            } else if (map[i][j] == 1) {                Bitmap bm = BitmapFactory.decodeResource(this.getResources(), R.drawable.wall);                canvas.drawBitmap(bm, j * 80, i * 80, paint);            } else if (map[i][j] == 2) {                Bitmap bm = BitmapFactory.decodeResource(this.getResources(), R.drawable.path);                canvas.drawBitmap(bm, j * 80, i * 80, paint);            }        }    }    if (path != null) {        canvas.drawPath(path, paint);    }}public interface OnTouchListener {    void onTouchPoint(int type, int row, int col);}}