# Thread: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

1. Member
Join Date
Oct 2016
Posts
5
Rep Power
0

## How to implement an algorithm in a game (A* algorithm in a 2D grid game)

'm a newbie in programming and in java and I need some lights and help.I'm developing a game in which two players have to play with tokens (say red and blue) by placing them in cells (75x75 grid). The goal is to "capture" opponent's tokens by surrounding them. (See the image, which is the actual game output, the surrounding is drawn by hand)

To do so, I need to make the tokens "listen" to neighborhood, meaning other cells in the grid. A token has to check for itself in the grid(what is its position in the grid) and check of there is another token close to it, checks it color (blue or red) then, in certain conditions, trigger the capturing mechanism (draw line segments from the last token to the first).

What I have done, technically:

Created the grid ( Grid/board is a 2 dimensional array of Token objects.)

The token (which is an enumeration:

Java Code:
`public enum Jeton{ VIDE, CERCLE_ROUGE, CERCLE_BLEU }`
).

A current player is also a Token
Java Code:
`private Jeton joueurActuel;`
, When it's a player's turn, they select an empty cell at which they click this place the
Java Code:
`joueurActuel`
into the grid/board at cell
Java Code:
` ligneSelectionnee, colonneSelectionnee`
then repaint the canvas with the newly added cell in the grid/board.

Everything works: every token is printed and switch as players click. Now i'm stuck on how to make the tokens listen the next cell surrounding them in order to see if there is an opponent or an ally so that

Someone suggested me the A algorithm* and the only documentations i found are in english - imagine the effort i have to do to understand properly. The one i found in french is about c++ implementation, I've no idea how to to it in java: keywords are different, etc.

PS: I posted this question on stack overflow first, but I guess no one is very interested in video games there. I'm just 15, so please be more tolerent. Please apologise for my english, i learn it from school and my mother language is french.

IMAGE:

Here is my code (took me several months and thousands attemps to make it work though): variables names are in french, I can provide translation if needed.

Java Code:
``` import javax.swing.JFrame;
import java.awt.*;
import java.awt.event.MouseEvent;
import javax.swing.*;

public final class Phagocyte extends JFrame {

public  static final int LIGNES = 75; //Cellules = lignes x colonnes
public static final int COLONNES = 75;//Cellules = lignes x colonnes

//Noms des constants des dimensions variées utilisées pour le dessins graphiques
public static final float TAILLE_CELLULE = (float) 20.0; //Largeur et hauteur des cellules (de forme carée)
public static final int LARGEUR_DE_LA_TOILE = (int) (TAILLE_CELLULE * COLONNES); // Dessine la toille (tableau)
public static final int HAUTEUR_DE_LA_TOILE = (int) (TAILLE_CELLULE * LIGNES);
public static final int LARGEUR_DE_LA_GRILLE = 2; // La largeur des lignes de la grille
public static final int DEMI_LARGEUR_GRILLE = LARGEUR_DE_LA_GRILLE / 2;

//Les symboles (rouge et bleu) sont affichés à l'intérieur des cercles avec rembourage des bordures
public static final int REMBOURAGE_CELLULE = (int) (TAILLE_CELLULE / 5);
public static final int TAILLE_SYMBOLE = (int) (TAILLE_CELLULE - REMBOURAGE_CELLULE *2 ); //Largeur / Hauteur
public static final int LARGEUR_TRAIT_SYMBOLE = 3; //Largeur des traits

//Utiliser une table d'ennumération (class interne) pour représenter les états variés du jeu
public enum EtatJeu{
JOUE, NUL, CERCLE_ROUGE_GAGNE, CERCLE_BLEU_GAGNE
}

private EtatJeu etatActuel;

public enum Jeton{
VIDE, CERCLE_ROUGE, CERCLE_BLEU
}

private Jeton joueurActuel; //Le joueur qui a la main

private Jeton[][] planche; //l'aire de jeu avec cellules composées des lignes et colonnes
private DessineToile toile; //Dessine la toile (avec JPanel) pour l'air de jeu
private JLabel barreDetat; // La barre d'état

/*Constructeurs pour definir les composants du jeu et de l'interface utilisateur (IU)*/
public Phagocyte(){

toile = new DessineToile(); //Construit une toile (JPanel)
toile.setPreferredSize(new Dimension(LARGEUR_DE_LA_TOILE, HAUTEUR_DE_LA_TOILE));

//Comportement de la toile (JPanel) en rapport avec un clic de la souris
@Override
public void mouseClicked(MouseEvent e) { //Gestion des clics de souris
int sourisX = e.getX();
int  sourisY = e.getY();

//Verifier le clic sur les lignes et colonnes
int ligneSelectionnee = (int) (sourisY / TAILLE_CELLULE);
int colonneSelectionnee;
colonneSelectionnee = (int) (sourisX / TAILLE_CELLULE);

if(etatActuel == EtatJeu.JOUE){
if(ligneSelectionnee >= 0 && ligneSelectionnee < LIGNES && colonneSelectionnee >= 0
&& colonneSelectionnee < COLONNES &&
planche[ligneSelectionnee][colonneSelectionnee] == Jeton.VIDE){
planche[ligneSelectionnee][colonneSelectionnee] = joueurActuel; //Joue un tour
actualiseJeu(joueurActuel, ligneSelectionnee, colonneSelectionnee); //Met a jour l'etat de jeu
joueurActuel = (joueurActuel == Jeton.CERCLE_ROUGE)? Jeton.CERCLE_BLEU : Jeton.CERCLE_ROUGE;
}
} else { //Fin de la partie
initJeu(); //Rejouer le jeu
}
//Actueliser le dessin de la toile
repaint(); //Rappeler la fonction dessinner
}

});

//Barre d'état (JPanel) pour afficher les messages
barreDetat = new JLabel("  ");
barreDetat.setFont(new Font(Font.DIALOG_INPUT, Font.ITALIC, 15));
barreDetat.setBorder(BorderFactory.createEmptyBorder(2, 5, 4, 5));

Container cp = getContentPane();
cp.setLayout(new BorderLayout());

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
pack(); //Emballer tous les composants dans cette JFrame
setTitle("Phagocyte par esQmo");
setVisible(true); //Afficher cette fenetre

planche = new Jeton[LIGNES][COLONNES]; //Allouer le tableau
initJeu(); //Initialise les contenus de l'aire de jeu et ses variables
}
/*initialisation  des contenus l'aire de jeu et les differenrs status*/
public void initJeu(){
for(int ligne = 0; ligne < LIGNES; ++ligne){
for(int colonne = 0; colonne < COLONNES; ++colonne){
planche[ligne][colonne] = Jeton.VIDE; //Toutes les cellules sont vides
}
}
etatActuel = EtatJeu.JOUE; //Pret a jouer
joueurActuel = Jeton.CERCLE_ROUGE; //Le rouge ouvre la partie
}

public void actualiseJeu(Jeton leJeton, int ligneSelectionnee, int colonneSelectionnee) {
if (aGagne(leJeton, ligneSelectionnee, colonneSelectionnee)) {  // check for win
etatActuel= (leJeton == Jeton.CERCLE_ROUGE) ? EtatJeu.CERCLE_ROUGE_GAGNE : EtatJeu.CERCLE_BLEU_GAGNE;
} else if (estNul()) {  // check for draw
etatActuel = EtatJeu.CERCLE_BLEU_GAGNE;
}

}
/**Need to create a drawn and win scenario**/

/*    public boolean estNul() {
for (int row = 0; row < LIGNES; ++row) {
for (int col = 0; col < COLONNES; ++col) {
if (planche[row][col] == Jeton.VIDE) {
return false;
}
}
}
return true;
}

public boolean aGagne(Jeton leJeton, int ligneSelectionnee, int colonneSelectionnee) {
return
}
*/

class DessineToile extends JPanel{

@Override
public void paintComponent(Graphics g){ //Invoqué via repaint()
super.paintComponent(g); //Pour remplir l'arriere plan
setBackground(Color.WHITE); //Defini la couleur de l'arriere plan

//Dessine les lignes de la toile
g.setColor(Color.BLACK);
for(int ligne = 1; ligne < LIGNES; ++ligne){
g.fillRoundRect(0, (int) (TAILLE_CELLULE * ligne - DEMI_LARGEUR_GRILLE), LARGEUR_DE_LA_TOILE - 1,
LARGEUR_DE_LA_GRILLE, LARGEUR_DE_LA_GRILLE, LARGEUR_DE_LA_GRILLE);
}
for(int colonne = 1; colonne < COLONNES; ++colonne){
g.fillRoundRect((int) (TAILLE_CELLULE * colonne - DEMI_LARGEUR_GRILLE), 0
, LARGEUR_DE_LA_GRILLE, HAUTEUR_DE_LA_TOILE - 1,
LARGEUR_DE_LA_GRILLE, LARGEUR_DE_LA_GRILLE);
}

//Dessine le jeton (seed) pour toutes les cellules si elles ne sont pas vides
//Utilise la Graphic2D pour le trait
Graphics2D g2d = (Graphics2D)g;
g2d.setStroke(new BasicStroke(LARGEUR_TRAIT_SYMBOLE,
BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND)); //Dessin en 2D uniquement
for(int ligne = 0; ligne < LIGNES; ++ligne){
for(int colonne = 0; colonne < COLONNES; ++colonne){
int x1 = (int) (colonne * TAILLE_CELLULE + REMBOURAGE_CELLULE);
int y1 = (int) (ligne * TAILLE_CELLULE + REMBOURAGE_CELLULE);

if(planche[ligne][colonne] == Jeton.CERCLE_ROUGE){
g2d.setColor(Color.RED);
g2d.drawOval(x1, y1, TAILLE_SYMBOLE, TAILLE_SYMBOLE);
g2d.fillOval(x1, y1, TAILLE_SYMBOLE, TAILLE_SYMBOLE);
} else
if(planche[ligne][colonne] == Jeton.CERCLE_BLEU){
int x2 = (int) (colonne * TAILLE_CELLULE + REMBOURAGE_CELLULE);
g2d.setColor(Color.BLUE);
g2d.drawOval(x1, y1, TAILLE_SYMBOLE, TAILLE_SYMBOLE);
g2d.fillOval(x2, y1, TAILLE_SYMBOLE, TAILLE_SYMBOLE);
}
}

}

//Imprime les messages sur la barre d'etat
if(etatActuel == EtatJeu.JOUE){
if(joueurActuel == Jeton.CERCLE_ROUGE){
barreDetat.setText("ROUGE, c'est votre tour");
barreDetat.setForeground(Color.RED);
} else {
barreDetat.setText("BLEU, c'est votre tour");
barreDetat.setForeground(Color.BLUE);
}
} else
if(etatActuel == EtatJeu.NUL){
barreDetat.setForeground(Color.yellow);
barreDetat.setText("Match nul! Cliquez pour rejouer");
} else
if(etatActuel == EtatJeu.CERCLE_ROUGE_GAGNE){
barreDetat.setText("Le jouer X a remporté la partie, cliquez pour rejouer");
barreDetat.setForeground(Color.RED);
} else
if(etatActuel == EtatJeu.CERCLE_BLEU_GAGNE){
barreDetat.setForeground(Color.BLUE);
barreDetat.setText("Le joueur O a remporté la partie, cliquez pour rejouer");
}
}
}

/*La méthode principale*/
public static void main(String[] args){
SwingUtilities.invokeLater(() -> {
Phagocyte phagocyte = new Phagocyte();
});
}```

2. ## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

Google for 'flood fill'; if the area leaks, or 'bleeds', the area isn't taken (yet) by the opponent. Note: this isn't trivial to implement.

kind regards,

Jos

3. Member
Join Date
Oct 2016
Posts
5
Rep Power
0

## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

I'm looking how I can implement it with my code. People suggested me to use A* algorithm

4. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

Did you google "Flood Fill" as Jos suggested? It is the algorithm used in Go which is similar to your requirement. The web should have plenty of examples
on various algorithms. But it will require effort on your part to apply them.

Regards,
Jim

5. Member
Join Date
Oct 2016
Posts
5
Rep Power
0

## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

I gooled it and found hundred of posts but in english. im just a newbie! and understanding English is not easy.

6. ## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

This wiki page explains it quite well: https://en.wikipedia.org/wiki/Flood_fill; a bit down the page click on the (badly drawn) smiley; it shows how the algorithm works; the page is also available in Dutch (for what it's worth to you).

kind regards,

Jos

7. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

Jos,

It didn't like the trailing semi-colon so I reposted the link -> https://en.wikipedia.org/wiki/Flood_fill

@OP, go do this site and there are various translations to the left. They aren't necessarily as complete as the English version but

Regards,
Jim

8. ## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

Originally Posted by jim829
Jos,

It didn't like the trailing semi-colon so I reposted the link -> https://en.wikipedia.org/wiki/Flood_fill
Oh dear; that semi colon was a small token of my (artistic) creativity and even that upset that stupid forum software ;-) I originally wrote that a flood fill algorithm isn't trivial because it is only part of the solution (and so is an A* algorithm); Go is a hell of a game ...

kind regards,

Jos

9. Member
Join Date
Oct 2016
Posts
5
Rep Power
0

## Re: How to implement an algorithm in a game (A* algorithm in a 2D grid game)

Thanks guys, I'll try