[Résolu] [Algo] Récupération de la zone de déplacement

[Tagu]

Bonjour,
Je bosse actuellement en javascript pour récupérer une zone de déplacement possible d'un joueur sur une carte. Ce joueur peut parcourir une certaine distance via des points sur la carte dont chaque tuile possède un malus pour la traverser.

J'ai réalisé un petit algorithme mais la complexité exponentielle et dépasser une certaine distance, mon navigateur favori me crie au scandale. Je voudrais donc l'améliorer avec votre aide ^^

Code :

var map = [
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,3,1],
    [1,1,3,1,1,1,3,1,3,1,1,1,3,1,1,1,1,1,2,1,1,1,2,1],
    [3,1,1,1,3,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,1,1,1,1],
    [1,1,2,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,3,1],
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,3,1],
    [1,1,3,1,1,1,3,1,3,1,1,1,3,1,1,1,1,1,2,1,1,1,2,1],
    [3,1,1,1,3,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,1,1,1,1],
    [1,1,2,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,3,1],
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,3,1],
    [1,1,3,1,1,1,3,1,3,1,1,1,3,1,1,1,1,1,2,1,1,1,2,1],
    [3,1,1,1,3,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,1,1,1,1],
    [1,1,2,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,3,1]
];
var zone = [];

function getMoveZone(x, y, point, from) {
    // On enlève le poids de la case courante
    point = point - map[y][x];
    if (point >= 0) {
        // Permet de vérifier si ce couple de coordonnées n'est pas déjà dans la liste
        var posNotInZone = true;
        for (var i = 0, l = zone.length; i < l; i++) {
            if (zone[i][0] === x && zone[i][1] === y) {
                posNotInZone = false;
            }
        }
        // On ajoute le couple de coordonnées
        if (posNotInZone) {
            zone.push([x,y]);
        }
        // On va à droite si la carte le permet
        // et si on ne vient pas deja de la droite
        if (x+1 < map[0].length && x+1 != from[0]) {
            getMoveZone(x+1,y,point,[x+1,y]);
        }
        // On va à gauche si la carte le permet
        // et si on ne vient pas deja de la gauche
        if (x-1 >= 0 && x-1 != from[0]) {
            getMoveZone(x-1,y,point,[x-1,y]);
        }
        // On desccend si la carte le permet
        // et si on ne vient pas deja d'en bas
        if (y+1 < map.length && y+1 != from[1]) {
            getMoveZone(x,y+1,point,[x,y+1]);
        }
        // On monte si la carte le veut ^^
        // et si on ne vient pas deja d'en haut
        if (y-1 >= 0 && y-1 != from[1]) {
            getMoveZone(x,y-1,point,[x,y-1]);
        }
        
    }
}

Merci.

[Tagu]

Juste pour signaler que j'ai modifié un peu l'algorithme. Au lieu de passer la dernière case visitée, je passe la liste des cases visitées. L'algorithme gagne un peu mais c'est pas flagrant.

[wild-D]

à mon avis tu devrais faire autrement^^

la tu travailles avec une fonction récursive qui a pour effet de te calculer le poids de tout les chemins. En allant direct jusqu'au bout du chemin.
Autant dire que tu dois exploser le nombre de récursion avec la longueur du chemin qui augmente

alors qu'il me semble qu'il faudrait plutot avancer par "cercle".
-> tous les chemin de poids 1 (cercle 1)
-> tous les chemins de poids total = 2 (cercle 2) (et biensûr tu retourne pas dans les cercles précédents)
-> tous les chemins de poids total = 3...

[Tagu]

Oui, le nombre de récursion est assez conséquent.
C'est une idée vers laquelle je vais me diriger.

Merci wild-D.

[Tagu]

Je tiens à remercier wild-D pour cette façon de voir les choses. Grâce à lui, j'ai pu finir un algorithme qui ne mets pas autant de temps que le précédent et sans que mon navigateur freeze.

Bien sur ma version est un peu crade mais je vais l'optimiser.

Code :

