python实现的生成随机迷宫算法核心代码分享(含游戏完整代码),python迷宫
python实现的生成随机迷宫算法核心代码分享(含游戏完整代码),python迷宫
完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar
最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏。游戏地址和对应的开源项目地址可以通过上面的链接找到。开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了。下面将简单的介绍下随机迷宫的生成算法。一旦理解后你会发现这个算法到底有多简单。
1.将迷宫地图分成多个房间,每个房间都有四面墙。
2.让“人”从地图任意一点A出发,开始在迷宫里游荡。从A房间的1/2/3/4个方向中的任选一个方向前进。在从A房间走到B房间的过程中,推倒A/B房间之间的墙。
3.如果方向x对面的房间已经走过,则选择其他方向。如果所有方向的房间都已经走过,则退回上一个房间看是否还有可选道路。
4.走到真正无路可走时,说明已经走过了所有房间,迷宫也生成好了。
下面是该算法的python实现(核心部分)
def gen_map(self, max_x=10, max_y=10): """ 生成迷宫 """ self.max_x, self.max_y = max_x, max_y # 设置地图大小 self.mmap = [[None for j in range(self.max_y)] for i in range(self.max_x)] # 生成原始地图 self.solution = [] # 迷宫解法 block_stack = [Block(self, 0, 0)] # 从0,0开始生成迷宫(同时将这点作为起点),将起点放到栈里 while block_stack: block = block_stack.pop() #取出当前所在的房间 next_block = block.get_next_block() # 获取下一个要去的房间 if next_block: # 如果成功获取下一走发,将走过的房间放回到栈里 block_stack.append(block) block_stack.append(next_block) if next_block.x == self.max_x - 1 and next_block.y == self.max_y - 1: # 走到终点了,栈里的路径就是解法 for o in block_stack: self.solution.append((o.x, o.y)) def get_next_block_pos(self, direction): """ 获取指定方向的房间号 """ x = self.x y = self.y if direction == 0: # Top y -= 1 elif direction == 1: # Right x += 1 if direction == 2: # Bottom y += 1 if direction == 3: # Left x -= 1 return x, y def get_next_block(self): """ 获取下一要去的房间 """ directions = list(range(4)) random.shuffle(directions) # 随机获取一个要去的方向 for direction in directions: x, y = self.get_next_block_pos(direction) if x >= self.mmap.max_x or x < 0 or y >= self.mmap.max_y or y < 0: # 房间号在许可范围内 continue if self.mmap.mmap[x][y]: # 如果已经走过 continue self.walls[direction] = False return Block(self.mmap, x, y, direction) return None # 没找到有可用的房间
注: 由于采用该方法生成的迷宫道路的分支数量并不是太多,coffeescript版在生成迷宫的过程中增加了随机处理,对应算法也稍微复杂一点点。
图的遍历有深度遍历算法和广度遍历算法,最近阿杰做了关于图的遍历的算法,下面是图的遍历深度优先的算法(C语言程序): #include<stdio.h> #include<w
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
/* define the size of maze */
#define MAX_COL 6
#define MAX_ROW 6
#define TRUE 1
#define FALSE 0
#define IS_USABLE(a, b) (a >= 0 && a < MAX_ROW) && (b >= 0 && b < MAX_COL) && maze[a][b] && (!my_maze[a][b])
static int maze[MAX_ROW][MAX_COL];
static int target_maze[MAX_ROW][MAX_COL];
static void init_maze();
static int move_to(int i, int j, int (*maze)[MAX_COL], int count);
static void print_maze(int (*maze)[MAX_COL]);
static void init_maze()
{
int i, j;
srand((unsigned) time(NULL));
for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
maze[i][j] = (int) (rand() % 2);
}
maze[1][0] = 1; /* start point */
maze[MAX_ROW - 1][MAX_COL - 2] = 1; /* end point */
}
static int move_to(int _i,int _j, int (*in_maze)[MAX_COL], int count) {
int my_maze[MAX_ROW][MAX_COL], i, j;
if (!in_maze) {
for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
my_maze[i][j] = 0;
}
} else {
for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
my_maze[i][j] = in_maze[i][j];
}
}
my_maze[_i][_j] = count;
/* reach the end point */
if (_i == MAX_ROW - 1 && _j == MAX_COL - 2) {
for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
target_maze[i][j] = my_maze[i][j];
}
return TRUE;
}
if (IS_USABLE(_i - 1, _j)) {
if (move_to(_i - 1, _j, my_maze, cou......余下全文>>
相关内容
- Python编写检测数据库SA用户的方法,python编写数据库s
- Python文件操作类操作实例详解,
- 使用nodejs、Python写的一个简易HTTP静态文件服务器,
- Python文件夹与文件的操作实现代码,
- 用python + openpyxl处理excel2007文档思路以及心得,
- 用python + hadoop streaming 分布式编程(一) -- 原理介绍,
- python re正则表达式模块(Regular Expression),pythonregular
- Python实现扫描指定目录下的子目录及文件的方法,
- Python重新引入被覆盖的自带function,python自带function
- Python实现动态添加类的属性或成员函数的解决方法,
评论关闭