Je développe une sorte de jeu 2D / 3D basé sur la perspective en javascript.
J'ai un axe X et un axe Y comme je l'ai affiché dans l'image ci-dessous .
À ma question: J'ai un tas d'objets (marqués de "1" et "2") sur ma carte avec des propriétés telles que: p>
Dans l'image, l'objet "1" obtient les coordonnées x: 3, y: 2 , et l'objet "2" obtient les coordonnées x: 5, y: 4 . SizeX et sizeY sont w: 1, h: 1 pour les deux objets.
Ce que j'aimerais faire avec cette information est de trier tous les objets par ordre croissant ( en fonction de la position et de la taille des objets) pour savoir en 3D quels objets viennent pour un autre objet pour dessiner ultérieurement tous mes objets triés dans ma toile (objets au premier plan / background = "calques").
Remarque: la caméra doit être en position fixe - disons que la caméra a la même valeur X et Y afin que la position de la caméra ne soit pas utilisée lors du calcul CameraX = CameraY .
Ce que j'ai essayé jusqu'à présent:
let objects = [
{
name: "objectA",
x: 8,
y: 12,
w: 2,
h: 2
},
{
name: "objectB",
x: 3,
y: 5,
w: 2,
h: 2
},
{
name: "objectC",
x: 6,
y: 2,
w: 1,
h: 3
}
]
let sortObjects = (objects) => {
return objects.sort((a, b)=> {
let distanceA = Math.sqrt(a.x**2 + a.y**2);
let distanceB = Math.sqrt(b.x**2 + b.y**2);
return distanceA - distanceB;
});
}
let sortedObjects = sortObjects(objects);
console.log(sortedObjects);
// NOTE in 3d: first Object drawn first, second Object drawn second and so on...
Modifiez l'extrait de code ci-dessus:
J'ai essayé de trier les objets en fonction de leur coordonnée x / y, mais cela ressemble à Les paramètres de largeur et de hauteur doivent également être utilisés lors du calcul pour éviter les erreurs.
Comment dois-je utiliser la largeur / hauteur? Tbh je n'ai aucune idée, donc toute aide serait vraiment appréciée.
5 Réponses :
Le problème ici est que vous utilisez la distance euclidienne pour mesurer la distance entre un objet et (0, 0) , pour essayer de mesurer la distance depuis le y = -x ligne. Cela ne fonctionnera pas, mais la distance de Manhattan le sera.
let sortObjects = (objects) => {
return objects.sort((a, b)=> {
let distanceA = a.x + a.y;
let distanceB = b.x + b.y;
return distanceA - distanceB;
});
}
Cela ordonnera vos objets verticalement dans votre système de coordonnées pivoté.
Merci pour votre réponse. Mais je dois être tout à fait honnête: cette réponse ne semble pas être vraie. Lorsque je calcule la distance de Manhattan, cela fonctionne partiellement, tout comme je l'ai calculé avec la distance euclidienne. Cependant, cela ne fonctionne pas dans tous les cas. J'ai donc ajouté que la raison de l'erreur est que je n'ai pas calculé avec la largeur et la hauteur des objets. Et je le pense toujours. Je suis content de votre réponse. Merci d'avance.
Je dois mal comprendre la question. Les objets peuvent-ils avoir différentes tailles? Si oui, où les images sont-elles ancrées (au centre, en haut à gauche, etc.)?
@ jonas00 J'ai juste du mal à voir où cela ne fonctionnerait pas, à condition que cameraX == cameraY , et (en supposant) que tous les objets aient une hauteur / largeur fixe
Ouais. Mais dans mon système de coordonnées pivoté, les couches sont en quelque sorte connectées à la largeur et à la hauteur des objets. Tous les objets peuvent avoir des tailles différentes, ce qui brisera votre / mon algorithme de tri. Et je suis presque sûr que cette solution ne fonctionne pas exactement comme elle le devrait :(
@ jonas00 les objets "se déplacent-ils" dans leurs rangées pour accueillir de l'espace pour des objets plus grands? Vos sprites ne sont-ils pas dessinés avec leurs centres à (x, y) ? Je ne comprends vraiment pas comment les largeurs / hauteurs des sprites changent le positionnement relatif. Pour moi, il semble qu'un sprite plus petit atterrirait toujours dans la même ligne horizontale qu'un sprite de taille normale.
@ jonas00 Je pourrais peut-être comprendre le problème maintenant. Vous dites qu'un objet peut s'étendre sur le rectangle (x: 0, y: 0) à (x: 1, y: 2) , et ainsi il serait positionné selon (x : (0 + 1) / 2, y: (0 + 2) / 2) = (0.5, 1) , mais cela peut entraîner des objets à peine en dessous (et à gauche ou à droite) être trié au-dessus.
Si tel est le cas, il n'est pas possible de résoudre avec votre méthodologie actuelle. Il n'existe aucune fonction de comparaison qui vous permettra de faire un tri basé sur la comparaison pour ordonner ces éléments, car cela violerait l'inégalité triangulaire. Exemple: carré (x: 0, y: 5), rectangle (x: 1, y: 5) à (x: 2, y: 5), carré (x: 3, y: 0). Le premier est au-dessus du second, le second au-dessus du troisième, mais le troisième est au-dessus du premier. Vous devrez repenser complètement votre algorithme.
Dans votre diagramme, considérez la valeur de x + y pour chaque cellule
Pour trier de haut en bas les cellules, vous pouvez simplement trier sur la valeur de x + y .
C'est exactement ce que fait mon code, mais OP prétend que cela ne fonctionne pas.
@DillonDavis: Je sais ... j'espérais que montrer un diagramme le rendrait clair
Mais un objet pourrait aller de (x: 0, y: 0) à (x: 1, y: 2) donc je ne peux pas trier les objets par leur position x / y comme le fait @DillonDavis, car c'est absolument faux. Le paramètre X / Y représente le point central de la zone.
@ jonas00: ce que vous devez vous demander est ... "est-ce que quelque chose de construit sur un carré marqué 3 peut cacher quelque chose sur un carré marqué 4?" ... (ou un autre marqué 3)
Je ne sais pas trop ce que vous entendez par:
Remarque: la caméra doit avoir une position fixe - disons que la caméra a la même valeur X et Y afin que la position de la caméra ne soit pas utilisée lors du calcul CameraX = CameraY.
Voici donc une solution au cas général.
Vous devez trier les objets en fonction de leur distance la plus proche de la caméra. Cela dépend des dimensions d'un objet ainsi que de sa position relative.
L'algorithme peut être implémenté dans JS comme suit:
// If e.g. horizontal distance > width / 2, subtract width / 2; same for vertical
let distClamp = (dim, diff) => {
let dist = Math.abs(diff);
return (dist > 0.5 * dim) ? (dist - 0.5 * dim) : dist;
}
// Closest distance to the camera
let closestDistance = (obj, cam) => {
let dx = distClamp(obj.width, obj.x - cam.x);
let dy = distClamp(obj.height, obj.y - cam.y);
return Math.sqrt(dx * dx + dy * dy);
}
// Sort using this as the metric
let sortObject = (objects, camera) => {
return objects.sort((a, b) => {
return closestDistance(a, camera) - closestDistance(b, camera);
});
}
EDIT cette solution ne fonctionne pas non plus car elle fait des hypothèses naïves, sera bientôt mise à jour ou supprimée.
Je pense que cette solution semble plutôt bonne. Surtout parce que vous utilisez la largeur et la hauteur pour le calcul. J'ai intégré votre algorithme dans mon code ... Bref, cette approche ne semble pas fonctionner non plus. Dans de nombreux cas, la fonction de calque fonctionne parfaitement (même si je devais permuter la distance la plus proche (a, caméra) - la distance la plus proche (b, caméra)), mais il existe de nombreuses exceptions où cela ne fonctionne pas comme il se doit ...
... Si je me tiens devant un objet (sizeX: 1, sizeY: 2) sur le côté droit, je suis peint en tant que joueur derrière l'objet plutôt que devant lui. De l'autre côté, cela semble fonctionner sans aucun problème.
@ jonas00 Pouvez-vous donner les coordonnées et les dimensions du lecteur et de l'objet, ainsi que les coordonnées de la caméra? Je ne vois pas comment ce problème devrait se poser.
Sûr! Player : {x: 7.16, y: 10.25, largeur: 0.2, hauteur: 0.2} , Object : {x: 6.66 , y: 11,44, largeur: 0,3, hauteur: 1,6} . J'ai localisé ma caméra à x: 100, y: 100 . L'endroit où se trouve mon appareil photo ne fera aucune différence car x et y sont identiques à tout moment. Ainsi, x: 200, y: 200 serait également valide.
@ jonas00 ah Je réalise ce qui ne va pas maintenant, excuses. J'ai totalement oublié qu'une approche simple comme celle-ci ne fonctionnera pas car elle ne prend pas en compte l'orientation des plans d'objets. Je republierai ou supprimerai.
D'accord. Merci beaucoup d'avance.
@ jonas00 juste une autre question - effectuez-vous le rendu en perspective ou en vue orthogonale? J'ai un algorithme possible en tête
Salut @meowgoesthedog. Désolé de demander si stupidement - mais avez-vous une idée de la façon dont je peux passer à autre chose? Je ne sais toujours pas comment continuer et vous avez écrit que vous aviez une autre approche. Salutations
Peut-être que vous pouvez trouver quelque chose d'utile ici (utilisez Firefox et vérifiez le DEMO )
Dans mon cas, la profondeur est essentiellement pos.x + pos.y [assetHelper.js -> get depth () {...] exactement comme la première réponse le décrit. Ensuite, le tri est une simple comparaison [canvasRenderer -> depthSortAssets () {...]
D'accord, allons-y! Nous devrons ordonner ces objets non pas par distance, mais par obstruction. Par cela, je veux dire pour deux objets A et B, A peut visiblement obstruer B, B peut visiblement obstruer A, ou aucun des deux ne fait obstruction à l'autre. Si A obstrue B, nous voudrons d'abord dessiner B, et vice-versa. Pour résoudre ce problème, nous devons être en mesure de dire si A obstrue B ou l'inverse.
Voici ce que j'ai trouvé. Je n'avais qu'une capacité limitée pour tester cela, donc il peut encore y avoir des défauts, mais le processus de réflexion est sain.
Étape 1. Mappez chaque objet à ses limites, en sauvegardant l'objet d'origine pour plus tard: p>
results = objects.map(o => {
const xmin = o.x,
xmax = o.x + o.w,
ymin = o.y,
ymax = o.y + o.h;
const [closestX, farthestX] = [xmin, xmax].sort((a, b) => Math.abs(camera.x - a) - Math.abs(camera.x - b));
const [closestY, farthestY] = [ymin, ymax].sort((a, b) => Math.abs(camera.y - a) - Math.abs(camera.y - b));
return {
original: o,
x1: closestX,
y1: xmin <= camera.x && camera.x <= xmax ? closestY : farthestY,
x2: ymin <= camera.y && camera.y <= ymax ? closestX : farthestX,
y2: closestY
};
}).sort((a, b) => {
const camSegmentA1 = {
x1: camera.x,
y1: camera.y,
x2: a.x1,
y2: a.y1
};
const camSegmentA2 = {
x1: camera.x,
y1: camera.y,
x2: a.x2,
y2: a.y2
};
const camSegmentB1 = {
x1: camera.x,
y1: camera.y,
x2: b.x1,
y2: b.y1
};
const camSegmentB2 = {
x1: camera.x,
y1: camera.y,
x2: b.x2,
y2: b.y2
};
// Intersection function taken from here: https://stackoverflow.com/a/24392281
function intersects(seg1, seg2) {
const a = seg1.x1, b = seg1.y1, c = seg1.x2, d = seg1.y2,
p = seg2.x1, q = seg2.y1, r = seg2.x2, s = seg2.y2;
const det = (c - a) * (s - q) - (r - p) * (d - b);
if (det === 0) {
return false;
} else {
lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;
gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;
return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
}
}
function squaredDistance(pointA, pointB) {
return Math.pow(pointB.x - pointA.x, 2) + Math.pow(pointB.y - pointA.y, 2);
}
if (intersects(camSegmentA1, b) || intersects(camSegmentA2, b)) {
return -1;
} else if (intersects(camSegmentB1, a) || intersects(camSegmentB2, a)) {
return 1;
}
return Math.max(squaredDistance(camera, {x: b.x1, y: b.y1}), squaredDistance(camera, {x: b.x2, y: b.y2})) - Math.max(squaredDistance(camera, {x: a.x1, y: a.y1}), squaredDistance(camera, {x: a.x2, y: a.y2}));
}).map(o => o.original);
Étape 2. Mappez chaque objet sur les deux coins qui, lorsqu'une ligne est tracée entre eux, forment le plus grand obstacle au champ de vision de la caméra:
let results = step3.map(o => o.original);
Étape 3. Triez les objets. Tracez un segment de ligne de la caméra à chaque extrémité d'un objet. Si le segment de ligne entre les extrémités de l'autre objet se croise, l'autre objet est plus proche et doit être dessiné après.
let step3 = step2.sort((a, b) => {
const camSegmentA1 = {
x1: camera.x,
y1: camera.y,
x2: a.x1,
y2: a.y1
};
const camSegmentA2 = {
x1: camera.x,
y1: camera.y,
x2: a.x2,
y2: a.y2
};
const camSegmentB1 = {
x1: camera.x,
y1: camera.y,
x2: b.x1,
y2: b.y1
};
const camSegmentB2 = {
x1: camera.x,
y1: camera.y,
x2: b.x2,
y2: b.y2
};
// Intersection function taken from here: https://stackoverflow.com/a/24392281
function intersects(seg1, seg2) {
const a = seg1.x1, b = seg1.y1, c = seg1.x2, d = seg1.y2,
p = seg2.x1, q = seg2.y1, r = seg2.x2, s = seg2.y2;
const det = (c - a) * (s - q) - (r - p) * (d - b);
if (det === 0) {
return false;
} else {
lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;
gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;
return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
}
}
function squaredDistance(pointA, pointB) {
return Math.pow(pointB.x - pointA.x, 2) + Math.pow(pointB.y - pointA.y, 2);
}
if (intersects(camSegmentA1, b) || intersects(camSegmentA2, b)) {
return -1;
} else if (intersects(camSegmentB1, a) || intersects(camSegmentB2, a)) {
return 1;
} else {
return Math.max(squaredDistance(camera, {x: b.x1, y: b.y1}), squaredDistance(camera, {x: b.x2, y: b.y2})) - Math.max(squaredDistance(camera, {x: a.x1, y: a.y1}), squaredDistance(camera, {x: a.x2, y: a.y2}));
}
});
Étape 4. Dernière étape - obtenir les objets d'origine en arrière, triés par ordre du plus éloigné au plus proche:
let step2 = step1.map(o => {
const [closestX, farthestX] = [o.xmin, o.xmax].sort((a, b) => Math.abs(camera.x - a) - Math.abs(camera.x - b));
const [closestY, farthestY] = [o.ymin, o.ymax].sort((a, b) => Math.abs(camera.y - a) - Math.abs(camera.y - b));
return {
original: o.original,
x1: closestX,
y1: o.xmin <= camera.x && camera.x <= o.xmax ? closestY : farthestY,
x2: o.ymin <= camera.y && camera.y <= o.ymax ? closestX : farthestX,
y2: closestY
};
});
Maintenant, pour tout rassembler:
let step1 = objects.map(o => ({
original: o,
xmin: o.x,
xmax: o.x + o.w,
ymin: o.y,
ymax: o.y + o.h
}));
Laissez-moi sachez si cela fonctionne!
@ jonas00 Je vois le problème: je testais si les segments de ligne de la caméra se croisaient avec l'autre ligne SEGMENT, alors que j'aurais dû tester si elle intersecte avec l'autre LINE. J'ai édité mon code. Ça marche maintenant?
@ jonas00 Fixé! Il y avait un bogue dans ma nouvelle approche pour trouver les intersections, je suis donc revenu à la méthode précédente en utilisant les intersections de segment et j'ai ajouté des vérifications pour le cas qui était mal géré. J'ai aussi réalisé en jouant avec votre JSFiddle que les objets ne sont pas centrés sur leurs coordonnées. Les coordonnées sont le coin supérieur gauche. J'ai modifié mon code dans ma réponse, et j'ai également modifié votre JSFiddle: jsfiddle.net/4z9bcu7o Les lignes de la caméra aux objets sont montrés à des fins de test. Notez également que vous devrez peut-être ajuster la position de votre caméra.
@ jonas00 Merci! Heureux d'avoir pu aider!
Jupyy. L'exemple fonctionne parfaitement - bon travail bro. Mais maintenant, j'ai testé votre code dans mon jeu - il ne fonctionne pas comme il se doit. Un millier de remerciements pour votre aide de toute façon - je vous accorde la prime même s'il reste quelques bugs que je viens de remarquer maintenant. Mhm. :)
@ jonas00 Quels sont les bugs maintenant? Quelle disposition des objets est mal dessinée? Je suis curieux de savoir quels scénarios je n’ai pas anticipé et comment mon code peut être corrigé.
Si tout ce que vous voulez faire est de trier vos objets dans l'ordre inverse à des fins de rendu (le soi-disant algorithme du peintre), pourquoi ne pas implémenter un arbre BSP. L'arbre BSP garantit un tri parfait, mais vous devrez faire des compromis ...