Python深度优先算法生成迷宫

本文实例为大家分享了Python深度优先算法生成迷宫，供大家参考，具体内容如下

import random 

#warning: x and y confusing 

sx = 10
sy = 10
dfs = [[0 for col in range(sx)] for row in range(sy)]
maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)]
#1:up 2:down 3:left 4:right
operation = {1:(0,-1),2:(0,1),3:(-1,0),4:(1,0)}
direction = [1, 2, 3, 4]
stack = [] 

for i in range(2*sx+1):
 if i%2 == 0:
  for j in range(2*sx+1):
   maze[i][j] = '#'
for i in range(2*sy+1):
 if i%2 == 0:
  for j in range(2*sy+1):
   maze[j][i] = '#' 

def show(graph):
 for i in graph:
  for j in i:
   print j,
  print 

def showRouter(stack):
 RGragh = [[0 for col in range(sx)] for row in range(sy)]
 for (x, y) in stack:
  RGragh[y][x] = 1
 show(RGragh)
 print 

def generateMaze(start):
 x, y = start
 dfs[y][x] = 1
 random.shuffle(direction)
 for d in direction:
  px, py = (x + y for x, y in zip(start, operation[d]))
  if px < 0 or px >= sx or py < 0 or py >= sy:
   pass
  else:
   if dfs[py][px] is not 1:
    mx = 2*x + 1
    my = 2*y + 1
    if d == 1:
     maze[my-1][mx] = ' '
    elif d == 2:
     maze[my+1][mx] = ' '
    elif d == 3:
     maze[my][mx-1] = ' '
    elif d == 4:
     maze[my][mx+1] = ' '
    generateMaze((px,py)) 

generateMaze((0,0))
show(dfs)
show(maze)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

您可能感兴趣的文章:

  • Python使用Tkinter实现机器人走迷宫
  • Python基于分水岭算法解决走迷宫游戏示例
  • Python使用回溯法子集树模板解决迷宫问题示例
  • Python基于递归算法实现的走迷宫问题
  • 用Python代码来解图片迷宫的方法整理
  • python实现的生成随机迷宫算法核心代码分享（含游戏完整代码）
  • 一道python走迷宫算法题
赞 (0)

相关推荐

  • python实现的生成随机迷宫算法核心代码分享（含游戏完整代码）

    完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar 最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏.游戏地址和对应的开源项目地址可以通过上面的链接找到.开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了.下面将简单的介绍下随机迷宫的生成算法.一旦理解后你会发现这个算法到底有多简单. 1.将迷宫地图分成多个房间,每个房间都有四面墙. 2.让"人"从地图任意一点A出发,开始在迷宫里游荡.从A房间的1/

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • 一道python走迷宫算法题

    一道python走迷宫算法题

    前几天逛博客时看到了这样一道问题,感觉比较有趣,就自己思考了下方案顺便用python实现了一下.题目如下: 用一个二维数组表示一个简单的迷宫,用0表示通路,用1表示阻断,老鼠在每个点上可以移动相邻的东南西北四个点,设计一个算法,模拟老鼠走迷宫,找到从入口到出口的一条路径. 如图所示: 先说下我的思路吧: 1.首先用一个列表source存储迷宫图,一个列表route_stack存储路线图,一个列表route_history存储走过的点,起点(0,0),终点(4,4). 2.老鼠在每个点都有上下左右

  • 用Python代码来解图片迷宫的方法整理

    用Python代码来解图片迷宫的方法整理

    译注:原文是StackOverflow上一个如何用程序读取迷宫图片并求解的问题,几位参与者热烈地讨论并给出了自己的代码,涉及到用Python对图片的处理以及广度优先(BFS)算法等. 问题by Whymarrh: 当给定上面那样一张JPEG图片,如何才能更好地将这张图转换为合适的数据结构并且解出这个迷宫? 我的第一直觉是将这张图按像素逐个读入,并存储在一个包含布尔类型元素的列表或数组中,其中True代表白色像素,False代表非白色像素(或彩色可以被处理成二值图像).但是这种做法存在一个问题,那

  • Python基于分水岭算法解决走迷宫游戏示例

    本文实例讲述了Python基于分水岭算法解决走迷宫游戏.分享给大家供大家参考,具体如下: #Solving maze with morphological transformation """ usage:Solving maze with morphological transformation needed module:cv2/numpy/sys ref: 1.http://www.mazegenerator.net/ 2.http://blog.leanote.com

  • Python使用回溯法子集树模板解决迷宫问题示例

    Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • Python使用Tkinter实现机器人走迷宫

    Python使用Tkinter实现机器人走迷宫

    这本是课程的一个作业研究搜索算法,当时研究了一下Tkinter,然后写了个很简单的机器人走迷宫的界面,并且使用了各种搜索算法来进行搜索,如下图: 使用A*寻找最优路径: 由于时间关系,不分析了,我自己贴代码吧.希望对一些也要用Tkinter的人有帮助. from Tkinter import * from random import * import time import numpy as np import util class Directions: NORTH = 'North' SOU

  • Python深度优先算法生成迷宫

    本文实例为大家分享了Python深度优先算法生成迷宫,供大家参考,具体内容如下 import random #warning: x and y confusing sx = 10 sy = 10 dfs = [[0 for col in range(sx)] for row in range(sy)] maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)] #1:up 2:down 3:left 4:right opera

  • Python实现随机生成迷宫并自动寻路

    Python实现随机生成迷宫并自动寻路

    Python深搜版: 核心在于带随机的深搜(见代码第23到27行,其实也可以用22行代替这几行代码,你可以试着把第24行的数字4改大或者改小,即调整随机程度) import os import random from queue import Queue import numpy import colorama from colorama import Fore, Back, Style import sys from bmpEditor import bmp colorama.init() #

  • 10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径

    10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径

    深度优先算法(DFS 算法)是什么? 寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径.主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且不能通过障碍节点.如果走到某个节点发现无路可走,那么就会回退到上一个节点,重新选择其他路径.直到找到出口,或者退到起点再也无路可走,游戏结束.当然,深度优先算法,只要查找到一条行得通的路径,就会停止搜索:也就是说只要有路可走,深度优先算法就不会回退到上一步. 如果你依然在编程的世界里迷茫,可以加入我们的Python学

  • java图的深度优先遍历实现随机生成迷宫

    java图的深度优先遍历实现随机生成迷宫

    最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢. 1.从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中的随机一个访问(每访问到一个可访问的点,就去掉该点的那个方向的墙),被访问点继续以这种方识向下进行访问. 2.对每个被访问的点都被标识为已访问,当一个点对某个方向进行访问时我们首先会判断被访问点是否已被访问,或者触到边界.如果该点四个方向皆已访

  • php实现的生成迷宫与迷宫寻址算法完整实例

    php实现的生成迷宫与迷宫寻址算法完整实例

    本文实例讲述了php实现的生成迷宫与迷宫寻址算法.分享给大家供大家参考,具体如下: 较之前的终于有所改善.生成迷宫的算法和寻址算法其实是一样.只是一个用了遍历一个用了递归.参考了网上的Mike Gold的算法. <?php header('Content-Type: text/html; charset=utf-8'); error_reporting(E_ALL); //n宫格迷宫 define('M', 39);//宫数 define("S", 20);//迷宫格大小 $_p

  • PHP树的深度编历生成迷宫及A*自动寻路算法实例分析

    本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法.分享给大家供大家参考.具体分析如下: 有一同事推荐了三思的迷宫算法,看了感觉还不错,就转成php 三思的迷宫算法是采用树的深度遍历原理,这样生成的迷宫相当的细,而且死胡同数量相对较少! 任意两点之间都存在唯一的一条通路. 至于A*寻路算法是最大众化的一全自动寻路算法 废话不多说,贴上带代码 迷宫生成类: 复制代码 代码如下: class Maze{     // Maze Create     private $_w;     priv

  • python使用ProjectQ生成量子算法指令集

    输出算法操作 首先介绍一个最基本的使用方法,就是使用ProjectQ来打印量子算法中所输入的量子门操作,这里使用到了ProjectQ中的DummyEngine后端用于保存操作的指令.比如最简单的一个Bell State的制备,可以通过如下代码实现,并且打印出所保存的基本操作: from projectq import MainEngine from projectq.cengines import DummyEngine from projectq.ops import H, CX, All,

  • Python编程实现生成特定范围内不重复多个随机数的2种方法

    Python编程实现生成特定范围内不重复多个随机数的2种方法

    本文实例讲述了Python编程实现生成特定范围内不重复多个随机数的2种方法.分享给大家供大家参考,具体如下: 在近期进行的一个实验中,需要将数据按一定比例随机分割为两个部分.这一问题的核心其实就是产生不重复随机数的问题.首先想到的递归的方法,然后才发现Python中居然已经提供了此方法的函数,可以直接使用.具体代码如下: #生成某区间内不重复的N个随机数的方法 import random; #1.利用递归生成 resultList=[];#用于存放结果的List A=1; #最小随机数 B=10

  • Python实现随机生成有效手机号码及身份证功能示例

    Python实现随机生成有效手机号码及身份证功能示例

    本文实例讲述了Python实现随机生成有效手机号码及身份证功能.分享给大家供大家参考,具体如下: 中国那么大,人那么多,几乎人手一部手机.手机号码已经作为各大互联网站的注册账户.同样,身份证更是如此.以下是生成有效手机号码和身份证号. 身份证需要下载districtcode.txt文件. 完整代码如下: import os import random import datetime BASE_DIR = os.path.dirname(os.path.dirname(__file__)) DC_

随机推荐