How to Build a Maze 隨機迷宮生成

http://www.mazeworks.com/mazegen/mazetut/

It's easier than you think.  Our objective here is to create a perfect maze, the simplest type of maze for a computer to generate and solve. A perfect maze is defined as a maze which has one and only one path from any point in the maze to any other point. This means that the maze has no inaccessible sections, no circular paths, no open areas.  We'll assume a rectangular maze, since that's the easiest type to create, but with the method presented here, we can create mazes of almost any shape and size, even 3-dimensional ones. To begin with, we'll need a grid:  Each square of the grid is a cell. The horizontal and vertical lines represent the walls of the maze. The generation algorithm we're using will assume that, at the beginning, all the walls of the maze are up. Then we selectively knock down walls until we've made a working maze that fits our definition of "perfect." We'll need a data structure to store information about the cells. But exactly what data should we be tracking? Assuming that we're interested in solving the maze as well as creating it, here's a graphical representation of all the information necessary:  The maze borders are gray, the walls are white, the starting position is green, the ending position is red, the solution path is yellow, and the backtrack path is light gray. The start and end points can easily be stored as individual variables. Then all we need to track, for each cell in the grid, are:  Any borders the cell has Which walls are still up If the solution path goes through it, and in which directions If the backtrack path goes through it, and in which directions Here's one way to do it (this is by no means the only way): a 12x16 maze grid can be represented as an array m[16][12] of 16-bit integers. Each array element would contains all the information for a single corresponding cell in the grid, with the integer bits mapped like this:  To knock down a wall, set a border, or create a particular path, all we need to do is flip bits in one or two array elements. You might think we don't really need to track the borders, since we could just use the minimum and maximum array indices to determine them. That's true, but storing border information in the array makes our maze much more flexible. It means we can easily change the shape of the maze in various ways and still be able to use our 2D array and maze generating algorithm without any code modification.    With a data structure in place for holding the maze information, we can initialize the maze by setting the appropriate borders and putting up all of the walls. Then we're ready to implement the algorithm.    Depth-First Search    This is the simplest maze generation algorithm. It works like this:  1) Start at a random cell in the grid.  2) Look for a random neighbor cell you haven't been to yet.  3) If you find one, move there, knocking down the wall between the cells. If you don't find one, back up to the previous cell.  4) Repeat steps 2 and 3 until you've been to every cell in the grid. Here's the DFS algorithm written as pseudocode:

create a CellStack (LIFO) to hold a list of cell locations  set TotalCells = number of cells in grid  choose a cell at random and call it CurrentCell  set VisitedCells = 1     while VisitedCells < TotalCells  find all neighbors of CurrentCell with all walls intact   if one or more found  choose one at random  knock down the wall between it and CurrentCell  push CurrentCell location on the CellStack  make the new cell CurrentCell  add 1 to VisitedCells else  pop the most recent cell entry off the CellStack  make it CurrentCell endIf endWhile

When the while loop terminates, the algorithm is completed. Every cell has been visited and thus no cell is inaccessible. Also, since we test each possible move to see if we've already been there, the algorithm prevents the creation of any open areas, or paths that circle back on themselves. We can put the start and end points wherever we want. This is another advantage of a perfect maze. Since, by definition, one and only one path will exist between any two points in the maze, we know that given a start/end pair, a unique solution to the maze must exist.  Depth-First Search is the most common algorithm used in maze generation programs: it's simple to implement, works quickly, and generates very pretty mazes. The algorithm can also be used to solve mazes. This is how MazeGen generates solutions for all mazes, no matter which algorithm was used to create them.

隨機迷宮說明文件

http://blog.yam.com/yuhaolin/article/196486
http://wenku.baidu.com/view/fd32d32758fb770bf78a557a.html

