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 !

[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.

[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]

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

Si j'ai bien compris, niveau structure de code, au lieux d'encastrer des boucles je dois, en gros gros, appeler des méthodes qui en appelleront d'autres/elle même et etc... jusqu'à obtenir le résultat ?

[Mat.M]

oui c'est cela éventuellement j'écris bien éventuellement faire une recherche sur les structures en arborescence.
Avec un pointeur sur une structure en arborescence pas besoin de boucler car boucler ça consomme du temps d'exécution

[Paphytos]

oui c'est cela éventuellement j'écris bien éventuellement faire une recherche sur les structures en arborescence.
Avec un pointeur sur une structure en arborescence pas besoin de boucler car boucler ça consomme du temps d'exécution

Merci pour les infos, très intéressant
Es-ce utile de passer par un pointer pour par exemple un double for pour faire un tableau x, y ?

Par exemple, pour trouver une case à X distance d'un personnage située dans auréole de case autour d'un autre personne qui va de, imaginons, 10 à 15 cases.
Es-ce une bonne solution de ;
-SI le tableau de cette distance n'existe pas je le crée via un bête tableau et calcule de distance individuel, je référence les position avec 0 comme origine
-Je randomise la liste de case (liste que je ne génère donc qu'une fois par distance, j'aurais 4 tableau max)
-Je parcours la liste et retourne la case située à bonne distance du perso qui est en recherche

[Mat.M]

Salut Paphytos ce que vous décrivez c'est l'agorithme du Pathfinding en A*.
Y'a plein de tutos là-dessus.
Sinon moi je parlais de "nodes" avec des branches haut,bas,droit,gauche.
Si on veut voir qu'un noeud adjacent est libre alors on teste s'il est nul.
Mais il faudrait plus détailler votre projet parce qu'on ne peut pas faire que des réponses à la "volée".
Détailler sur l'avancement du projet, quelles sont les problématiques.
Un jeu ça devient vite complexe, je rejoins thelvin, d'un point de vue algorithmique.

[Paphytos]

Salut Paphytos ce que vous décrivez c'est l'agorithme du Pathfinding en A*.
Y'a plein de tutos là-dessus.
Sinon moi je parlais de "nodes" avec des branches haut,bas,droit,gauche.
Si on veut voir qu'un noeud adjacent est libre alors on teste s'il est nul.
Mais il faudrait plus détailler votre projet parce qu'on ne peut pas faire que des réponses à la "volée".
Détailler sur l'avancement du projet, quelles sont les problématiques.
Un jeu ça devient vite complexe, je rejoins thelvin, d'un point de vue algorithmique.

On va dire que c'est entre le rpg, la base defense, age of Empire et Minecraft (pour celui en cours), j'ai fais ma lib d’interprétation LWJGL pour me monter un moteur d'interface et de jeux. Il y à une très grande map procédurale, avec environnement interractif (croissance des végétaux, biomes, journée, nuit, le fleu existe aussi et se propage, le vent peut faire des bourrasques. Tu gère ton bonhomme pour en taper d'autre, rejoindre/créer une faction, gerer tes bâtiments, constructions, productions de ressources, tu gère tes unité en paramétrant les bâtiments.
Environ 40 000 lignes pour la lib graphique que j'ai fais et entre 30 - 60 000 lignes pour le petit jeux actuel.

Maintenant j'en suis à ajouter de la subtilités on va dire, le gros est posé et est stable, même sur un petit pc de merde^^ Je suis un de ces dev autodidacte à qui on à dit il y à 10 ans que je me découragerais, mais au contraire, je me suis motivé.

Pour situer mes compétences, je reste sur du 2d (je préfère passer du temps à dessiner pleins de trucs et faire du contenu plutôt qu'investir toute mon énergie pour avoir du 3D de base), mais à force j'arrive à faire du vrais temps réel (avec la boucle serveur qui à de l'avance) au point de pouvoir par exemple faire un genre de pvp hyper dynamique et évolutif dans un environnement géométrique et physique (entre agar.io, diep.io, digdig.io et autres pour synthétiser)

Etant autodidacte j'ai tendance à vouloir réinventer la roue, butter sur la limite des techniques que j'ai trouvé et enfin faire des recherches (avec du coups les bonnes questions) pour voir ce qui se fait et ce qui peut être fait.
Actuellement, c'est en arrivant sur des algorithme précis que je dois exécuter rapidement que je trouve des limites, quand par exemple une entités doit checker les ressources pertinente pas trop loin, les objets qu'on peut ramasser, ainsi que les autres entitées à proximités, qu'on dois décider ce qu'il faut faire à partir de X qualité de donnée, pour en suite déterminée un vecteur directe ou un pathfinder pour continuer d'avancer dans les taches, la ça devient tendu.
En gros, mon jeux actuel tiens sans soucis 150 entitée sur une map de 1000*1000 cases (elles sont assez grande) en mêlée général, avec coagulation en faction, regroupement, attaque coordonnée, des tonnes de calcules de pathfinder, et proximités.. J'aimerais bien idéalement pouvoir en tenir 10 fois plus sur un pc basique.
Je vais déjà jouer des pauses rôle-play, des structures hiérarchique pour que la troupe suive le pathfinder du capitaine, des paterne globaux pour les chemins les plus emprunté (qui deviennent terreux à force), des trucs comme ça.

Mais ce qu'il me manque le plus c'est la structure optimale qui ressort d'un apprentissage sérieux du fonctionnement de la JVM^^ Vous auriez quelques liens de sites qui listent les mauvais comportement niveau compilation de code et l'alternative pro classique ?