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

[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;
    }
}