2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

p1ayer · 发表于 2006-9-19 13:18:00

//File: stdafx.h
#pragma once

#define WIN32_LEAN_AND_MEAN // ? Windows ?祟^排除不常使用的成?T
#include <stdio.h>
#include <tchar.h>

// TODO: 在此?⒖寄?某淌剿?枰?钠渌?祟^
#include <iostream>

#include <string>

//--------------------------------------------------
#include <vector>

template <typename TYPE>
class CArrayT : private std::vector<TYPE>
{
public:
//TODO: (STL) typedef
typedef std::vector<TYPE>::iterator iterator;
typedef std::vector<TYPE> inherited;

protected:
iterator GetIterFromIndex(int uIndex)
     {
     iterator iter = begin();
     iter += uIndex;
     // int t = 0; while (t != uIndex) {iter++;t++;}
     return iter;
     }

public:
//TODO: (STL) Attributes
     int GetCount() const { return size(); }
     int GetSize() const { return size(); }
     int GetUpperBound() const { return (int)(size() - 1); }
     bool IsEmpty() const { return empty(); }
     void SetSize(int nNewSize) { resize(nNewSize); }



//TODO: (STL) Operations
void RemoveAll() { clear(); }
//void FreeExtra() { }

//TODO: (STL) Element Access
TYPE& ElementAt(int nIndex) { return at(nIndex); }
TYPE& ElementAt(int nIndex) const { return at(nIndex); }
TYPE& GetAt(int nIndex ) { return at(nIndex); }
TYPE& GetAt(int nIndex) const { return at(nIndex); }
void SetAt(int nIndex, const TYPE& data) { TYPE& x = at(nIndex); x = data; }
iterator GetData() const { return begin(); }
iterator GetData() { return begin(); }

//TODO: (STL) Growing the Array
int Add(const TYPE& x) { push_back(x); return GetUpperBound(); }
//int Append(const CArrayT<TYPE>& src) { }
//void Copy(const CArrayT<TYPE>& src) { }
//void SetAtGrow( int nIndex, TYPE& newElement) { }

//TODO: (STL) Insertion/Removal
void InsertAt(int uIndex, const TYPE& x) { insert(GetIterFromIndex(uIndex), x); }
void RemoveAt(int uIndex) { erase(GetIterFromIndex(uIndex)); }

//TODO: (STL) Operators
TYPE& operator[](int iIndex) { return inherited:

perator[](iIndex); }
TYPE operator[](int iIndex) const { return inherited::operator[](iIndex); }

//TODO: (STL) Sort
void Sort(bool bAscending)
{
if (bAscending)
std::sort (begin (), end (), std::less<TYPE> ());
else
std::sort (begin (), end (), std::greater<TYPE> ());
}
};

//--------------------------------------------------
#include <map>

template <typename KEY, typename VALUE>
class CMapT : private std::map<KEY, VALUE>
{
public:
//TODO: (STL) Status
int GetCount() const { return size(); }
int GetSize() const { return size(); }
bool IsEmpty() const { return empty(); }

//TODO: (STL) Operations
void SetAt( KEY key, VALUE newValue)
{
insert(std::map<KEY, VALUE>::value_type(key, newValue));
}
bool RemoveKey( KEY key )
{
return erase(key) != 0;
}

bool Lookup( KEY key, VALUE& rValue ) const
{
const_iterator iter = find(key);
if (iter == end())
{
return FALSE;
}
else
{
rValue = iter->second;
return TRUE;
}
}

void RemoveAll() { clear(); }

VALUE& operator[](KEY& key)
{
return std::map<KEY, VALUE>::operator[](key);
}

};

#include <list>

template <typename TYPE>
class CStackT : private std::list<TYPE>
{
public:
//TODO: (STL) typedef
typedef std::list<TYPE>::iterator iterator;
typedef std::list<TYPE>::const_iterator const_iterator;

//TODO: (STL) Status
int GetCount() const { return size(); }
int GetSize() const { return size(); }
bool IsEmpty() const { return empty(); }

//TODO: (STL) Push / Pop
void Push(const TYPE& x) { push_back(x); }
TYPE Pop()// const
{
TYPE ret = back();
std::list<TYPE>::pop_back();
return ret;
}

//TODO: (STL) Peek
iterator Peek() { return IsEmpty() ? end() : back(); }
const_iterator Peek() const { return IsEmpty() ? end() : back(); }

//TODO: (STL) IteratorValid?
bool IteratorValid(const_iterator &iter) const { return (iter != end()); }
bool IteratorValid(iterator &iter) { return (iter != end()); }
};

using namespace std;

