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
           

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

感谢您的阅读，如果您有收获，请给我一个三连吧！

如果您觉得这还不够，可以点击 打赏 按钮，告诉我： 你币有了！