Raytracing (LoS) sur les cartes de tuile hexagonale comme 3D

Question

Bonjour,

Je travaille sur un projet de jeu qui utilise une variante 3D de cartes de tuiles hexagonales. Les carreaux sont en fait des cubes, pas maléfices, mais sont disposés comme hexagones (car un carré peut être transformé en un cube pour extrapoler de la 2D à la 3D, mais il n'y a pas de version 3D d'un hexagone). Au lieu d'une description verbeux, va ici un exemple d'une carte de 4x4x4:

(j'ai mis en évidence une tuile arbitraire (vert) et ses tuiles adjacentes (jaune) pour aider à décrire comment la chose est censé fonctionner, mais les fonctions de contiguïté sont pas la question , qui est déjà résolu.)

J'ai un type struct pour représenter les tuiles et les cartes sont représentées sous forme de tableau 3D de tuiles (enveloppé dans une classe Map d'ajouter quelques méthodes utilitaires, mais ce n'est pas très pertinent). Chaque tuile est censé représenter un parfaitement cubage, et ils sont tous exactement de la même taille. En outre, le décalage entre les « lignes » adjacentes est exactement moitié de la taille d'une tuile.

Ce contexte est assez; ma question est:
Étant donné les coordonnées de deux points A et B, comment puis-je générer une liste des tuiles (ou plutôt leurs coordonnées) qu'une ligne droite entre A et B traverserait?

Ce serait plus tard utilisé pour des fins diverses, telles que la détermination de la ligne de visée, la légalité de chemin de charge, et ainsi de suite.

BTW, cela peut être utile: mes cartes utilisent (0,0,0) comme position de référence. Le « matage » de la carte peut être définie comme la compensation de chaque ((y+z) mod 2) * tileSize/2.0 de tuiles à droite de la position qu'elle avait eu sur un « sain d'esprit » cartésienne. Pour les rangées non déchiquetées, que les rendements 0; pour les lignes où (y+z) mod 2 est 1, on obtient 0,5 tuiles.

Je travaille sur C # 4 ciblant le Net Framework 4.0; mais je ne code spécifique vraiment pas besoin, juste l'algorithme pour résoudre le problème géométrique / mathématique bizarre. J'ai essayé pendant plusieurs jours pour résoudre ce sans succès; et en essayant de tirer le tout sur papier « visualisera » il n'a pas aidé non :(.

Merci d'avance pour toute réponse

Answer 1

Jusqu'à ce que l'un des Soers intelligent se présente, voici ma solution stupide. Je vais vous expliquer dans cos » 2D qui le rend plus facile à expliquer, mais il va généraliser 3D assez facilement. Je pense que toute tentative d'essayer de travailler ce entièrement dans l'espace d'index cellulaire est vouée à l'échec (bien que je l'avoue est juste ce que je pense et je suis impatient d'être mal prouvé).

Vous devez donc définir une fonction à la carte à partir des coordonnées cartésiennes aux indices cellulaires. Ceci est simple, si un peu délicat. Tout d'abord, décider si point(0,0) est le coin inférieur gauche de cell(0,0) ou du centre, ou un autre point. Comme il rend les explications plus facile, je vais aller avec coin inférieur gauche. Notez que toute point(x,floor(y)==0) cartes à cell(floor(x),0). En effet, toute point(x,even(floor(y))) cartes à cell(floor(x),floor(y)).

Ici, j'invente la fonction booléenne even qui retourne Vrai si son argument est un entier pair. Je vais utiliser odd suivant:. Tout point(x,odd(floor(y)) point cartes à cell(floor(x-0.5),floor(y))

Maintenant, vous avez les bases de la recette pour déterminer les lignes de visée.

Vous aurez également besoin d'une fonction de carte de retour de cell(m,n) à un point dans l'espace cartésien. Cela devrait être simple une fois que vous avez décidé où se trouve l'origine.

Maintenant, à moins que je l'ai égaré quelques parenthèses, je pense que vous êtes sur votre chemin. Vous devrez:

• décider où vous en cell(0,0) la position point(0,0); et ajuster en conséquence la fonction;
• décider où les points le long des limites cellulaires tombent; et
• généralise cela en 3 dimensions.

En fonction de la taille du terrain de jeu, vous pouvez stocker les coordonnées cartésiennes des limites des cellules dans une table de recherche (ou une autre structure de données), ce qui serait sans doute des choses à accélérer.

Answer 2

Peut-être que vous pouvez éviter tous les calculs complexes si vous regardez votre problème d'une autre manière:

Je vois que vous passez seulement vos blocs (en alternance) le long du premier axe de la moitié du blocksize. Si vous divisez vos blocs le long de cet axe l'exemple ci-dessus deviendra (avec des changements) un (9x4x4) simple, système de coordonnées cartésiennes avec des blocs empilés réguliers. Maintenant faire raytracing devient beaucoup plus simple et moins sujette aux erreurs.