复古游戏地图绘制
5.00/5 (11投票s)
从捕获的游戏玩法中重建游戏世界地图的算法。
引言
该算法通过对游戏画面的视频捕捉来重构游戏世界，因此它具有通用性，因为它不依赖于游戏内部的世界表示。为了实现这一点，我们扫描游戏画面的每一帧并提取特征，然后利用这些特征来确定我们在世界中的位置。我们维护一个已识别特征的数据库，称为“草图”，并随着处理的每一帧进行更新。一旦确定了帧的位置并更新了草图，我们就存储帧的图像数据以及运动信息。我们使用运动信息从最终地图中移除移动的物体。
由于该算法基于视频输出运行，因此对支持的游戏画面存在一些限制。
- 视频颜色数量有限（最多16色）。
- 游戏画面必须在游戏世界中持续滚动。
- 支持的游戏画面示例：CJ's Elephant Antics
- 不支持的游戏画面示例：Cybernoid
- 世界的每个部分都需要有足够可区分的特征，并且它们的布局必须是唯一的。
我们可以看到一些生成的地图示例。
在开始之前，请注意，该算法及其实现尚未进行充分优化，无法支持实时地图绘制，因为它处理游戏画面视频所需的时间比录制它所需的时间要长。
由于这只是算法的一个演示，而不是一个功能完善的“产品”，因此没有考虑最终应用程序的用户友好性。应用程序处理ZIP文件，这些文件将单个帧存储为独立文件。存档文件中的帧没有特定的格式，它们只是预定义大小的视频输出的原始像素捕捉。帧文件中存储的像素不是RGB格式，而是平台特定的颜色值。
在此实现中，所有内容（屏幕大小、调色板等）都固定为支持Commodore 64视频输出。提供的所有游戏画面文件都是通过此模拟器的C++端口玩游戏时抓取的。
在解决了这些技术细节之后，我们可以继续描述算法。
确定活动窗口
我们需要确定显示游戏世界一部分的活动屏幕区域。我们假设只有一个这样的区域，并且它是屏幕上最大的区域。屏幕的其余部分被忽略，因为它们很可能显示HUD。
为了确定活动窗口，我们扫描帧之间的变化，并维护一个矩阵，该矩阵存储屏幕上每个像素检测到的变化。每次我们检测到帧之间像素颜色的变化时，我们都会在此矩阵中标记它们。每次更新后，我们提取变化像素的“岛屿”（轮廓），并搜索最大的那个。轮廓提取在本节中有解释。
我们正在寻找覆盖屏幕总像素至少三分之一的轮廓，但我们将继续扫描帧，只要该区域保持增大。只有在连续100帧没有检测到最大轮廓的尺寸增加时，我们才会停止扫描。发生这种情况时，轮廓的边界矩形将被声明为活动窗口。
“Window”模块实现了确定活动窗口的逻辑。该模块定义了以下实体：
- “Pending”记录 – 存储窗口扫描过程的状态：像素变化矩阵、最大轮廓的大小及其边界矩形……
- “Window”记录 – 表示最终确定的活动窗口：边界矩形以及已扫描帧的列表。
- “WindowState”区分联合 – “update”函数的返回结果。
- “update”函数 – 处理当前帧并更新窗口扫描过程的状态。如果已达到声明活动窗口的标准，函数将返回“Complete Window”，否则结果将是“Incomplete Pending”以表示失败。
创建地图
一旦确定了游戏世界的窗口，就可以开始拼接地图了。
基本思想是识别当前帧中的特征，并将它们与已识别特征的数据库（称为草图）进行匹配，以确定当前帧在游戏世界中的位置。我们处理两种类型的特征：角点和轮廓。
提取特征
原始图像不适合特征提取，因为它们包含过多的信息。游戏世界被设计得美观且色彩丰富，但这不幸地为我们的需求引入了大量“噪音”。因此，为了减少我们处理的信息量和提取的特征数量，我们对源图像应用中值滤波器。我们使用5x5像素的窗口进行过滤。
 | > |  |