p1ayer · 发表于 2006-9-19 13:19:00

// maze2.cpp : 定?主控台??贸淌降倪M入?。
//

#include "stdafx.h"
#include <assert.h>

enum {
UP = 1,
RIGHT = 2,
DOWN = 4,
LEFT = 8,
END =0xFF
};

typedef union _pos_t
{
struct
{
unsigned int x : 16;
unsigned int y : 16;
};
int key;
} pos_t;

typedef struct _node_t
{
struct _node_t* root; //?碓垂??

struct _node_t* node[3]; //??
int index; //??索引

pos_t pos; //??在迷?m的座?

int level; //??Tree的第??
int Passage; //通道
int direction; //方向
} node_t;

typedef CArrayT<string> CStringArrayT;

int width, height;
CStringArrayT MazeData;
CMapT<int, node_t*> mapNode;
CStackT<node_t*> stackNode;

int xt = 0, yt =0, lt =0, st=0;

int LookMaze(int x, int y)
{
//if ((x<=0) || (x>=(width-1)) || (y<=1) || ((y>=height-1)))
if ((x>=(width-1)) || (y>=(height-1)))
{
xt = x;
yt= y;
return END;
}

CStringArrayT& src = MazeData;
int IsPassage = NULL;

if (src[y-1][x] == ' ')
IsPassage |= UP;

if (src[y][x-1] == ' ')
IsPassage |= LEFT;

if (src[y][x+1] == ' ')
IsPassage |= RIGHT;

if (src[y+1][x] == ' ')
IsPassage |= DOWN;

return IsPassage;
}

int GetPassageCount(const int IsPassage)
{
int nCount = 0;
if (IsPassage & UP)
nCount += 1;
if (IsPassage & LEFT)
nCount += 1;
if (IsPassage & RIGHT)
nCount += 1;
if (IsPassage & DOWN)
nCount += 1;
return nCount;
}

node_t* FindNode(node_t* pRoot, int x, int y, int direction)
{
pos_t pt;
pt.x = x;
pt.y = y;

node_t* pNode = mapNode[pt.key];
if (pNode == NULL)
{
assert(pRoot->index >= 0 && pRoot->index <= 3);
pNode = new node_t;

pRoot->node[pRoot->index] = pNode;
pRoot->index++;

pNode->pos.x = x;
pNode->pos.y = y;
pNode->level = pRoot->level + 1;
pNode->root = pRoot;
pNode->node[0] = NULL;
pNode->node[1] = NULL;
pNode->node[2] = NULL;
//pNode->node[3] = NULL;
pNode->index = 0;
pNode-&gt

assage =  LookMaze(x, y);
pNode->direction = direction;

mapNode[pNode->pos.key] = pNode;

if (lt < pNode->level)
lt = pNode->level;
}
else
{
pNode->direction = direction;
}
return pNode;
}

int FindMazePath(node_t* pNode)
{
int x = pNode->pos.x;
int y = pNode->pos.y;
bool bForward = true;

do
{
//switch (pNode->direction)
//{
//case UP: y--; break;
//case RIGHT: x++; break;
//case DOWN: y++; break;
//case LEFT: x--; break;
//}
//st++;

int IsPassage = LookMaze(x, y);
if (IsPassage == END)
{
node_t* pNodeOutput = pNode;
while (pNodeOutput)
{
stackNode.Push(pNodeOutput);
pNodeOutput = pNodeOutput->root;
}

return END;
}

int nCount = GetPassageCount(IsPassage);

switch ( nCount )
{
case 1: //死路
return 0;
case 2: //通道
if (pNode->direction & IsPassage)
{
switch (pNode->direction)
{
case UP: y--; break;
case RIGHT: x++; break;
case DOWN: y++; break;
case LEFT: x--; break;
}
st++;

bForward = true;
break;
}
case 3:
case 4:
if ((IsPassage & UP) && (pNode->direction != DOWN))
FindNode(pNode, x, y-1, UP);
if ((IsPassage & RIGHT) && (pNode->direction != LEFT))
FindNode(pNode, x+1, y, RIGHT);
if ((IsPassage & DOWN) && (pNode->direction != UP))
FindNode(pNode, x, y+1, DOWN);
if ((IsPassage & LEFT) && (pNode->direction != RIGHT))
FindNode(pNode, x-1, y, LEFT);

for (int i=0; i<pNode->index; i++)
{
int nFind = FindMazePath(pNode->node);

if (nFind == END)
return END;

if ((nFind == 0) && (i == (pNode->index-1)))
return 0;
}

break;
}

} while (bForward);

return 0;//END;
}

