可以使用一对 x,y 坐标来跟踪蛇的头部。当然,您需要头部的当前方向。(尾部需要的不仅仅是一个 x,y 对,可能 x,y 对的循环缓冲区是最好的选择。那么您实际上不需要与历史缓冲区分开的尾部 x,y。)
正如 @Daniel 的回答所解释的那样,当头部移动时,查看您要绘制的下一个像素会告诉您蛇吃什么:什么都没有,苹果,墙壁或它自己。
(如果您对视频 RAM 具有高效的读取访问权限,则可以简单地读取像素,而不必同时保留阴影板阵列。但大多数现代系统don't具有高效的视频 RAM 读取访问权限;在典型的 x86 VGA 内存上,写组合无法缓存。但如果你假装你正在为真正的 8086 编写,VGA RAM 位于 ISA 总线的另一侧,所以速度也很慢。但8086没有任何缓存。一些甚至更早的系统可能将视频 RAM 作为主存储器的一部分,IDK。)
另一种选择是搜索苹果和蛇方块的列表,但这比检查一个数组条目要多得多的工作。编写游戏(或其他实时软件)的一个关键因素是对最坏的情况下表现。当有很多带有蛇的方块,并且步骤时间很短(蛇移动速度很快)时,您不希望游戏变得笨重并且某些步骤比其他步骤花费更长的时间,因为搜索时间太长。那很快就无法播放了。
所以你可能想要一个数组rows * cols
存储代码的字节(您对其进行二维索引)0
对于空的,1
用于墙壁等。如果您使用调色板视频模式,则可以使用与视频 RAM 中的像素相同的代码,如果您直接绘制到 VRAM 中,或者使用现代视频 API、屏幕缓冲区或 OpenGL 纹理。否则,您的状态数组中将只有代码,屏幕缓冲区中只有 24 或 32 位像素。
为了简化索引,您可以使存储格式使用 2 行步幅的幂,即使板宽度不是如此。因此,每行末尾可能会有填充列。但这可能会浪费大量内存,通常您只需要相对于当前位置进行索引(例如,+-1 字节用于左/右下一列,或 +-row_stride 来向下/向上获取下一行。)
头/尾 x,y 坐标could只是平板数组中的单个索引或指针,但我们还需要实际的 x,y 坐标来单独绘制图形。
每走一步还需要清除尾部的一个方块(除非蛇仍在从最近的苹果中生长;您将需要一个计数器来显示有多少待处理的生长)。我们知道在哪里将屏幕涂回黑色,因为我们有尾巴 x,y。
但我们如何update尾部 x,y 所以next步骤将遵循头部实际走过的路径?您可能希望通过观察尾巴周围的方块,可以找出哪一个是第二古老的。我们可以通过两个不同的轨迹导致具有相同头和尾的相同棋盘位置的示例来证明情况并非如此。玩家可以通过水平或垂直之字形来创建此棋盘布局。
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
所以我们必须以某种方式记录历史。我认为最好和最简单的选择是:
Use a 作为队列的循环缓冲区 https://en.wikipedia.org/wiki/Circular_buffer(x,y) 对记录蛇的路径
你的蛇将在内存地址中爬行,这与蛇在屏幕上爬行的方式非常相似,因此这种数据结构导致简单的实现(每个步骤只需要做很少的工作)是适当的而不是巧合。
该缓冲区的大小将设置我们可以支持的最大蛇长度,此时我们将重用缓冲区条目来记录头部右侧after读尾巴。您可以将其设置为大于行 * 列,因此如果您愿意,游戏不会施加实际限制。
这可能是许多真正的经典贪吃蛇游戏都有最大蛇长度的技术原因。 (除了游戏玩法原因。)由于您的游戏是唯一在 CPU 上运行的东西,因此没有理由不始终使用相同大小的循环缓冲区,即静态分配您需要的大小。这样你就不会因为在成长或其他任何事情后复制它而导致游戏卡顿。
您可以编写类似于此 C 的汇编:
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 风格。 (并不是intended是。)我知道并非所有事情都已声明。在等待按键和计时器事件的事件循环的 asm 版本中,您在寄存器中保留多少状态取决于您。您调用的函数必须保存/恢复 regs,但是如果您使用标准调用约定并无论如何都这样做,那么让最外层循环将其状态保留在 regs 中并没有什么坏处。
乘法过去很慢,所以你可以考虑保留 x,yand一维数组索引或蛇结构中的实际指针。但现代 CPU 通常具有快速乘法器。 (例如,从 Core 2 左右开始,Intel 上的完全流水线延迟为 3 个周期,而非流水线 8086 上的延迟超过 100 个)。
特别是在 16 位机器上,将绝对地址嵌入到多个指令中不会花费很多代码字节。在 32 位代码中情况会变得更糟。 x86-64 可以在 Linux 上的位置相关代码中使用 32 位绝对地址,仍然允许诸如[snakepath + rbx*2]
,否则您会像 RISC 一样,在寄存器中获取至少一个基地址并引用与之相关的静态数据。
根据您的目标 ISA,您可能会在寄存器中保留更多或更少的指针。
另一种方法是记录玩家每次转身的时间。但在最坏的情况下,玩家每一步转动一次,因此您仍然需要与蛇的长度一样多的缓冲区条目。 (或者如果你有更少,你有highly不良的游戏玩法:玩家可能会意外地无法转身,因为他们过去转身太多,并令人沮丧地死去。)
每个条目至少需要与 x,y 对一样多的空间,并且需要稍多的解码工作。 (在每个回合仅记录 x,y 对可以提供足够的信息,通过查看尾部 x,y 与最后一个回合来重建路径。)
A previous-direction + length could actually be much more compact, though: 1 byte per record. If you pack bits into bitfields, direction takes 2 bits, and we can choose to make new entries early to keep the length at 6 bits even if the board is wider or taller than 63 = 26-1 squares. So each entry can easily be 1 byte. (Decode with dir = x & 3
and len = x >> 2
).
您可以通过减少尾部条目的长度直到达到 0(这意味着尾部到达转弯,并且应该开始查看下一个缓冲区条目)来使用此 dir+len 格式。为了提高效率,您可以将当前正在处理的文件解压,或者使用sub byte [rsi], 4
并检查进位(以检测递减时长度是否已经为零,从而使其换行)。