function getMoveZoneSquare(x,y,point) {
    
    function makeMove(x,y) {
        var moved = false;
        if (y >= 0 && x >= 0 && y < move.length && x+1 < move[0].length && move[y][x+1] != null) {
            if (move[y][x+1] > 0) {
                move[y][x] = Math.max(move[y][x], move[y][x+1] - map[y][x]);
                moved |= true;
            } else {
                var _a = null, _b = null;
                if (y > 0 && x+1 < move[0].length) {
                    _a = move[y-1][x+1] - map[y][x+1];
                }
                if (y+1 < move.length && x+1 < move[0].length) {
                    _b = move[y+1][x+1] - map[y][x+1];
                }
                move[y][x+1] = Math.max(_a, _b);
            }
        }
        if (y >= 0 && x > 0 && y < move.length && x < move[0].length && move[y][x-1] != null) {
            if (move[y][x-1] > 0) {
                move[y][x] = Math.max(move[y][x], move[y][x-1] - map[y][x]);
                moved |= true;
            } else {
                var _a = null, _b = null;
                if (y > 0 && x > 0) {
                    _a = move[y-1][x-1] - map[y][x-1];
                }
                if (y+1 < move.length && x > 0) {
                    _b = move[y+1][x-1] - map[y][x-1];
                }
                move[y][x+1] = Math.max(_a, _b);
            }
        }
        if (y > 0 && x >= 0 && y < move.length && x < move[0].length && move[y-1][x] != null) {
            if (move[y-1][x] > 0) {
                move[y][x] = Math.max(move[y][x], move[y-1][x] - map[y][x]);
                moved |= true;
            } else {
                var _a = null, _b = null;
                if (y > 0 && x > 0) {
                    _a = move[y-1][x-1] - map[y-1][x];
                }
                if (y > 0 && x+1 < move[0].length) {
                    _b = move[y-1][x+1] - map[y-1][x];
                }
                move[y][x+1] = Math.max(_a, _b);
            }
        }
        if (y >= 0 && x >= 0 && y+1 < move.length && x < move[0].length && move[y+1][x] != null) {
            if (move[y+1][x] > 0) {
                move[y][x] = Math.max(move[y][x], move[y+1][x] - map[y][x]);
                moved |= true;
            } else {
                var _a = null, _b = null;
                if (y+1 < move.length && x > 0) {
                    _a = move[y+1][x-1] - map[y+1][x];
                }
                if (y+1 < move.length && x+1 < move[0].length) {
                    _b = move[y+1][x+1] - map[y+1][x];
                }
                move[y][x+1] = Math.max(_a, _b);
            }
        }
        return moved;
    }
    
    // Création de la matrice de stockage des points
    var move = [];
    for (var i = 0, l = map.length; i < l; i++) {
        move.push([]);
        for (var j = 0, l = map[0].length; j < l; j++) {
            move[i].push(null);
        };
    };
    move[y][x] = point;
    
    var modif = true;
    var dist = 1;
    while (modif) {
        _modif = false;
        // Permet d'obtenir toutes les cases formant un carre incliné
        for (var i = 0, l = dist + 1; i < l; i++) {
            if (y+i < move.length && x-dist+i >= 0 && x-dist+i < move[0].length) {
                _modif |= makeMove((x-dist+i), (y+i));
            }
            if (y-i >= 0 && x-dist+i >= 0 && x-dist+i < move[0].length) {
                _modif |= makeMove((x-dist+i), (y-i));
            }
            if (y+1 < move.length && x+dist-i >= 0 && x+dist-i < move[0].length) {
                _modif |= makeMove((x+dist-i), (y+i));
            }
            if (y-i >= 0 && x+dist-i >= 0 && x+dist-i < move[0].length) {
                _modif |= makeMove((x+dist-i), (y-i));
            }
        };
        dist += 1;
        modif = _modif;
    }
}

[mdcarter]

Bonsoir tout le monde,
désolé d'intervenir mais je ne comprend absolument rien à ton script O_o
Peut tu m'en expliquer le concept assez rapidement ? Comment tu parcours les case, ce genre de choses