Optimisation algorithme déplacement d'une grille uniforme

Bonjour à tous,

Dans le cadre d’un monde pseudo-infinie que j’ai divisé en chunks pour ne pas l’avoir complètement chargé, je cherche à déplacer une grille uniforme qui me sert pour tester mes collisions par la suite. Sauf que le déplacement est un peu coûteux avec l’algorithme que j’ai écris et je n’ai pas trop d’idée comment l’optimiser

Voici la fonction en question :

void Grid::moveCenter(int mX, int mY) {
    int pixelGridSize = NB_ITEMS * 32;
    if (mX % pixelGridSize != 0 && mY % pixelGridSize != 0) return;

    int maxX = size.x / pixelGridSize;
    int maxY = size.y / pixelGridSize;

    glm::ivec2 topCorner = glm::ivec2(mX, mY) - size / 2 + pixelGridSize / 2;

    // erasing superfluous nodes
    for (auto it = nodes.begin(); it != nodes.end();) {
        glm::ivec2 nPos = (*it)->getPos();
        if (nPos.x >= topCorner.x + size.x || nPos.y >= topCorner.y + size.y ||
            nPos.x < topCorner.x || nPos.y < topCorner.y) {
            nodes.erase(it);
        } else {
            it++;
        }
    }

    // adding nodes not present yet
    for (int i = 0; i < maxX; i++) {
        for (int j = 0; j < maxY; j++) {
            glm::ivec2 nPos = topCorner + glm::ivec2(i * pixelGridSize, j * pixelGridSize);

            if (nPos.x >= pos.x + size.x || nPos.y >= pos.y + size.y || nPos.x < pos.x ||
                nPos.y < pos.y) {
                int index = i * maxY + j;
                auto it = nodes.begin();
                it += index;
                nodes.insert(
                    it, std::make_unique<GridNode>(manager, topCorner.x + i * pixelGridSize,
                                                   topCorner.y + j * pixelGridSize, pixelGridSize,
                                                   pixelGridSize));
            }
        }
    }

    pos.x = topCorner.x;
    pos.y = topCorner.y;
}

Merci d’avance pour les pistes que vous pourriez me donner

Merci pour vos réponses

La ligne 3 est fausse oui, merci

Nodes est un vector donc l’insertion et la suppression est en O(n) n étant le nombre d’éléments insérés/supprimés + les éléments à réorganiser par la suite (si j’ai bien compris la doc)

J’utilise un itérateur car je fais des suppressions. À ma connaissance, ça revient au même que d’utiliser une boucle for avec une variable i qui va de 0 à vector.size() (je me trompe peut-être)

Pour tes deux propositions :

• Je vais essayer la première en récupérant les GridNodes déjà créé de l’ancien tableau (sinon je perds la liste de points appartenant à cette node)
• Je ne vois pas vraiment l’intérêt de la deuxième comparé à ceux que je fais actuellement. Je suis pas sur que le calcul d’un index plus l’accès dans un vector soit plus long que d’accéder/de parcourir une map. Et parcourir une grille de 5x5 ou un tableau unidimensionnel de 25 éléments n’a-t-il pas le même coût ?

Une structure de hachage te permet de supprimer et d’insérer des éléments en temps (quasi)-constant, ou un arbre balancé ou un dictionnaire malin sur les entiers en temps logarithmique. Ça va être beaucoup, beaucoup plus rapide que ton approche où insérer ou supprimer un élément (ce que tu fais à la louche (mX+mY)*pixelGridSize fois) demande de décaler tous les éléments suivants dans le vecteur, ce qui rend ton algorithme cubique (au lieu de "quadratique avec de petits facteurs constants" avec l’approche (1), et "linéaire avec de plus gros facteurs constants" avec l’approche (2)).

Par ailleurs je n’ai pas réfléchi en profondeur mais j’ai du mal à me convaincre que ton code actuellement est correct: tu insères les nouveaux éléments à des indices qui sont des coordonnées par rapport à la nouvelle grille, mais les anciens éléments sont placés à des indices qui étaient calculés à partir des anciennes coordonnées… et en plus entre les suppressions et les ajouts les indices existants sont décalés !

En fait je pense que ce qui se passe, c’est que l’ordre des éléments dans la grille à l’arrivée est complètement faux (par rapport à la projection de deux dimensions en une dimension que tu as en tête), mais ce n’est pas grave puisque tu n’y accès pas par position (dans cette fonction), mais en testant p.x et p.y qui sont corrects, donc tu as bien les éléments que tu veux dans un certain ordre. Ça revient à utiliser un vecteur dynamique comme un ensemble (non ordonné) de points, et tu pourrais toujours ajouter les nouveaux points à la fin, ce serait équivalent mais plus rapide (mais la suppression resterait très lente, à moins de retirer intelligemment).

Salut !

Ligne 10, tu itères avec des itérateurs sur nodes et tu erase si une condition est remplie. Or erase invalide tout les itérateurs après ou en lieu de l’itérateur que tu lui fournis. Donc it est invalide à la prochaine itération.

@Vanadiae effectivement j’aurais du faire it = nodes.erase(it) mais étonnamment ça déconne pas et fonctionne sans problème

@gasche Le code que j’avais mis au dessus fonctionnait et me mettait les éléments dans le bon ordre. J’ai vérifié ^^. Je vais de l’indice le plus petit au plus grand lors de l’insertion donc je règle ce décalage au fur et à mesure. Et la boucle d’insertion se fait maxX * maxY fois

Enfin bref, au vu de ton premier post @gasche j’ai changé mon code pour qu’il corresponde à la première proposition (qui à le mérite d’être plus cours au moins) mais il m’augmente mon temps de frame dès que je l’exécute (moins qu’avant cependant). Je vais essayer de comprendre comment faire ta deuxième méthode

void Grid::moveCenter(int mX, int mY) {
    int pixelGridSize = NB_ITEMS * 32;
    if (mX % pixelGridSize != 0 || mY % pixelGridSize != 0) return;

    int maxX = size.x / pixelGridSize;
    int maxY = size.y / pixelGridSize;

    glm::ivec2 topCorner = glm::ivec2(mX, mY) - size / 2 + pixelGridSize / 2;

    std::vector<std::unique_ptr<GridNode>> newNodes;
    glm::ivec2 offset = (topCorner - pos) / pixelGridSize;
    int oldIndex = 0;

    for (int i = 0; i < maxX; i++) {
        for (int j = 0; j < maxY; j++) {
            oldIndex = (i + offset.x) * maxY + j + offset.y;
            if (oldIndex >= 0 && oldIndex < maxX * maxY) {  // get old node if exists
                newNodes.push_back(std::move(nodes[oldIndex]));
            } else {  // create new one
                newNodes.push_back(std::make_unique<GridNode>(
                    manager, topCorner.x + i * pixelGridSize, topCorner.y + j * pixelGridSize,
                    pixelGridSize, pixelGridSize));
            }
        }
    }

    nodes = std::move(newNodes);

    pos.x = topCorner.x;
    pos.y = topCorner.y;
}