java – 深度优先搜索 – 2D游戏地图
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – 深度优先搜索 – 2D游戏地图，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5007字，纯文字阅读大概需要8分钟。
内容图文
我创建了一个2D迷宫,我想找到红色和蓝色的节点之间最快的路径.我不确定如何实施深度优先搜索.我知道可以使用邻接矩阵或列表来表示节点之间的连接.虽然,我不确定如何构建它.
为简洁起见：我需要返回一个列表,其中搜索了瓷砖坐标(当寻找目标节点时),因此我可以在迷宫上描绘搜索.或者我将如何为此构建一个邻接矩阵？和相应的顶点列表？
深度首先搜索一般结构
>访问节点(单元格)(将访问标志更改为true)
>推送到堆栈
>如果没有(pop stack),则获取未访问的顶点(peek stack) – 更新迷宫模型视图
重复1 – 3直到堆栈为空
这是迷宫类的当前代码.
public class Maze {
//Tile ids
public static short OBSTICLE = 0;
public static short START_LOC_VALUE = -2;
public static short GOAL_LOC_VALUE = -3;
private int rows, cols;
private int numTiles;
private int[][] map;
private int[][] adjMatrix;
private Queue theQueue;
public Maze(int rows, int cols){
this.rows = rows;
this.cols = cols;
theQueue = new Queue();
numTiles = rows*cols;
map = new int[rows][cols];
adjMatrix = new int[rows][cols];
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
map[i][j] = 1;
}
}
}
/*
* Generate Maze
* @param numObstacles - number of obstacles
*/
public void generateMaze(int numObstacles){
for (int i = 0; i < numObstacles; i++)
setTile((int)(Math.random()*rows),(int)(Math.random()*cols), Maze.OBSTICLE);
//setTile((int)(Math.random()*rows),(int)(Math.random()*cols),Maze.START_LOC_VALUE);
//setTile((int)(Math.random()*rows),(int)(Math.random()*cols),Maze.GOAL_LOC_VALUE);
createAdjMatrix();
}
public void createAdjMatrix(){
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
if (map[i][j] == 1) {
addEdge(i,j);
}
}
}
}
/*
* Set Tile
* @param x - x cord
* @param y - y cord
* @param entity - OBSTICLE,START_LOC_VALUE or GOAL_LOC_VALUE ID
*/
public void setTile(int x, int y, short entity){
this.map[x][y] = entity;
}
public void addEdge(int start, int end) {//Start and end arguments index multidimensional array
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
public void bfs(int startDest, int goalDest) // breadth-first search
{
// begin at vertex 0
vertexList[startDest].wasVisited = true; // mark it
displayVertex(startDest); // display it
theQueue.enQueue(startDest); // insert at tail
int v2;
while (!theQueue.isEmpty()) // until queue empty,
{
int v1 = theQueue.deQueue(); // remove vertex at head
// until it has no unvisited neighbors
while ((v2 = getAdjUnvisitedVertex(v1)) != -1)
{ // get one,
vertexList[v2].wasVisited = true; // mark it
displayVertex(v2); // display it
theQueue.enQueue(v2); // insert it
} // end while(unvisited neighbors)
} // end while(queue not empty)
// queue is empty, so we’re done
for (int j = 0; j < nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
}// end bfs()
/*
* Drawn Maze
* @param g - Graphics object
*/
public void draw(Graphics g){
for (int y = 0; y < cols; y++)
for (int x = 0; x < rows; x++) {
int val = map[x][y];
if (val==Maze.OBSTICLE) {
g.setColor(Color.BLACK);
g.fillRect(x*20, y*20, 20, 20);
}else if(val == Maze.START_LOC_VALUE){
g.setColor(Color.RED);
g.fillRect(x*20, y*20, 20, 20);
}else if(val==Maze.GOAL_LOC_VALUE){
g.setColor(Color.BLUE);
g.fillRect(x*20, y*20, 20, 20);
}else{
g.setColor(Color.BLACK);
g.drawRect(x*20, y*20, 20, 20);
}
}
}
}
目前的DFS代码..
public void dfs(int vertexStart) // depth-first search
{
// begin at vertexStart
vertexList[vertexStart].wasVisited = true; // mark it
displayVertex(vertexStart); // display it
theStack.push(vertexStart); // push it
while (!theStack.isEmpty()) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1) // if no such vertex,
theStack.pop(); // pop a new one
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while
}
以下图片描绘了迷宫结构,它是伪随机生成的;最终的迷宫实施将得到完善.
谢谢,如果你能引导我朝着正确的方向前进,我将会非常满意……
解决方法:
对于2D迷宫,您可以简单地使用Breadth First Search而不是深度优先搜索,如果您有n * n迷宫,它将在O(n2)中找到它.
但还有另一种选择,即标签和BFS,可以在您的迷宫上运行(无需图表).
编号算法
了解广度优先搜索的一种有趣方法是以这种方式(对于迷宫)：
>将所有单元格设置为0,并将块设置为-1
>从源位置开始将其设置为1,将其全部标记为0
邻居为2,并将所有2个保存在列表中.在那之后全部为0
2到3的邻居,2的清单和3的保存列表然后去
到达目的地.在每个级别只是不改变
来源价值.
>现在假设你在目的地,你想找到路径,你的
目的地得分m,找到分数为m-1的邻居,….并输出路径.
事实上,BFS的正常和简单方式是使用Q,但我提供了它的简单性,因为它模拟Q方式.
使用邻接矩阵
为了创建邻接矩阵,你应该有命名节点和边,所以你可以为边和节点创建如下所示的类(我用伪C#编写)：
public class Edge
{
public Edge(Node start, Node end, decimal weight)
{
StartNode = ...,...,...
}
public Node StartNode;
public Node EndNode;
public decimal weight;
public bool IsDirected;
}
public class Node
{
public Node(int index)
{
this.Index = index;
}
public int Index;
public List<Edge> Edges = new List<Edge>();
public bool Visited = false;
}
现在您的图表是Node对象的列表：
public class Graph
{
public List<Node> Nodes = new List<Node>();
}
对于Maze的建模,您应该选择单元格作为节点,并在相邻单元格之间绘制边缘.
我会告诉你如何在你的图表中添加节点.
内容总结
以上是互联网集市为您收集整理的java – 深度优先搜索 – 2D游戏地图全部内容，希望文章能够帮你解决java – 深度优先搜索 – 2D游戏地图所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。