Fully hardwired Space Invaders in BSV

Introduction

I had the opportunity to participate in two ADAS (Advanced Driving Assistant System) projects using the same FPGA (Xilinx Zynq UltraScale+ MPSoC). To learn about FPGAs and the development environment, I created a Space Invaders game using Verilog in 2018 for the 40th anniversary at that time. I did not use high-level synthesis at this time because if I used FPGA, its environment, and high-level synthesis at the same time for the first time, it would be difficult to determine the cause when things went wrong. For this reason, I used Verilog, with which I was familiar.

In January 2020, Bluespec open-sourced bsc (Bluespec SystemVerilog Compiler). So I installed bsc, a compiler that performs high-level synthesis of designs written in BSV (Bluespec SystemVerilog). BSV, like any other language, cannot be learned by reading manuals, so I thought that the only way to learn a new language was to actually design the application. So, I tried to redesign the Space Invaders game using BSV.

BSV

Briefly, Verilog HDL is a hardware design language (HDL) standardized as IEEE 1364, while SystemVerilog is an extension of it standardized as IEEE 1800. BSV is an HDL that further extends SystemVerilog.

Other implementations

At the beginning of the development, I thought that I was the only one who would do such a foolish thing (designing with HDL, which is hard to design). However, after completing the project, I searched YouTube, etc., and found about 10 examples in the world.

However, in some respects, this is unavoidable because it is implemented in HDL, a nonfree language, but most of them are simple, such as the lack of shields (barricades) and the fact that the invaders do not shoot at us. Not only that, but there is no pixel-by-pixel collision detection, which I was impressed with 40 years ago, and which was present in the original. So I tried to make the behavior of the implementation as close to the original as possible. Moreover, we can use backstage tricks such as "Nagoya-uchi" and "Rainbow", which will be discussed later.

Equipments used

In the previously developed system, I used the Ultra96 FPGA board, which required the Ultra96toPMOD board developed by our company, shown in the first figure. I also have ported the system to the Arty board, which basically requires only the Arty board and each interface board; since the Arty board has four PMOD interfaces, the newly developed Ultra96toPMOD board is not necessary. Besides, the price of Arty board is less than half the price of the Ultra96 board.

First step - Sound FSM (Finite State Machine) design

In applying BSV for the first time, the sound state machine is relatively small in scale, so that was the first design target.

Determining the sound channels

There are 10 different sounds used in the game; the number of simultaneous occurrences (= the number of sound channels) needs to be determined. Considering the conditions for simultaneous occurrences in the game scenario, I assume that there are 4 channels: the sound of the player's own ship, Invader sounds 1 and 2, and the UFO sound.

Sound System Block Diagram

The block diagram of the new specification is shown in the figure below. The sound FSM was expanded to 4 channels from the previous design and a new mixer was installed to enable simultaneous voicing.

I started with the BSV study and completed the sound FSM in about a week.

Second step - Game FSM design

Then I continued with the state machine design of the game FSM.

In designing the sound FSM, I designed the FSM using a state-based design methodology. State-based FSM design method, in this article, refers to a method in which a sequence is manually decomposed into states, and rules are written for each state one by one. This method basically requires the same amount of man-hours as Verilog. In other words, there is little benefit in using a high-level language.

On the other hand, BSV has a library called StmtFSM that allows the efficient design of state machines. In this game FSM, I took full advantage of this and designed it without manual state decomposition. This approach will be referred to as sequence-based in this article.

Algorithm of game FSM

Basically, I found that the game can be written in the same way as it is written in C. For example, if I consider the algorithms for bullet movement, collision detection, collision processing, and showing and erasing the explosion mark, the algorithms are the same for both self and enemy bullets as follows.

if (bullet_explosion_timer >= 1) { // Bullet exploding
    bullet_explosion_timer++;
    if (bullet_explosion_timer == MAX) {
        bullet deletion; // logical deletion
        erase bullet_explosion_mark; // logical erasure
        bullet_explosion_timer <= 0;
    }
} else {
    if (no bullets and bullet generation condition) {
        bullet generation process;
        bullet sound; // only own bullets, no sound for enemy bullets
    }
    if (bullet exists) {
        Collision detection;
        if (collision with object) { // invader and UFO for own bullets, ship for enemy bullets
            delete bullet; // logical deletion
            erase bullet_mark; // Physical deletion
            object state <= explosion;
            object_explosion_timer <= 0;
        } else if (up down hash || base || bullets) { // bullets: if own bullets, enemy bullets; if enemy bullets, own bullets
            erase bullet_mark; // physical erase
            show bullet_explosion_mark;
            bullet_explosion_timer <= 1; // start timer
        } else { // if no collision
            advance bullet; // if no collision, advance the bullet; // if no collision, advance the bullet
        }
    }
}

