Discussion :

[Paphytos]

Bonjour à tous !

Je développe un jeux en 2D avec pas mal d’interaction multiples. Parmi elle, le spawn des créatures. Je génère la map avec un perlin noise, il se peut donc que des zones soient close.

J'ai donc écris un code qui crée une liste contenant seulement les cases marchable. Il prends une case au hasard et fait un étalement sur les quatre cases adjacentes (haut, droite, bas et gauche) tant qu'elles sont présente dans la liste (donc marchable)
De cette façon j'obtiens des listes de cases de zone entière avec un % me permettant d'estimer si cette liste de case doit figurer ou non à la liste du spawn.

Donc le code marche, mon soucis qui me fais venir poster sur ce forum est le suivant ; Ce code est quasiment 20 fois plus lent à exécuter que la génération de la map, pourriez-vous m'aider à l'optimiser/trouver une solution plus efficace ?

Voici le code ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
	/** on définis quel est la grande zone de la map **/
	private void makeSpawnPossible() {
		Map<Pos, Cell> possible = new HashMap<>();
 
		/** on liste les cases marchable **/
		for(Chunk cc : chunks.values())
			for(Cell c : cc.cells.values())
				if(c != null && !c.unwalkable)
					possible.put(c.realPos(), c);
 
		int size = possible.size();
 
		Map<Integer, List<Cell>> zones = new HashMap<>();
 
		spawnPossible.cleanup();
 
		/** tant qu'il reste des cases à caser **/
		while(possible.size() > 0) {
 
			/** on choisis d'abord une case au hasard **/
			List<Cell> ll = new LinkedList<>(possible.values());
			Collections.shuffle(ll);
 
			Cell start = ll.get(0);
			possible.remove(start.realPos());
 
			/** étalement **/
			/** pouf info, SynchMap c'est juste une HashMap que j'ai synchronisé **/
			SynchMap<Pos, Cell> select = new SynchMap<>();
 
			select.put(start.realPos(), start);
 
			while(true) {
				boolean hasResult = false;
 
				for(Cell cell : select.values())
					for(Cell c : cell.getNears())
						if(c != null && possible.containsKey(c.realPos())) {
							possible.remove(c.realPos());
							select.put(c.realPos(), c);
							hasResult = true;
						}
 
				if(!hasResult) break;
			}
 
			double f1 = select.size();
			double f2 = size;
			double f = (f1 * 100) / f2;
 
			/** si contient plus de 30% de la map ont garde **/
			if(f > 30) {
				for(Cell c : select.values())
					spawnPossible.put(c.realPos(), c);
			}
 
			zones.put(zones.size()+1, new ArrayList<>(select.values()));
		}
	}

Dans le pire des cas je fais tourner l'algorithme passivement mais en partant du joueur..

En vous remerciant

[thelvin]

Hello,

Il ne faut pas passer ton temps à recommencer à examiner toutes les cases.
Tu dois propager à partir des cases adjacentes de celles qui ont été traitées. Une solution est de mettre ces cases adjacentes dans un HashSet, et de propager à partir d'une case contenue dans ce HashSet et que tu enlèves.

[Paphytos]

Hello,

Il ne faut pas passer ton temps à recommencer à examiner toutes les cases.
Tu dois propager à partir des cases adjacentes de celles qui ont été traitées. Une solution est de mettre ces cases adjacentes dans un HashSet, et de propager à partir d'une case contenue dans ce HashSet et que tu enlèves.

HA OUI ! C'est si évident maintenant que tu le dis... Je vais faire la correction pour voir la différence de temps Merci !

[Mat.M]

Ce code est quasiment 20 fois plus lent à exécuter que la génération de la map, pourriez-vous m'aider à l'optimiser/trouver une solution plus efficace ?

d'une part faire des new dans une boucle là c'est un truc très pénalisant à mon sens.
Si vous faites de new dans une boucle pour peu que la JVM embraie des tas de routines pour contrôler les exceptions à chaque fois c'est certain ça va pénaliser la rapidité d'exécution.
Donc le tableau du jeu il faut le créer au lancement de chaque partie et si on veut mettre à jour des cases alors il suffit de se positionner sur la case voulue.
Ensuite beaucoup trop de déclarations de conteneurs dans tous les sens il faut utiliser un conteneur à la fois.

[thelvin]

d'une part faire des new dans une boucle là c'est un truc très pénalisant à mon sens.
Si vous faites de new dans une boucle pour peu que la JVM embraie des tas de routines pour contrôler les exceptions à chaque fois c'est certain ça va pénaliser la rapidité d'exécution.
Donc le tableau du jeu il faut le créer au lancement de chaque partie et si on veut mettre à jour des cases alors il suffit de se positionner sur la case voulue.
Ensuite beaucoup trop de déclarations de conteneurs dans tous les sens il faut utiliser un conteneur à la fois.

Quand on a des soucis d'optimisation on commence par vérifier la complexité de l'algorithme.

Après que ça, ça ait échoué, on peut commencer à se demander ce que la JVM fait de notre code qui pourrait la ralentir. Mais quand on en arrive là, il n'est plus vraiment excusable de se passer d'un profiler pour voir exactement quels sont les goulots d'étranglement au lieu de se dire qu'on sait jamais ça peut être ci ou ça.

