Yesterday I spoke to @MMz_ about my Space invaders quine. As is was a general meeting and a lot of people attended we didn’t have time to look into the solution properly. So I promised him to explain the details on a later moment. I think more people would like to know how the technical solution works so I decided to write this blog.

The first step in the program is to read the “field”. The last statements in the file are:

field =
"
#####################################################r
#01   **********                                     #
#02   **********                                     #
#03   **********                                     #
#04   **********                                     #
#05                                                  #
#06                                                  #
#07                                                  #
#08                                                  #
#09                                                  #
#XX                       %                          #
###0        1         2         3         4         5#
###12345678901234567890123456789012345678901234567890#
######################################################
"

invaders =  SpaceInvaders.new(field)
invaders.next_move

Basically the space invaders field is initialized and next_move is called.

Below you can find an simplified version of the next_move code.

def next_move
	move_invaders
	calculate_new_field
	move_darts_up
	calculate_new_field
	player_shoot
end

So the invaders are moved, a new state of the field is calculated, the darts (bullets/lasers) are moved upwards, a new field is calculated and finally the player puts a new dart in the field as the shot is calculated.

While initializing the SpaceInvaders class the field is pre-processed. In order to move the invaders and the darts it is easier if the input field is split into two separate fields. One containing only the darts and another only containing the invaders. This makes moving each type of objects a lot easier.

The darts field is a String that contains line-ends, spaces and darts (i). To move all darts up basically the only thing that has to be done is remove the first line of the String and add a new line at the bottom. In code this is like:

def move_darts_up
    lines = @darts.split(/\n/)
    lines.map! {|s| s = move_line_up(s)}

    #add extra bottom line 
    lines.insert(9,"#09                                                  #")
    
    #remove top line
    lines.rotate!(1).pop    

    result = ''
    lines.each {|line| result += line + "\n"}
    @darts = result;
end

The next step is calculating the resulting field. The top line of the field doesn’t change neither do the bottom lines starting with the line #XX ……. So these lines are just copied. For the middle part both the dart field and the invaders field are overlay-ed. For each position in the field if a dart and a invader are found on the same position they both are removed from the resulting field. The actual overlay code looks like this:

def calculate_new_char(dart,invader)
  if(invader == ' ' ) 
   return dart
  elsif (dart == 'i')
    return ' ' 
  else
    invader
  end
end

Next step is to move the invaders. Initially the invaders move right. But if the wall is “touched” they move one line down. After the move down the invaders move left till the left wall is “touched” resulting in an “s”-like pattern.

The current direction of the invaders should be “remembered” by the source code. If you look at the last character of the first line in the field you see the “r”. This is the current direction.

Moving the invaders right is actually quite easy. The most right character of the field is certainly an empty place, otherwise the wall was “touched” and the invaders move down. If each line in the invaders field is put in an array of characters and the resulting array is rotated the invaders are moved right. The only thing left is to make a new string of that array. In code this looks like:

def move_line_right(line)
  if line.match(/^(#\d\d)(.*)#/)
    return $1 + $2.split(//).rotate(-1).join + '#'
  end
end

Moving left works similar only rotating 1 position to the other side. Moving down is similar to moving darts up. One extra thing for moving invaders down is to detect if any invader reaches the “player line”. If this happens the user failed to defend the earth.

Last step is to let the player shoot. When running the program is is possible to supply a number as argument. This argument is used to determine where the player shoots. Shooting is just replacing the player line with the new version.

Last step is to make the code a quine. I simplified the next_move method shown above. There are some extra steps. These steps are to see if the player has won/lost and also to calculate & write the next state of the source code. At this moment the new field is calculated. So the “only” thing left is some String manipulation in the source code to replace the old field, with the new field. With a regexp that is quite easy. The code looks like this:

  input.gsub!(/(\r?\n#####(l|r|.|\n|\r)+?#######\r?\n)/,@field)

Now you’ve seen my solution some closing thoughts. The first steps into my solution was moving the invaders right. Initially my solution was to read the field and use a regexp to match a line with “*” in it and remove the last space character and adding a new space on the left. Getting this to work is not really difficult. After implementing moving down and moving left I decided to introduce darts and to move these darts up. I couldn’t find out how to get that working. After thinking about it for half an hour or so I decided I couldn’t fix that. I stopped coding at that moment to come back at a later moment. As someone put it before:

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.

The morning after I suddenly had an idea how to solve it. I remembered that during the global day of code retreat in December some people solved Conway’s Game of Life by overlaying multiple copies of the initial state. I’m convinced that attending the global day of code retreat helped me create this quine. Waiting a day to get the solution is for me just like the “Thoughtful walking” technique described in Pragmatic thinking and learning.

P.S. If someone else is trying to make a quine and write it to a file, please make sure you don’t overwrite your source file until you’re ready to release your solution. As you are replacing things in the original source file and you make a mistake (I know you don’t make mistakes), you loose the original version. It happened to me several times. Thank got I had Git & committed a lot. The full code can be found on GitHub.