Discussion :

[Warlack]

Bonjour à tous

Je dois développer un bomberman-like en groupe pour un projet scolaire, et je bloque sur un point particulier : le jeu doit pouvoir accepter un nombre "illimité" de joueurs (réels ou IA), et les répartir sur la map en les plaçant au maximum de distance les uns des autres. Cela fait un moment que je cherche un solution à ce problème, sans succès. Si quelqu'un a une idée qui puisse m'aider à résoudre ce casse-tête, je suis à l'écoute

[LittleWhite]

Bonjour,

Une méthode très bourrine serait de tester toutes les cases, de faire le calcul de distance entre cette case et chaque joueur, de garder la distance minimal trouvée et ensuite, de prendre la case qui a la plus grande distance jusqu'à présent.

Mais, j'ai peur que ce soit un peu lent ...

[MoDDiB]

Mais, j'ai peur que ce soit un peu lent ...

Il y a moyen d'accélèrer un peu cet algo : à chaque ajout de joueur on remplit les cases alentours de leur distance à ce joueur jusqu'à ce qu'on trouve une distance inférieure.

Concrètement quel sera le nombre de cases et le nombre de joueurs limite ?

[Warlack]

Merci pour vos réponses
La taille peut aller très loin (500x500 par exemple), pour un nombre de joueurs IA pouvant atteindre plusieurs centaines (en théorie en tout cas). C'est tout le problème d'ailleurs, si les joueurs étaient limités (genre 4), trouver comment les disperser de façon égale serait beaucoup plus simple

Pour cette même raison, un algo "lent" est à éviter, mais je vais quand même essayer d'implémenter celui de LittleWhite (qui sait, l'inspiration pourrait venir en codant).

MoDDiB, tu pensais à quelque chose comme ça ?
x = joueur
x1221x
123321
234332
343233
432123
321x12

Où le premier 4 serait la position d'un nouveau joueur?

[MoDDiB]

Oui c'était sur la base de l'algo de LittleWhite.
Par contre pour un damier si grand et autant de joueurs je pense qu'il vaut mieux partir d'une sorte de Quadtree et de placer le nouveau joueur là où il y a le moins de joueur puis ensuite le placer à une distance min des joueurs proches.

Ca ne sera pas parfait, mais les joueurs ne devraient pas s'en rendre compte et c'est bien l'essentiel.

[Warlack]

Je me suis renseigné sur les QT pendant le weekend, le truc c'est que ça m'a l'air relativement complexe à implémenter (et un peu too much pour un bomberman aussi ). Cela dit, l'effort technique pourrait apporter un plus durant la soutenance du projet.

Je pense que je vais partir en priorité sur le premier algo, puis m'essayer à l'implémentation d'un quadtree s'il me reste un peu de temps (si j'ai bien réalisé ma classe (abstraction notamment), ça ne devrait faire aucune différence pour le reste du prog).

Merci encore pour votre aide

[MoDDiB]

Le quadtree ce n'est vraiment pas compliqué une fois que l'on passe outre les explications complexes trouvées sur le net

Au pire tu peux partitionner ton espace avec une grille : ça sera bien suffisant.

[Ti-R]

Justement je pense que QT c'est super "simple" ou SFML pour la gestion des fenêtres, événements, affichage etc... Et c’est à mon avis un indispensable à voir/apprendre.

Pourquoi ne pas découper le tableau en une grille uniforme comme le jeu Bomberman ?
Chaque personnage est équidistant l'un de l'autre car chaque personnage à une zone équidistante.

Ensuite si le nombre de joueur n'est pas égale au nombre d'emplacement, il suffit de les placer aléatoirement dans chaque zone.

Il restera des zones vides, mais c'est cela qui est justement sympa dans bomberman.