實現(xiàn)的效果圖

Screenshot_20181213-143828.jpeg

思路分析

根據(jù)啟發(fā)算法理論 f(n) = g(n)+h(n); 其中，g(n)表示實際代價（即已經(jīng)走過的路程）宪哩，h(n)代表預(yù)估代價锚沸，由于使用的網(wǎng)格構(gòu)造，所以使用曼哈頓距離公式谓苟，表示h(n)官脓。

代碼實現(xiàn)

數(shù)據(jù)結(jié)構(gòu)（采用單向鏈表）

  public class Node implements Comparable<Node> {
Coord coord;
Node parent;
int g; // G：是個準(zhǔn)確的值，是起點到當(dāng)前結(jié)點的代價
int h; // H：是個估值涝焙，當(dāng)前結(jié)點到目的結(jié)點的估計代價

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;
}

@Override
public int compareTo(@NonNull Node o) {
    return g+h - (o.g+o.h);
}

@Override
public boolean equals(Object obj) {
    Node node = (Node) obj;
    return coord.x == node.coord.x && coord.y == node.coord.y;
}

}

說明：

由于尋路需要通過一個點找附近最近的點卑笨，最終形成一條多段的線段，在數(shù)據(jù)結(jié)構(gòu)中與單向鏈表吻合仑撞，故選擇單向鏈表存儲赤兴。compareTo方法是按f(n)大小排序。

核心代碼思路

1.將起點加入開放列表
2.從開放列表中移除掉其中f(n)最小的一個Node隧哮，并將該節(jié)點加入到關(guān)閉列表
3.從該節(jié)點向周圍擴(kuò)展桶良，如果符合條件，則加入到開放列表
4.重復(fù)23步驟直至終點與2步驟的節(jié)點重合

代碼：

 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();
        //將節(jié)點放入關(guān)閉列表中
        System.out.println(node.coord);
        closeList.add(node);
        //如果取出來的最近的點為終點沮翔，結(jié)束循環(huán)
        if (end.equals(node)) {
            end = node;
            break;
        }
        //將擴(kuò)展的節(jié)點加入開放列表(朝八個方向)
        addNeighborNode(node);

    }
    //把關(guān)閉列表選中
    Node node = end;
    //將數(shù)據(jù)依次放入棧實現(xiàn)鏈表倒序
    Stack<Node> pathStack = new Stack<>();
    while (node != null) {
        pathStack.push(node);
        node = node.parent;
    }
    return pathStack;
}

/**
 * 向八個方向擴(kuò)展添加節(jié)點
 *
 * @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);
}

/**
 * 單獨添加一個相鄰節(jié)點
 *
 * @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;
}

/**
 * 能否添加進(jìn)開放列表
 *
 * @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;
    }
    //如果節(jié)點在地圖上位墻壁 false
    int mapPoint = map[y][x];
    if ( mapPoint == MapUtils.WALL) {
        return false;
    }
    //如果節(jié)點在開放列表或者關(guān)閉列表中 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;

@Override
protected 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();
}

@Override
public boolean onTouchEvent(MotionEvent event) {
    if (touchFlag >= 2) {
        return super.onTouchEvent(event);
    }
    float x = event.getX();
    float y = event.getY();
    //每格地圖大小為80*80,注意:數(shù)組和屏幕坐標(biāo)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);
}

@Override
protected 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);
}
}