Algorithm for minimizing the amount of lines to draw?

Question

I am currently working on optimizing a project of mine that is a few years old now. The purpose is to draw an image after hitting a certain combination of keys. The original version that I made a few years ago manually moved to each square section, but I've recently optimized it to draw rectangles for consecutive squares which makes it a lot faster.

The next step I want to take is optimizing the way the program draws a given layout, but I don't know where to start looking. I'm hoping someone can point me in the right direction since I can't even think of a search term for this.

Currently the program has a function called Draw which takes an input like this:

Invader =
(
00100000100
00010001000
00111111100
01101110110
11111111111
10111111101
10100000101
00011011000
)

Draw(Invader, 10) ; Where 10 is the size in pixels of each square

The layout above is for this image:

Draw will take that layout and draw it top to bottom, left to right in the following way:

In total, it takes 18 separate sections to finish the picture. What I'm looking for is some algorithm that can minimize this number. For instance, the following is one of the few ways of having only 16 sections:

Likewise, the difference between the current way and something I just made up on the spot for this image is 19 (65 compared to 46).

Where should I start with this?

Also for reference, here is the current Draw function:

Draw(Layout, BlockSize)
{
  Len := StrLen(Layout)                         ; Total amount of characters
  RowSize := StrLen(StrSplit(Layout, "`n")[1])  ; Size of a single row
  Index := 0

  While (Index < Len)
  {
    Length := 1
    Char := GetChar(Layout, Index)  ; Get next character in string

    if (Char == "1")
    {
      ; Get the number of consecutive 1s
      While (GetChar(Layout, Index + Length) == "1")
      {
        Length := Length + 1
      }

      ; Draw the rectangle
      FillRectangle(Length, BlockSize)
    }
    else if (Char == "0")
    {
      ; Get the number of consecutive 0s
      While (GetChar(Layout, Index + Length) == "0")
      {
        Length := Length + 1
      }

      ; Skip the entire length
      MouseMove, BlockSize * Length, 0, 0, R
    }
    else
    {
      ; End of line, reset position
      MouseMove, -(RowSize * BlockSize), BlockSize, 0, R
    }

    Index := Index + Length
  }
}

FillRectangle(Width, BlockSize)
{
  MouseGetPos, mX, mY
  mY2 := mY                     ; Same Y for straight line
  mX2 := mX + Width * BlockSize ; Add Width of rectangle times the block size to get final X position

  Loop %BlockSize%
  {
    ; Draw line
    MouseClickDrag, L, mX, mY, mX2, mY2

    ; Move to next line
    mY -= 1
    mY2 -= 1
  }

  ; Move mouse to next position
  MouseMove, 0, BlockSize - 1, 0, R
}

GetChar(String, Index)
{
  return SubStr(String, Index, 1)
}

Answer 1

This is expanded from EpiGen's answer, but I felt it needed its own post to explain the differences.

This is the current status of what I have, but it's still not 100% optimal in all cases (as shown below). If there are any improvements feel free to add them.

So, the basic flow of the algorithm is as follows:

1. Get horizontal length from current point
2. Get vertical length from current point
3. Pick bigger length and use that direction

However, it doesn't just give the length it sees. Instead it picks the max length that doesn't intersect a line that has a greater length. Here are the steps:

1. Check if next pixel is a 1 (Going right for horizontal, down for vertical)
2. If it is, then check the length in the opposite direction starting from that index.
3. If that length is longer than the current length, then save the current length and the opposite length value.
4. Once a character that isn't a 1 is seen, if the max length in the direction being checked is lower than the max length in the opposite direction, then return the length in our direction before that point.

Here is an example of this logic in action. The grey lines represent lines that have already been drawn, the green line represents the line being checked, and the red line indicates a boundary.

Since the red line's horizontal length is greater than the current vertical length at this point, the values are saved in their current form (vertical 1, horizontal 7). After the vertical line check completes and finds a length of 2, it then sees that it crossed a line of length 7. Since it's less efficient to split this line for a smaller one, it instead changes its length back to 1 which is what it had before it crossed that line. That makes the final output look like this with a total of 16 segments, which is optimal as far as I know.

However, it fails under certain conditions; specifically the bottom left corner of this image.

The green line has a length of 10, and the row it stops at has a length of 9. Since that row isn't greater or equal to its size, it splits the line which leaves a single block to the side. If this problem were fixed, then this image would be optimal as far as I'm aware. (Lowest I've gotten is 44, current logic gets 45).

Regardless, this seems to be working as good as I need it to. If there are any other answers with better solutions in the next day or so I'll take a look at them.

As an extra, here's a gif of it running for one of the larger ones: