+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : [Résolu] [Algo] Récupération de la zone de déplacement (/showthread.php?tid=3480)
[Résolu] [Algo] Récupération de la zone de déplacement - Tagu - 27-12-2008
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.
RE: [Algo] Récupération de la zone de déplacement - Tagu - 29-12-2008
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.
RE: [Algo] Récupération de la zone de déplacement - wild-D - 29-12-2008
à 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...
RE: [Algo] Récupération de la zone de déplacement - Tagu - 29-12-2008
Oui, le nombre de récursion est assez conséquent.
C'est une idée vers laquelle je vais me diriger.
Merci wild-D.
RE: [Algo] Récupération de la zone de déplacement - Tagu - 29-12-2008
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;
}
}RE: [Résolu] [Algo] Récupération de la zone de déplacement - mdcarter - 23-01-2009
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
