Comment rendre mon algorithme de remplissage d'inondation plus efficace?

Question

J'ai une fonction de remplissage d'inondation dans mon code qui renvoie juste un nombre sur les cellules remplies. Mais il est atrocement lent, mon algorithme de recherche de chemin A * est exponentiellement plus rapide que lui. Voici l'extrait:

bool withinBoundaries(_2D::Point p) { 
//cerr << "Checking if x: " << p.x << " y: " << p.y << " is within boundaries" << endl; 
if (p.x <= 29 && p.y <= 19 && p.x >= 0 && p.y >= 0) { 
    return true; 
} 
return false; 
} 


bool canMove(_2D::Point point, _2D::Point offset, map<pair<int, int>, bool> gameGrid) { 
if (!gameGrid[(point + offset).toPair()] && withinBoundaries(point + offset)) return true; 
else return false; 
} 

int floodFillGetArea(_2D::Point point, map<pair<int, int>, bool> gameGrid) { 
    map<pair<int, int>, bool> checked; 
    map<pair<int, int>, bool> gameGridCopy = gameGrid; 
    deque<_2D::Point> openPoints; 
    openPoints.push_back(point); 
    int count = 0; 

    while (!openPoints.empty()) { 
    _2D::Point curPoint = openPoints.back(); 
    openPoints.pop_back(); 
    if(checked[curPoint.toPair()]) break; 
    gameGridCopy[curPoint.toPair()] = true; 
    count++; 
    if (canMove(curPoint, _2D::Point::UP(), gameGridCopy)) { 

     openPoints.push_back(curPoint + _2D::Point::UP()); 
    } 
    if (canMove(curPoint, _2D::Point::RIGHT(), gameGridCopy)) { 
     openPoints.push_back(curPoint + _2D::Point::RIGHT()); 
    } 
    if (canMove(curPoint, _2D::Point::DOWN(), gameGridCopy)) { 
     openPoints.push_back(curPoint + _2D::Point::DOWN()); 
    } 
    if (canMove(curPoint, _2D::Point::LEFT(), gameGridCopy)) { 
     openPoints.push_back(curPoint + _2D::Point::LEFT()); 
    } 
    checked[curPoint.toPair()] = true; 
} 
return count; 
} 

Ceci vérifie un nœud toutes les secondes, pourquoi est-il si lent? Et _2D :: Point est juste un objet avec int x et int y. Aussi, il crée des hochements de tête ouverts quand ils sont déjà étiquetés comme étant vérifiés, pourquoi?

Answer 1

Pour le démarreur, vous copiez un objet std::map 6 fois pour rien.

Essayez de passer l'objet carte comme référence const plutôt que de passer par la valeur (= copie)

Answer 2

Pouvez-vous essayer avec un tableau 2D de booléens au lieu d'une carte (qui prend O (log N) opérations à regarder up) pour l'objet "gameGrid"? Peut-être que passer à une table de hachage pourrait donner des performances similaires si un tableau n'est pas une option?

S'il y a 1024 points dans une carte, cela devrait multiplier la vitesse de référence par 10-11. Si cela ne suffit pas, vous pouvez avoir plusieurs threads et plusieurs étapes (synchronisation) pour calculer 1, 4, 16, 20, 20, 20, 16, 4, 1, 1, 4, 16, 2, 4 ... tuiles à la fois et finir plus vite.

Essayez quelque chose comme ça (scanline remplir?) Sur le tableau:

while(canMove(right)){enqueue} // Sequential memory access 
    reset horizontal pos, enable reverse prefetching 
    while(canMove(left)){enqueue} // Sequential memory access 

.... 

    then repeat for verticals 

Recommencez ensuite avec une alternance de calculs horizontal + vertical jusqu'à ce que fait. Ce modèle devrait donner un multiplicateur de performance de la mémoire x2, et en plus de cela une mise à niveau du timing d'accès au réseau 10-11x, car il n'aura pas accès aux structures (paire) de la mémoire, juste un seul octet. D'une autre manière, vous pouvez également démarrer plusieurs points de remplissage à des endroits aléatoires et itérer jusqu'à ce que l'un d'entre eux touche le flot original, ajouter ses points à la zone des points d'origine, déplacer tout son fil de flot initial et à la fin toutes les inondations non-touchantes. Cela pourrait utiliser le cache plus souvent peut-être? Mais il faut plus de noyaux. Essayer aussi une version de gpgpu ne ferait pas de mal.

Remarque: Ceci impliquerait implicitement une autre optimisation suggérée par @David Haim. Avec toutes ces optimisations, vous devez voir l'accélération exponentielle que vous avez mentionné à propos de votre algorithme A *.