-5

我对组装完全陌生，不管你信不信，我们的第一个任务是在组装中创建蛇。我应该如何存放蛇？我应该将它放在堆栈中，还是应该将它放入某个寄存器中？我已经对这种“可怕的”语言进行了大约 3 天的研究，但无法找到一个好的开始方式。我可能会在 c++ 中使用某种链接列表，但不幸的是这不是 c++。

非常感谢任何帮助

4

3 回答 3

2

可以使用一对 x,y 坐标来跟踪蛇的头部。当然，您需要头部的当前方向。 （尾巴需要的不仅仅是 x,y 对，可能 x,y 对的循环缓冲区是最好的选择。那么您实际上不需要将尾巴 x,y 与历史缓冲区分开。）

正如@Daniel 的回答所解释的那样，当头部移动时，查看您将要绘制的下一个像素会告诉您蛇吃什么：什么都没有，苹果、墙或它自己。

（如果您对视频 RAM 具有有效的读取访问权限，则可以简单地读取像素而不是保留影子板阵列。但是大多数现代系统没有有效的视频 RAM 读取访问权限；在典型的 x86 VGA 内存上，无法通过写入缓存-结合。但是如果你假装你正在为一个真正的 8086 写，VGA RAM 在 ISA 总线的另一端，所以这也很慢。但是 8086 没有任何缓存。一些甚至更早的系统可能有视频 RAM主内存的一部分，IDK。）

另一种选择是搜索苹果方块和蛇方块的列表，但这比检查一个数组条目要多得多。编写游戏（或其他实时软件）的一个关键因素是对最坏情况的性能设置严格的上限。当有很多带有蛇的方格，并且步时间很短（蛇移动速度很快）时，您不希望游戏变得笨拙并且由于搜索时间过长而使某些步长比其他步长。那很快就无法播放了。

rows * cols因此，您可能需要一个字节数组（您对其进行 2D 索引），您可以在其中存储诸如0空、1墙等代码。如果您使用调色板视频模式，您可以使用与视频 RAM 中的像素相同的代码，如果您直接在 VRAM 中绘图，或者使用现代视频 API、屏幕缓冲区或 OpenGL 纹理。否则，您的状态数组中只有代码，屏幕缓冲区中只有 24 位或 32 位像素。

为了简化索引，您可以使存储格式使用 2 行步长的幂，即使板宽不是。因此，每行的末尾可能会有填充列。但这可能会浪费大量内存，通常您只需要相对于当前位置进行索引（例如，下一列左/右的 +-1 字节，或 +-row_stride 以使下一行向下/向上。）

头/尾 x,y 坐标可以只是指向平板数组的单个索引或指针，但我们还需要实际的 x,y 坐标来单独绘制图形。

在每一步之后，您还需要在尾部清除一个正方形（除非蛇仍在从最近的苹果中生长；您需要一个向下计数器来计算有多少未决的生长）。我们知道在哪里将屏幕画回黑色，因为我们有尾巴 x,y。

但是我们如何更新尾部 x,y 以便下一步将遵循头部所走的实际路径？ 您可能希望通过查看尾巴周围的方块，您可以找出哪个是下一个最古老的。我们可以通过一个例子来证明情况并非如此，两条不同的轨迹导致相同的棋盘位置具有相同的 Head 和 Tail。玩家可以通过水平或垂直之字形来创建此棋盘布局。

   H123        H167          H is the head, T is the tail
    654         258            snake segments are 1..8 in order of moves.
    78T         34T

如果没有 1..8 的历史，所有的方格都只是“蛇”，没有算法可以明确地决定尾部在擦除后应该向哪个方向移动。（即使是一个可以查看整个电路板的慢速算法。）

对于仅查看尾部周围的 8 个方格的合理算法，还有其他模棱两可的情况，例如

    54               H12          # defeating a "local" algorithm
    T321H              34
                       T5

所以我们必须以某种方式记录历史。 我认为最好和最简单的选择是：

使用循环缓冲区作为(x,y) 对的队列来记录蛇的路径

您的蛇将在内存地址中爬行，与蛇在屏幕上爬行的方式非常相似，因此这种数据结构导致简单的实现是一种适当的而不是巧合（每一步要做的工作很少。）

这个缓冲区的大小将设置我们可以支持的最大蛇长度，此时我们正在重用缓冲区条目来在读取尾部后立即记录头部。您可以使其大于行 * 列，因此如果您愿意，游戏不会施加实际限制。

这可能是许多真正的经典贪吃蛇游戏都具有最大贪吃蛇长度的技术原因。（除了游戏方面的原因。）由于您的游戏是唯一在 CPU 上运行的东西，因此没有理由不总是使用相同大小的循环缓冲区，即静态分配尽可能大的内存。然后，您将永远不会因为在成长或其他任何事情后复制游戏而结结巴巴。

您可以编写类似于此 C 的 asm：

typedef struct xy {uint8_t x, y;} xy_t;
static const unsigned max_snakelen = 512;
struct xy snakepath[max_snakelen];
// uint16_t []  board array offsets is great if we don't also need x,y for graphics

enum board_entry { SQUARE_EMPTY=0, SQUARE_APPLE, SQUARE_SNAKE, SQUARE_WALL };
static const unsigned rows = 40;
static const unsigned cols = 80;   // including walls
board_entry board[rows * cols];  // we'll do 2D indexing manually because asm has to

