MySQL 3D "Flood Fill" 实施

Question

我有一个 MySQL table 结构如下：

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;

我想要两个 select 查询，它们可以在给定匹配特定条件的起始体素的情况下找到所有连接的体素。一个 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 数组，具体取决于数据的密度）和运行 stack/queue 或您可以在中编写的任何其他实现手边的编程语言。 Flood-fill 根据定义是递归的（即使它通常由循环实现）并且 SQL 不擅长递归或循环。

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

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

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

MySQL 3D "Flood Fill" 实施

MySQL 3D "Flood Fill" Implementation

mysql

flood-fill