Discussion :

[Kropernic]

Hello,

Lors d'un après-midi de profond ennui, je me suis lancé le défi de coder un candy crush like. Ce qui conceptuellement ne semble pas du tout insurmontable.

Par contre, je sèche pour l'implémentation la fonction/procédure qui sera chargée de trouver s'il y a des combinaisons dans la grille.

J'ai tenté la recherche google car j'imagine que ce genre de problématique doit déjà avoir été à maintes reprises mais je ne dois pas utiliser les bons mots clefs car j'ai fait chou blanc jusqu'ici.

Quelqu'un aurait-il une idée quant aux mots clefs à utiliser ?

Sinon, pour quelque chose de plus concret, j'ai en fait un tableau de 10*10 cases qui contient des nombres entiers entre 1 à 5 (pour simplifier).
Ce que je cherche, c'est comment faire ma recherche de manière élégante. Les choses non élégantes se produisant en bordure de grille. L'idée de devoir faire des if pour tester si l'index de la ligne ou de la colonne vaut 0, 1, 8 ou 9 ne me plaît pas du tout. Je cherche donc une manière élégante de pallier à cela.

[Kropernic]

Hello,

Finalement, en puisant dans mes cellules grises, je suis parvenu à ceci :

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
    Public Sub CheckForPattern()
        Dim tilesToPop As New List(Of Tile)
        For Each t As Tile In MovedTiles
            'initialization
            MatchingTilesInRow = New List(Of Tile)
            MatchingTilesInCol = New List(Of Tile)
 
            'horizontal lookup
            MatchingTilesInRow.Add(t)
            'leftwards
            Dim r As Short = t.Row
            Dim c As Short = t.Col - 1
            Dim break As Boolean = False
            While Not (c < 0 Or break)
                If Tiles(r, c).Candy.Value = t.Candy.Value Then
                    MatchingTilesInRow.Add(Tiles(r, c))
                Else
                    break = True
                End If
                c -= 1
            End While
            'rightwards
            c = t.Col + 1
            break = False
            While Not (c > 9 Or break)
                If Tiles(r, c).Candy.Value = t.Candy.Value Then
                    MatchingTilesInRow.Add(Tiles(r, c))
                Else
                    break = True
                End If
                c += 1
            End While
            'vertical lookup
            MatchingTilesInCol.Add(t)
            'upwards
            r = t.Row - 1
            c = t.Col
            break = False
            While Not (r < 0 Or break)
                If Tiles(r, c).Candy.Value = t.Candy.Value Then
                    MatchingTilesInCol.Add(Tiles(r, c))
                Else
                    break = True
                End If
                r -= 1
            End While
            'downwards
            r = t.Row + 1
            break = False
            While Not (r > 9 Or break)
                If Tiles(r, c).Candy.Value = t.Candy.Value Then
                    MatchingTilesInCol.Add(Tiles(r, c))
                Else
                    break = True
                End If
                r += 1
            End While
 
            If MatchingTilesInCol.Count >= 3 Then
                For Each tile As Tile In MatchingTilesInCol
                    If Not tilesToPop.Contains(tile) Then
                        tilesToPop.Add(tile)
                    End If
                Next
            End If
            If MatchingTilesInRow.Count >= 3 Then
                For Each tile As Tile In MatchingTilesInRow
                    If Not tilesToPop.Contains(tile) Then
                        tilesToPop.Add(tile)
                    End If
                Next
            End If
        Next
        Pop(tilesToPop) 'delete matching candies
    End Sub

Y a probablement moyen d'optimiser le bousin alors s'il y en a parmi vous qui sont intéressés, n'hésitez pas ! (je peux filer le code de tout le projet s'il faut)

Reste encore à écrire le code qui reconnaîtra le type de pattern et lui attribuera un score.

[Uranne-jimmy]

