返回首页
当前位置: 主页 > 网络编程 > Jsp实例教程 >

j2me版本的A*寻路搜索算法代码

时间:2012-02-29 22:09来源:2018年最新注册送彩金www.zhixing123.cn 编辑:麦田守望者

MIDlet:

import javax.microedition.lcdui.Display;
import javax.microedition.midlet.MIDlet;
import javax.microedition.midlet.MIDletStateChangeException;
/**
*
* @author peiandsky
*
*/
public class Main extends MIDlet {

public Main() {

}

protected void destroyApp(boolean arg0) throws MIDletStateChangeException {

}

protected void pauseApp() {

}

protected void startApp() throws MIDletStateChangeException {
Display.getDisplay(this).setCurrent(new StarCanvas());
}

}

 

NODE:

/**
*
* @author peiandsky
*
*/
public class Node {
int col;
int row;
Node parent;
double cost;

public Node(int c, int r, int cost, Node p) {
col = c;
row = r;
parent = p;
this.cost = cost;
}

public void setParent(Node parent) {
this.parent = parent;
}

public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (this == obj) {
return true;
}
Node o = (Node) obj;
if (o.row == this.row && o.col == this.col) {
return true;
}
return false;
}

}


Canvas:

import java.util.Vector;

import javax.microedition.lcdui.Canvas;
import javax.microedition.lcdui.Graphics;

/**
*
* @author peiandsky
*
*/
public class StarCanvas extends Canvas implements Runnable {
int rows = 10;
int cols = 10;
int[][] map = new int[rows][cols];
// 起始位置
int startCol = 4;
int startRow = 5;
// 目标位置
int destCol = 6;
int destRow = 1;

Node start = new Node(startCol, startRow, 0, null);
Node end = new Node(destCol, destRow, 0, null);

public StarCanvas() {
setFullScreenMode(true);
new Thread(this).start();
initMap();
}

private void initMap() {
// 1
map[0][0] = 1;
map[0][1] = 1;
map[1][0] = 1;
// 2
map[8][0] = 1;
map[7][0] = 1;
map[7][1] = 1;
map[7][2] = 1;
// 3
map[9][6] = 1;
map[9][7] = 1;
// 4
map[3][3] = 1;
map[3][4] = 1;
map[3][5] = 1;
map[3][6] = 1;
map[3][7] = 1;
map[4][7] = 1;
map[5][7] = 1;
map[6][7] = 1;
}

protected void paint(Graphics g) {
g.setColor(0xffffff);
g.fillRect(0, 0, getWidth(), getHeight());
g.setColor(0);
paintMap(g);
}

private void paintMap(Graphics g) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
if (map[i][j] == 0)
g.drawRect(j * 20, i * 20, 20, 20);
else if (map[i][j] == 1)
g.fillRect(j * 20, i * 20, 20, 20);
else {
g.setColor(0xff0000);
g.fillRect(j * 20, i * 20, 20, 20);
g.setColor(0);
}
}
}
}

public void run() {
while (true) {
boolean b = this.pathFinding(start, end);
repaint();
try {
Thread.sleep(500);
if (b) {
System.out.println("找到通路");
} else {
System.out.println("没有通路");
}
break;
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}

public boolean pathFinding(Node start, Node end) {
Vector openlist = new Vector();
Vector closelist = new Vector();
Node current = null;
// 1,添加开始点到openlist
openlist.addElement(start);
// 2.寻路逻辑
while (!openlist.isEmpty()) {
current = findMinCostInOpenlist(openlist);
if (current.equals(end)) {
System.out.println("搜索结束,返回路径");
while (current != null) {
System.out.println(current.row + " " + current.col);
map[current.row][current.col] = 2;
current = current.parent;
}
return true;
} else {
openlist.removeElement(current);
closelist.addElement(current);
findAdjacentNodeAndAddToOpenlist(openlist, closelist, current,
end);
}
}

return false;
}

private void findAdjacentNodeAndAddToOpenlist(Vector openlist,
Vector closelist, Node current, Node end) {
Vector adj = new Vector();
int currentCol = current.col;
int currentRow = current.row;
if (currentRow - 1 >= 0) {
Node n1 = new Node(currentCol, currentRow - 1, 0, current);
adj.addElement(n1);
if (currentCol - 1 >= 0) {
Node n2 = new Node(currentCol - 1, currentRow - 1, 0, current);
adj.addElement(n2);
Node n3 = new Node(currentCol - 1, currentRow, 0, current);
adj.addElement(n3);
}
if (currentCol + 1 < cols) {
Node n4 = new Node(currentCol + 1, currentRow - 1, 0, current);
adj.addElement(n4);
Node n5 = new Node(currentCol + 1, currentRow, 0, current);
adj.addElement(n5);
}

}

if (currentRow + 1 < rows) {
Node n6 = new Node(currentCol, currentRow + 1, 0, current);
adj.addElement(n6);
if (currentCol - 1 >= 0) {
Node n7 = new Node(currentCol - 1, currentRow + 1, 0, current);
adj.addElement(n7);
}
if (currentCol + 1 < cols) {
Node n8 = new Node(currentCol + 1, currentRow + 1, 0, current);
adj.addElement(n8);
}
}

for (int i = 0, size = adj.size(); i < size; i++) {
Node n = (Node) adj.elementAt(i);
if (closelist.contains(n) || openlist.contains(n)
|| map[n.row][n.col] != 0) {
continue;
}
int x = (end.col - n.col) * (end.col - n.col);
int y = (end.row - n.row) * (end.row - n.row);
n.cost = current.cost + 1 + Math.sqrt(x + y);
openlist.addElement(n);
}

}

/***************************************************************************
* 查找到openlist中花费最少的节点
*
* @param openlist
* @return 返回该节点
*/
public Node findMinCostInOpenlist(Vector openlist) {
Node minNode = (Node) openlist.elementAt(0);
double minCost = minNode.cost;
int size = openlist.size();
if (size == 1) {
return minNode;
}
for (int s = openlist.size(), i = 1; i < s; i++) {
Node t = (Node) openlist.elementAt(i);
if (t.cost < minCost) {
minCost = t.cost;
minNode = t;
}
}
return minNode;
}
}


 

顶一下
(0)
0%
踩一下
(0)
0%
标签(Tag):Java JAVA实例教程 JAVA基础教程 Java源代码 Java技巧
------分隔线----------------------------
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:点击我更换图片
博聚网