189 8069 5689
最有效，切不复杂的方法使用Breadth First Search (BFS). 基本代码如下（伪代码）。因为BFS不用递归，所以可能会有点难理解。
武义ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联公司的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：028-86922220（备注：SSL证书合作）期待与您的合作！
public Stack findPath(Vertex 起始景点, Vertex 目标景点){
Queue Vertex q = new QueueVertex();
s.enqueue(起始景点);
Vertex 当前位置;
while(!s.isEmpty()){
当前位置 = s.dequeue();
if (当前位置 == 目标景点) break;
for (每一个相邻于 当前位置 的景点 Vertex v){
if (!v.visited){
v.parent = 当前位置;
// 不是规定，不过可以节省一点时间
if (v == 目标景点){
current = v;
break;
}
s.enqueue(Vertex v);
v.visited = true;
}
}
}
Stack Vertex solution = new Stack Vertex();
Vertex parent = current;
while (parent != 起始景点){
solution.push(parent);
parent = current.parent;
}
for (graph中的每一个vertex) vertex.visited = false;
return solution(); // 其实这里建议用一个 Path 的inner class 来装所获得的路线
}
然后再 main 求每两个景点之间的距离即可
public static void main(String[] argv){
PathFinder pf = new PathFinder();
Stack[][] 路径 = new Stack[10][10];
for(int i=0; ipf.vertices.length; i++){
for(int j=i+1; jpf.vertices.length; j++){
Stack s = pf.findPath(pf.vertices[i], pf.vertices[j]);
路径[i][j] = s; 路径[j][i] = s; // 假设你的graph是一个undirected graph
}
}
// 这么一来就大功告成了！对于每两个景点n 与 m之间的最短路径就是在 stack[n][m] 中
}
还有一种方法就是用Depth First Search递归式的寻找路径，不过这样比较慢，而且我的代码可能会造成stack overflow
public Stack dfs(Vertex 当前景点，Vertex 目标景点){
if(当前景点 == 目标景点) return;
Stack solution = new Stack();
Stack temp;
for (相邻于 点钱景点 的每一个 Vertex v){
if (!v.visited){
v.visited = true;
temp = dfs(v, 目标景点);
// 抱歉，不记得是stack.size()还是stack.length()
if (solution.size() == 0) solution = temp;
else if(temp.size() solution.size()) solution = temp;
v.visited = false; 复原
}
}
return solution;
}
然后再在上述的Main中叫dfs...
参考：
自己写着玩的,很简单,你试一试哦...
主要用了javax.swing.Timer这个类:
import java.awt.*;
import javax.swing.*;
@SuppressWarnings("serial")
public class MainClass extends JFrame {
ControlSnake control;
Toolkit kit;
Dimension dimen;
public static void main(String[] args) {
new MainClass("my snake");
}
public MainClass(String s) {
super(s);
control = new ControlSnake();
control.setFocusable(true);
kit = Toolkit.getDefaultToolkit();
dimen = kit.getScreenSize();
add(control);
setLayout(new BorderLayout());
setLocation(dimen.width / 3, dimen.height / 3);// dimen.width/3,dimen.height/3
setSize(FWIDTH, FHEIGHT);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setResizable(false);
setVisible(true);
}
public static final int FWIDTH = 315;
public static final int FHEIGHT = 380;
}
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.Timer;
import java.util.Random;
@SuppressWarnings("serial")
public class ControlSnake extends JPanel implements ActionListener {
Random rand;
ArrayListPoint list, listBody;
String str, str1;
static boolean key;
int x, y, dx, dy, fx, fy, flag;
int snakeBody;
int speed;
public ControlSnake() {
snakeBody = 1;
str = "上下左右方向键控制 P键暂停...";
str1 = "现在的长度为:" + snakeBody;
key = true;
flag = 1;
speed = 700;
rand = new Random();
list = new ArrayListPoint();
listBody = new ArrayListPoint();
x = 5;
y = 5;
list.add(new Point(x, y));
listBody.add(list.get(0));
dx = 10;
dy = 0;
fx = rand.nextInt(30) * 10 + 5;// 2
fy = rand.nextInt(30) * 10 + 5;// 2
setBackground(Color.WHITE);
setSize(new Dimension(318, 380));
final Timer time = new Timer(speed, this);
time.start();
addKeyListener(new KeyAdapter() {
public void keyPressed(KeyEvent e) {
if (e.getKeyCode() == 37) {
dx = -10;
dy = 0;
} else if (e.getKeyCode() == 38) {
dx = 0;
dy = -10;
} else if (e.getKeyCode() == 39) {
dx = 10;
dy = 0;
} else if (e.getKeyCode() == 40) {
dx = 0;
dy = 10;
} else if (e.getKeyCode() == 80) {
if (flag % 2 == 1) {
time.stop();
}
if (flag % 2 == 0) {
time.start();
}
flag++;
}
}
});
}
public void paint(Graphics g) {
g.setColor(Color.WHITE);
g.fillRect(0, 0, 400, 400);
g.setColor(Color.DARK_GRAY);
g.drawLine(3, 3, 305, 3);
g.drawLine(3, 3, 3, 305);
g.drawLine(305, 3, 305, 305);
g.drawLine(3, 305, 305, 305);
g.setColor(Color.PINK);
for (int i = 0; i listBody.size(); i++) {
g.fillRect(listBody.get(i).x, listBody.get(i).y, 9, 9);
}
g.fillRect(x, y, 9, 9);
g.setColor(Color.ORANGE);
g.fillRect(fx, fy, 9, 9);
g.setColor(Color.DARK_GRAY);
str1 = "现在的长度为:" + snakeBody;
g.drawString(str, 10, 320);
g.drawString(str1, 10, 335);
}
public void actionPerformed(ActionEvent e) {
x += dx;
y += dy;
if (makeOut() == false) {
JOptionPane.showMessageDialog(null, "重新开始......");
speed = 700;
snakeBody = 1;
x = 5;
y = 5;
list.clear();
list.add(new Point(x, y));
listBody.clear();
listBody.add(list.get(0));
dx = 10;
dy = 0;
}
addPoint(x, y);
if (x == fx y == fy) {
speed = (int) (speed * 0.8);//速度增加参数
if (speed 200) {
speed = 100;
}
fx = rand.nextInt(30) * 10 + 5;// 2
fy = rand.nextInt(30) * 10 + 5;// 2
snakeBody++;// 2
} // 2
repaint();
}
public void addPoint(int xx, int yy) {
// 动态的记录最新发生的50步以内的移动过的坐标
// 并画出最新的snakeBody
if (list.size() 100) {//蛇身长度最长为100
list.add(new Point(xx, yy));
} else {
list.remove(0);
list.add(new Point(xx, yy));
}
if (snakeBody == 1) {
listBody.remove(0);
listBody.add(0, list.get(list.size() - 1));
} else {
listBody.clear();
if (list.size() snakeBody) {
for (int i = list.size() - 1; i 0; i--) {
listBody.add(list.get(i));
}
} else {
for (int i = list.size() - 1; listBody.size() snakeBody; i--) {
listBody.add(list.get(i));
}
}
}
}
public boolean makeOut() {
if ((x 3 || y 3) || (x 305 || y 305)) {
return false;
}
for (int i = 0; i listBody.size() - 1; i++) {
for (int j = i + 1; j listBody.size(); j++) {
if (listBody.get(i).equals(listBody.get(j))) {
return false;
}
}
}
return true;
}
}
去学习A星寻路，可以得到最短路径，其中也包括了绕开障碍物的代码，然后就是动画的图片切换了，如果说要地图跟随主角移动，那个应该是滚屏操作，也就是说你主角往右走，超过窗口或者屏幕（全屏）坐标一半的时候，地图整个往左移动，速度和主角的一样就出来效果了。如果你看不懂A星的话，那咂就给你一段BFS的C++语言代码，自己转换成JAVA代码写法（就是改些关键字，有不少经典的游戏算法都来自C/C++）就可以了，这个是简化版的A星寻路，一样可以找到最近的路径，你把path 这个路径记录下来再换算成像素位置就可以得到行走的具体步伐了...
#include "stdafx.h"
#include iostream
using namespace std;
const int rows = 10;//行数
const int cols = 10;//列数
const int nummax = 4;//每一步，下一步可以走的方向：4个
//四种移动方向(左、右、上、下)对x、y坐标的影响
//x坐标：竖直方向，y坐标：水平方向
const char dx[nummax] = {0,0,-1,1};
const char dy[nummax] = {-1,1,0,0};
//障碍表
char block[rows][cols] = {
0,1,0,0,0,0,0,0,0,0,
0,1,1,0,1,1,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,
1,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,1,1,0,
0,1,0,0,0,0,1,0,0,0,
0,0,0,0,0,0,1,1,0,1,
0,1,0,0,0,1,0,1,0,1,
0,1,1,1,0,0,0,1,0,1,
0,0,0,0,0,0,0,0,0,0,
};
char block2[rows][cols] = {
0,1,0,0,0,0,0,0,0,0,
0,1,1,0,1,1,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,
1,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,1,1,0,
0,1,0,0,0,0,1,0,0,0,
0,0,0,0,0,0,1,1,0,1,
0,1,0,0,0,1,0,1,0,1,
0,1,1,1,0,0,0,1,0,1,
0,0,0,0,0,0,0,0,0,0,
};
char path[rows][cols] = {0};//记录路径
int startX = 0,startY = 0;//起始点坐标
int endX = rows - 1,endY = cols - 1;//目标点坐标
//保存节点位置坐标的数据结构
typedef struct tagQNode{
char x,y;
int parentNode;//父节点索引
}QNode;
//打印路径
void printPath()
{
cout "" endl;
for (int i = 0;i rows;++i)
{
for (int j = 0;j cols;++j)
{
if (1 == path[i][j])
{
cout "♀";
}
else if(block2[i][j]==0)
cout "∷";
else if(block2[i][j]==1)
cout "■";
}
cout endl;
}
cout endl;
cout endl;
}
void BFS()
{
int num = rows * cols;
//利用数组来模拟队列
QNode *queue = (QNode *)malloc(num * sizeof(QNode));
//起始点入队列
queue[0].x = queue[0].y = 0;
queue[0].parentNode = -1;//起始点没有父节点
int front = 0,rear = 1;//队列的头和尾
while(front != rear)//队列不为空
{
for (int i = 0;i nummax;++i)
{
char nextX,nextY;//下一步的坐标
nextX = queue[front].x + dx[i];
nextY = queue[front].y + dy[i];
//下一个节点可行
if (nextX = 0 nextX rows nextY = 0 nextY cols 0 == block[nextX][nextY])
{
//寻找到目标点
if (nextX == endX nextY == endY)
{
//生成路径
path[nextX][nextY] = 1;
int ParIn = front;
while(ParIn != -1)
{
path[queue[ParIn].x][queue[ParIn].y] = 1;
ParIn = queue[ParIn].parentNode;
}
//printPath();
}
//入栈
queue[rear].x = nextX;
queue[rear].y = nextY;
queue[rear].parentNode = front;
++rear;
//标记此点已被访问
block[nextX][nextY] = 1;
}
}
++front;
}
free(queue);
}
int _tmain(int argc, _TCHAR* argv[])
{
BFS();
printPath();
system("pause");
return 0;
}
1、算法用途：
是一种图像搜索演算法。用于遍历图中的节点，有些类似于树的深度优先遍历。这里唯一的问题是，与树不同，图形可能包含循环，因此我们可能会再次来到同一节点。
2、主要思想：
主要借助一个队列、一个布尔类型数组、邻接矩阵完成（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将各点以及各点的关系存入邻接矩阵。
再从第一个点开始，将一个点存入队列，然后在邻接表中找到他的相邻点，存入队列，每次pop出队列头部并将其打印出来（文字有些抽象，实际过程很简单），整个过程有点像往水中投入石子水花散开。
（邻接表是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集）
3、代码（java）：
(以上图为例的代码）
1 import java.util.*; 2 3 //This class represents a directed graph using adjacency list
4 //representation 5 class Graph1 { 6 private static int V; // No. of vertices 7 private LinkedListInteger a Lists 8 9 // Constructor10 Graph1(int v) {11 V = v;12 adj = new LinkedList[v];13 for (int i = 0; i v; ++i)14 adj[i] = new LinkedList();15 }16 17 // Function to add an edge into the graph18 void addEdge(int v, int w) {19 adj[v].add(w);20 }21 22 // prints BFS traversal from a given source s23 public void BFS() {24 // Mark all the vertices as not visited(By default25 // set as false)26 boolean visited[] = new boolean[V];27 // Create a queue for BFS28 LinkedListInteger queue = new LinkedListInteger();29 30 for (int i = 0; i V; i++) {31 if (!visited[i]) {32 BFSUtil(i, visited, queue);33 }34 }35 }36 37 public void BFSUtil(int s, boolean visited[], LinkedListInteger queue) {38 // Mark the current node as visited and enqueue it39 visited[s] = true;40 queue.add(s);41 42 while (queue.size() != 0) {43 // Dequeue a vertex from queue and print it44 s = queue.poll();45 System.out.print(s + " ");46 47 // Get all adjacent vertices of the dequeued vertex s48 // If a adjacent has not been visited, then mark it49 // visited and enqueue it50 IteratorInteger i = adj[s].listIterator();51 while (i.hasNext()) {52 int n = i.next();53 if (!visited[n]) {54 visited[n] = true;55 queue.add(n);56 }57 }58 }59 }60 61 // Driver method to62 public static void main(String args[]) {63 Graph1 g = new Graph1(4);64 65 g.addEdge(0, 1);66 g.addEdge(0, 2);67 g.addEdge(1, 2);68 g.addEdge(2, 0);69 g.addEdge(2, 3);70 g.addEdge(3, 3);71 72 System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");73 g.BFS();74 }75 }
4、复杂度分析：
算法借助了一个邻接表和队列，故它的空问复杂度为O(V）。 遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。 邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E)。