int _tmain(int argc, _TCHAR* argv[])
{

int start_x = 1,
start_y = 1;

//cin >> width;
//cin >> height;

//for (int i=0; i<height; i++)
//{
// string strData;
// cin >> strData;
// MazeData.Add(strData);
//}

width = 41;
height = 41;
MazeData.Add("+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+");
MazeData.Add("| |       |    |       |    | |");
MazeData.Add("+ +-+-+ + + + +-+ + +-+-+-+ + + +-+ + +-+");
MazeData.Add("|    | | |    |    | | | | | |");
MazeData.Add("+-+-+ + +-+-+-+ +-+-+ + + +-+-+-+ + +-+ +");
MazeData.Add("|    | | |    | |    | | |    |");
MazeData.Add("+ +-+-+-+ + + +-+-+ + +-+-+-+ + + + + +-+");
MazeData.Add("| | | |    | | |    | | | | | |");
MazeData.Add("+-+ + + +-+-+-+-+ + +-+ + + + +-+-+ + + +");
MazeData.Add("| | |       | | | | | | | | |");
MazeData.Add("+ +-+-+ +-+ +-+-+ +-+ + + + +-+ + +-+-+-+");
MazeData.Add("| |    | | | | | | | | |    |");
MazeData.Add("+ + +-+-+ +-+ + + + + +-+ +-+ + +-+-+-+ +");
MazeData.Add("| | | | | | | | | | | | | | |");
MazeData.Add("+ +-+ +-+ + +-+ + +-+-+ + + + + + + + + +");
MazeData.Add("| | | | | | |    | | | | | | | |");
MazeData.Add("+ + + + +-+-+ + + +-+-+ +-+ + +-+ + +-+-+");
MazeData.Add("|    |    | | |    | |    |    |");
MazeData.Add("+-+-+-+-+-+-+-+ + +-+ +-+ +-+-+-+-+-+-+ +");
MazeData.Add("| |    |    | | | |       | | |");
MazeData.Add("+ + + +-+ + +-+ +-+ +-+ +-+-+-+-+ + + +-+");
MazeData.Add("| | | | | | |    | | | | |");
MazeData.Add("+ +-+-+ +-+ + +-+ +-+ +-+-+ + + + +-+-+ +");
MazeData.Add("| | |    | | | |    | |       |");
MazeData.Add("+ +-+ + +-+-+-+ + + + + +-+-+-+-+-+-+-+-+");
MazeData.Add("|    | |    | | | | | |    |    |");
MazeData.Add("+-+-+-+ + +-+ + + + +-+-+ + +-+ + +-+-+ +");
MazeData.Add("|    | | | | | | |    | |    |");
MazeData.Add("+ +-+-+-+ + + + + +-+ +-+-+-+-+-+-+ + + +");
MazeData.Add("| |    | | | |    | |       | | |");
MazeData.Add("+ + +-+ + + +-+-+-+-+-+ + + +-+-+-+-+ +-+");
MazeData.Add("| | | | |    | | | | |");
MazeData.Add("+ +-+ +-+-+-+ + + +-+-+-+-+-+ + + +-+ + +");
MazeData.Add("| | | | | | |       | |    | |");
MazeData.Add("+-+-+ + + + + +-+-+ + +-+-+-+-+ + +-+-+ +");
MazeData.Add("|    | | | | | |    | | | | |");
MazeData.Add("+ +-+-+-+-+ + + + +-+-+ +-+ + +-+ + + + +");
MazeData.Add("| | |    | |    | | | | | | |");
MazeData.Add("+ + + +-+-+-+-+-+ +-+-+-+ + +-+ + + +-+-+");
MazeData.Add("| |                   | | |    |");
MazeData.Add("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +");

node_t* pNode = new node_t;
pNode->pos.x = start_x;
pNode->pos.y = start_y;
pNode->root = NULL;
pNode->node[0] = NULL;
pNode->node[1] = NULL;
pNode->node[2] = NULL;
//pNode->node[3] = NULL;
pNode->index = 0;
pNode->level = 1;
pNode->direction = DOWN;
pNode->Passage =  LookMaze(start_x, start_y);
mapNode[pNode->pos.key] = pNode;

FindMazePath(pNode);

for (int i=0; i< height; i++)
cout << MazeData << "\n";

node_t* pNodeOutput;
do {

pNodeOutput = stackNode.Pop();
cout << pNodeOutput->pos.x << "," <<  pNodeOutput->pos.y << "\n";

} while (!stackNode.IsEmpty());

cout << "\n\n";

return 0;
}

p1ayer · 发表于 2006-9-19 13:22:00

