[Résolu] Génération d'un graphe respectant un visuel

[Sephi-Chan]

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

[NicoMSEvent]

j'ai remplacé les chiffres dans tes boules (les coordonées?) par x,y au lieu de 0,0 (pour la boule centrale)

[Sephi-Chan]

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

[NicoMSEvent]

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.

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)

[pascal]

C'est pour un nouveau jeu ?

[Sephi-Chan]

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.

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 !

[Sephi-Chan]

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

[NicoMSEvent]

héhé, ça avance

je n'ai pas compris ce qu'était un axe...

[Sephi-Chan]

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

[Sephi-Chan]

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