最有效，切不復(fù)雜的方法使用Breadth First Search (BFS). 基本代碼如下（偽代碼）。因為BFS不用遞歸，所以可能會有點難理解。
武義ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：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 = 當前位置;
// 不是規(guī)定，不過可以節(jié)省一點時間
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; // 假設(shè)你的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; 復(fù)原
}
}
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 = "現(xiàn)在的長度為:" + 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 = "現(xiàn)在的長度為:" + 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);//速度增加參數(shù)
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) {
// 動態(tài)的記錄最新發(fā)生的50步以內(nèi)的移動過的坐標
// 并畫出最新的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星尋路，可以得到最短路徑，其中也包括了繞開障礙物的代碼，然后就是動畫的圖片切換了，如果說要地圖跟隨主角移動，那個應(yīng)該是滾屏操作，也就是說你主角往右走，超過窗口或者屏幕（全屏）坐標一半的時候，地圖整個往左移動，速度和主角的一樣就出來效果了。如果你看不懂A星的話，那咂就給你一段BFS的C++語言代碼，自己轉(zhuǎn)換成JAVA代碼寫法（就是改些關(guān)鍵字，有不少經(jīng)典的游戲算法都來自C/C++）就可以了，這個是簡化版的A星尋路，一樣可以找到最近的路徑，你把path 這個路徑記錄下來再換算成像素位置就可以得到行走的具體步伐了...
#include?"stdafx.h"
#include?iostream
using?namespace?std;
const?int?rows?=?10;//行數(shù)
const?int?cols?=?10;//列數(shù)
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;//目標點坐標
//保存節(jié)點位置坐標的數(shù)據(jù)結(jié)構(gòu)
typedef?struct?tagQNode{
char?x,y;
int?parentNode;//父節(jié)點索引
}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;
//利用數(shù)組來模擬隊列
QNode?*queue?=?(QNode?*)malloc(num?*?sizeof(QNode));
//起始點入隊列
queue[0].x?=?queue[0].y?=?0;
queue[0].parentNode?=?-1;//起始點沒有父節(jié)點
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];
//下一個節(jié)點可行
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、算法用途：
是一種圖像搜索演算法。用于遍歷圖中的節(jié)點，有些類似于樹的深度優(yōu)先遍歷。這里唯一的問題是，與樹不同，圖形可能包含循環(huán)，因此我們可能會再次來到同一節(jié)點。
2、主要思想：
主要借助一個隊列、一個布爾類型數(shù)組、鄰接矩陣完成（判斷一個點是否查看過，用于避免重復(fù)到達同一個點，造成死循環(huán)等），先將各點以及各點的關(guān)系存入鄰接矩陣。
再從第一個點開始，將一個點存入隊列，然后在鄰接表中找到他的相鄰點，存入隊列，每次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、復(fù)雜度分析：
算法借助了一個鄰接表和隊列，故它的空問復(fù)雜度為O(V）。 遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程，其耗費的時間取決于所采用結(jié)構(gòu)。 鄰接表表示時，查找所有頂點的鄰接點所需時間為O(E)，訪問頂點的鄰接點所花時間為O（V）,此時，總的時間復(fù)雜度為O(V+E)。
重慶分公司
重慶分公司
