Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|improve this question
Programming games will need lots of math. You should study up on that: – Byte56 Sep 9 '13 at 13:48
Yes I know ... I'm currently studying vectors with my character movements. Thanks for the link ! – Antoine Guillien 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!

share|improve this answer
Thank you for the hint ! I will try it soon and provide my feedback ! – Antoine Guillien Sep 9 '13 at 14:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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