求java实现矩阵图上任意两点的最短路径源码

我用的是递归调用方法，有个小问题就是在打印步数的时候是返向的，原因是就是程序不断的调用自己，到最后判断基值位准退出调用。这才开始从栈里取出方法进行执行的原因。

10年积累的网站设计制作、做网站经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站制作后付款的网站建设流程，更有大关免费网站建设让你可以放心的选择与我们合作。

代码欣赏：

public static int step = 1;

public static StringBuffer printStep = new StringBuffer();

public static int[][] maze ={{1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,1,0,0,0,0,0,1 },

{1,0,1,0,0,0,1,0,1,1,1 },

{1,0,0,0,1,0,1,0,0,0,1 },

{1,0,1,1,0,0,1,0,0,1,1 },// 0代表可以通过，1代表不可通过

{1,0,1,0,1,1,0,1,0,0,1 },

{1,0,0,0,0,0,0,0,1,0,1 },

{1,0,1,0,1,0,1,0,1,0,1 },

{1,0,0,1,0,0,1,0,1,0,1 },

{1,1,1,1,1,1,1,1,1,1,1 } };

public static void main(String[] args) {

int i, j; //循环记数变量

Sample.way(1, 1);//二维数组起始值从下标1，1开始

System.out.println("起点从坐标 x = 1, y = 1开始");

System.out.println("终点坐标是 x = 8, y = 9结束");

System.out.println("这是迷宫图表");

System.out.println("  0    1    2    3    4    5    6    7    8    9   10");

System.out.println("  +---+---+---+---+---+---+---+---+---+---+---+---+---+");

for(i = 0; i  10; i++){

System.out.print(" " + i + "‖");

for(j = 0; j  11; j++)

System.out.print("-" + maze[i][j] + "-‖");

System.out.println("");

System.out.println("  +---+---+---+---+---+---+---+---+---+---+---+---+---+");

}

//打印显示步数

System.out.print(printStep.toString());

}