[Paphytos]

Après petites corrections je suis passé de quelques secondes à 80 ms C'est bête, pour les autres code j'avais bien pensé à ne travailler que sur une ligne de front x) Marie-Jeane est donc exclue de l'équipe de développement !

Justement, le mois prochain je vais finalement prendre la version payante d'intelliJ, au moins j'aurais un profiler tout préparé ^^ Sinon le reste tourne tranquilou, je suis toujours surpris de la puissance qu'on à avec Java et OpenGL

Merci à vous !

[Mat.M]

Quand on a des soucis d'optimisation on commence par vérifier la complexité de l'algorithme.
Après que ça, ça ait échoué, on peut commencer à se demander ce que la JVM fait de notre code qui pourrait la ralentir.

je pense que mon message a été mal compris.
Si on déclare trop de conteneurs, on fait trop de boucles imbriquées eh bien je sais pas ce que fait le compilateur Java mais il doit rajouter certainement un paquet de code par derrière notamment pour contrôler les exceptions,les allocation mémoires etc..
Donc oui c'est évident qu'il faut optimiser le code.

Globalement je cadence l'exécution de mes routines en fonction du temps qu'elle prennes à s’exécuter. La il s'agit d'un rush d'algo pendant le fondu noir qui débouche sur le perso, à ce moment la de l’exécution il y à un trou d’activités.

Je ne comprends pas pourquoi vous faites des allocations dans votre méthode Respawn.
C'est pas possible de faire une sorte de tableau global une fois pour toutes ?
Rien qu'une instruction comme celle-ci ,Collections.shuffle(ll),ça doit prendre un certain temps d'exécution.
Pas moyen de gérer ça dans un tableau plutôt ?

Après vous faites ce que vous voulez,libre à vous..

[thelvin]

Si on déclare trop de conteneurs, on fait trop de boucles imbriquées eh bien je sais pas ce que fait le compilateur Java mais il doit rajouter certainement un paquet de code par derrière notamment pour contrôler les exceptions,les allocation mémoires etc..
Donc oui c'est évident qu'il faut optimiser le code.

Oui. Mais à de rares exceptions près, ça ne change rien du tout à la complexité de l'algorithme et n'est donc pas la chose à regarder.

Au lieu de penser qu'il y a trop de boucles imbriquées, il faut regarder si on peut faire la même chose avec moins de boucles imbriquées, par exemple.

La magie noire du compilateur et de la JVM, ça vient après. Sauf à la rigueur pour des trucs comme découvrir que les String et les regex c'est pas du temps constant.

[Paphytos]

je pense que mon message a été mal compris.
Si on déclare trop de conteneurs, on fait trop de boucles imbriquées eh bien je sais pas ce que fait le compilateur Java mais il doit rajouter certainement un paquet de code par derrière notamment pour contrôler les exceptions,les allocation mémoires etc..
Donc oui c'est évident qu'il faut optimiser le code.


Je ne comprends pas pourquoi vous faites des allocations dans votre méthode Respawn.
C'est pas possible de faire une sorte de tableau global une fois pour toutes ?
Rien qu'une instruction comme celle-ci ,Collections.shuffle(ll),ça doit prendre un certain temps d'exécution.
Pas moyen de gérer ça dans un tableau plutôt ?

Après vous faites ce que vous voulez,libre à vous..

Je suis partant pour le faire avec moins de boucles dans les boucles Je suis curieux, si tu as le temps je veux bien que tu édites le code que j'ai posté ^^
C'est comme le pathfinder, j'ai des boucles dans les boucles, je suis un peut contraint, donc si tu pourrais m'expliquer comment faire dans ces cas la

Cette méthode est exécutée qu'une fois au chargement du jeux et sera ré-exécutée temps en à autre, ce n'est pas critique. Elle est bien conservée dans un tableau.

J’utilise régulièrement Collections.shuffle lorsque je dois récupéré une liste de cases environnant une autre. Cela me permets de randomiser les pathfinder à distance équivalente ainsi qu'un tas de random dans le jeux.
Par exemple, pour la régen de l’environnement j’utilise aussi shuffle sur mes listes adjacente pour avoir du bruit au lieux de motifs java de base.

Quel serait l'alternative à Collections.shuffle dans mon cas ? Sachant que j'ai besoin de faire hasard et non de hasard répétitif.

[Mat.M]

rebonjour Paphytos regarder éventuellement tout ce qui est utilisation d'octrees par exemple.
Cela permet d'éviter de boucler

[Paphytos]

d'une part faire des new dans une boucle là c'est un truc très pénalisant à mon sens.
Si vous faites de new dans une boucle pour peu que la JVM embraie des tas de routines pour contrôler les exceptions à chaque fois c'est certain ça va pénaliser la rapidité d'exécution.
Donc le tableau du jeu il faut le créer au lancement de chaque partie et si on veut mettre à jour des cases alors il suffit de se positionner sur la case voulue.
Ensuite beaucoup trop de déclarations de conteneurs dans tous les sens il faut utiliser un conteneur à la fois.

Globalement je cadence l'exécution de mes routines en fonction du temps qu'elle prennes à s’exécuter. La il s'agit d'un rush d'algo pendant le fondu noir qui débouche sur le perso, à ce moment la de l’exécution il y à un trou d’activités.