http://www.gamedev.net/reference/articles/article1637.asp
有一??
MazeGen.c

但是他的SolveMaze的算法
不是我要的DFS

p1ayer · 发表于 2006-9-19 18:35:00

??念
算出?淼母??pos的x,y
?成???或?叉路後的第一??位置
所以???P?不太起?砹

1,1 (自定的起?)
2,3 (原本???取 1,3 的)
5,4 (原本???取 5,3 的)
4,5 (原本???取 5,5 的)
1,6 (原本???取 1,5 的)
2,7
3,8
4,9
5,8
6,7
7,8
7,10
6,11
3,12
4,13
5,14
6,15
7,16
8,17
13,16
12,15
11,14
12,13
13,12
14,11
15,12
16,21
17,22
18,27
19,26
20,23
21,22
20,21
19,20
18,19
17,18
17,14
16,7
13,6
12,5
11,6
10,7
9,6
8,5
7,4
8,1
10,1
11,2
12,3
14,3
15,4
16,5
19,6
20,9
21,10
22,11
23,10
24,7
25,8
26,13
27,14
26,17
25,18
24,19
23,20
24,21
27,22
26,23
23,24
24,25
25,26
26,27
27,26
28,25
31,26
32,27
33,26
34,25
39,26
38,27
37,28
38,31
39,32
38,37
37,36
36,35
35,36
36,39
39,40

p1ayer · 发表于 2006-9-19 19:34:00

//多加了一堆修正之後.......

// maze2.cpp : 定?主控台??贸淌降倪M入?。
//

#include "stdafx.h"
#include <assert.h>

enum {
UP = 1,
RIGHT = 2,
DOWN = 4,
LEFT = 8,
END =0xFF
};

typedef union _pos_t
{
struct
{
unsigned int x : 16;
unsigned int y : 16;
};
int key;
} pos_t;

typedef struct _node_t
{
struct _node_t* root; //?碓垂??

struct _node_t* node[3]; //??
int index; //??索引

pos_t pos; //??在迷?m的座?

int level; //??Tree的第??
int Passage; //通道
int direction; //方向

pos_t pos0; //?出用的座?
} node_t;

typedef CArrayT<string> CStringArrayT;

int width, height;
CStringArrayT MazeData;
CMapT<int, node_t*> mapNode;
CStackT<node_t*> stackNode;

int xt = 0, yt =0, lt =0, st=0;

int LookMaze(int x, int y)
{
//if ((x<=0) || (x>=(width-1)) || (y<=1) || ((y>=height-1)))
if ((x>=(width-1)) || (y>=(height-1)))
{
xt = x;
yt= y;
return END;
}

CStringArrayT& src = MazeData;
int IsPassage = NULL;

if (src[y-1][x] == ' ')
IsPassage |= UP;

if (src[y][x-1] == ' ')
IsPassage |= LEFT;

if (src[y][x+1] == ' ')
IsPassage |= RIGHT;

if (src[y+1][x] == ' ')
IsPassage |= DOWN;

return IsPassage;
}

int GetPassageCount(const int IsPassage)
{
int nCount = 0;
if (IsPassage & UP)
nCount += 1;
if (IsPassage & LEFT)
nCount += 1;
if (IsPassage & RIGHT)
nCount += 1;
if (IsPassage & DOWN)
nCount += 1;
return nCount;
}

node_t* FindNode(node_t* pRoot, int x, int y, int direction)
{
pos_t pt;
pt.x = x;
pt.y = y;

node_t* pNode = mapNode[pt.key];
if (pNode == NULL)
{
assert(pRoot->index >= 0 && pRoot->index <= 3);
pNode = new node_t;

pRoot->node[pRoot->index] = pNode;
pRoot->index++;

pNode->pos.x = x;
pNode->pos.y = y;

switch (direction)
{
case UP: pNode->pos0.x = x; pNode->pos0.y = (y+1); break;
case RIGHT: pNode->pos0.x = (x-1); pNode->pos0.y = y; break;
case DOWN: pNode->pos0.x = x; pNode->pos0.y = (y -1); break;
case LEFT: pNode->pos0.x = (x+1); pNode->pos0.y = y; break;
}
pNode->level = pRoot->level + 1;
pNode->root = pRoot;
pNode->node[0] = NULL;
pNode->node[1] = NULL;
pNode->node[2] = NULL;
pNode->index = 0;
pNode-&gt

assage =  LookMaze(x, y);
pNode->direction = direction;

mapNode[pNode->pos.key] = pNode;

if (lt < pNode->level)
lt = pNode->level;
}
else
{
pNode->direction = direction;
}
return pNode;
}

