bfs算法java代码 java nfs
Java 鼠标控制人物移动，地图随人物移动
去学习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;
}
java中如何把图用邻接表表示出来
package my.graph;
import java.util.ArrayList;
import java.util.Iterator;
import my.queue.*;
import my.stack.StackX;
/**
* 邻接表表示
* @author xiayi
*
*/
public class Graph {
private int MAX_VERTS = 20;
private Vertex vertexList[];
private boolean is = false;//是否为有向图
private int nVerts = 0;
private StackX stackX;
private Vertex dfs[];
private Vertex bfs[];
private Queue queue;
public Graph(){
vertexList = new Vertex[MAX_VERTS];
dfs = new Vertex[MAX_VERTS];
bfs = new Vertex[MAX_VERTS];
}
public Graph(int n){
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
public Graph(int n, boolean is){
this.is = is;
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
//////////////////////////////////////////////
public boolean isIs() {
return is;
}
public void setIs(boolean is) {
this.is = is;
}
public Vertex[] getVertexList() {
return vertexList;
}
public Vertex[] getDfs() {
return dfs;
}
public Vertex[] getBfs() {
return bfs;
}
////////////////////////////////////////////////////
/**
* 添加顶点
*/
public void addVertex(Vertex vertex){
vertex.setIndex(nVerts);
vertexList[nVerts] = vertex;
nVerts++;
}
/**
* 添加边
*/
public void addEdge(int start, int end){
vertexList.addAdj(vertexList);
if (!is) {vertexList.addAdj(vertexList);}
}
/**
* 返回节点个数
* @return
*/
public int getVertsCount(){
return vertexList.length;
}
/**
* 深度优先迭代器
* @return
*/
public Iterator dfsIterator(){
dfs();
return new DfsIterator();
}
/**
* 广度优先迭代器
* @return
*/
public Iterator bfsIterator(){
bfs();
return new BfsIterator();
}
////////////////////////////////////////////////////////
public void displayGraph(){
ArrayListVertex next = null;
for (int i = 0; i vertexList.length; i++) {
printVertx(vertexList[i]);
}
}
public void printVertx(Vertex vertex){
ArrayListVertex next = vertex.getAdj();
if(next == null){ System.out.println(vertex.toString()+" 无连接点");}
else{
System.out.print(vertex.toString()+"有邻接点:");
for (int i = 0; i next.size(); i++) {
System.out.print("顶点"+next.get(i).label+", ");
}
System.out.println();
}
}
///////////////////////////////////////////////////////////
public void dfs(){
stackX = new StackX(MAX_VERTS);
vertexList[0].isVisted = true;
dfs[0] = vertexList[0];
stackX.push(vertexList[0]);
int dfsIndex = 0;
Vertex vertex;
while(!stackX.isEmpty()){
vertex = getAdjVertex((Vertex)stackX.peek());
if(vertex == null){
stackX.pop();
}else{
vertex.isVisted = true;
dfs[++dfsIndex]=vertex;
stackX.push(vertex);
}
}
for (int i = 0; i getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
public void bfs() {
queue = new Queue(MAX_VERTS);
vertexList[0].isVisted = true;
bfs[0] = vertexList[0];
queue.insert(vertexList[0]);
int bfsIndex = 0;
Vertex vertex;
while(!queue.isEmpty()){
Vertex vertex2 = (Vertex)queue.remove();
while((vertex = getAdjVertex(vertex2))!=null){
vertex.isVisted = true;
bfs[++bfsIndex] = vertex;
queue.insert(vertex);
}
}
for (int i = 0; i getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
/**
* 得到一个邻接点
* @param vertex
* @return
*/
public Vertex getAdjVertex(Vertex vertex){
ArrayListVertex adjVertexs = vertex.getAdj();
for (int i = 0; i adjVertexs.size(); i++) {
if(!adjVertexs.get(i).isVisted){
return adjVertexs.get(i);
}
}
return null;
}
/////////////////////////////////////////////////////////////
private abstract class GraphIterator implements Iterator{
int count = 0;
public GraphIterator(){
}
public boolean hasNext() {
return count != getVertsCount()-1;
}
public Object next() {
// TODO Auto-generated method stub
return null;
}
public void remove() {
// TODO Auto-generated method stub
}
}
//深度优先迭代
private class DfsIterator extends GraphIterator{
public DfsIterator(){
super();
}
public Vertex next() {
return dfs[count++];
}
}
//广度优先迭代
private class BfsIterator extends GraphIterator{
public BfsIterator(){
super();
}
public Object next() {
return bfs[count++];
}
}
/////////////////////////////////////////////////////////
public static void main(String[] args) {
int nVerts = 10;
int c = 'A'-1;
Vertex vertex;
Graph myGraph = new Graph(nVerts, false);
for (int i = 0; i nVerts; i++) {
c++;
vertex = new Vertex((char)(c));
myGraph.addVertex(vertex);
}
myGraph.addEdge(0, 1);
myGraph.addEdge(0, 4);
myGraph.addEdge(1, 2);
myGraph.addEdge(2, 3);
myGraph.addEdge(4, 5);
myGraph.addEdge(4, 6);
myGraph.addEdge(5, 8);
myGraph.addEdge(6, 7);
myGraph.addEdge(7, 8);
myGraph.addEdge(8, 9);
System.out.println("深度优先迭代遍历：");
for (Iterator iterator = myGraph.dfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());
}
System.out.println("/n广度优先迭代遍历：");
for (Iterator iterator = myGraph.bfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());
}
}
}
class Vertex{
public char label;
public boolean isVisted;
public int index;
private ArrayListVertex next = null;
public Vertex(char lab) // constructor
{
label = lab;
isVisted = false;
}
//为节点添加邻接点
public void addAdj(Vertex ver){
if(next == null) next = new ArrayListVertex();
next.add(ver);
}
public ArrayListVertex getAdj(){
return next;
}
public void setIndex(int index){
this.index = index;
}
public String toString(){
return "顶点 "+label+",下标："+index+".";
}
}
代码来自：
贪吃蛇 java代码
自己写着玩的,很简单,你试一试哦...
主要用了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;
}
}
JAVA求10个景点间各个景点的最短路径 图随便话 距离随便 求代码
最有效，切不复杂的方法使用Breadth First Search (BFS). 基本代码如下（伪代码）。因为BFS不用递归，所以可能会有点难理解。
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...
参考：
分别用DFS和BFS算法给电脑设置AI(JAVA)
有必胜策略的吧。。状态空间的上限是3^9也就是不到20000实际上没有这么多。所以直接采用BFS标记会比较好。算法的话就是填充表，把表（九个格子）填为必胜、必败，己胜，开始的时候全部标为必败，再从胜状态开始向回BFS（或者DFS也可以），己胜状态向回标的一定是败状态，必胜状态的上一状态为必败态，必败态的上一状态可能是必败或者必胜（这就是因为这家伙走错棋了所以要输！）
我的习惯。不写代码。没有意思。
本文名称：bfs算法java代码 java nfs
转载来于：http://pwwzsj.com/article/hidpce.html
