[PHP] Structure d'un tableau pour un graphe

[zeppelin]

Bonjour tout le monde,

Dans le cadre de mon jeu (http://nolaya.com), je rencontre un petit problème.

Je vais ajouter un système qui permet de "fusionner" des objets. Basiquement votre inventaire a 4 places, mais grâce a ces fusions, ceci n'est pas un problème. Pour ceux qui connaissent, ça reprends le principe des DOTA, de League of Legends et j'en passe.
En gros, il est donc possible de fusionner l'objet 1 et l'objet 2 pour obtenir l'objet 3.

Petit exemple pour illustrer mon propos



Et ensuite, un petit exemple de la structure de ma config (je mets simplement en PHP, c'est différent sur le jeu mais c'est assez lisible il me semble).

<?php

// halberd

$array[1] = array // le 1 correspond a l'id de l'objet

(

	'quality' => 1,

	'cost' => array('gold' => 800),

	'effects' => array

	(

		'strenght' => array('att' => 250, 'def' => 250)

	)

);



// amulet - mana

$array[2] = array

(

	'quality' => 1,

	'cost' => array('gold' => 1000),

	'effects' => array

	(

		'production' => array('mana' => 10)

	)

);



// fusion halberd - amulet

$array[3] = array

(

	'quality' => 2,

	'cost' => array('gold' => 1100),

	'requires' => array(1, 2),

	'effects' => array

	(

		'strenght' => array('att' => 500, 'def' => 500),

		'production' => array('mana' => 20)

	)

);

Voila donc en gros, les fusions pour chaque objet est dans le champ "requires" (si il existe biensur), sous forme de array, avec les ids des objets nécessaire. Jusque la, rien de bien compliqué, si je veux récupérer les "requires" des objets.
Mon problème se pose pour des fusions de plus haut niveau, par exemple pour l'objet 9 de mon image, car chaque objet connait uniquement les dépendances vers les 2 objets juste en dessous de lui. L'objet 9 sait donc uniquement qu'il est construit avec 5 et 6, mais ne sait pas avec quoi sont créer ces derniers.
Si je veux donc connaitre l’arborescence complète, je dois passer par une fonction récursif, qui me renverrais un array du genre:



C'est la que je bloque. Je ne vois pas quelle structure donner a ce tableau de l’arborescence complète d'un objet. J'en ai toutefois besoin pour par la suite afficher graphiquement l’arborescence, calculer des prix etc etc.

Imaginons que je veux fusionner 2 fois le même objet pour un obtenir un autre... paf, je ne peux plus utiliser les ids des objets comme clé dans mon tableau d’arborescence.



Bref je suis un peu perdu... Et si ça se trouve je fais fausse route sur ma conception.

Des pistes, des idées, voir même des solutions? Votre aide est vraiment la bienvenue!

Un grand merci d'avance a tous!

Zepp

[Viciousity]

Ben tu stocke les items dans une tables objet-propriétaire :

ID: 1
user_id: 234
item_id: 8

Quand tu veux récupérer les item de ton joueur 234 tu fais un select sur son id ^^

---

Du coup leur identifiant est unique et tu peux meme avoir 4 items identique sans problème ^^

[zeppelin]

Erm oui ça c'est bon, pas de soucis pour sauvegarder en base de données

Non en gros je veux juste connaitre l’arborescence complète d'un objet vis a vis de la config.

Genre une méthode getRequiresTree($itemid) me retournerais les 2 dépendances de lui même, ainsi que les dépendances des dépendances des dépendances des dépendances...

[Hideaki]

La récursion est la meilleur solution avec une table contenant l'id ( qui peut être un id composé de deux autres ids) des deux parents en clef étrangère, ce qui est le plus propre mais je pense que tu as déjà cette solution.

L'id de l'objet est-elle auto-incrémenté, si oui

Imaginons que je veux fusionner 2 fois le même objet pour un obtenir un autre... paf, je ne peux plus utiliser les ids des objets comme clé dans mon tableau d’arborescence.

cela ne pose aucun problème.

[zeppelin]

Coucou Hideaki, et merci pour ta réponse. A part contre je ne comprends pas bien avec la table... Je ne veux pas de table mysql ni rien...

Je veux juste une méthode, a laquelle je passe un ID d'un objet en paramètre, qui me dirais ses dépendances (ses "requires"). Exemple sur mon image: Je ferais getRequiresTree(11) et la méthode me renverrais tous les objets dont j'ai besoin pour obtenir celui la, donc: l'objet 11 est construit et a donc besoin de l'objet 9 et de l'objet 10, l'objet 9 a lui même besoin de l'objet 5 et 6, qui eux...

Quand je parlais de tableau, je pensais a un array! Désolé d'avoir été si peu clair

[Hideaki]

Ok je comprends mieux,
je ne connais pas trop le php mais la solution suivante devrait fonctionné, remplace ta ligne 'requires' par celle-là :

Code :

'requires' => array(0 => 6, 1=> 6),

il faut ensuite adapter ton code pour la recherche,
si ton champ 'requires' contient toujours 2 paramètres, pourquoi ne pas faire deux lignes

J'espère avoir résolu ton problème ^^

[zeppelin]

Re!

Erm c'est déjà la cas, array(6, 6) = array(0 => 6, 1=> 6) en PHP

Mais l'objet 6 contient lui même 2 requires que je veux connaitre, mais ma méthode ne peux pas retourner array(6 => array(require1, require2), 6 => array(require1, require2)) par exemple... et c'est la que je bloque.

En gros mon code ressemblerais a ceci, mais je ne sais pas comment retourner ce dont j'ai besoin...

<?php



private function recursiveRequires($itemid)

{

	$requires = $this->getRequires($itemid); // on recup le array(1, 2) par exemple, ou NULL si l'objet n'a pas de require

		

	if(!is_null($requires))

	{

		foreach($requires as $key => $value)

		{

			$tree ... = $this->recursiveRequires($value); // la je bloque, je ne sais pas comment recup le resultat...

		}

	}

		

	return $tree; // voila quoi...

}

[Hideaki]

Je dirais un truc comme cela :

private function recursiveRequires($itemid)

{

	$requires = $this->getRequires($itemid); // on recup le array(1, 2) par exemple, ou NULL si l'objet n'a pas de require

 

	if(is_null($requires)){

		return null;

	}

	$count = 0;

	$tree[0] = $itemid;

	$a = array(); // Pas certain de la syntaxe

	foreach($requires as $key => $value)

	{

		$a[count] = $this->recursiveRequires($value);

		$count++;

	}

 	$tree[1] = $a;

	return $tree; 

}

tu devrais obtenir la réponse pour l'id 9 :

Code :

{9, { {6, {3,2}},  {6, {3,2}} } }

Il y a sans doute mieux comme solution mais es-ce bien cela que tu souhaitais ?

[niahoo]

et bien ton objet est capable de renvoyez ses objets parents, donc les objets parents sont capables de faire de même.

class Item {



	public function getRequiresRecursive() {

		$requires_id = $this->requires(); // doit retourner array() vide si pas de parents

		$parents = array();

		foreach ($requires_id as $rid) {

			$parent = new self($rid);

			$parents[$rid] = $parent->getRequiresRecursive();



		}

		return $parents;

	}



}

ah merde grillé. bon y a ma boss qui me prend la tête alors le temps que je finisse de coder mon truc..

[zeppelin]

Salut les loulous!

J'y suis presque, reste le petit bugg avec les clés identiques. Voila ce que j'ai niveau code:

Mon "Model" pour la config des objets (en gros comme pour un Model database, mais lecture seulement; J'extend l'objet Config qui lui a un singleton pour ne charger et parser le fichier config (json) qu'une seule fois, comme pour les database une seul connexion etc.) $this->config contient le tableau de mes objets. Bon je laisse que les 2 méthode qui nous intéressent pour ce cas.

<?php



class ItemsConfig extends Config

{



	public function getRequires($itemid)

	{

		return isset($this->config[$itemid]['requires']) ? $this->config[$itemid]['requires'] : array();

	}

	

	public function getRequiresTree($itemid)

	{

		$Item = new Item($itemid);

		

		return $Item->getRequiresRecursive();

	}

}

Ensuite ce que j'ai construit avec les conseils de niahoo

<?php



class Item

{

	private $id;

	

	public function __construct($id)

	{

		$this->id = $id;

	}

	

	public function getRequiresRecursive()

	{

		$requires_id = ItemsConfig::getInstance()->getRequires($this->id); // doit retourner array() vide si pas de parents

		

		$parents = array();

		

		foreach($requires_id as $rid)

		{

			$parent = new self($rid);

			$parents[$rid] = $parent->getRequiresRecursive();

		}

		return $parents;

	}

}

Et voici les résultats var_dump() pour quelques tests:

Objet 10, résultat correct, il se compose de l'objet 1 et 3


Objet 11, résultat correct, il se compose de l'objet 1 et 2


Objet 100, résultat correct, il se compose de l'objet 10, qui se compose du 1 et du 3, ainsi que de l'objet 11, qui so compose du 1 et du 2


Et c'est la qu'il y a l'erreur, l'objet 12, se compose de l'objet 3 et de l'objet 3 (donc DEUX fois du même objet). Mais ça foire car il y aurait deux fois la clé 3...


Voila enfaite le problème est la, mais j'ai du mal m'expliquer dans mon premier post (je suis une pive pour les explications, j'ai toujours été ainsi ce n'est rien de nouveau )

Bon après si ça complique trop car je devrait passer par je ne sais quoi comme structure et tout, je vais faire en sorte qu'il n'y ai pas besoin de deux même objets au même niveau.