int FindMazePath(node_t* pNode)
{
int x = pNode->pos.x;
int y = pNode->pos.y;
bool bForward = true;

do
{
//switch (pNode->direction)
//{
//case UP: y--; break;
//case RIGHT: x++; break;
//case DOWN: y++; break;
//case LEFT: x--; break;
//}
//st++;

int IsPassage = LookMaze(x, y);
if (IsPassage == END)
{
node_t* pNodeOutput = pNode;
while (pNodeOutput)
{
stackNode.Push(pNodeOutput);
pNodeOutput = pNodeOutput->root;
}

return END;
}

int nCount = GetPassageCount(IsPassage);

switch ( nCount )
{
case 1: //死路
return 0;
case 2: //通道
if (pNode->direction & IsPassage)
{
switch (pNode->direction)
{
case UP: y--; break;
case RIGHT: x++; break;
case DOWN: y++; break;
case LEFT: x--; break;
}
st++;

bForward = true;
break;
}
case 3:
case 4:
if ((IsPassage & UP) && (pNode->direction != DOWN))
FindNode(pNode, x, y-1, UP);
if ((IsPassage & RIGHT) && (pNode->direction != LEFT))
FindNode(pNode, x+1, y, RIGHT);
if ((IsPassage & DOWN) && (pNode->direction != UP))
FindNode(pNode, x, y+1, DOWN);
if ((IsPassage & LEFT) && (pNode->direction != RIGHT))
FindNode(pNode, x-1, y, LEFT);

for (int i=0; i<pNode->index; i++)
{
int nFind = FindMazePath(pNode->node);

if (nFind == END)
return END;

if ((nFind == 0) && (i == (pNode->index-1)))
return 0;
}

break;
}

} while (bForward);

return 0;//END;
}

int _tmain(int argc, _TCHAR* argv[])
{

int start_x = 1,
start_y = 1;

//cin >> width;
//cin >> height;

//for (int i=0; i<height; i++)
//{
// string strData;
// cin >> strData;
// MazeData.Add(strData);
//}

width = 41;
height = 41;

MazeData.Add("+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+");
MazeData.Add("| |       |    |       |    | |");
MazeData.Add("+ +-+-+ + + + +-+ + +-+-+-+ + + +-+ + +-+");
MazeData.Add("|    | | |    |    | | | | | |");
MazeData.Add("+-+-+ + +-+-+-+ +-+-+ + + +-+-+-+ + +-+ +");
MazeData.Add("|    | | |    | |    | | |    |");
MazeData.Add("+ +-+-+-+ + + +-+-+ + +-+-+-+ + + + + +-+");
MazeData.Add("| | | |    | | |    | | | | | |");
MazeData.Add("+-+ + + +-+-+-+-+ + +-+ + + + +-+-+ + + +");
MazeData.Add("| | |       | | | | | | | | |");
MazeData.Add("+ +-+-+ +-+ +-+-+ +-+ + + + +-+ + +-+-+-+");
MazeData.Add("| |    | | | | | | | | |    |");
MazeData.Add("+ + +-+-+ +-+ + + + + +-+ +-+ + +-+-+-+ +");
MazeData.Add("| | | | | | | | | | | | | | |");
MazeData.Add("+ +-+ +-+ + +-+ + +-+-+ + + + + + + + + +");
MazeData.Add("| | | | | | |    | | | | | | | |");
MazeData.Add("+ + + + +-+-+ + + +-+-+ +-+ + +-+ + +-+-+");
MazeData.Add("|    |    | | |    | |    |    |");
MazeData.Add("+-+-+-+-+-+-+-+ + +-+ +-+ +-+-+-+-+-+-+ +");
MazeData.Add("| |    |    | | | |       | | |");
MazeData.Add("+ + + +-+ + +-+ +-+ +-+ +-+-+-+-+ + + +-+");
MazeData.Add("| | | | | | |    | | | | |");
MazeData.Add("+ +-+-+ +-+ + +-+ +-+ +-+-+ + + + +-+-+ +");
MazeData.Add("| | |    | | | |    | |       |");
MazeData.Add("+ +-+ + +-+-+-+ + + + + +-+-+-+-+-+-+-+-+");
MazeData.Add("|    | |    | | | | | |    |    |");
MazeData.Add("+-+-+-+ + +-+ + + + +-+-+ + +-+ + +-+-+ +");
MazeData.Add("|    | | | | | | |    | |    |");
MazeData.Add("+ +-+-+-+ + + + + +-+ +-+-+-+-+-+-+ + + +");
MazeData.Add("| |    | | | |    | |       | | |");
MazeData.Add("+ + +-+ + + +-+-+-+-+-+ + + +-+-+-+-+ +-+");
MazeData.Add("| | | | |    | | | | |");
MazeData.Add("+ +-+ +-+-+-+ + + +-+-+-+-+-+ + + +-+ + +");
MazeData.Add("| | | | | | |       | |    | |");
MazeData.Add("+-+-+ + + + + +-+-+ + +-+-+-+-+ + +-+-+ +");
MazeData.Add("|    | | | | | |    | | | | |");
MazeData.Add("+ +-+-+-+-+ + + + +-+-+ +-+ + +-+ + + + +");
MazeData.Add("| | |    | |    | | | | | | |");
MazeData.Add("+ + + +-+-+-+-+-+ +-+-+-+ + +-+ + + +-+-+");
MazeData.Add("| |                   | | |    |");
MazeData.Add("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +");

node_t* pNode = new node_t;
pNode->pos.x = start_x;
pNode->pos.y = start_y;
pNode->pos0.x = start_x;
pNode->pos0.y = start_y;
pNode->root = NULL;
pNode->node[0] = NULL;
pNode->node[1] = NULL;
pNode->node[2] = NULL;
pNode->index = 0;
pNode->level = 1;
pNode->direction = DOWN;
pNode->Passage =  LookMaze(start_x, start_y);
mapNode[pNode->pos.key] = pNode;

FindMazePath(pNode);

for (int i=0; i< height; i++)
cout << MazeData << "\n";

node_t* pNodeOutput;

int x1 = start_x,
y1 = start_y;
//出口路?降淖???
do {

pNodeOutput = stackNode.Pop();
cout << pNodeOutput->pos0.x << "," <<  pNodeOutput->pos0.y << "\n";

int x0 = pNodeOutput->pos0.x;
int y0 = pNodeOutput->pos0.y;
//MazeData[y0][x0] = '*';
if (x0 == x1)
{
if (y1> y0)
for (int y=y0; y<=y1; y++)
MazeData[y][x0] = '*';
else if (y1< y0)
for (int y=y1; y<=y0; y++)
MazeData[y][x0] = '*';
}
else if (y0 == y1)
{
if (x1> x0)
for (int x=x0; x<=x1; x++)
MazeData[y0][x] = '*';
if (x1< x0)
for (int x=x1; x<=x0; x++)
MazeData[y0][x] = '*';
}

x1 = x0;
y1 = y0;

} while (!stackNode.IsEmpty());

cout << "\n\n";

for (int i=0; i< height; i++)
cout << MazeData << "\n";

return 0;
}