| 原始图像
| 过滤后的图像
|
“Filter”模块包含“median”函数，该函数实现了中值滤波器。
“Feature”模块定义了一些数据类型，用于表示不同用途的特征。
- “Feature”记录 - 存储特征的位置和区域。
- “Fid”别名 - 特征的描述（例如，对于角点，它表示所有周围像素的颜色）。
- “Handle”别名 - 特征的唯一定义：其描述、位置和区域。
角点
在计算机视觉中，角点通常是图像中最有趣的部分。我们将它们用作地图上的地标来识别帧的位置。
为了提取角点，我们不会使用任何花哨的算法，而是一个简单的实现，它只检查相邻像素。对于帧中的每个像素，我们取一个3x3像素的窗口并检查其中的像素。只有以下模式被识别为角点：
请注意，角点识别操作的是经过中值滤波器处理的帧。
一旦识别出角点，我们就切换到非过滤图像，并在角点位置取一个5x5像素的窗口来创建其描述。我们将此窗口中的颜色值转换为字节数组，然后转换为一个整数。该数字将是特征描述。我们将描述与角点位置结合起来以唯一地识别一个角点。将区域添加到混合中以满足“Feature”合同，但该信息对我们来说不是很有用，因为所有角点都将具有相同的对应于窗口大小的区域。
“Corner”模块定义了“extract”函数，该函数将从图像中提取角点并将其作为特征列表返回。
轮廓
轮廓代表了相同颜色的连接像素。在我们的算法中，我们使用它们来识别帧的移动部分，其应用在此处描述。另一个应用是识别活动窗口，不同的是，我们不处理真实帧，而是处理1位像素，这些像素标识原始图像的像素在扫描期间是否有颜色变化。该应用在此部分有描述。
使用队列的简单4向洪水填充算法用于识别轮廓。
“Contour”模块定义了处理轮廓的函数和数据类型。
- “Contour”记录 - 存储关于轮廓的信息：位置、区域、边界矩形、颜色、ID（图像中的轮廓编号）以及边缘像素列表。
- “Buffers”记录 - 表示轮廓检测算法使用的缓冲区。它还提供一些有用的信息，如边缘像素图和轮廓ID图。
- “buffer”函数 - 创建一个可以处理指定图像的“Buffers”实例。
- “single”函数 - 接受图像内的坐标，以从指定像素所属的图像中提取单个轮廓。
- “extract”函数 - 提取图像中的所有轮廓。它将所有提取的轮廓作为“Contour”列表返回。
- “recover”函数 - 从提供的轮廓列表中重新创建图像。
- “encode”函数 - 从“Contour”实例创建“Feature”对象。
构建特征图
我们将所有发现的特征保存在一个名为“sketch”的数据库中。数据库有两个主要部分：待定特征和已确认特征。只有已确认的特征才用于定位帧。当特征首次被发现并添加到数据库时，它会进入待定列表。只有在确定同一个特征在连续的帧中（25帧）以相同位置存在后，它才会进入已确认列表。这样做是为了移除属于移动对象的特征。
这两个部分由以下内容表示：
- 所有检测到的特征的地图，它将唯一特征映射到其确认状态。
- 已确认特征的多重映射，它将特征描述映射到已确认位置列表。
数据库有两个操作：
- find操作，它接收特征列表作为输入并返回匹配列表。
- update操作，它使用特征列表更新数据库。所有特征都经过确认过程。
匹配列表包含在数据库已确认列表中找到的特征描述及其已知的全局位置。如果输入列表中的某个特征描述未找到，则不会出现在结果集中。
由于特征提取过程返回的特征位置是相对于所处理帧的局部位置，因此我们需要对草图更新操作进行调整。调整是新特征所属帧的实际全局位置。帧位置的确定在下一节中有描述。
更新循环如下：
- 从帧中提取特征。
- 将提取的特征与当前草图进行匹配。
- 使用匹配项确定帧的全局位置。
- 使用实际帧位置调整的帧特征更新草图：我们将新特征添加到待定列表，并将具有足够确认数的特征移动到已确认列表。
“Sketch”模块定义了草图结构和上述两个操作。
- “Sketch”记录 - 表示草图（特征数据库）。
- “Matches”记录 - 特征描述匹配。
- “find”函数 - find操作。
- “update”记录 - update操作。
确定位置
为了确定帧的位置，我们使用feature数据库的find操作返回的匹配项。正如前面提到的，匹配项包含特征描述和已知位置列表。对于每个匹配的特征，我们取所有已知位置并进行调整，以便获得帧左上角的位置。我们将所有这些位置声明为可能的帧位置候选。
我们计算每个位置在候选中的出现次数，并将此计数作为输入到对位置可行性进行评分的公式中。公式中的第二个参数是位置与前一帧位置的距离。我们选择得分最高的位置。我们用于计算位置分数的公式如下：
在选择得分最高的位置后，我们需要验证它是否可接受。为了使位置得到验证，帧区域中的已确认特征至少有50%必须在匹配项中。如果我们在此区域中得到的匹配项较少，我们将通知调用者我们未能确定帧的位置。
“Locate”模块具有“byFeatureCount”函数，该函数负责根据特征匹配确定帧的位置。
检测移动物体
移动物体会在我们的地图上产生各种伪影，因此我们需要尽可能地过滤掉它们。为此，我们需要检测两个连续帧之间的运动。由于两帧可能具有不同的全局位置，因此我们需要调整位置并找到重叠区域，然后仅在该区域内进行运动检测。
进行调整后，我们还需要进行两个步骤。第一步，我们找到自上一帧以来所有像素发生变化的轮廓。第二步，我们创建一个矩阵，该矩阵标记这些轮廓边界矩形内的所有像素。
| 帧 #1
| 帧 #2
|
 |  |
 | |
