ub
启发式寻路代码
输入起点和终点,在地图中查找到最短路径
github代码:https://github.com/chengdongba/SearchRoad.git
整体思路:
AStart.java
从起点开始,向起点周围8个方向(上下左右,斜上下左右)搜索可以走的格子(Node),用开放列表openList存放,
从开放列表中找出离终点最近的点,放入关闭列表(closelist),然后从这个点继续向周围8个方向扩张,直到到达终点,路径就是closeList里面的点相连
地图绘制
ShowMapView.java
继承View重写onTouchEvent和onDraw方法
在onTouchEvent中实现选择起点和终点的绘制
用一个flag计数器,点一下就++,0表示还没有选,1表示选了起点,2表示选的终点
在onDraw里面实现地图的绘制
地图用二维数组建模
0表示草地
1表示墙
2表示路径
根据二维数组中的数据来绘制地图,用三张图片分别表示草地,墙和路径
注意: 二维数组和屏幕坐标系是相反的,二维数组的x轴上的数据表示的是列,即屏幕坐标系的y轴
package com.dqchen.www.searchroad;
import android.os.Handler;
import android.os.Looper;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import com.dqchen.www.searchroad.map_util.MapInfo;
import com.dqchen.www.searchroad.map_util.MapUtils;
import com.dqchen.www.searchroad.map_util.Node;
import com.dqchen.www.searchroad.map_util.ShowMapView;
import static com.dqchen.www.searchroad.map_util.MapUtils.map;
import static com.dqchen.www.searchroad.map_util.MapUtils.printMap;
import static com.dqchen.www.searchroad.map_util.MapUtils.touchFlag;
public class MainActivity extends AppCompatActivity {
ShowMapView showMapView;
Handler handler = null;
@Override
protected void onCreate(Bundle savedInstanceState) {
handler = new Handler(Looper.getMainLooper());
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
showMapView = findViewById(R.id.show);
}
public void cal(View view) {
MapInfo mapInfo = new MapInfo(map, map[0].length, map.length, new Node(MapUtils.startCol, MapUtils.startRow), new Node(MapUtils.endCol, MapUtils.endRow));
Log.i("dechen","start="+MapUtils.startCol+" "+MapUtils.startRow);
Log.i("dechen","end="+MapUtils.endCol+" "+MapUtils.endRow);
new Astar().start(mapInfo);
new MoveThread(showMapView).start();
}
public void reset(View view) {
MapUtils.path = null;
MapUtils.result.clear();
MapUtils.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;
}
}
}
showMapView.invalidate();
}
class MoveThread extends Thread{
ShowMapView showMapView;
public MoveThread(ShowMapView showMapView){
this.showMapView = showMapView;
}
@Override
public void run() {
while (MapUtils.result.size()>0){
Log.i("dqchen",MapUtils.result.size()+" ");
Node node = MapUtils.result.pop();
map[node.coord.y][node.coord.x] = 2;
handler.post(new Runnable() {
@Override
public void run() {
showMapView.invalidate();
}
});
try {
Thread.sleep(300);
} catch (InterruptedException e) {
e.printStackTrace();
}
map[node.coord.y][node.coord.x] = 0;
}
touchFlag = 0;
}
}
}
package com.dqchen.www.searchroad;
import android.graphics.Path;
import com.dqchen.www.searchroad.map_util.Coord;
import com.dqchen.www.searchroad.map_util.MapInfo;
import com.dqchen.www.searchroad.map_util.MapUtils;
import com.dqchen.www.searchroad.map_util.Node;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* Created by Jett on 2018/10/31.
*/
class Astar {
public final static int DIRECT_VALUE = 10;
public final static int OBLIQUE_VALUE = 14;
//开放列表 白格子
private Queue<Node> openList = new PriorityQueue<Node>();
//关闭列表 黄格子
private List<Node> closeList = new ArrayList<Node>();
/**
* 计算H值
*/
private int calcH(Coord end, Coord coord) {
return Math.abs(end.x - coord.x) + Math.abs(end.y - coord.y);
}
/**
* 判断是否为终点
*/
private boolean isEndNode(Coord end, Coord coord) {
return coord != null && end.equals(coord);
}
/**
* 从open中查找
*/
private Node findNodeInOpen(Coord coord) {
if (coord == null || openList.isEmpty()) return null;
for (Node node : openList) {
if (node.coord.equals(coord)) {
return node;
}
}
return null;
}
/**
* 判断是否在close中
*/
private boolean isCoordInClose(Coord coord) {
return coord != null && isCoordInClose(coord.x, coord.y);
}
private boolean isCoordInClose(int x, int y) {
if (closeList.isEmpty()) return false;
for (Node node : closeList) {
if (node.coord.x == x && node.coord.y == y) {
return true;
}
}
return false;
}
/**
* 判断一个位置是否可以选择
*/
private boolean canAddNodeToOpen(MapInfo mapInfo, int x, int y) {
//是否在地图中
if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.height) return false;
//判断是否能过
if (mapInfo.map[y][x] == MapUtils.WALL) return false;
//判断是否已经被 选择过的
if (isCoordInClose(x, y)) return false;
return true;
}
/**
* 算法开始
*/
public void start(MapInfo mapInfo) {
if (mapInfo == null) return;
//清空以前的所有的内容
openList.clear();
closeList.clear();
//开始搜索
openList.add(mapInfo.start);
//开始向周围扩展
moveNodes(mapInfo);
}
private void moveNodes(MapInfo mapInfo) {
while (!openList.isEmpty()) {
if (isCoordInClose(mapInfo.end.coord)) {//如果已经是终点了
//统计结果
calcPath(mapInfo.map, mapInfo.end);
}
//把open中最小的一个取出来 ,放到close中
Node current = openList.poll();
closeList.add(current);
//开始扩展
addNeighborNodeInOpen(mapInfo, current);
}
}
private void calcPath(int[][] map, Node end) {
MapUtils.path = new Path();
if (end != null) {
MapUtils.path.moveTo(end.coord.x * 80 + 40, end.coord.y * 80 + 40);
}
while (end != null) {//把结果入栈
MapUtils.path.lineTo(end.coord.x * 80 + 40, end.coord.y * 80 + 40);
MapUtils.result.push(end);
end = end.parent;
}
}
private void addNeighborNodeInOpen(MapInfo mapInfo, Node current) {
int x = current.coord.x;
int y = current.coord.y;
addNeighborNodeInOpen(mapInfo, current, x - 1, y, DIRECT_VALUE);
addNeighborNodeInOpen(mapInfo, current, x, y - 1, DIRECT_VALUE);
addNeighborNodeInOpen(mapInfo, current, x + 1, y, DIRECT_VALUE);
addNeighborNodeInOpen(mapInfo, current, x, y + 1, DIRECT_VALUE);
addNeighborNodeInOpen(mapInfo, current, x + 1, y + 1, OBLIQUE_VALUE);
addNeighborNodeInOpen(mapInfo, current, x - 1, y - 1, OBLIQUE_VALUE);
addNeighborNodeInOpen(mapInfo, current, x + 1, y - 1, OBLIQUE_VALUE);
addNeighborNodeInOpen(mapInfo, current, x - 1, y + 1, OBLIQUE_VALUE);
}
/**
* 核心移动功能
*/
private void addNeighborNodeInOpen(MapInfo mapInfo, Node current, int x, int y, int directValue) {
if (canAddNodeToOpen(mapInfo, x, y)) {//是否可以通过
Node end = mapInfo.end;//地图的终点
Coord coord = new Coord(x, y);//需要填入的位置
int g = current.g + directValue;
Node child = findNodeInOpen(coord);
if (child == null) {//如果能填入数字
int h = calcH(end.coord, coord);
if (isEndNode(end.coord, coord)) {//如果到了终点
child = end;
child.parent = current;
child.g = g;
child.h = h;
} else {//否则
child = new Node(coord, current, g, h);
}
openList.add(child);
} else {
//如果已经填过的数据，不用理会
}
}
}
}
package com.dqchen.www.searchroad.map_util;
/**
* Created by Administrator on 2019/2/16.
* 地图上坐标点的实例类
*/
public class Coord {
public int x;
public int y;
public Coord(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (obj == null) return false;
if (obj instanceof Coord) {
Coord o = (Coord) obj;
return x == o.x && y == o.y;
} else {
return false;
}
}
}
package com.dqchen.www.searchroad.map_util;
import android.util.Log;
/**
* Created by Administrator on 2019/2/16.
*
* 地图实例类
*
* int[][] map : 二维数组地图
* int width : 宽度
* int height : 高度
* Node start : 起点
* Node end : 终点
*
*/
public class MapInfo {
public int[][] map;
public int width;
public int height;
public Node start;
public Node end;
public MapInfo(int[][] map, int width, int height, Node start, Node end) {
this.map = map;
this.width = width;
this.height = height;
this.start = start;
this.end = end;
Log.i("dqchen","地图初始化成功");
}
}
package com.dqchen.www.searchroad.map_util;
import android.graphics.Path;
import java.util.Stack;
/**
* Created by Administrator on 2019/2/16.
*
* 地图模型类
*
*/
public class MapUtils {
public static int startRow = 0;
public static int startCol = 0;
public static int endRow = 0;
public static int endCol = 0;
public static int touchFlag = 0;
public static Stack<Node> result = new Stack<>();
public static Path path;
public final static int WALL = 1; // 障碍
public final static int PATH = 2; // 路径
public static int[][] map = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1},
{1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1},
{0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1},
{0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0},
{1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1},
{1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1},
{1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1}
};
public static int mapRowSize = map.length;
public static int mapColSize = map[0].length;
/**
* 打印地图
*/
public static void printMap(int[][] maps) {
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[i].length; j++) {
System.out.print(maps[i][j] + " ");
}
System.out.println();
}
}
}
package com.dqchen.www.searchroad.map_util;
import android.support.annotation.NonNull;
/**
* Created by Administrator on 2019/2/16.
* 路径结点实例类
* <p>
* Coord coord: 坐标
* Node parent : 父节点
* int g : 起点到当前节点的实际代价
* int h : 当前节点到终点的预估代价
*/
public class Node implements Comparable<Node> {
public Coord coord;
public Node parent;
public int g;
public int h;
public Node(int x, int y) {
this.coord = new Coord(x, y);
}
public Node(Coord coord, Node parent, int g, int h) {
this.coord = coord;
this.parent = parent;
this.g = g;
this.h = h;
}
@Override
public int compareTo(@NonNull Node o) {
if (o == null) {
return -1;
} else {
if (o.g + o.h > g + h) {
return -1;
} else if (o.g + o.h < g + h) {
return 1;
} else {
return 0;
}
}
}
}
package com.dqchen.www.searchroad.map_util;
import android.content.Context;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.os.Build;
import android.support.annotation.Nullable;
import android.support.annotation.RequiresApi;
import android.util.AttributeSet;
import android.view.MotionEvent;
import android.view.View;
import com.dqchen.www.searchroad.R;
/**
* Created by Administrator on 2019/2/16.
*
* 地图绘制实例类
*
*/
public class ShowMapView extends View {
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);
}
@RequiresApi(api = Build.VERSION_CODES.LOLLIPOP)
public ShowMapView(Context context, @Nullable AttributeSet attrs, int defStyleAttr, int defStyleRes) {
super(context, attrs, defStyleAttr, defStyleRes);
}
@Override
public boolean onTouchEvent(MotionEvent event) {
float x = event.getX();
float y = event.getY();
//地图每格大小为80*80,屏幕x,y和数组x,y是相反的
int row = (int) (y/80);
int col = (int) (x/80);
if (MapUtils.map[row][col]==0){
MapUtils.touchFlag++;
if (MapUtils.touchFlag==1){
MapUtils.startRow = row;
MapUtils.startCol = col;
MapUtils.map[row][col] = 2;
}else if (MapUtils.touchFlag==2){
MapUtils.endRow = row;
MapUtils.endCol = col;
MapUtils.map[row][col] = 2;
}
}
this.invalidate();
return super.onTouchEvent(event);
}
@Override
protected void onDraw(Canvas canvas) {
super.onDraw(canvas);
Paint paint = new Paint();
paint.setAntiAlias(true);
paint.setStyle(Paint.Style.STROKE);
paint.setStrokeWidth(5);
paint.setColor(Color.BLUE);
for (int i = 0; i < MapUtils.map.length; i++) {
for (int j = 0; j < MapUtils.map[i].length; j++) {
if (MapUtils.map[i][j]==0){
Bitmap bitmap = BitmapFactory.decodeResource(this.getResources(), R.drawable.route);
canvas.drawBitmap(bitmap,j*80,i*80,paint);
}else if (MapUtils.map[i][j]==1){
Bitmap bitmap = BitmapFactory.decodeResource(this.getResources(),R.drawable.wall);
canvas.drawBitmap(bitmap,j*80,i*80,paint);
}else if (MapUtils.map[i][j]==2){
Bitmap bitmap = BitmapFactory.decodeResource(this.getResources(),R.drawable.path);
canvas.drawBitmap(bitmap,j*80,i*80,paint);
}
}
}
if (MapUtils.path!=null){
canvas.drawPath(MapUtils.path,paint);
}
}
}