怪盗基德 · 发表于 2006-9-19 20:58:00

p1ayer · 发表于 2006-9-21 18:09:00

上面那??是??版的
後?砀某赊?圈版了

// maze3.cpp : 定?主控台??贸淌降倪M入?。
//

#include "stdafx.h"
#include <assert.h>

enum {
UP = 1,
RIGHT = 2,
DOWN = 4,
LEFT = 8,
END =0xFF
};

typedef union  _pos_t
{
struct
{
unsigned int x : 16;
unsigned int y : 16;
};
int key;
} pos_t;

typedef struct _node_t
{
struct _node_t* root; //?碓垂??

struct _node_t* node[3]; //??
int index; //????索引
int select; //路?竭x?竦墓??

pos_t pos; //??在迷?m的座?

int level; //??Tree的第??
int direction; //方向

pos_t pos0; //?出用的座?

} node_t;

typedef CArrayT<string> CStringArrayT;

int width, height;
CStringArrayT MazeData;
CMapT<int, node_t*> mapNode;
CStackT<node_t*> stackNode;

int LookMaze(int x, int y)
{
if ((x>=(width-1)) || (y>=(height-1)))
{
return END;
}

CStringArrayT& src = MazeData;
int IsPassage = NULL;

if (src[y-1][x] == ' ')
IsPassage |= UP;

if (src[y][x-1] == ' ')
IsPassage |= LEFT;

if (src[y][x+1] == ' ')
IsPassage |= RIGHT;

if (src[y+1][x] == ' ')
IsPassage |= DOWN;

return IsPassage;
}

int GetPassageCount(const int IsPassage)
{
int nCount = 0;
if (IsPassage & UP)
nCount += 1;
if (IsPassage & LEFT)
nCount += 1;
if (IsPassage & RIGHT)
nCount += 1;
if (IsPassage & DOWN)
nCount += 1;
return nCount;
}