| 检测到的运动
| |
运动检测示例
“Motion”模块定义了“mark”函数，该函数接收两个连续帧并返回一个标记了检测到运动区域的矩阵。
绘制地图
到目前为止，我们处理的都是算法用来理解游戏世界所需的内容，而不是它实际的视觉表示。这是我们创建游戏世界统一视图的最后一步。为此，我们维护一个单独的缓冲区，该缓冲区存储我们已确定位置的每一帧的内容。
缓冲区的大小偶尔需要扩展，我们以活动窗口的高度/宽度增量进行扩展 - 取决于哪个维度需要扩展。由于我们的第一帧位置是*(0, 0)*，我们还保留了地图真实左上角的坐标。每次我们将地图向左顶部扩展时，都需要更新这些坐标。
当前帧的内容不能简单地粘贴到确定的位置，因为移动的物体会在地图上留下伪影。因此，我们没有只保留地图打印中的最新像素值，而是保留每个像素所有可能颜色的历史记录。由于我们使用的是有限数量的颜色，因此我们将这些值保存在一个简单的数组中。这里的想法是，数组的每个元素都保存一种颜色的权重。权重是根据某种颜色在该位置出现的次数计算的。每次观察到一种颜色时，其权重都会增加，但前提是未检测到该像素所属区域的运动。如果检测到运动，该颜色的权重将重置。
有两种生成实际像素值的方法：快速和流畅。快速方法仅选择权重最高的颜色，而流畅选项则使用相邻单元格中的值执行类似模糊的操作。
“Print”模块具有“update”函数，该函数使用当前帧更新地图打印，以及“plot”和“quickPlot”函数，它们将实际地图打印转换为图像。
将所有内容缝合在一起
我们的最后一步是组合前面讨论的所有内容。实现分为两个模块：
- “World”模块 - 定义“World”记录，它包含世界的草图（特征数据库）和地图打印。它还跟踪最后一个定位帧的位置。“update”函数负责用每一新帧更新世界：它定位帧，更新草图和地图打印。
- “Stitcher”模块 - 定义“loop”函数。它接收帧序列并运行算法的主循环，创建世界表示。它有三个步骤：
- 识别活动窗口。
- 创建游戏世界表示。
- 将地图打印绘制成实际图像。
辅助内容
以下模块定义了辅助数据类型和函数：
- “Primitive”模块 - 定义“Point”和“Rect”记录，用于表示世界中的位置和区域。
- “Palette”模块 - 定义一组函数，用于将不同调色板和格式的像素颜色进行转换。
- “Matrix”模块 - 定义“Matrix”类，它表示用于表示图像数据的矩阵，并提供初始化、调整大小等基本操作。
- “Image”模块 - 定义一组函数，用于将图像数据（存储为矩阵）转换为不同的调色板和格式。
- “Filter”模块 - 提供中值滤波器和模糊滤波器的实现。
- “Stitcher”模块 - 包含“IStitchingObserver”，可用于通知外部代码算法的进度。
未来工作和改进
正如文章开头所说，这只是一个概念验证，还需要大量工作才能在游戏进行时进行实时地图绘制，使其实用且可用。这是一个必需改进的简短列表：
- 代码优化 - 显而易见，我们无法实时处理世界地图绘制。
- 处理非重叠段 - 当前实现无法处理地图的不同非重叠段。如果我们突然“瞬移”到一个尚未绘制的世界的不同部分，我们会“迷失”。我们无法用该部分世界修补我们的地图。
- 包含移动物体 - 寻找一种跟踪移动物体并将其包含在最终地图打印中的方法。
- 改进伪影过滤 - 正如结果所示，我们无法过滤掉移动物体在我们地图上留下的所有痕迹。
希望未来的一些文章能解决这些问题。
历史
- 2020年7月29日：初始版本