verilog實作Lemmings（瘋狂小旅鼠）遊戲

此部落格為個人部落格，不涉及商業用途，僅提供學習參考，内容均來自個人原創以及網際網路轉載和摘錄。

此部落格上帶有原創辨別的文章、圖檔、檔案等，未經本人允許，不得用于商業用途以及傳統媒體。

本文首發于CSDN，版權所有，禁止轉載。

如需轉載，請在評論區留言或私信申請，經同意後可轉載，否則屬于侵權行為。

原部落格連結：https://blog.csdn.net/qq_38305370

原部落客昵稱：城外南風起

————————————————

目錄

• Lemmings1
• Lemmings2
• Lemmings3
• Lemmings4

Lemmings1

原題目（波形demo見連結）：

The game Lemmings involves critters with fairly simple brains. So simple that we are going to model it using a finite state machine.

In the Lemmings’ 2D world, Lemmings can be in one of two states: walking left or walking right. It will switch directions if it hits an obstacle. In particular, if a Lemming is bumped on the left, it will walk right. If it’s bumped on the right, it will walk left. If it’s bumped on both sides at the same time, it will still switch directions.

Implement a Moore state machine with two states, two inputs, and one output that models this behaviour.

這是一個簡單地2D運動描述。

實作思路：根據{bump_left,bump_right}确定下一狀态。具體架構為正常的組合邏輯+時序邏輯。

需要注意的是，題中說明If it’s bumped on both sides at the same time, it will still switch directions.

即{bump_left,bump_right} = 2’b11時，旅鼠仍需轉換運動方向。

實作代碼：

module top_module(
    input clk,
    input areset,    // Freshly brainwashed Lemmings walk left.
    input bump_left,
    input bump_right,
    output walk_left,
    output walk_right); //  

    parameter LEFT=0, RIGHT=1;
    reg state, next_state;

    always @(*) begin
        // State transition logic
        case({bump_left,bump_right})
            2'b01: next_state = LEFT;
            2'b10: next_state = RIGHT; 
            2'b11: begin
                case(state)
                    LEFT: next_state = RIGHT;
                    RIGHT: next_state = LEFT;
                endcase
            end
            default: next_state = state;
        endcase
    end

    always @(posedge clk, posedge areset) begin
        // State flip-flops with asynchronous reset
        if(areset)
            state <= LEFT;
        else
            state <= next_state;
    end

    // Output logic
    assign walk_left = (state == LEFT);
    assign walk_right = ~walk_left;

endmodule
           

比較複雜的是Lemmings2。

Lemmings2

原題目（波形demo見連結）：

在Lemmings1的基礎上，有新的要求：

In addition to walking left and right, Lemmings will fall (and presumably go “aaah!”) if the ground disappears underneath them.

In addition to walking left and right and changing direction when bumped, when ground=0, the Lemming will fall and say “aaah!”. When the ground reappears (ground=1), the Lemming will resume walking in the same direction as before the fall. Being bumped while falling does not affect the walking direction, and being bumped in the same cycle as ground disappears (but not yet falling), or when the ground reappears while still falling, also does not affect the walking direction.

Build a finite state machine that models this behaviour.

與Lemmings1相比，增加了地面消失的情況，新的難點主要有三個：

1.墜落結束後，旅鼠延續墜落前的運動方向。

2.如果墜落時産生左右碰撞（哪怕地面恢複），旅鼠不改變運動方向；

3.如果碰撞時地面消失（哪怕還未墜落），旅鼠不改變運動方向；

這裡需理清一個邏輯：地面消失後，旅鼠不會馬上墜落，而是需等到clk上升沿才會墜落；地面恢複後，旅鼠也不會馬上結束墜落，而是需等到clk上升沿才會結束墜落。

針對難點1，引入reg變量old_state記錄之前的運動方向，但需要注意的是，必須在時序邏輯裡面進行記錄，隻有時序邏輯裡面的狀态更新才是必然會發生的狀态。組合邏輯裡面更新的next_state是不一定會發生的。如果在組合邏輯裡面記錄，那麼記錄的将是還未發生的狀态，如果下一狀态為FALL，那麼将出現記錄錯誤。墜落結束後延續運動方向時也會發生錯誤。如下圖所示，Mismatch=1處發生了測試錯誤，該代碼即是在組合邏輯裡面記錄舊狀态。可以看到，錯誤處并沒有成功延續之前的運動方向，而是因為t=1100時刻{bump_left,bump_right} = 2’b11 改變了之前的運動方向。但實際上，t=1100時刻正好處于墜落結束後（aaah剛好置零），是以這裡應該延續walk_left。

同時，組合邏輯裡隻執行LEFT和RIGHT兩種狀态的判斷，FALL狀态的判斷放在時序邏輯裡，将兩種運動狀态和墜落這種特殊狀态分開，便于old_state隻記錄運動狀态。