node_t* FindNode(node_t* pRoot, int x, int y, int direction)
{
pos_t pt;
pt.x = x;
pt.y = y;

node_t* pNode = mapNode[pt.key];
if (pNode == NULL)
{
assert(pRoot->index >= 0 && pRoot->index <= 3);
pNode = new node_t;

pRoot->node[pRoot->index] = pNode;
pRoot->index++;

pNode->pos.x = x;
pNode->pos.y = y;

switch (direction)
{
case UP: pNode->pos0.x = x; pNode->pos0.y = (y+1); break;
case RIGHT: pNode->pos0.x = (x-1); pNode->pos0.y = y; break;
case DOWN: pNode->pos0.x = x; pNode->pos0.y = (y -1); break;
case LEFT: pNode->pos0.x = (x+1); pNode->pos0.y = y; break;
}
pNode->level = pRoot->level + 1;
pNode->root = pRoot;
pNode->node[0] = NULL;
pNode->node[1] = NULL;
pNode->node[2] = NULL;
pNode->index = 0;
pNode->select = 0;
pNode->direction = direction;

mapNode[pNode->pos.key] = pNode;
}
else
{
pNode->direction = direction;
}
return pNode;
}

int FindMazePath(node_t* pNode)
{
bool bFin = false;
bool bIsStackPop = false;

while (bFin == false)
{
int x = pNode->pos.x;
int y = pNode->pos.y;
bool bForward = true;

do
{
int IsPassage = LookMaze(x, y);
if (IsPassage == END)
{
do {
node_t* pNodeOutput = stackNode.Pop();
} while (!stackNode.IsEmpty());

node_t* pNodeOutput = pNode;
while (pNodeOutput)
{
stackNode.Push(pNodeOutput);
pNodeOutput = pNodeOutput->root;
}

return END;
}

int nCount = GetPassageCount(IsPassage);

switch ( nCount )
{
case 1: //死路
bForward = false;
bIsStackPop = true;
break;
case 2: //通道
if (pNode->direction & IsPassage)
{
switch (pNode->direction)
{
case UP: y--; break;
case RIGHT: x++; break;
case DOWN: y++; break;
case LEFT: x--; break;
}

bForward = true;
break;
}
case 3:
case 4:
if ((IsPassage & UP) && (pNode->direction != DOWN))
FindNode(pNode, x, y-1, UP);
if ((IsPassage & RIGHT) && (pNode->direction != LEFT))
FindNode(pNode, x+1, y, RIGHT);
if ((IsPassage & DOWN) && (pNode->direction != UP))
FindNode(pNode, x, y+1, DOWN);
if ((IsPassage & LEFT) && (pNode->direction != RIGHT))
FindNode(pNode, x-1, y, LEFT);

stackNode.Push(pNode);
pNode = pNode->node[pNode->select];
bForward = false;

break;
}

} while (bForward);

if (bIsStackPop)
{
do
{ pNode = stackNode.Pop();
pNode->select++;
if (pNode->select < pNode->index)
{
pNode = pNode->node[pNode->select];
bIsStackPop = false;
}
} while (bIsStackPop);
}
}

return END;
}

