MySQL 3D « Fill Flood » de mise en œuvre

J'ai une table MySQL avec la structure suivante:MySQL 3D « Fill Flood » de mise en œuvre

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;

Je veux deux requêtes de sélection qui peuvent trouver tous les voxels connectés donné un voxel de départ qui correspond à une condition spécifique. Un WHERE world = @world AND value > @minvalue AND property_id IS NULL et l'autre WHERE world = @world AND property_id = @property_id. L'algorithme de remplissage d'inondation utilisé doit être suffisamment rapide pour ne pas causer de retard notable (il sera utilisé sur un serveur de jeu). Il devrait également y avoir une boîte englobante centrée sur le voxel de départ dont la requête ne peut pas sortir. Sur l'axe y, cela passerait de 0 à @ymax. La valeur par défaut pour cela sera 31. Pour l'axe x et z, cela doit s'étendre à @hdistance à partir du de départ ou z.

Entrée

@world
@startx
@starty
@startz
@minvalue ou @property_id (dépend de ce que le programme cherche.)
@hdistance Par défaut: 13
@ymax Par défaut: 31

J'ai cherché sur Google, et n'ont pas trouvé une implémentation existante dans MySQL. Je ne comprends pas comment les algorithmes de remplissage d'inondation plus rapides et plus compliqués fonctionnent pour tenter d'écrire ceci par moi-même.

Source

2015-09-27 Ruby

La saturation rapide ne doit PAS être implémentée dans SQL. Vous pouvez charger toutes les données nécessaires à votre application vers des structures appropriées (probablement une représentation graphique ou un tableau 3d en fonction de la densité de vos données) et exécuter la pile/file ou toute autre implémentation que vous pouvez écrire dans le langage de programmation.Flood-fill est par définition récursif (même lorsqu'il est souvent implémenté par des boucles) et SQL n'est pas bon en récursivité ni avec des boucles. – jkavalik

@jkavalik Bon point. J'ai d'abord pensé que ce serait plus rapide si mysql faisait ce genre de traitement. Pouvez-vous republier cela comme une réponse pour que je puisse le marquer comme accepté? – Ruby

La saturation rapide ne doit PAS être implémentée dans SQL. Vous pouvez charger toutes les données nécessaires à votre application vers des structures appropriées (probablement une représentation graphique ou un tableau 3d en fonction de la densité de vos données) et exécuter la pile/file ou toute autre implémentation que vous pouvez écrire dans le langage de programmation. Flood-fill est par définition récursif (même lorsqu'il est souvent implémenté par des boucles) et SQL n'est pas bon en récursivité ni avec des boucles.

Mais il y a quelque chose qui pourrait être utilisé dans mysql, même si ce n'est pas une solution SQL normale. Il y a un moteur spécial pour gérer les graphiques - OQGRAPH. Il est disponible dans MariaDB et pourrait être installable sur MySQL probablement.

Il supporte le stockage efficace de graphes combinatoires dont une grille est juste un cas particulier et il peut calculer les chemins les plus courts et l'accessibilité. De la page d'exemples il connaît dijkstras et breadth_first - ce dernier devrait être utilisable comme une mise en œuvre de remplissage d'inondation. En fonction de vos besoins, vous devriez être capable d'écrire quelque chose de plus performant, car vous pouvez l'adapter à votre besoin spécifique. Mais si vous voulez expérimenter et comparer plus d'implémentation, vous pouvez l'essayer.

Source

2015-10-03 05:26:30 jkavalik

MySQL 3D « Fill Flood » de mise en œuvre

Répondre

Questions connexes