同樣，next_state = old_state這句話也隻能放在組合邏輯中的狀态判斷塊外面，因為如果放在裡面，那麼可能會被墜落開始前的{bump_left,bump_right}信号覆寫，就無法延續之前的狀态了。例如，下圖t=1080時刻的bump_left置高，會将next_state置位RIGHT，但是，這個狀态還沒來得及發生，就進入了FALL狀态，是以FALL結束後，仍應延續LEFT而不是RIGHT。而如果放在外面，t=1080時刻next_state仍會被置為RIGHT，但是，後續在FALL的時段内，通過next_state=old_state又可以将其置為已經發生的LEFT。

針對難點2，在組合邏輯處給出了判斷條件if(state != FALL)。

針對難點3，在時序邏輯裡利用 if(!ground) 提高FALL的優先級。

此外，由于狀态增加，友善起見，狀态采用獨熱碼進行編碼。

實作代碼：

module top_module(
    input clk,
    input areset,    // Freshly brainwashed Lemmings walk left.
    input bump_left,
    input bump_right,
    input ground,
    output walk_left,
    output walk_right,
    output aaah ); 

    parameter LEFT=3'b000, RIGHT=3'b010, FALL=3'b100;
    reg [2:0] state, next_state, old_state;

    always @(*) begin
        // State transition logic
        next_state = old_state;
        if(state != FALL) begin            
            case({bump_left,bump_right})
                2'b01: next_state = LEFT;
                2'b10: next_state = RIGHT; 
                2'b11: begin
                    case(state)
                        LEFT: next_state = RIGHT;
                        RIGHT: next_state = LEFT;
                    endcase
                end
                default: next_state = state;
            endcase            
        end        
    end

    always @(posedge clk, posedge areset) begin
        // State flip-flops with asynchronous reset
        if(areset) begin
            state <= LEFT;
        end
        else begin
            aaah <= ~ground;
            if(!ground)
                state <= FALL;
            else begin
                state <= next_state;
                old_state <= next_state; //必須在時序邏輯裡面進行記錄
            end
        end
    end

    // Output logic
    assign walk_left = (state == LEFT);
    assign walk_right = (state == RIGHT);
endmodule
           

Lemmings3

原題目（波形demo見連結）：

在Lemmings1和Lemmings2的基礎上，有新的要求：

In addition to walking and falling, Lemmings can sometimes be told to do useful things, like dig (it starts digging when dig=1). A Lemming can dig if it is currently walking on ground (ground=1 and not falling), and will continue digging until it reaches the other side (ground=0). At that point, since there is no ground, it will fall (aaah!), then continue walking in its original direction once it hits ground again. As with falling, being bumped while digging has no effect, and being told to dig when falling or when there is no ground is ignored.

(In other words, a walking Lemming can fall, dig, or switch directions. If more than one of these conditions are satisfied, fall has higher precedence than dig, which has higher precedence than switching directions.)

Extend your finite state machine to model this behaviour.

與Lemmings2相比，增加了挖掘的情況，新的難點主要有兩個：

1.挖掘中的碰撞無效；

2.墜落中和地面消失時挖掘信号無效。

針對難點1，在組合邏輯中的if判斷中引入state != DIG。

針對難點2，在時序邏輯中引入判斷if(!ground)和if(dig && state != FALL)。

最初的代碼：

module top_module(
    input clk,
    input areset,    // Freshly brainwashed Lemmings walk left.
    input bump_left,
    input bump_right,
    input ground,
    input dig,
    output walk_left,
    output walk_right,
    output aaah,
    output digging ); 

    parameter LEFT=4'b0000, RIGHT=4'b0010, FALL=4'b0100, DIG=4'b1000;
    reg [3:0] state, next_state, old_state;

    always @(*) begin
        // State transition logic
        next_state = old_state;
        if(state != FALL && state != DIG) begin            
            case({bump_left,bump_right})
                2'b01: next_state = LEFT;
                2'b10: next_state = RIGHT; 
                2'b11: begin
                    case(state)
                        LEFT: next_state = RIGHT;
                        RIGHT: next_state = LEFT;
                    endcase
                end
                default: next_state = state;
            endcase            
        end        
    end

    always @(posedge clk, posedge areset) begin
        // State flip-flops with asynchronous reset
        if(areset) begin
            state <= LEFT;
        end
        else begin
            aaah <= ~ground;            
            if(!ground)
                state <= FALL;
            else if(dig && state != FALL)
                state <= DIG;
            else if(state != DIG) begin
                state <= next_state;
                old_state <= next_state; //必須在時序邏輯裡面進行記錄
            end
        end
    end

    // Output logic
    assign walk_left = (state == LEFT);
    assign walk_right = (state == RIGHT);
    assign digging = (state == DIG);

endmodule
           

但上述代碼在測試向量中仍有12個mismatch。

由于HDLBits沒有提供t=860時刻前的波形，我無法看出bug。

是以，我決定換一種實作方式。事實上，當情況變得複雜後，還是應該先畫出狀态機，分析清楚各個狀态的轉換情況。