On the other hand, the object requires dedicated processing, as shown in the following code.

if (object state == explosion) {
    if (object_explosion_timer == 0) {
        object_explosion_timer <= 1; // start timer
        object explosion sound;
        show object_explosion_mark ;
    } else {
        object_explosion_timer++;
        if (object_explosion_timer == MAX) {
           delete object; // logical deletion
           erase object_explosion_mark; // physical erasure
        }
    }
}

By applying StmtFSM, I can describe the bullet sequence as an algorithm without decomposing it into clock-by-clock states. I wrote the above pseudo-code in a C-like language, but I just need to change '{' to seq and '}' to endseq in BSV. The control syntax of if, while, for, etc. is behaviorally synthesized by bsc and converted into a state machine in Verilog.

Backstage tricks

I implemented the "Rainbow" and "Nagoya-uchi", which also exist in the original, as backstage tricks.

"Rainbow"

"Rainbow" is a bug whereby shooting an invader behind an invader leaves a trail of movement that does not disappear. The invader moves 2 pixels to the left and 3 pixels to the right when there is only one left. The bottom two invaders have a shape that does not leave a mark when it moves up to 2 pixels to the left or right, but when it moves 3 pixels, the mark is not erased and remains. In this implementation, we can experience the same rainbow as in the original. The following figure illustrates the principle of the rainbow, showing how it moves by 3 pixels to the right.

"Nagoya-uchi"

I have also implemented "Nagoya-uchi." This takes advantage of the behavior of the invader's bullets, which emerge from 16 pixels below so that if the ship is between the invader and the bullets, it will not be hit by enemy bullets.

Completion of the game

The following movie shows what is probably the world's first movie of a BSV-designed Space Invaders game in action.

The basic algorithm was completed in 2018 and required no adjustments this time. Therefore, I completed the Space Invaders game in about 2 weeks, starting with learning the language, 1 week for the sound FSM, and 1 week for the game FSM. Other additions, such as UFO functionality, were completed in the following week or so.

The completed invader hierarchy is shown in the following figure. button_0 is simply a circuit that ORs the onboard and external switches. invader_move_0 is the game FSM designed by BSV. blk_mem_gen_0 is a ROM connected to the game FSM that stores patterns for invaders, etc.

Advantages of BSV

Although BSV seems to be more efficient, it adds a new compile time of bsc, which can be more than an hour for a large design. Thus, for such a design, the TAT (turnaround time) for modification, model creation, and simulation will be very long, which may make it less efficient than Verilog. However, simulation was about 3, 000 times faster in Bluesim than in iverilog.

As a result, I was able to design two FSMs using two different design methods: a state-based design for the sound FSM and a sequence-based design for the game FSM. The ratio of the number of lines between BSV and Verilog shows a dramatic increase of 2.1x for rule-based and 300x for sequence-based. However, it is necessary to take into account that the scale of the design differs by a factor of several dozen. The reason for this dramatic increase is presumably due to the automatic generation of state machines and the inline expansion of functions.

Since BSV supports namespaces for packages, it would be efficient if each external function could be compiled separately. However, I have not yet been able to achieve this, although I have been inquiring with the developer.

About the game itself

Forty years ago, I was stacking 100 yen coins on the game table, and this time I have played the game dozens of times for debugging, and I must say that the shape of the invader, the movement timing based on 1/60sec, a gradual faster movement, the collision detection for each pixel, the UFOs that appear from time to time, the sounds, etc. are all geniuses. I have nothing but respect for the original game developer, as everything is genius and does not feel old even after 40 years.

Addendum 1.

This is the one I designed in Verilog previously, and it is almost the same as the BSV one in appearance, operation, etc. However, the sound was changed to 4 simultaneous voices when I redesigned it in BSV.

Addendum 2.

I have published the Verilog source on GitHub. You can synthesize these sources in Vivado and download the bitstream to your FPGA to run the Space Invaders game.

Addendum 3.

I have written several articles, albeit in Japanese, as follows.

• https://qiita.com/mocapapa/items/f92dd112cceba7c229b3
• https://qiita.com/mocapapa/items/3928c7f727b97f64d036
• https://qiita.com/mocapapa/items/a2faa710503e4affa88b
• https://qiita.com/mocapapa/items/93349b92d14682c601dc