int _tmain(int argc, _TCHAR* argv[])
{

int start_x = 1,
start_y = 1;

//cin >> width;
//cin >> height;

//for (int i=0; i<height; i++)
//{
// string strData;
// cin >> strData;
// MazeData.Add(strData);
//}

width = 41;
height = 41;

MazeData.Add("+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+");
MazeData.Add("| |       |    |       |    | |");
MazeData.Add("+ +-+-+ + + + +-+ + +-+-+-+ + + +-+ + +-+");
MazeData.Add("|    | | |    |    | | | | | |");
MazeData.Add("+-+-+ + +-+-+-+ +-+-+ + + +-+-+-+ + +-+ +");
MazeData.Add("|    | | |    | |    | | |    |");
MazeData.Add("+ +-+-+-+ + + +-+-+ + +-+-+-+ + + + + +-+");
MazeData.Add("| | | |    | | |    | | | | | |");
MazeData.Add("+-+ + + +-+-+-+-+ + +-+ + + + +-+-+ + + +");
MazeData.Add("| | |       | | | | | | | | |");
MazeData.Add("+ +-+-+ +-+ +-+-+ +-+ + + + +-+ + +-+-+-+");
MazeData.Add("| |    | | | | | | | | |    |");
MazeData.Add("+ + +-+-+ +-+ + + + + +-+ +-+ + +-+-+-+ +");
MazeData.Add("| | | | | | | | | | | | | | |");
MazeData.Add("+ +-+ +-+ + +-+ + +-+-+ + + + + + + + + +");
MazeData.Add("| | | | | | |    | | | | | | | |");
MazeData.Add("+ + + + +-+-+ + + +-+-+ +-+ + +-+ + +-+-+");
MazeData.Add("|    |    | | |    | |    |    |");
MazeData.Add("+-+-+-+-+-+-+-+ + +-+ +-+ +-+-+-+-+-+-+ +");
MazeData.Add("| |    |    | | | |       | | |");
MazeData.Add("+ + + +-+ + +-+ +-+ +-+ +-+-+-+-+ + + +-+");
MazeData.Add("| | | | | | |    | | | | |");
MazeData.Add("+ +-+-+ +-+ + +-+ +-+ +-+-+ + + + +-+-+ +");
MazeData.Add("| | |    | | | |    | |       |");
MazeData.Add("+ +-+ + +-+-+-+ + + + + +-+-+-+-+-+-+-+-+");
MazeData.Add("|    | |    | | | | | |    |    |");
MazeData.Add("+-+-+-+ + +-+ + + + +-+-+ + +-+ + +-+-+ +");
MazeData.Add("|    | | | | | | |    | |    |");
MazeData.Add("+ +-+-+-+ + + + + +-+ +-+-+-+-+-+-+ + + +");
MazeData.Add("| |    | | | |    | |       | | |");
MazeData.Add("+ + +-+ + + +-+-+-+-+-+ + + +-+-+-+-+ +-+");
MazeData.Add("| | | | |    | | | | |");
MazeData.Add("+ +-+ +-+-+-+ + + +-+-+-+-+-+ + + +-+ + +");
MazeData.Add("| | | | | | |       | |    | |");
MazeData.Add("+-+-+ + + + + +-+-+ + +-+-+-+-+ + +-+-+ +");
MazeData.Add("|    | | | | | |    | | | | |");
MazeData.Add("+ +-+-+-+-+ + + + +-+-+ +-+ + +-+ + + + +");
MazeData.Add("| | |    | |    | | | | | | |");
MazeData.Add("+ + + +-+-+-+-+-+ +-+-+-+ + +-+ + + +-+-+");
MazeData.Add("| |                   | | |    |");
MazeData.Add("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +");

node_t* pNode = new node_t;
pNode->pos.x = start_x;
pNode->pos.y = start_y;
pNode->pos0.x = start_x;
pNode->pos0.y = start_y;
pNode->root = NULL;
pNode->node[0] = NULL;
pNode->node[1] = NULL;
pNode->node[2] = NULL;
pNode->index = 0;
pNode->select = 0;
pNode->level = 1;
pNode->direction = DOWN;
mapNode[pNode->pos.key] = pNode;

FindMazePath(pNode);

for (int i=0; i< height; i++)
cout << MazeData << "\n";

node_t* pNodeOutput;

int x1 = start_x,
y1 = start_y;
//出口路?降淖???
do {

pNodeOutput = stackNode.Pop();
cout << pNodeOutput->pos0.x << "," <<  pNodeOutput->pos0.y << "\n";

int x0 = pNodeOutput->pos0.x;
int y0 = pNodeOutput->pos0.y;
if (x0 == x1)
{
if (y1> y0)
for (int y=y0; y<=y1; y++)
MazeData[y][x0] = '*';
else if (y1< y0)
for (int y=y1; y<=y0; y++)
MazeData[y][x0] = '*';
}
else if (y0 == y1)
{
if (x1> x0)
for (int x=x0; x<=x1; x++)
MazeData[y0][x] = '*';
if (x1< x0)
for (int x=x1; x<=x0; x++)
MazeData[y0][x] = '*';
}

x1 = x0;
y1 = y0;

} while (!stackNode.IsEmpty());

cout << "\n\n";

for (int i=0; i< height; i++)
cout << MazeData << "\n";

return 0;
}

p1ayer · 发表于 2006-9-21 18:18:00

?於有使用到的template (像是 CArrayT , CStackT, CMapT ...)
目前最後的版本放在

http://ez-templates.cvs.sourceforge.net/ez-templates/cpp/Template/Collection/

如果有??Collection相?的template
?有bug的?
?┱?用msn 告?我一?
playercd8@hotmail.com

因?槊?m求解的code??得?M?y的
如果版主??橛惺盏骄???哪且稽c??r值的?
?版主自行重新整理code後, 您另?一篇後再收吧

账号		自动登录	找回密码
密码			立即注册

2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

Re:2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

Re:2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

Re:2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

Re:2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

Re:2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

Re:2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??

Re:2d的Maze求出口路?降??? ...???中, ?臀铱纯丛?怎?改好??