MySQL 3D "Flood Fill"实现

Question

我有一个具有以下结构的 MySQL 表:

CREATE TABLE IF NOT EXISTS `np_voxels` (
  `world` VARCHAR(16) NOT NULL,
  `x` INT NOT NULL,
  `y` INT NOT NULL,
  `z` INT NOT NULL,
  `value` DOUBLE NOT NULL DEFAULT 0,
  `property_id` INT NULL,
  PRIMARY KEY (`world`, `x`, `y`, `z`) ,
  INDEX `np_fk_voxels_properties_idx` (`property_id` ASC) ,
  CONSTRAINT `np_fk_voxels_properties`
    FOREIGN KEY (`property_id`)
    REFERENCES `np_properties` (`property_id`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
ENGINE = InnoDB;

我想要两个选择查询，它们可以在给定匹配特定条件的起始体素的情况下找到所有连接的体素。一个 WHERE world = @world AND value > @minvalue AND property_id IS NULL ，另一个 WHERE world = @world AND property_id = @property_id。使用的洪水填充算法应该足够快，不会导致明显的延迟(这将在游戏服务器上使用)。还应该有一个以起始体素为中心的边界框，查询不能超出该边界框。在 y 轴上，这将从 0 到 @ymax。默认值为 31。对于 x 和 z 轴，这应该从起始 x 或 z 延伸出 @hdistance .

输入

• @world
• @startx
• @starty
• @startz
• @minvalue 或 @property_id(取决于程序要查找的内容。)
• @hdistance 默认值:13
• @ymax 默认:31

我在 Google 上搜索过，但没有找到 MySQL 中现有的实现。我不明白更快、更复杂的洪水填充算法如何工作来尝试自己编写这个。

Answer 1

快速洪水填充不应在 SQL 中实现。您可以将所有需要的数据加载到应用程序中，以适当的结构(可能是一些图形表示或 3d 数组，具体取决于数据的密度)，并运行堆栈/队列或您可以用现有编程语言编写的任何其他实现。根据定义，Flood-fill 是递归的(即使它经常通过循环实现)，而 SQL 不擅长递归，也不擅长循环。

但是有一些东西可以在 mysql 中使用，即使它不是一个正常的 SQL 解决方案。有一个特殊的引擎来处理图形 - OQGRAPH 。它在 MariaDB 中可用，并且可能可以安装到 MySQL。

它支持组合图的有效存储，其中网格只是一个特例，它可以计算最短路径和可达性。从示例页面中它知道 dijkstras 和 breadth_first - 后者应该可用作洪水填充实现。

根据您的需求，您应该能够编写性能更高的东西，因为您可以根据您的特定需求对其进行定制。但如果你想尝试和比较更多的实现，你可以尝试一下。