Discussion :

[Davidbrcz]

Bonjour a tous.
Dans un jeu je suis en train de coder une fonction pour selectioner plusieurs unite a la fois.
Comme il n'y a pas moyen qu'lle se retrouve toutes sur la meme case , je recherche un algo me permetant de "cree" les surface d'unite prenant le minimum d'espace (et donc le plus compacte possible) en fonction du nombre d'unites.
Exemple:Je selectione 4 unite qui ne se touche pas
Et si je clique a un endroit , je souhaite quelle forme un "carre" d'unite pour un cote de 2 unite.
Comment faire ?

Je n'ai pas la moindre idée pour ce genre d'algo ni meme du nom .

Si quelqu'un peut m'aider.
Merci a lui.

David

[O( N )]

C pas trés clair pour moi

(je suppose que c'est pour un jeu de type wargame)

Indique moi plus d'infos, car sinon déjà, ma réponse actuelle est fausse

Ton problème se situe au niveau de la sélection ou
au niveau de la formation d'un carré à partir d'unités éloignés?

La sélection : Si l'unité est dans la zone de sélection , elle s'insère dans un groupe d'objet sélectionnable ...

La formation : Les unités d'un même groupe se donne soit un rendez-vous avant d'aller ensemble quelquepart en groupe
soit se dirige séparément vers ce point.

Le problème sous-jacent (il me semble) est lorsque d'autres unités risquent de faire sauter ton carré.

Soit tu considères que ton carré (= groupe d'unité) est un nouvel objet qui agit d'abord et indique à ses unités comment faire. Soit les unités peuvent agir indépendamment les unes des autres et elles doivent se retrouver ensemble par la suite.

[Davidbrcz]

Desole si mon message precedent n'etait pas tres clair.
Alors mon problemme n'est au niveau de la selection , ca sa roule.
Il se situe pour le lieu d'arrive du groupe d'unite.
Je pense qu'une fois le groupe selectioner ,chaque unite le composant est semi-independate.
Je m'explique.
JE penche pour que chaque deplacement d'unite soit lance dans un thread pour atteindre son point d'arrive.Mais en meme temps , je definirai des point de passage intermediaire obligatoire de façon a ce que au fur et a mesure de deplacement un groupe se constitue.(Pour les pont de passage , je pense au barycentre de deux unitées, est ce un chemin a asuivre ?)

Mon problemme reside dans le fait de definir un point d'arrive a partir d'un seul clic pour chaque unite de facon a avoir un groupe le plus compacte possible et aussi de facon a ce que il n'y est pas de problemme si un batiment ou autre est dans la zone d'arrive du groupe.

P.S: mon jeu est un jeu de strategie en temps reel en 2D.

[O( N )]

Desole si mon message precedent n'etait pas tres clair.

C'est normal, il faut déjà savoir ce que l'on veut soi même et en général, il faut se tromper pour mieux se comprendre

Je pense qu'une fois le groupe selectioner ,chaque unite le composant est semi-independate.
Je m'explique.
JE penche pour que chaque deplacement d'unite soit lance dans un thread pour atteindre son point d'arrive.Mais en meme temps , je definirai des point de passage intermediaire obligatoire de façon a ce que au fur et a mesure de deplacement un groupe se constitue.(Pour les pont de passage , je pense au barycentre de deux unitées, est ce un chemin a asuivre ?)

Pourquoi pas le barycentre (bien que je ne m'en rappelle plus )
Sais-tu comment connaître le nombre de points de passage pour chaque unités ? (elles ne ne sont pas à égales distances les une des autres => nombre de points de passage différents ?)
Une unité doit attendre les autres, à son point de passage, pour qu'elle forme le groupe, non ?

Mon problemme reside dans le fait de definir un point d'arrive a partir d'un seul clic pour chaque unite de facon a avoir un groupe le plus compacte possible et aussi de facon a ce que il n'y est pas de problemme si un batiment ou autre est dans la zone d'arrive du groupe.

Ton plan de jeu est un maillage, du moins tu peux le voir comme çà, car cela te permettra d'avoir des routes vituelles que tu pourras faire suivre par tes unités, puis si un obstacle est sur le point de ralliement final, tu cherches le noeud (là ou se regroupe des segments dans ton maillage) le plus proche de ton clic de souris

P.S: mon jeu est un jeu de strategie en temps reel en 2D.

Avant de réaliser tes unités, as-tu fabriqué un éditeur ?
Cela te permettrais de générer plus facilement plusieurs niveaux de jeux entre autre ...
Temps réel (pas mal), cependant as-tu testé les limites de ta bécane en nombre d'unités (çà risque de ramer sinon)
N'oublie pas que si tu réalises des IAs contre toi , elles auront leurs unités également (7 IAs, avec ou contre toi, cela fait 8 joueurs potentiels => nombre d'unités gérables max par personne = nombre d'unités gérable max / nombre de personne présentent dans le niveau)

(Une dernière) Quel est ton langage de développement ?

Bon Courage , c'est un projet sympathique

[Davidbrcz]

Pour les point de passages , il vont se constituer a fur a et mesure.
Les unites avance.Certaine attendent et se regroupe.Puis reavence ensemble tout en restant indepandant pour pouvoir casser le groupe en cas d'obstacle...

Pour la question de distance , les barycentre c'est le pied.

Mon plateau est un tableau de 128*96 cases.
Chaque case un statut (occupe,instaversable) pour trouver le path.
pour la qestion de route , le type de terrain rentre ne jeu dans le path et de "vrai" route existe qui sont le + souvent emprunte par mes unite.

Le nombre d'unite par camps est de 200 au max.
Et j'envisage jusqu'a 8 joueur en meme temps.


Pour eviter que ca rame j'ai mes methodes pas de pb.

P.S:je dev en C++.
pour + d'info sur mon projet recherche dans le forum projet ,le seul topic que j'ai cree.

Edit: mon pb reste la recherche d'un algo pour cree le groupe d'unite le plus compacte possible a l'arrive.

Edit²:l'editeur ca viendra apres.Pour le moment c'est a la main sous Noteapd++

[O( N )]

Je viens de voir ton projet , plutôt sympathique

Je vais te proposer quelques idées perso ,
elles sont certainement pas justes vis à vis de ce qu'ils faudraient faire complètement ,
vue que je n'ai pas encore réalisé ce genre de jeu.
Je pense que beaucoup de gens expérimentés ne manquent pas ici

pour la qestion de route , le type de terrain rentre ne jeu dans le path et de "vrai" route existe qui sont le + souvent emprunte par mes unite.

Je suppose donc que tes unités seraient ralentis si elles traversaient certains types de routes
(où seraient limiter en nombre déplacement ?)

Donc le path se fait sur des probabilités de qualité et de longueur de route afin de ne pas perdre trop d'unités de déplacement ?

Le nombre d'unite par camps est de 200 au max.
Et j'envisage jusqu'a 8 joueur en meme temps.

Pour eviter que ca rame j'ai mes methodes pas de pb.

Je suppose que tu as essayé de générer tous ces petits bonhommes et de les voir évoluer
et essayer juste de s'éviter entre eux (pour commencer) ?

(pour qu'ils s'évitent, ils faut qu'ils se voient, donc un algorithme que chacun appellent ...)

(car 200 * 8 =1600 objets se déplaçant chacun avec son petit contexte différents et ses priorités)

Edit: mon pb reste la recherche d'un algo pour cree le groupe d'unite le plus compacte possible a l'arrive.

Chacune de tes unités appartient à une classe ?
Si cela est le cas (C++ oblige)
tu peux rajouter à ta classe
int _Num_Groupe de type = 0;

Deux méthodes :
private void Set_Num_Groupe(int);
public int Get_Num_Groupe();

et dans tes algorithmes de déplacement tu vérifies avant d'aller dans une direction si tu appartiens à un groupe
(_Num_Groupe != 0) et donc de te rapprocher de celui-ci
ou de le suivre.

Après cela dépend de comment tu veux implémenter tes idées : (je m'explique) , Attention je suis un peu rouillé en C++ cela fait un petit momment que je n'en fait plus ^^

Soit toutes tes unités suivent le groupe comme elles peuvent.
Soit elles se déplacent indépendemment et essayent de coller le groupe.

C'est deux manières différentes d'approches.
Voici une idée de la première (il me semble)

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
 
class Unite {
...
/* 
  toutes les unités 
  (alliés ou ennemis ont accés à ce numéros)
  cependant seules celles ayant ce numéros pourront y répondre
*/
static int _Num_Groupe = 0;
private Groupe* _Mon_Groupe;
 
// Constructeur par défaut
Unite::Unite() {
  ...
  _Mon_Groupe = NULL;
  ...
}
 
Unite::Unite(..., Groupe* _groupe,...) {
   ...
   _MonGroupe = _groupe; // référence à ce groupe.
   ...
  // Ne pas oublier d'incrémenter _Num_Groupe
  _Num_Groupe++;
  ...
}
...
 
}

Donc lorsque tu créés un groupe, toutes les unités y appartenant feront référence à ce même groupe.


Apres ceci :
Soit tu donnes un ordre à ce groupe qui donnera des ordres à ses unités,
soit tu donnes un ordre à une unité qui relaieras l'ordre aux unités partageant le même numéros de groupe et elles essayeront de se suivre.

Pour la formation d'un groupe, il devrait y avoir aussi une déformation du groupe
(rien à voir avec la création et la suppression)
(exemple simple : tu crées un groupe et essaie de la faire
passer dans une zone ou seule une personne peut passer.
Si le groupe a bien formé un carré pour 4 personnes,
il devraient se déformer ou se reformer dans un autre style de forme que le carré
(une ligne, un serpentin, ...), puis se reformer en carré après ! )

Pour la formation la plus correcte, tu dois voir en fonction du contexte : obstacle, environnement proche,...
Chaque unité s'affiche sur sa case, donc toutes les unités tentent de rentrer dans une zone non occupée
de la zone du groupe (la variable de type Groupe connaît toutes ses unités et
donc le nombre de cases totales à occuper par ce groupe,
c'est là que je verrais bien la regénération d'une nouvelle forme dans le cas où il y a incompatibilié avec la forme actuelle)

voilà