Public Group

# maze reduction

This topic is 4964 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm creating a maze game and a maze is currently represented by a simple 2d array like so: 11111111111111111 11100000000000111 11100000000000111 11111111111111111 11111111111111111 The 1's represent cube walls, and the 0's are empty space. Does anyone know an easy and elegant way to convert this into the minimum number of polygons possible? For instance this one would convert into 4 polygons that comprise the rectangle bordering the 1's and 0's. Right now, my program would convert it into 26 polygons, which is too much (due to some ray tracing culling I am doing). Mike C. http://www.coolgroups.com/zoomer/

##### Share on other sites
There won't be a very easy and elegant way, you will probably have to just brute force it.

If you could somehow walk the maze, each straight line could be a quad.

ace

##### Share on other sites
Hmmm... I have an idea that I think might work.
Basically, I can just toss the maze into a vector of Quad objects.

repeat a lot {

I can choose two distinct random Quad objects from the vector. For simplicity I'll remove them from the vector and put them in two objects q1 and q2.

If the quads are not coplanar, I'll just throw them back in the vector.

otherwise {
If the first and last points of one Quad q1 are equal to the 2nd and third points of q2 respectively,

{then I'll insert a new Quad back into the vector. It will have the 2nd and 3rd points of q1 and the 1st and 4th points of q2. Hmmm... The points will have to be ordered (1st of q2, 2nd of q2, 3rd of q1, 4th of q2).
}
Otherwise I'll just throw q1 and q2 back in the vector.

}

}

Sorry if this sounds like gibberish - it's late and I'm low on caffeine.

Mike C.
http://www.coolgroups.com/zoomer/

##### Share on other sites
Here's some code that seems to successfully reduce those mazes:

for (int ctr = 0; ctr < 10000000; ctr++)
{
int rand1 = rand() % v.size();

int rand2 = rand() % v.size();

// if it's not co-planar, forget it
if ((q2.isparalleltox() && !q1.isparalleltox())
|| (!q2.isparalleltox() && q1.isparalleltox())) continue;

if (vertequal(q1.vert0, q2.vert1)
&& vertequal(q1.vert3, q2.vert2))
{
int smallrand, bigrand;
if (rand1 < rand2) {smallrand=rand1; bigrand=rand2;}
else {smallrand=rand2; bigrand=rand1;}
v.erase(v.begin()+bigrand);
v.erase(v.begin()+smallrand);

v.insert(v.begin(), q3);
}

}

Mike C.
http://www.coolgroups.com/zoomer/

##### Share on other sites
Not optimal, but should be good enough.

#include <iostream>#include <vector>#include <algorithm>struct Rectangle {  public:   int x1, y1, x2, y2;      Rectangle(int x1, int y1, int x2, int y2): x1(x1), y1(y1), x2(x2), y2(y2)    {} };class Maze: public std::vector<Rectangle> {  public:   Maze(const char * const *data)    {     if(data && *data)      {       std::vector<Rectangle> last, current;              for(int y = 0; ; )        {         int x = 0;                  for(const char *cell = *data; *cell;) if(*cell != ' ')          {           Rectangle &rect(*current.insert(current.end(),                                           Rectangle(x, y, 0, 0)));                      for(++cell, ++x; *cell && *cell != ' '; ++cell, ++x) {}                      rect.x2 = x;          }         else ++cell, ++x;                  for(std::vector<Rectangle>::iterator a(current.begin()), b(last.begin()); b != last.end(); )          {           if(a->x2 >= b->x1)            {             if(a->x1 == b->x1 && a->x2 == b->x2)              a->y1 = b->y1;             else              {               b->y2 = y;               insert(end(), *b);              }                          ++b;            }                      if(++a == current.end())            {             for(; b != last.end(); ++b)              {               b->y2 = y;               insert(end(), *b);              }                          break;            }          }                  ++y;                  if(*++data)          {           current.swap(last);           current.clear();          }         else          {           for(std::vector<Rectangle>::iterator a(current.begin()); a != current.end(); ++a)            {             a->y2 = y;             insert(end(), *a);            }                      break;          }        }      }    } };int main() {  const char *maze_data[] =   {" #          #",    " # ####   ###",    " # ####   #  ",    " # ########  ",    " #   #    #  ",    "######    #  ",    "#    ########",    0};    Maze maze(maze_data);    std::cout << "Created " << maze.size() << " rectangles:\n\n" << std::endl;    /* Testing:          Numbers are the number of times a rectangle intersects that cell.     Should be 1, anything else means something went fubar. */    char output[20][20];    for(int y = 0; y < 20; ++y)   for(int x = 0; x < 20; ++x)    output[x][y] = ' ';    for(Maze::const_iterator i(maze.begin()); i != maze.end(); ++i)   for(int y = i->y1; y < std::min(20, i->y2); ++y)    for(int x = i->x1; x < std::min(20, i->x2); ++x)     if(output[x][y] == ' ')      output[x][y] = '1';     else      ++output[x][y];    for(int y = 0; y < 20; ++y)   {    for(int x = 0; x < 20; ++x)     std::cout << output[x][y];        endl(std::cout);   } }

Output:

Created 12 rectangles: 1          1 1 1111   111 1 1111   1 1 11111111 1   1    1111111    11    11111111

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 28
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634104
• Total Posts
3015541
×