Bonjour,
Je l'avoue, je ne connais pas le principe de candy crush, uniquement le principe de ce genre de jeu ^^ et de ce que j'ai compris du code, ça fonctionne uniquement sur des lignes, sauf cas particulier dans le sens où tu ne regarde pas autour de toutes les cases identiques que tu as trouvé (en espérant que tu comprennes ma phrase O.o).
Une autre méthode, assez semblable, donc pas forcement intéressante, aurait était d'effectuer le même chemin que les cases, en changeant la case observé à chaque fois, en récursif, si je ne me trompe pas :

Code :

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

1
2
3
4
5
6
7
8
9
 
fonction regarderCaseAdjacente(case) :
pour i allant de 1 à 4
si coté(i) = case
enregistrer coté(i)
regarderCaseAdjacente(côté(i))
fin si
fin pour
fin fonction

Après je suis un débutant ^^'

[Kropernic]

[TROLL]
La vache, tu vis dans une grotte pour pas connaître candy crush ?!
[/TROLL]

Le principe de ce jeu est simple. On a une grille de x cases sur y cases (il peut y avoir des cases spéciales mais ne compliquons pas pour le moment^^) et chaque case possède une valeur entre 1 et 5 qui sont représentés, pour le cas de candy crush, par des bonbons de couleurs (et de formes) différentes. Il y en a des bleus, des rouges, des verts, des mauves et des jaunes*.

Le jeu se joue en permutant des cases directement adjacentes (ie pas en diagonale). Une fois les cases permutées, s'il y a une série de bonbons de la même couleur (donc de cases ayant la même valeur), on retire les bonbons** (ça fait marquer des points) et les vides sont comblés par ceux du dessus qui tombent (si le vide est sur la ligne supérieure, on en crée des nouveaux).

Les séries de bonbons (les patterns) se recherchent aussi bien verticalement qu'horizontalement. Les patterns existants sont :

• 3 à la suite
• 4 à la suite
• 5 à la suite
• En T (ou en L mais c'est pareil, juste l'intersection qui a bougé)

Du coup, soit je pige pas bien ton LDA, soit il te manquait de l'info et, du coup, ça ne correspond pas à la situation.

A priori, l'algo que j'ai pondu me trouve bien les séries de cases de même valeur lorsque je permute deux cases. Reste à prioriser maintenant. Car quand on a un T, faut pas qu'il prenne pour 3 à la suite. Ca fait moins de points^^.

* Y a encore des autres valeurs possibles mais ce sont des cas spéciaux donc plus tard.
** Pour les patterns autres que 3 à la suite, un bonbon spécial est créé mais c'est pour plus tard aussi.

[Kropernic]

Dans l'algo de mon 2e message, je stocke les cases qui constituent un pattern. Peut-être faudrait-il plutôt que je détecte à ce moment le type de pattern dont il s'agit et stocker carément le pattern en question (via une nouvelle classe qui va bien) histoire de pouvoir l'identifier par après pour l'attribution des points (et en bonus, la création du bonbon spécial s'il y a lieu)

[Uranne-jimmy]

[troll]
J'évite les jeux casus/sociaux dans ce genre là, je préfère un émulateur de GB ou un bon jeu de réflexion à un jeu comme celui là, surtout si, lié à facebook, il me demande de me mettre à genou et demander avec insistance des "vies" à mes contacts
[/troll]

J'ai oublié de préciser que i alant de 1 à 4 représente les 4 côtés, un for each CaseAdjacente fait pareil en plus clair.
Je ne sais pas si mon algo est correct, je pense qu'il marche, sauf qu'effectivement, je n'ai pas introduit la notion de ligne, de T ou de L uniquement de paquet de bonbons identiques collés quelque soit la forme du paquet. (ba oui, je connais le même type de jeu mais avec des règles légèrement différentes).

Pour autant, je vois des cas qui semblent ne pas fonctionner dans ton algo.
Imaginons que la case que tu test, qui vient donc de bouger, est à l'extrémité d'un T ? (le 2 dans le schéma suivant)

00000
02110<-- ligne testé
00100
00100
00000
-/\---
-||---
Colonne testé


Pour les patterns : si ils sont peu nombreux, c'est sans doute un moyen d'éviter une surcharge de travail du pc, si ils sont nombreux, tu vas te créer une surcharge de travail à faire tout les patterns.

Encore une fois, je nuance mes propos par l'expérience que j'ai : faible.

[Kropernic]

Cela ne pourra pas arriver.

Une combinaison valide est automatiquement supprimée

impossible donc d'avoir (en admettant que 0 est une valeur aléatoire dont on ne tient pas compte pour l'exemple)
0000000
0111000
0010000
0010000
0000000
0000000
où les cases ayant permutées sont celles en gras. Car la série en italique aurait été supprimée au coup précédent.

[Uranne-jimmy]

Je suis face à plus fort que moi ^^'

Dans la mesure de ce que tu m'apportes, le nombre de pattern différent est faible (2 lignes, 4 L et 4 T pour les cas en 5; 4 L et 2 ligne pour les cas en 4, 2 lignes pour les cas en 3). Moi je les enregistrerais en forme de tableau de coordonnées, en comparant ensuite de la même façon qu'on compare des vecteurs dans un graphique.

[Kropernic]

Oulah ! Je n'en ai pas autant lol.

Voici ce que j'ai fait pour les patterns.

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
Public MustInherit Class Pattern
    Public Property TileList As List(Of Tile)
End Class
 
Public Class ThreeInARow
    Inherits Pattern
 
    Public Sub New(tiles As List(Of Tile))
        Me.TileList = tiles
    End Sub
End Class
 
Public Class FourInARow
    Inherits Pattern
 
    Public Sub New(tiles As List(Of Tile))
        Me.TileList = tiles
    End Sub
End Class
 
Public Class FiveOrMoreInARow
    Inherits Pattern
 
    Public Sub New(tiles As List(Of Tile))
        Me.TileList = tiles
    End Sub
End Class
 
Public Class FiveOrMoreInT
    Inherits Pattern
 
    Public Sub New(tiles As List(Of Tile))
        Me.TileList = tiles
    End Sub
End Class

On pourrait débattre par contre quant au fait de savoir s'il est préférable de faire des classes séparées comme je l'ai fait ou d'avoir une propriété qui définirait le type de pattern sur base d'un Enum...

Si j'dis pas de connerie, c'est amplement suffisant.

[Uranne-jimmy]

Si on observe comment j'ai décidé de faire sur le projet que je monte, dont on a parlé à plusieurs reprises, je peux dire que j'opterais pour la même solution que toi. ^^

[Kropernic]

A l'occasion (p-e ce w-e sinon la semaine prochaine), je metterai à disposition toutes mes sources pour ce projet si jamais ça intéresse quelqu'un.

[Sankasssss]

Hello,

[troll]
Je ne connaissais pas non plus, juste de nom de par sa popularité, j'ai du aller voir une vidéo du jeu
[/troll]

l'idée de récursivité d'Uranne-jimmy est la meilleur, pas besoin de pattern.

Ca permet d'avoir des fonctions très courte pour tout vérifier.
J'ai vite fait un petit projet WPF à l'arrache pour tester et ça fonctionne :
grille de départ :

Clic sur le bouton qui inverse la case bleue et rouge et il marque toutes les cases qui sont bonnes :



On peut voir que la fonction récursive de vérification ne fait que 7 lignes, je l'ai placée volontairement au début du code :

Code vb.net :

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
Class MainWindow
    Sub recur(ByVal pionPrecedent As Point, ByVal couleur As SolidColorBrush, ByVal direction As Point, ByRef lPoint As List(Of Point))
        Dim p As New Point(pionPrecedent.X + direction.X, pionPrecedent.Y + direction.Y)
        If p.X < 0 Or p.X > nbreCol - 1 Then Exit Sub
        If p.Y < 0 Or p.Y > nbreRow - 1 Then Exit Sub
        If getColorCase(p).Equals(couleur) Then
            lPoint.Add(p)
            recur(p, couleur, direction, lPoint)
        End If
    End Sub
 
    Sub verifCase(ByVal p As Point)
        Dim lHorizontal As New List(Of Point)
        recur(p, getColorCase(p), New Point(-1, 0), lHorizontal)
        recur(p, getColorCase(p), New Point(1, 0), lHorizontal)
        Dim lVertical As New List(Of Point)
        recur(p, getColorCase(p), New Point(0, -1), lVertical)
        recur(p, getColorCase(p), New Point(0, 1), lVertical)
 
        If lHorizontal.Count >= 3 Then
            ' Le 4iem étant la case du millieu
            plateau(p.X, p.Y).Content = "OK"
            For Each p2 In lHorizontal
                plateau(p2.X, p2.Y).Content = "OK : H"
            Next
        End If
 
 
        If lVertical.Count >= 3 Then
            ' Le 4iem étant la case du millieu
            plateau(p.X, p.Y).Content = "OK"
            For Each p2 In lVertical
                plateau(p2.X, p2.Y).Content = "OK : V"
            Next
        End If
    End Sub
 
    Private plateau As Label(,)
 
    Private nbreCol As Integer = 10
    Private nbreRow As Integer = 10
 
    Public Sub New()
 
        ' Cet appel est requis par le concepteur.
        InitializeComponent()
 
        ' Ajoutez une initialisation quelconque après l'appel InitializeComponent().
        creePlateau()
        rempliPlateau()
    End Sub
 
    Sub creePlateau()
        ReDim plateau(nbreCol, nbreRow)
        GridPlateau.Background = Brushes.Black
        GridPlateau.RowDefinitions.Clear()
        GridPlateau.ColumnDefinitions.Clear()
        For i As Integer = 0 To 9
            GridPlateau.RowDefinitions.Add(New RowDefinition() With {.Name = "RowDefinition" & i})
            GridPlateau.ColumnDefinitions.Add(New ColumnDefinition() With {.Name = "ColumnDefinition" & i})
        Next
        For x As Integer = 0 To nbreCol - 1
            For y As Integer = 0 To nbreRow - 1
                Dim elem As New Label
                elem.Margin = New Thickness(1)
                elem.Background = Brushes.Brown
                elem.Content = x & " : " & y
                elem.VerticalContentAlignment = Windows.VerticalAlignment.Center
                elem.HorizontalContentAlignment = Windows.HorizontalAlignment.Center
                elem.Name = "Label_" & x & "_" & y
                GridPlateau.Children.Add(elem)
                Grid.SetColumn(elem, x)
                Grid.SetRow(elem, y)
                plateau(x, y) = elem
            Next
        Next
    End Sub
 
    Sub rempliPlateau()
        For x As Integer = 0 To nbreCol - 1
            For y As Integer = 0 To nbreRow - 1
                setCase(x, y, Brushes.Brown)
                plateau(x, y).Content = ""
            Next
        Next
        setCase(1, 1, Brushes.Red)
        setCase(1, 2, Brushes.Red)
        setCase(1, 3, Brushes.Red)
        setCase(2, 4, Brushes.Red)
        setCase(3, 4, Brushes.Red)
        setCase(4, 4, Brushes.Red)
 
        setCase(0, 3, Brushes.Blue)
        setCase(0, 5, Brushes.Blue)
        setCase(0, 6, Brushes.Blue)
 
        setCase(0, 4, Brushes.Red)
        setCase(1, 4, Brushes.Blue)
 
    End Sub
 
    Sub setCase(ByVal x As Integer, ByVal y As Integer, ByVal couleur As SolidColorBrush)
        plateau(x, y).Background = couleur
    End Sub
    Sub setCase(ByVal p As Point, ByVal couleur As SolidColorBrush)
        setCase(p.X, p.Y, couleur)
    End Sub
    Function getColorCase(ByVal x As Integer, ByVal y As Integer) As SolidColorBrush
        Return plateau(x, y).Background
    End Function
    Function getColorCase(ByVal p As Point) As SolidColorBrush
        Return getColorCase(p.X, p.Y)
    End Function
 
 
 
    Sub permutCase(ByVal c1 As Point, ByVal c2 As Point)
        Dim coulC1 As SolidColorBrush = getColorCase(c1)
        setCase(c1, getColorCase(c2))
        setCase(c2, coulC1)
        verifCase(c1)
        verifCase(c2)
 
    End Sub
 
 
 
 
    Private Sub ButtonPermuteCase_Click(ByVal sender As System.Object, ByVal e As System.Windows.RoutedEventArgs) Handles ButtonPermuteCase.Click
        permutCase(New Point(0, 4), New Point(1, 4))
    End Sub
End Class

Code xaml :

Code xaml :

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
<Window x:Class="MainWindow"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Title="MainWindow" Height="350" Width="525">
    <Grid>
        <Grid.RowDefinitions>
            <RowDefinition Height="274*" />
            <RowDefinition Height="37*" />
        </Grid.RowDefinitions>
        <Grid Grid.Row="0" Name="GridPlateau">
 
        </Grid>
 
        <WrapPanel Grid.Row="1">
            <Button Name="ButtonPermuteCase">Permute case</Button>
        </WrapPanel>
    </Grid>
 
</Window>

[Sankasssss]

J'ai voulu faire un test plus poussé et j'ai profité de cette soirée. Voila ce que ça donne :

Je pense que l'algo fonctionne bien ou alors j'ai rien compris au jeu

[shayw]

Bonjour

remplace les par des bonbons

[Kropernic]

J'ai voulu faire un test plus poussé et j'ai profité de cette soirée. Voila ce que ça donne :

Je pense que l'algo fonctionne bien ou alors j'ai rien compris au jeu

Je ne suis pas aussi convaincu que toi.

Après tes déplacements, il y a des séries de 3 qui ne sont détectées et supprimées.
Faut aussi pouvoir, en plus de détecter les séries, reconnaitre de quel type de série il s'agit.

Mais je pense aussi qu'il y a moyen de faire récursif... Mais je n'étais pas arrivé à un résultat probant. Alors j'ai fait quick & (not so much) dirty.

[Sankasssss]

Après tes déplacements, il y a des séries de 3 qui ne sont détectées et supprimées.

euh c'est normal, le jeu est réglé pour détecter des séries de 4 (C'est ce que j'ai vu dans les vidéo).

Faut aussi pouvoir, en plus de détecter les séries, reconnaitre de quel type de série il s'agit.

Tu peux préciser? Tu veux détecter quoi? Le nombre de case? La forme? De toute façon ce n'est plus très dur une fois que l'on traite une case il suffit de regarder quel sens il a trouvé et d’additionner (si haut + droite = L , si haut + droite + gauche = T, si une seule direction ou deux direction opposée = ligne, etc...)

[Sankasssss]

Hello,

j'ai modifié mon jeu pour le faire passer à 3 cases au lieu de 4 et j'ai essayé de penser à la reconnaissance de patterns.
Ca donne ça sans les points et les patterns en 3 cases :

Actuellement la fonction récursive est bonne si on se contente du jeu en l'état.
L'ajout de reconnaissance de patterns ne devrait pas poser de problème pour l'inversion de cases par contre, lors de la comptabilisation de l'abaissement du plateau, c'est une toute autre histoire vu que nous pouvons avoir énormément de solutions différentes :



et c'est la que la technique récursive atteint ces limites vu que je test toutes les colonnes, colonne par colonne en partant du bas vers le haut. Ou alors je dois faire un brut force...

Donc actuellement toutes les cellules qui sont marquées comme explosées sont testées même si elle sont déjà marquées comme explosées. Je pourrais faire en sorte qu'une fois marqué comme explosées elles ne soient plus testées mais ça ne changerait pas qu'il faut détecter le meilleur coup.
Du coup dans l'image ci-dessus, pour le T vert en dessous à droite il n'y aurait que le T de valable et actuellement avec mon algo il faudrait que je commence la recherche à l'intersection. C'est pas gagné...

[Kropernic]

Comme promis, en pièce jointe se trouve mes sources sur ce projet (ainsi qu'un backup de la db sql server qui va avec)

C'est encore moche. Y a pas encore de jolies images dans les cases et les items spéciaux (créés par les combinaisons autres que 3 à la suite) ne sont pas encore là.

Cela mis à part, il est fonctionnel. Il n'y a encore qu'un seul niveau et je bosse sur l'éditeur de niveau pendant que ma compagne me fait de jolies images pour illustrer le jeu (elle va faire avec des monstres si j'ai bien compris ^^)

Encore à implémenter :

• les bonbons spéciaux
• un multiplicateur de score pour les réactions en chaîne
• ajouter un nombre de permutation maximum pour atteindre l'objectif du niveau
• retenir le niveau maximal atteint pour un joueur histoire de mettre en place une progression
• un éventuel système de profil pour permettre à des utilisateurs différents (mais sur le même compte) de jouer.

Je pense qu'on pourrait continuer la liste longtemps^^.

Sinon, un truc qui me dérange c'est que je n'arrive pas à diminuer l'espace entre les cases du tablelayoutpanel que j'utilise pour afficher la grille... C'est assez frustrant. Je cherche aussi un joli moyen pour indiqué qu'une case est sélectionnée car pour le moment, c'est moche et presque invisible.

[mactwist69]

Mister TLP is here !

Sinon, un truc qui me dérange c'est que je n'arrive pas à diminuer l'espace entre les cases du tablelayoutpanel que j'utilise pour afficher la grille... C'est assez frustrant. Je cherche aussi un joli moyen pour indiqué qu'une case est sélectionnée car pour le moment, c'est moche et presque invisible.

J'imagine que tu as joué avec la propriété Margin...

Mais le truc c'est que ce n'est pas celui du TLP qu'il faut manipuler (celui là gère les marges extérieurs du TLP).

Le TLP n'a pas d’espace entre ses cases... C'est en fait les Margins de chacun des contrôles (avec Dock=Fill) qui se trouve à l'intérieur d'une case qu'il faut réduire à 0. Théoriquement, on pourrait tout coller bout à bout.

Il faut savoir aussi que tu peux changer la couleur de fond de chaque cellule du TLP (pratique)

DONC, en mettant les margins de chacun des contrôles à 1 par exemple (au lieu de 0), ça pourrait régler ton problème de "sélection" de case. Tu mets la couleur de fond par défaut transparent ou noir ou blanc, et pour les cases sélectionnées par exemple en rouge.

En jouant avec les margin, ça te fera une sélection plus ou moins épaisse. (3 par défaut)

Voir, avec un peu de travail, tu pourrais tout mettre à 0, et quand tu as une sélection, tu les mets à 1 temporairement, l'effet sera encore plus grand je pense. Tu pourrais aussi faire clignoter en alternant des couleurs... Il faut laisser parler l'artiste !

[Kropernic]

Merci Mactwist !

Ca faisait bien 1 semaine que je cherchais vaguement car pas bien important au demeurant.

Et c'est juste après t'avoir mis sur le coup que ça m'a fait tilt. Le usercontrol ! C'était pourtant l'évidence.

Quoi qu'il en soit, un grand merci pour ton intervention. Je vais sûrement pouvoir jouer avec ça pour la sélection de la case comme tu l'indiques