0
\$\begingroup\$

I have an 2D array containing 1 for walls or 0 for empty cells.

I can draw my maze by iterating through the map, placing a wall when map[x][y] is equal to 1 but I want to get the points of the different polygon formed by the 1 in order to have minimum draw call.

But I'm not sure about the Maths and I don't know how to proceed.

Would you please give me some hint ?

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Programming games will need lots of math. You should study up on that: khanacademy.org/math/linear-algebra/vectors_and_spaces. \$\endgroup\$
    – House
    Sep 9, 2013 at 13:48
  • \$\begingroup\$ Yes I know ... I'm currently studying vectors with my character movements. Thanks for the link ! \$\endgroup\$
    – Sladix
    Sep 9, 2013 at 14:09

1 Answer 1

Reset to default
1
\$\begingroup\$

A simple to understand, but probably not optimal method is the following:

  • Step through all elements of the array, starting at the top left.
  • At each step, examine the current element and 3 of its neighbors: the one to its right, the one to its bottom, and the on to its bottom right.
  • Check how many of the 4 elements have the value 1. If exactly 4 or 0, you don't have a point there. If 1 or 3, you have a point. If 2, and these two are in the same row OR in the same column, you don't have a point.

Some illustration:

enter image description here

Black means a wall, white means empty space. A,B,C and D are the elements of your array, e.g. [i,j], [i+1,j], [i,j+1] and [i+1,j+1]. The red dot shows where a polygon point must be created.

So go through the whole array, collect the points in a list (there will be many duplicate points, just don't add them or remove them later). Pay extra attention to the area near the boundaries of the array!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Thank you for the hint ! I will try it soon and provide my feedback ! \$\endgroup\$
    – Sladix
    Sep 9, 2013 at 14:32
  • \$\begingroup\$ Rather than iterating across the array in row/column order, you might instead prefer to follow the wall like a spider crawling along it: sticking to the barrier between 0 & 1, and turning corners when the passages do. This not only gives you the list of points you need, but also the order of traversal for turning them into edges & polygons for rendering. Each time you make a concave turn, you know it's time to make a split in your triangulation. \$\endgroup\$
    – DMGregory ♦
    May 22, 2018 at 16:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .