+- 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] Génération d'un graphe respectant un visuel (/showthread.php?tid=4580)
RE: Génération d'un graphe respectant un visuel - Sephi-Chan - 11-02-2010
J'ai du mal à cerner ce que tes X et Y désignent. Quelle est l'origine ?
Merci à ceux qui se penchent sur mon problème. :p
Sephi-Chan
RE: Génération d'un graphe respectant un visuel - NicoMSEvent - 11-02-2010
j'ai remplacé les chiffres dans tes boules (les coordonées?) par x,y au lieu de 0,0 (pour la boule centrale)
RE: Génération d'un graphe respectant un visuel - Sephi-Chan - 11-02-2010
Ah okay !
Ma notation indique l'index de l'anneau et l'index de la sphère sur l'anneau (en prenant comme origine le haut de l'anneau puis en circulant dans le sens horaire).
Ce que tu proposes semble applicable directement, dans mon cas. Je vais faire quelques essais et je vous tiens au courant.
Pour expliciter un peu plus mon besoin, cette figure représente un quartier d'une ville. Chaque sphère est un emplacement de bâtiment.
Je pense avoir besoin d'un graphe car j'aurais besoin d'accéder aux sphères voisines pour calculer la valeur du terrain, ou pour savoir s'il y a une source d'eau dans les environs, ou encore pour savoir s'il y a un bâtiment adjacent à la case où l'on veut construire, etc.
Sephi-Chan
RE: Génération d'un graphe respectant un visuel - NicoMSEvent - 11-02-2010
(11-02-2010, 12:32 PM)Sephi-Chan a écrit : Pour expliciter un peu plus mon besoin, cette figure représente un quartier d'une ville. Chaque sphère est un emplacement de bâtiment.en fait, ça ressemble fort à un problème de cartographie, tu pourrais remplacer la valeur d'un terrain par une altitude, et appliquer un lissage dessus, et rajouter un peu de "bruit" (histoire que deux propriétés proches n'ai pas un ecart de prix ton éloigné, et le bruit pour que tu ai une part faible d'aléatoire dans tes valeurs)
Je pense avoir besoin d'un graphe car j'aurais besoin d'accéder aux sphères voisines pour calculer la valeur du terrain, ou pour savoir s'il y a une source d'eau dans les environs, ou encore pour savoir s'il y a un bâtiment adjacent à la case où l'on veut construire, etc.
RE: Génération d'un graphe respectant un visuel - pascal - 11-02-2010
C'est pour un nouveau jeu ?
RE: Génération d'un graphe respectant un visuel - Sephi-Chan - 11-02-2010
NicoMSEvent, ça ressemble effectivement à de la cartographie : je cherchais une manière originale de représenter une carte sans avoir besoin de beaucoup d'éléments graphiques.
(11-02-2010, 12:42 PM)pascal a écrit : C'est pour un nouveau jeu ?
Peut-être. J'ai pas de machine ces jours-ci, donc pour pas rester passif en terme de création de jeux, je réfléchis.
Sephi-Chan, qui retourne à ses expérimentations !
RE: Génération d'un graphe respectant un visuel - Sephi-Chan - 11-02-2010
En fait, les coordonnées des 6 éléments (au maximum) qui composent le voisinage d'une sphère change selon que cette sphère est sur un axe ou non.
Donc, je peux déjà écrire ce code :
class Sphere
attr_reader :index, :ring_index
def initialize(ring, index)
@ring = ring
@index = index
end
# Return true if the sphere is on the x or y axe.
def on_axe?
return true if @index == 0
return true if @ring == @index
return true if @ring == @index * 2
return true if @ring == @index * 3
false
end
end
class Graph
attr_reader :grid
def initialize(grid)
@graph = grid
end
def neighbours(ring_index, index)
sphere = sphere_at_coordinates(ring_index, index)
neighbours = if sphere.on_axe?
[
sphere_at_coordinates(sphere.ring_index - 1, sphere.index),
sphere_at_coordinates(sphere.ring_index, sphere.index - 1),
sphere_at_coordinates(sphere.ring_index, sphere.index + 1),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index - 1),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 1)
]
else
# Trouver les relations comme plus haut, mais pour les sphères situées hors des axes.
[
]
end
neighbours.delete_if { |sphere| sphere.nil? }
end
# Return the sphere at the given coordinates or nil.
# Handle "outs of bounds" positions.
def sphere_at_coordinates(ring_index, index)
max_index_for_ring = @grid[ring_index].size - 1
if max_index_for_ring < index
# Et maintenant ? Il y a une histoire de modulo pour faire abstraction de l'index demandé.
else
# ...
end
nil
end
end
J'ai donc encore 2 tâches à gérer : faire abstraction de l'index demandé (quand on demande un index plus élevé que l'index maximum de l'anneau) et déterminer les coordonnées des voisins pour les sphères situées hors des axes.
Sephi-Chan
RE: Génération d'un graphe respectant un visuel - NicoMSEvent - 11-02-2010
héhé, ça avance
je n'ai pas compris ce qu'était un axe...
RE: Génération d'un graphe respectant un visuel - Sephi-Chan - 11-02-2010
Ce que j'appelle les axes sont les deux lignes (l'une verticale, l'autre horizontale) qui passent par le centre de la sphère centrale.
Voilà un essai pour les coordonnées des sphères qui ne sont pas sur un axe :
def neighbours(ring_index, index)
sphere = sphere_at_coordinates(ring_index, index)
neighbours = if sphere.on_axe?
[
sphere_at_coordinates(ring_index - 1, index),
sphere_at_coordinates(ring_index, index - 1),
sphere_at_coordinates(ring_index, index + 1),
sphere_at_coordinates(ring_index + 1, index - 1),
sphere_at_coordinates(ring_index + 1, index),
sphere_at_coordinates(ring_index + 1, index + 1)
]
else
[
sphere_at_coordinates(ring_index - 1, index - ring_index - 1)
sphere_at_coordinates(ring_index - 1, index - ring_index)
sphere_at_coordinates(ring_index, index - 1)
sphere_at_coordinates(ring_index, index + 1)
sphere_at_coordinates(ring_index + 1, index + ring_index)
sphere_at_coordinates(ring_index + 1, index + ring_index + 1)
]
end
neighbours.delete_if { |sphere| sphere.nil? }
end
Il faut encore mettre ça à l'épreuve pour tester un peu mais je pense me planter (ça semble fonctionner uniquement dans la partie supérieure gauche du cercle).
J'ai du mal à mettre au point la fonction qui retourne la sphère présente aux coordonnées indiqués. Voici le début de cette fonction :
# Return the sphere at the given coordinates or nil.
# Handle "outs of bounds" positions.
def sphere_at_coordinates(ring_index, index)
real_index = index % @grid[ring_index].size
@grid[ring_index][real_index]
end
Cette fonction doit donc être "intelligente". Si on lui demande la sphère de coordonnées (1; 4), elle doit retourner la sphère (1; 0). Elle doit gérer toutes les "exceptions".
S'il y a un matheux dans l'assemblée pour ces 2 problèmes...
iffle:Sephi-Chan
RE: Génération d'un graphe respectant un visuel - Sephi-Chan - 11-02-2010
Voilà, je pense que c'est bon. Voici le code :
class Sphere
attr_reader :index, :ring_index
def initialize(ring_index, index)
@ring_index = ring_index
@index = index
end
# Return true if the sphere is on the x or y axe.
def on_axe?
[ 'TOP', 'RIGHT', 'BOTTOM', 'LEFT' ].include?(position)
end
def position
@position ||= if @index == 0 && @ring_index == 0
'ORIGIN'
elsif @index == 0
'TOP'
elsif @index == @ring_index
'RIGHT'
elsif 2 * @ring_index == @index
'BOTTOM'
elsif 3 * @ring_index == @index
'LEFT'
elsif @index < @ring_index
'TOPRIGHT'
elsif @index < 2 * @ring_index
'BOTTOMRIGHT'
elsif @index < 3 * @ring_index
'BOTTOMLEFT'
else
'TOPLEFT'
end
end
def to_s
"(#{@ring_index}; #{@index})"
end
end
class Graph
attr_accessor :grid
def initialize(grid = [])
@grid = grid
end
def generate(rings_count)
@grid = []
@grid[0] = [ Sphere.new(0, 0) ]
rings_count.times do |ring_index|
ring_index += 1
@grid[ring_index] = []
(0..(ring_index * 4 - 1)).each do |index|
@grid[ring_index] << Sphere.new(ring_index, index)
end
end
@grid
end
def neighbours(ring_index, index)
sphere = sphere_at_coordinates(ring_index, index)
neighbours = case sphere.position
when 'ORIGIN'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 1),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 2),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 3)
]
when 'TOP'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 1),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index - 1)
]
when 'TOPRIGHT'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 1),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 1),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index)
]
when 'RIGHT'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 2),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 1),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 1)
]
when 'BOTTOMRIGHT'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 1),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 2),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 1),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 2)
]
when 'BOTTOM'
[
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 2),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 1),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 2),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 3)
]
when 'BOTTOMLEFT'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 3),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 2),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 3),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 2)
]
when 'LEFT'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 4),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 2),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 3),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 3),
]
when 'TOPLEFT'
[
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 3),
sphere_at_coordinates(sphere.ring_index + 1, sphere.index + 4),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 3),
sphere_at_coordinates(sphere.ring_index - 1, sphere.index - 4)
]
end
# Adjacent spheres are in the neighbours, except for origin sphere.
if sphere.position != 'ORIGIN'
neighbours << sphere_at_coordinates(sphere.ring_index, sphere.index - 1)
neighbours << sphere_at_coordinates(sphere.ring_index, sphere.index + 1)
end
neighbours.delete_if { |sphere| sphere.nil? }
end
# Return the sphere at the given coordinates or nil.
# Handle "outs of bounds" positions.
def sphere_at_coordinates(ring_index, index)
if @grid[ring_index]
real_index = index % @grid[ring_index].size
@grid[ring_index][real_index]
else
nil
end
end
end
graph = Graph.new
graph.generate(3)
puts
graph.grid.each_with_index do |ring, ring_index|
ring.each_with_index do |sphere, index|
puts "Neighbours of #{sphere} are #{graph.neighbours(sphere.ring_index, sphere.index).join(", ")}."
end
end
puts
Et la sortie sur la console :
Neighbours of (0; 0) are (1; 0), (1; 1), (1; 2), (1; 3).
Neighbours of (1; 0) are (2; 0), (2; 1), (0; 0), (2; 7), (1; 3), (1; 1).
Neighbours of (1; 1) are (2; 1), (2; 3), (2; 2), (0; 0), (1; 0), (1; 2).
Neighbours of (1; 2) are (0; 0), (2; 3), (2; 4), (2; 5), (1; 1), (1; 3).
Neighbours of (1; 3) are (2; 7), (2; 5), (2; 6), (0; 0), (1; 2), (1; 0).
Neighbours of (2; 0) are (3; 0), (3; 1), (1; 0), (3; 11), (2; 7), (2; 1).
Neighbours of (2; 1) are (3; 2), (3; 1), (1; 0), (1; 1), (2; 0), (2; 2).
Neighbours of (2; 2) are (3; 2), (3; 4), (3; 3), (1; 1), (2; 1), (2; 3).
Neighbours of (2; 3) are (3; 4), (3; 5), (1; 2), (1; 1), (2; 2), (2; 4).
Neighbours of (2; 4) are (1; 2), (3; 5), (3; 6), (3; 7), (2; 3), (2; 5).
Neighbours of (2; 5) are (3; 8), (3; 7), (1; 2), (1; 3), (2; 4), (2; 6).
Neighbours of (2; 6) are (3; 10), (3; 8), (3; 9), (1; 3), (2; 5), (2; 7).
Neighbours of (2; 7) are (3; 10), (3; 11), (1; 0), (1; 3), (2; 6), (2; 0).
Neighbours of (3; 0) are (2; 0), (3; 11), (3; 1).
Neighbours of (3; 1) are (2; 0), (2; 1), (3; 0), (3; 2).
Neighbours of (3; 2) are (2; 1), (2; 2), (3; 1), (3; 3).
Neighbours of (3; 3) are (2; 2), (3; 2), (3; 4).
Neighbours of (3; 4) are (2; 3), (2; 2), (3; 3), (3; 5).
Neighbours of (3; 5) are (2; 4), (2; 3), (3; 4), (3; 6).
Neighbours of (3; 6) are (2; 4), (3; 5), (3; 7).
Neighbours of (3; 7) are (2; 4), (2; 5), (3; 6), (3; 8).
Neighbours of (3; 8) are (2; 5), (2; 6), (3; 7), (3; 9).
Neighbours of (3; 9) are (2; 6), (3; 8), (3; 10).
Neighbours of (3; 10) are (2; 7), (2; 6), (3; 9), (3; 11).
Neighbours of (3; 11) are (2; 0), (2; 7), (3; 10), (3; 0).
Sephi-Chan