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 ?

  • \$\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 '13 at 13:48
  • \$\begingroup\$ Yes I know ... I'm currently studying vectors with my character movements. Thanks for the link ! \$\endgroup\$
    – Sladix
    Sep 9 '13 at 14:09

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!

  • \$\begingroup\$ Thank you for the hint ! I will try it soon and provide my feedback ! \$\endgroup\$
    – Sladix
    Sep 9 '13 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 '18 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.