public static boolean way(int x, int y){

if(maze[8][9] == 2)//代表递归终止条件（也就是当走出出口时标记为 2）

return true;

else{

if(maze[y][x] == 0){

maze[y][x] = 2;

/*

* 下面if判断条件代表当前坐标为基点，

* 根据判断对当前位置进行递归调用：如：

* 往上、往右上、往右、往右下、往下、

* 往左下、往左、往左上的坐标是否可走，

* 判断是否可走的返回条件是：

* 2代表可通过、1代表不能通过、3表示已经走过，但是未能走通。

*/

if(way(x, y - 1)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else if(way(x + 1, y - 1)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else if(way(x + 1 , y)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else if(way(x + 1, y + 1)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else if(way(x, y + 1)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else if(way(x - 1, y + 1)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else if(way(x - 1, y)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else if(way(x - 1, y - 1)){

printStep.append("第 " + step + " 步的所走的位置是 x = " + x + " y = " + y + "\n");

step++;

return true;

}else{

maze[y][x] = 3;

return false;

}

}else

return false;

}

}

复制代码前需要楼主自己创建个 类

Sample.way(1, 1);这句代码是我的类的静态调用，改下XXXXX.way(1, 1);

XXXXX代表你创建的类。

下面是这个程序运行后的截图

Java 寻路算法,贪吃蛇，俄罗斯方块，连连看

这3个算法都不简单，给你写出完整代码，至少要一下午的时间，才10分，太实惠了吧

java 怎么使用navmesh

1 将你的地型、带有collider的模型等等资源设置为静态资源

2 使用烘焙，计算这些资源“能够行走的位置”

3 在需要寻路的人物或者其他单位上面加上navMeshAgent组件

4 使用代码进行寻路navMeshAgent中有setDestination();方法用于设定目标

求程序代码（java版的数据结构）

3个class，运行UI.java。

******

public class CircuitException extends Exception {public CircuitException(){}}

*****

import java.util.LinkedList;

public class GPS {

public static final int MAX = 65535;

public GPS(int maxSize){

graph = new Graph(maxSize);

}

public GPS(){

graph = new Graph();

}

public Graph graph;

public static void main(String args[]){

GPS gps = new GPS();

try {

gps.graph.addEdge("a", "b", 1);

gps.graph.addEdge("a", "c", 1);

gps.graph.addEdge("b","d" , 1);

gps.graph.addEdge("c","d" , 1);

gps.graph.addEdge("d","e" , 1);

gps.graph.addEdge("d","f" , 1);

gps.graph.addEdge("e","t" , 2);

gps.graph.addEdge("f","t" , 1);

LinkedList list = gps.graph.getPath("a", "d");

for(int i = 0 ; i list.size() ; i++){

System.out.print(list.get(i));

}System.out.println();

} catch (CircuitException e) {

System.out.println("出现了自环！");

}

gps.graph.showGraph();

System.out.println(gps.graph.gap);

}

public class Graph{

public int Zuidazhi = 50;

public int changdu = 0;

public Jiao[] vertex;

public double gap;

public Graph(){

vertex = new Jiao[Zuidazhi];

}

public Graph(int maxSize){

this.Zuidazhi = maxSize;

vertex = new Jiao[maxSize];

}

public void addVertex(String name){

vertex[changdu++] = new Jiao(name);

}

public void addEdge(String v1, String v2,double edge) throws CircuitException{

//先找到v1；

if(v1.equals(v2))

throw new CircuitException();

Jiao from = null;

Jiao to = null;

for(int i = 0 ; i changdu ; i++){

if(vertex[i].name.equals(v1)){

from = vertex[i];

}else if(vertex[i].name.equals(v2)){

to = vertex[i];

}

}

if(from == null){

this.addVertex(v1);

from = this.vertex[changdu-1];

}

if(to == null){

this.addVertex(v2);

to = this.vertex[changdu-1];

}//已经找到v1和v2；

//没有检测是否v1 v2边已经存在！

//加入边。

Jiao v1adj = new Jiao(v2);

v1adj.edge = edge;

Jiao v2adj = new Jiao(v1);

v2adj.edge = edge;

//添加联系

//检查联系是否已经存在

Jiao temp = from;

while(temp.next!=null){

Jiao temppar = temp;

temp = temp.next;

if(temp.name.equals(v1adj.name)){

temppar.next = temp.next;

}

}

v1adj.next = from.next;

from.next = v1adj;

//v2adj.next = to.next;

//to.next = v2adj;

}

//假设要找的必然存在，不用想是否不在

public LinkedList getPath(String v1 ,String v2){

int count = 0;

//System.out.println(count++);

boolean found[] = new boolean[changdu];

double distance[] = new double[changdu];

int to = 0;

Jiao from = null;

for(int i = 0 ; i changdu ; i++){

found[i] = false;

distance[i] = MAX;

}

for(int i = 0 ; i changdu ; i++){

if(vertex[i].name.equals(v1)){//找到始发地

from = vertex[i];

distance[i] = 0;

found[i] = true;

//System.out.println(count++);

}

if(vertex[i].name.equals(v2)){//找到目的地

to = i;

//System.out.println(count++);

}

}

//必须先准备好路径！

Jiao forCount = from;

int degree = 0;

while(forCount!=null){

degree++;

forCount=forCount.next;

}

LinkedList[] list = new LinkedList[degree];

int [] mark = new int[degree];

for(int i = 0 ; i degree ; i++){

list[i]=new LinkedList();

mark[i]=MAX;

}

int test=0;

int count2 = 0;

int count3 = 0;

//System.out.println(count+++"xx");

while(!found[to]test++100){

//System.out.println(count+++"FIRST");

//开始时from到所有都是最大值。

//找到标记了的节点

//找标记了的节点邻接的未标记的节点。

//得到最短的边，并标记。

//更新现有路径

double min = MAX;

int address = -1;

int father = -1;

for(int i = 0 ; i changdu ; i++){//对于已经找到的顶点寻找最小的往后的距离。

if(found[i]){//找到了的。

Jiao temp = vertex[i];

while(temp!=null){//vertex的邻接顶点~~

//先看temp的号码~

int tempNumber = -1;

for(int j = 0 ; j changdu ; j++){

if(vertex[j].name.equals(temp.name)){

tempNumber = j;

break;

}

}

if(!found[tempNumber]){//如果是还没有找到的~

double dist = distance[i]+temp.edge;

if(dist min){

min = dist;

father = i;

//System.out.println(" "+min);

address = tempNumber;

}

}

temp = temp.next;

}

}

}found[address] = true;

distance[address] = min;

//添加到已有路径中去！

//知道father

for(int i = 0 ; i degree ; i++){

if(list[i].isEmpty()||list[i].getLast().equals(vertex[father].name)){

list[i].addLast(vertex[address].name);

break;

}

}

}

for(int i = 0 ; i degree ; i++){

if(list[i].isEmpty())

continue;

else{

if(list[i].getLast().equals(v2)){

gap=0;

//先求出gap

Jiao pre = from;

Jiao nex = null;

for(int j = 0 ; j list[i].size() ; j++){

for(int k = 0 ; k changdu ; k++){

if(vertex[k].name.equals(list[i].get(j))){

nex = vertex[k];break;

}

}

while(pre.next!=null){//找到下一个的长度

pre = pre.next;

//System.out.println(nex.name +"nex.name");

if(pre.name.equals(nex.name)){

gap+=pre.edge;

//System.out.println(" gap2 "+gap);

}

}

pre = nex;

}

//System.out.println(gap+"gap");

return list[i];

}

}

}

return null;

}

public void showGraph(){

Jiao temp;

for(int i = 0 ; i changdu ; i++){

temp = vertex[i];

while(temp!=null){

System.out.print(temp.name+temp.edge+" ");

temp = temp.next;

}System.out.println();

}System.out.println("Show Over!");

}

}

public class Jiao{

public String name;

public Jiao next = null;

public double edge;

public Jiao(String name){

this.name = name;

}

}

}

******

import java.awt.EventQueue;

import java.awt.event.ActionEvent;

import java.awt.event.ActionListener;

import java.util.LinkedList;

import javax.swing.JButton;

import javax.swing.DefaultListModel;

import javax.swing.JFrame;

import javax.swing.JLabel;

import javax.swing.JList;

import javax.swing.JOptionPane;

import javax.swing.JScrollPane;

import javax.swing.JSeparator;

import javax.swing.JTextField;

import javax.swing.SwingConstants;

public class UI extends JFrame implements ActionListener{

private JTextField textField_5;

private JTextField textField_4;

private JList list_1;

private JList list;

private JTextField textField_1;

private JTextField textField_3;

private JTextField textField_2;

private JTextField textField;

private DefaultListModel model = new DefaultListModel();

private DefaultListModel model_1 = new DefaultListModel();

/**

* Launch the application

* @param args

*/

public static void main(String args[]) {

EventQueue.invokeLater(new Runnable() {

public void run() {

try {

UI frame = new UI();

frame.setVisible(true);

} catch (Exception e) {

e.printStackTrace();

}

}

});

}

/**

* Create the frame

*/

public UI() {

super();

setTitle("GPS寻路");

getContentPane().setLayout(null);

setBounds(100, 100, 500, 375);

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

final JScrollPane scrollPane = new JScrollPane();

scrollPane.setBounds(11, 36, 221, 193);

getContentPane().add(scrollPane);

list = new JList(model);

scrollPane.setViewportView(list);

final JScrollPane scrollPane_1 = new JScrollPane();

scrollPane_1.setBounds(253, 36, 218, 193);

getContentPane().add(scrollPane_1);

list_1 = new JList(model_1);

scrollPane_1.setViewportView(list_1);

final JLabel label = new JLabel();

label.setText("从");

label.setBounds(10, 249, 24, 18);

getContentPane().add(label);

final JLabel label_1 = new JLabel();

label_1.setText("到");

label_1.setBounds(11, 273, 24, 18);

getContentPane().add(label_1);

textField = new JTextField();

textField.setBounds(50, 247, 103, 22);

getContentPane().add(textField);

textField_2 = new JTextField();

textField_2.setBounds(50, 271, 103, 22);

getContentPane().add(textField_2);

final JLabel label_2 = new JLabel();

label_2.setText("距离");

label_2.setBounds(11, 297, 37, 18);

getContentPane().add(label_2);

textField_3 = new JTextField();

textField_3.setBounds(50, 295, 103, 22);

getContentPane().add(textField_3);

final JButton button = new JButton();

button.setText("添加");

button.setBounds(155, 250, 73, 28);

getContentPane().add(button);

final JButton button_1 = new JButton();

button_1.setText("删除");

button_1.setBounds(155, 285, 73, 28);

getContentPane().add(button_1);

final JLabel label_3 = new JLabel();

label_3.setText("距离：");

label_3.setBounds(253, 297, 39, 18);

getContentPane().add(label_3);

textField_1 = new JTextField();

textField_1.setBounds(293, 295, 86, 22);

getContentPane().add(textField_1);

final JButton button_2 = new JButton();

button_2.setText("显示路径");

button_2.setBounds(385, 249, 86, 68);

getContentPane().add(button_2);

final JLabel label_4 = new JLabel();

label_4.setText("路径表示");

label_4.setBounds(11, 10, 66, 18);

getContentPane().add(label_4);

final JLabel label_5 = new JLabel();

label_5.setText("最佳路径");

label_5.setBounds(253, 12, 66, 18);

getContentPane().add(label_5);

//

button.addActionListener(this);

button_1.addActionListener(this);

button_2.addActionListener(this);

final JLabel label_6 = new JLabel();

label_6.setText("从");

label_6.setBounds(253, 249, 24, 18);

getContentPane().add(label_6);

textField_4 = new JTextField();

textField_4.setBounds(293, 247, 86, 22);

getContentPane().add(textField_4);

final JLabel label_7 = new JLabel();

label_7.setText("到");

label_7.setBounds(253, 273, 24, 18);

getContentPane().add(label_7);

textField_5 = new JTextField();

textField_5.setBounds(293, 271, 86, 22);

getContentPane().add(textField_5);

final JSeparator separator = new JSeparator();

separator.setOrientation(SwingConstants.VERTICAL);

separator.setBounds(239, 10, 8, 317);

getContentPane().add(separator);

}

@Override

public void actionPerformed(ActionEvent e) {

// TODO Auto-generated method stub

if(e.getActionCommand().equals("添加")){

try{String from = textField.getText();

String to = textField_2.getText();

if(from.equals(to)){

JOptionPane.showMessageDialog(null, "始点与终点不能相同");

return;

}

if(from.equals("")||to.equals("")){

JOptionPane.showMessageDialog(null, "添加不能为空");

return;

}for(int i = 0 ; i model.size() ; i ++){

if(model.get(i).toString().substring(0, model.get(i).toString().indexOf(":")).equals(

from+"-"+to))

model.remove(i);

}

double length = Double.parseDouble(textField_3.getText());

model.addElement(from+"-"+to+": "+length);

}catch(Exception e1){

JOptionPane.showMessageDialog(null, "距离为数字值");

}

}

if(e.getActionCommand().equals("删除")){

for(int i = 0 ; i model.size() ; i++){

if(list.isSelectedIndex(i))

model.remove(i);

}

}

if(e.getActionCommand().equals("显示路径")){

try{

model_1.removeAllElements();

GPS gps = new GPS();

String full,from,to;

double length;

for(int i = 0 ; i model.size() ; i++){

full = model.get(i).toString();

from = full.substring(0,full.indexOf("-"));

to = full.substring(full.indexOf("-")+2,full.lastIndexOf(":"));

length = Double.parseDouble(full.substring(full.indexOf(":")+1, full.length()-1));

//System.out.println(from);

//System.out.println(to);

try {

gps.graph.addEdge(from, to, length);

System.out.println(from +" "+ to);

} catch (CircuitException e1) {

System.out.println("有环存在");

}

}LinkedList list = gps.graph.getPath(textField_4.getText(), textField_5.getText());

model_1.addElement(textField_4.getText());

for(int i = 0 ; i list.size() ; i++){

model_1.addElement(list.get(i));

}//计算路径长度

textField_1.setText(""+gps.graph.gap);

}catch(Exception e1){

JOptionPane.showMessageDialog(null, "没有找到有关节点");

}

}

}

}

用java编写 深度优先法 寻路时 怎么实现八个方向的路径选择

//循环遍历八个方向：

for(int dx = -1; dx = 1; dx++) {

for(int dy = -1; dy = 1; dy++) {

//向x方向移动dx,向y方向移动dy

int nx = x+dx, ny = y + dy;

if()//这里是你要查找的满足条件的元素

}

}

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寻路代码 java迷宫寻路
网页地址：http://scyanting.com/article/dodcsei.html