static inline unsigned dir_to_board_byte_offset(enum cur_direction) { ... }
 // top bit maps to +- rows, or bottom bit to +- 1
static inline xy_t dir_to_xy_offset(enum directions  cur_direction) { ... }
 // map 0..3 to  {+1, 0}, {-1,0}, {0,+1}, {0,-1} in some order.

void step(enum directions cur_direction)
{
    static unsigned tailidx = 0;  // maybe kept in a register
    static unsigned headidx = 5;  // and arrange for the initial snake to be in the buffer somehow

    if (!growth)    // tail stays still while snake grows
        --growth;
        xy_t tail = snakepath[tailidx++];      // movzx edx, byte [snakepath + rbx*2] // movzx ecx, byte [snakepath + rbx*2 + 1]
        tailidx &= max_snakelen - 1;   // wrap the circular buffer idx.  AND ebx, MAX_SNAKELEN - 1

        board[tail.y * cols + tail.x] = SQUARE_EMPTY;   // imul stuff
        // and update graphics
    }

    // Most of the registers used for the above stuff are dead now, and can be reused below

    // Tail segments disappear *before* the head moves: snake can be head-to-tail
    // and go full Ouroboros without crashing.

    xy_t headxy = snakepath[headidx++];  // or track head separately, maybe in a reg so we can more quickly  like our function arg.
    headidx &= max_snakelen - 1;

    headxy += dir_to_xy_offset(cur_direction);  // maybe use a 16-bit add to do both components in parallel, except that `-1` will carry into the upper element.  So that only works with SIMD `paddb` or something. 
    // pretend that's a C++ overload and do the component adds separately

    enum board_entry headtype = board[headxy.y * cols + headxy.x];
    if (headtype != SQUARE_EMPTY) {
       apple or death;
    }

    board[headxy.y * cols + headxy.x] = SQUARE_SNAKE;
 // ADD NEW HEAD to circular buffer
    snakepath[headidx] = headxy;                   // mov [snakepath + 2*rbx], ax
    // and draw graphics for head, using its x,y.
}

这只是为了给你一个大致的想法，它非常笨重而且不是很好的 C 风格。（并且不打算这样做。）我知道并非所有内容都已宣布。在等待按键和计时器事件的事件循环的 asm 版本中，您在寄存器中保留多少状态取决于您。您调用的函数必须保存/恢复 regs，但是如果您使用标准调用约定并且无论如何都这样做，那么让最外层循环将其状态保持在 regs 中并没有什么害处。

乘法过去很慢，因此您可以考虑在蛇结构中保留 x、y和一维数组索引或实际指针。但是现代 CPU 通常具有快速乘法器。（就像 3 周期延迟完全流水线，在 Intel 自 Core 2 左右，而非流水线 8086 上超过 100）。

特别是在 16 位机器上，在多条指令中嵌入绝对地址不会占用很多代码字节。它在 32 位代码中变得更糟。x86-64 可以在 Linux 上的位置相关代码中使用 32 位绝对地址，但仍然允许[snakepath + rbx*2]像

根据您的目标 ISA，您可能会在寄存器中保留更多或更少的指针。

另一种方法是记录玩家每次转身的时间。但在最坏的情况下，玩家每步转一次，所以你仍然需要与蛇的长度一样多的缓冲区条目。（或者如果你有更少，你有非常不受欢迎的游戏玩法：玩家可能意外地无法转身，因为他们过去转身太多，并且令人沮丧地死去。）

每个条目至少需要与 x,y 对一样多的空间，并且需要更多的工作来解码。（在每一个转弯处只记录一对 x,y 可以提供足够的信息来通过查看尾部 x,y 与最后一个转弯来重建路径。）

但是，前一个方向 + 长度实际上可能更紧凑：每条记录 1 个字节。如果将位打包到位域中，方向需要 2 位，我们可以选择尽早创建新条目以将长度保持在 6 位，即使板比 63 = 2 6 -1 方格更宽或更高。所以每个条目可以很容易地成为 1 个字节。dir = x & 3（用和解码len = x >> 2）。

您可以通过减少尾部条目的长度直到达到 0 来使用这种 dir+len 格式（这意味着尾部到了转弯处，并且应该开始查看下一个缓冲区条目）。为了提高效率，您将保持当前正在处理的文件未打包，或者您将使用sub byte [rsi], 4并检查进位（以检测当您递减时长度是否已经为零，并使其包装）。

于 2019-02-03T07:35:25.790 回答
1

我希望 6 年后不再是问题，但就我而言，我基于像素。例如，有一个像素被指定为蛇的头部。我总是保存它的位置（x 轴和 y 轴），并在循环中检查是否在蛇的方向上有任何绘制的像素：

  • 如果它是黑色的——我什么也没做，继续移动蛇。黑色是背景。

  • 如果它是红色的——我知道这条蛇会吃掉一个苹果。

  • 如果它是蓝色的，我就知道蛇要撞墙了，以此类推。

于 2019-02-02T18:47:20.647 回答
0

我应该如何存放蛇？我应该将它放在堆栈中，还是应该将它放入某个寄存器中？

假设您谈论的是 Snake 动画/游戏，答案可能都不是。您很可能使用二维数组来表示“屏幕”上的细胞，并将蛇的身体表示为给定“颜色”的细胞。

我可能会首先找出用 C 或 C++ 实现代码的最简单方法……而不使用任何数据结构库……然后在汇编程序中重新编码算法。

于 2012-11-10T07:22:01.273 回答