You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

使用递归Flood Fill算法时如何避免屏幕闪烁

汇编实现Flood Fill的问题与分析

维基百科中关于Flood Fill的条目描述了如下递归算法:

Flood-fill (node):

  1. 若节点不在区域内则返回。
  2. 设置该节点。
  3. 对节点南侧的位置执行Flood-fill。
  4. 对节点北侧的位置执行Flood-fill。
  5. 对节点西侧的位置执行Flood-fill。
  6. 对节点东侧的位置执行Flood-fill。
  7. 返回。

网上能找到的汇编实现Flood Fill的示例不多,我自行用FASM写了个还算不错的版本,Stack Overflow上还有两个更差的递归实现!

从性能角度看,邻域像素的遍历顺序影响不大,不一定非要按南→北→西→东的顺序。24种排列随便用哪种都行,但千万别选方向和其相反方向不紧邻的顺序——这会让栈使用量直接翻倍!合适的顺序包括SNWE、NSWE、SNEW、NSEW、WESN、EWSN、WENS和EWNS。

这个程序能正常运行,但屏幕会出现闪烁(flicker)。会不会是递归实现Flood Fill导致的?真的是这个原因吗?

; ------------------------------
; BL is OldColor
; BH is NewColor
; CX is X
; DX is Y
; IN (bx,cx,dx)
FloodWhile:
    pusha
    mov   al, bl                ; NewColor
    mov   ah, 0Ch
    mov   si, ax                ; CONST
    shr   bx, 8                 ; -> BL is OldColor, BH=0 is DisplayPage

    cmp   al, bl                ; NewColor must be different from OldColor
    je    .z
    mov   ah, 0Dh               ; BIOS.ReadPixel
    int   10h                   ; -> AL
    cmp   al, bl                ; First pixel must have OldColor
    jne   .z
    call  .Flood                ; -> (AX)
.z: popa
    ret
; - - - - - - - - - - - - - - -
; IN (bx,cx,dx,si) OUT () MOD (ax)
.Flood:
    push  di
    mov   di, 12
    mov   ax, si                ; -> AL is NewColor, AH=0Ch is FunctionID
    int   10h                   ; BIOS.WritePixel

.a: add   cx, [.c+di]           ; Try a neighboring pixel (SNWE)
    cmp   cx, 320
    jnb   .b
    add   dx, [.c+di+2]
    cmp   dx, 200
    jnb   .b
    mov   ah, 0Dh               ; BIOS.ReadPixel
    int   10h                   ; -> AL
    cmp   al, bl
    jne   .b
    call  .Flood
.b: sub   di, 4
    jns   .a
    dec   cx                    ; X-- Return from East

    pop   di
    ret
;         East  West   North South  <-- SNWE
.c: dw    +2,0, -1,+1, 0,-2, 0,+1
; ------------------------------

内容的提问来源于stack exchange,提问作者Sep Roland

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.14 08:55:12