迷宮程式可以區分為兩種，第一種就是固定式的，也就是在程式一開始前，迷宮已經內建好；而第二種也就是我們所採用的隨機迷宮的產生。 
原本迷宮的產生是傾向先產生多個內建迷宮，然後交替變換來達到隨機迷宮的效果，但畢竟還是不能算隨機產生，而且不切實際。因此最後決定直接產生隨機迷宮。
隨機迷宮的產生方法有很多種，我們所採用的是在圖學常用的演算法，深度優先搜尋(Depth-First Search, DFS)。利用DFS所產生的地圖相較於其它的方法會細緻許多(上圖為實作結果)，且有以下的特色：
1. 任兩個節點皆有路徑到達。
2. 沒有Circular Paths的產生。
由於任兩個節點之間，絕對會有路徑且唯一，因此這個迷宮的優點之一，也就是我們可以任取兩點來當作出口和入口。而沒有Circular Paths產生的好處是可以有效的避免設計不當的走迷宮程式，陷入一個無窮止盡的迴路裡，永遠走不出去。
隨機迷宮產生的主要演算法如下：
1. 將所有的節點都建立四面牆(東、西、南、北四個方向)。
2. 從任意一個節點出發。
3. 隨機選取一個未拜訪過的鄰近節點。
4. 若找到，則將彼此相隔的牆給打掉。若找不到則回去之前的節點。
5. 重覆3、4步驟，直到全部節點都拜訪過即結束。
這個演算法最重要的部分就是在找尋鄰近沒被拜訪過的節點，而這也是為何會產生隨機迷宮的地方，當節點有多個未拜訪的鄰近節點，利用隨機的方式，隨便挑選一個來拜訪，自然每次執行的時候，迷宮皆會不一樣。
而由於LCD尺寸大小的限制，迫使我們把迷宮大小縮成15*15，但我們卻發現一個問題，那就是產生的隨機迷宮，複雜程度不如大迷宮的效果，後來我們就找到解決的方法，那就是原本步驟二任選一個節點出發，我們預設都是在入口處開始，現在我們改成從迷宮的中間點開始出發拜訪，產生的隨機迷宮明顯改善許多，才不至於每次一下子就走出迷宮了。最後我們所完成的隨機迷宮產生的程式，註明只能產生奇數乘奇數的迷宮，其實只是因為我們將每道牆都一起算進去，所以實際上，任何大小都是可以的。
Depth-First Search是很常被用來產生迷宮的演算法，因為實作相當容易且產生出的迷宮具有一定的複雜度，相較其它演算法有一定的優勢，且每個節點皆有唯一路徑到達，沒有Circular Paths的產生，對於我們寫走迷宮的程式大大的有幫助，所以我們也就選擇利用DFS來完成此迷宮。而DFS的好處不只在可以用來產生迷宮，同時也可以用來解決走迷宮的方法，可以說是相當好用。 

【Cocos2d-x】打印指定目录下所有文件

http://koyoter.blog.51cto.com/6156214/1203134

原创作品，允许转载，转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。http://koyoter.blog.51cto.com/6156214/1203134

无聊的时候写写代码,哇咔咔.以下是一个cocos2d-x打印指定目录下的所有文件.(跨平台的呦，C++初学者,代码污染请勿喷)...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

void HelloWorld::FindAllFile(string folderPath) {     // Window处理方式 #if (CC_TARGET_PLATFORM == CC_PLATFORM_WIN32)     _finddata_t FileInfo;     string strfind = folderPath + "\\*";     long Handle = _findfirst(strfind.c_str(), &FileInfo);     if (Handle == -1L)     {         CCLog("can not match the folder path");         return;     }     do{         //判断是否有子目录         if (FileInfo.attrib & _A_SUBDIR)           {             //这个语句很重要             if( (strcmp(FileInfo.name,".") != 0 ) &&(strcmp(FileInfo.name,"..") != 0))              {                 string newPath = folderPath + "\\" + FileInfo.name;                 FindAllFile(newPath);             }         }         else         {             count++;             CCLog("%s\\%s" , folderPath.c_str() , FileInfo.name);         }     }while (_findnext(Handle, &FileInfo) == 0);     _findclose(Handle); #else     CCLog(folderPath.c_str());     DIR *dp;     struct dirent* dirp;     if((dp = opendir(folderPath.c_str())) == NULL)     {         CCLog("can not match the folder path");         return;     }     while ((dirp=readdir(dp))!=NULL)     {         struct stat buf;         stat(folderPath.c_str(), &buf);         // 如果是目录         if (S_ISDIR(buf.st_mode))         {                 string path;                 if( (strcmp(dirp->d_name,".") != 0 ) &&(strcmp(dirp->d_name,"..") != 0))                  {                     path =  folderPath + "/" + dirp->d_name;                 }                 //如果是目录，递归调用                 FindAllFile(path);          }         else         {             // 如果是文件直接打印             CCLog("%s/%s\n",folderPath.c_str(),dirp->d_name);         }     }     CCLog("\n");     closedir(dp); #endif }

记得在#include处添加如下代码:

1 2 3 4 5 6

#if (CC_TARGET_PLATFORM != CC_PLATFORM_WIN32)     #include <dirent.h>     #include <sys/stat.h> #else     #include <io.h> #endif

更多Cocos2d-x开发博文尽在 Koyoter's Blog

原文标题：【Cocos2d-x】打印指定目录下所有文件

原文地址：http://acoder.me/print-the-specified-directory-of-all-documents.html