狀态機如圖所示。共有六個狀态，FALL_L和FALL_R分别表示從左行墜落和右行墜落。DIG_L和DIG_R分别表示左行挖掘和右行挖掘。DIG_L隻會轉換到FALL_L，FALL_L隻會轉換到LEFT，都不會轉換到右行。可以看到，狀态機中有很多無關項，這在之前的思路和代碼中很難展現完全。

實作代碼：

module top_module(
    input clk,
    input areset,    // Freshly brainwashed Lemmings walk left.
    input bump_left,
    input bump_right,
    input ground,
    input dig,
    output walk_left,
    output walk_right,
    output aaah,
    output digging ); 

    parameter LEFT=3'b000, RIGHT=3'b001, FALL_L=3'b010, FALL_R=3'b011, DIG_L=3'b100, DIG_R=3'b101;
    reg [2:0] state, next_state;

    always @(*) begin
        // State transition logic
        case(state)
            LEFT: next_state = ground ? (dig ? DIG_L : (bump_left ? RIGHT : LEFT)) : FALL_L;
            RIGHT: next_state = ground ? (dig ? DIG_R : (bump_right ? LEFT : RIGHT)) : FALL_R;
            DIG_L: next_state = ground ? DIG_L : FALL_L;
            DIG_R: next_state = ground ? DIG_R : FALL_R;
            FALL_L: next_state = ground ? LEFT : FALL_L;
            FALL_R: next_state = ground ? RIGHT : FALL_R;
        endcase            
    end    
    
    always @(posedge clk, posedge areset) begin
        // State flip-flops with asynchronous reset
        if(areset) begin
            state <= LEFT;
        end
        else 
            state <= next_state;
    end

    // Output logic
    assign walk_left = (state == LEFT);
    assign walk_right = (state == RIGHT);
    assign aaah = (state == FALL_L || state == FALL_R);
    assign digging = (state == DIG_L || state == DIG_R);

endmodule
           

可以發現，代碼結構和思路都清晰許多。通過三目運算符?:可以確定墜落、挖掘和前進的優先級順序。

Lemmings4

原題目（波形demo見連結）：

在Lemmings1、Lemmings2和Lemmings3的基礎上，有新的要求：

Although Lemmings can walk, fall, and dig, Lemmings aren’t invulnerable. If a Lemming falls for too long then hits the ground, it can splatter. In particular, if a Lemming falls for more than 20 clock cycles then hits the ground, it will splatter and cease walking, falling, or digging (all 4 outputs become 0), forever (Or until the FSM gets reset). There is no upper limit on how far a Lemming can fall before hitting the ground. Lemmings only splatter when hitting the ground; they do not splatter in mid-air.

Extend your finite state machine to model this behaviour.

與Lemmings3相比，增加了粉碎的情況，是以引入新的狀态SPLATTER。SPLATTER僅發生在墜落超過20個周期且地面恢複時。

計數放在時序邏輯中，如果next_state為墜落，則計數加一，否則置零。

實作代碼：

module top_module(
    input clk,
    input areset,    // Freshly brainwashed Lemmings walk left.
    input bump_left,
    input bump_right,
    input ground,
    input dig,
    output walk_left,
    output walk_right,
    output aaah,
    output digging ); 

    parameter LEFT=3'b000, RIGHT=3'b001, FALL_L=3'b010, FALL_R=3'b011, DIG_L=3'b100, DIG_R=3'b101, SPLATTER=3'b110;
    reg [2:0] state, next_state;
    reg [7:0] count;

    always @(*) begin
        // State transition logic
        case(state)
            LEFT: next_state = ground ? (dig ? DIG_L : (bump_left ? RIGHT : LEFT)) : FALL_L;
            RIGHT: next_state = ground ? (dig ? DIG_R : (bump_right ? LEFT : RIGHT)) : FALL_R;
            DIG_L: next_state = ground ? DIG_L : FALL_L;
            DIG_R: next_state = ground ? DIG_R : FALL_R;
            FALL_L: next_state = ground ? (count > 8'd20 ? SPLATTER: LEFT) : FALL_L;
            FALL_R: next_state = ground ? (count > 8'd20 ? SPLATTER: RIGHT) : FALL_R;
            SPLATTER: next_state = SPLATTER;
        endcase            
    end    
    
    always @(posedge clk, posedge areset) begin
        // State flip-flops with asynchronous reset
        if(areset) begin
            state <= LEFT;
            count <= 8'd0;
        end
        else begin
            state <= next_state;
            count <= (next_state == FALL_L | next_state == FALL_R) ? count + 8'd1 : 8'd0;                
        end
    end

    // Output logic
    assign walk_left = (state == LEFT);
    assign walk_right = (state == RIGHT);
    assign aaah = (state == FALL_L || state == FALL_R);
    assign digging = (state == DIG_L ||  state == DIG_R);

endmodule
           

————————————————

感謝您的閱讀，如果您有收獲，請給我一個三連吧！

如果您覺得這還不夠，可以點選 打賞 按鈕，告訴我： 你币有了！