artificial intelligence for a tank
I have te do this this program in wich the tank has to go get a flag and retrun it to bas as many times as possible and if it sees another tank, it must shoot it, the game is only won if the tank has collected more falg than the openent, the teacher gave us the Tank examples in wich there are no intelligence so I have been trying to program it but its not working, i was woundering if somebody could help me,
Code:
/** Template pour creer un Tank */
class FranckTheTank extends Tank
{
boolean drapeauVu;
int drapeauPosX;
int drapeauPosY;
boolean tankVu;
int tankPosX;
int tankPosY;
boolean baseVu;
int basePosX;
int basePosY;
int[][] tableauXY;
String messageEnvoyer;
private final static int penalite = 9; // on doit avoir une penalite sur chaque noeud source: http://www.codeproject.com/KB/recipes/mazesolver.aspx
public NoeudChemin [] ListeNoeud;
public int ListeIndex = 0; // Marque notre position dans notre liste
private int LargeurTableau;
private int HauteurTableau;
private int[][] tableau;
/** initialisation */
void init()
{
messageEnvoyer = "Pizza";
tableauXY = new int[getDimX()][getDimY()];
for(int i=0;i < getDimX();i++)
{
for(int j=0;j < getDimY();j++)
{
tableauXY[i][j] = -1;
}
}
drapeauVu = false;
drapeauPosX = drapeauPosY = -1;
tankVu = false;
tankPosX = tankPosY = -1;
baseVu = false;
basePosX = basePosY = -1;
}
// Methodes d'input
/**
* Cette methode est appele a chaque debut de tour...
* Si vous avez des variables a initialiser a chaque tour,
* c'est la que ca se passe!!!
*/
void debutTour()
{
tankVu = false;//Le tank bouge
messageEnvoyer = "Pizza";//Reinitialise le message
}
/**
Recoit un message de la part d'un tank autre tank
(pas necessairement de la meme equipe
**/
void processTankMessage( String message ) {}
/**
Recoit un message du serveur. Par exemple
Tank 7 from team 2 dead
Flag returned to base 1
Team 1 wins
*/
void processGameMessage( String gameMessage ) {}
/**
Voit un morceau de map statique (vide, mur, drapeau).
Trois valeurs possibles pour elementType:
WALL , EMPTY ou FLAG
*/
void seeBoardElement( int elementType , int x , int y )
{
if(elementType == WALL)
{
if(tableauXY[x][y] == -1)//effectue l'action seulement s'il n'est pas deja en memoire
{
tableauXY[x][y] = WALL;
if(messageEnvoyer.length() <= 50)//Garde de l'espace pour si on voit un tank
{
messageEnvoyer = messageEnvoyer +"";//******
}
}
}else if(elementType == FLAG)
{
if(tableauXY[x][y] == -1)//effectue l'action seulement s'il n'est pas deja en memoire
{
tableauXY[x][y] = FLAG;
drapeauVu=true;
drapeauPosX=x;
drapeauPosY=y;
if(messageEnvoyer.length() <= 50)//Garde de l'espace pour si on voit un tank
{
messageEnvoyer = messageEnvoyer +"";//******
}
}
}else if(elementType == EMPTY)
{
if(tableauXY[x][y] == -1)//effectue l'action seulement s'il n'est pas deja en memoire
{
tableauXY[x][y] = EMPTY;
if(messageEnvoyer.length() <= 50)//Garde de l'espace pour si on voit un tank
{
messageEnvoyer = messageEnvoyer +"";//******
}
}
}
}
/** Voit le tank d'id unique specifie d'equipe specifiee en position absolue (x,y) */
void seeTank( int seenTankId , int seenTankTeamId , int x , int y )
{
if(seenTankTeamId != getTeamId())
{
tankVu = true;
tankPosX=x;
tankPosY=y;
messageEnvoyer = messageEnvoyer +"";//******
}
}
/** voit la base de l'equipe specifiee */
void seeBase( int teamId , int x , int y )
{
if(teamId != getTeamId())
{
baseVu = true;
basePosX = x;
basePosY = y;
}
}
// Methode d'ouput
Action makeAction()
{
Action action=null;
int direction = 0;
int dxBut, dyBut;
if(tankVu == true)
{
action = new FireAction(tankPosX,tankPosY,messageEnvoyer);
}
else
{
Point initial = new Point(getX(),getY());
Point destination = new Point(10,10);
Point suivant = TrouverPointPremier(initial,destination);
dxBut = suivant.getX();
dyBut = suivant.getY();
if(dxBut-initial.getX() >= 1 && dyBut-initial.getY() == 0)
{
direction = EAST;
}
if(dxBut-initial.getX() < 1 && dyBut-initial.getY() == 0)
{
direction = WEST;
}
if(dyBut-initial.getY() >= 1 && dxBut-initial.getX() == 0)
{
direction = NORTH;
}
if(dyBut-initial.getY() < 1 && dxBut-initial.getX() == 0)
{
direction = SOUTH;
}
if(dxBut == initial.getX() && dyBut == initial.getY())
{
direction = 0;
}
action = new MoveAction(direction,messageEnvoyer);
}
return action;
}
private NoeudChemin RechercheListeNoeud(Point p) // Rechcher si le Noeud a la postion x,y existe
{
int IndexListe = 0;
NoeudChemin NoeudRecherche = null;
while(NoeudRecherche == null && IndexListe < ListeIndex) // Tant qu'on a pas trouve un noeud recherche ou qu'on a parcouru tous les noeuds sans resultat.
{
if(ListeNoeud[IndexListe].courrant.CompareA(p))
{
NoeudRecherche = ListeNoeud[IndexListe];
}
else
{
IndexListe++;
}
}
return NoeudRecherche;
}
private int SommeNoeudOuvert() // Calcul la somme des noeuds ouverts les noeuds ouverts. S'il n'en reste plus aucun il n'y a plus d'options possible
{
int somme = 0;
for(int i = 0;i < ListeIndex;i++)
{
if(ListeNoeud[i].estVisite == false) // Noeuds vistes ignores
{
somme++;
}
}
return somme;
}
private NoeudChemin RechercherNoeudDepenseMin() // Noeud ouvert qui a la depense la plus faible
{
NoeudChemin NoeudDepenseMin = null;
for(int i = 0; i < ListeIndex;i++)
{
if(!ListeNoeud[i].estVisite && (NoeudDepenseMin == null || ListeNoeud[i].getDepenseF() < NoeudDepenseMin.getDepenseF())) // Si depense plus petite que precedement
{
NoeudDepenseMin = ListeNoeud[i];
}
}
return NoeudDepenseMin;
}
private void AjouteNoeudOuvertListe(NoeudChemin n) // Ajoute un noeud ouvert.
{
n.estVisite = false;
ListeNoeud[ListeIndex] = n;
ListeIndex++;
}
private int CalculHeuristique(NoeudChemin n, Point arrivee)
{
int heuristique = (int) arrivee.Distance(arrivee, n.courrant, false); // manhattan method
int SommePenalite = 0;
for(int x = n.courrant.x - penalite; x <= n.courrant.x + penalite;x++)
{
for(int y = n.courrant.y - penalite; y <= n.courrant.y + penalite;y++)
{
if(x < LargeurTableau && y < HauteurTableau && x >= 0 && y >= 0) // Out of bounds?
{
if(tableau[y][x] == TANK)
{
SommePenalite = penalite - (int)n.courrant.Distance(n.courrant, new Point(x,y), false);
if (SommePenalite < 0) SommePenalite = 0; // penalite aux distances entre le noeud et les ennemis
{
SommePenalite += SommePenalite*100;
}
}
}
}
}
return heuristique;
}
public Point TrouverPointPremier(Point initial, Point destination) // Retourne le prochain Point
{
if(initial.CompareA(destination)) // Si les deux sont pareils, on retourne le point de depart.
{
return initial;
}
else
{
NoeudChemin chemin = RechercheChemin(initial, destination);
Point PointPremier = null;
while(chemin != null)
{
if(chemin.origine.origine == null)
{
PointPremier = chemin.courrant;
}
chemin = chemin.origine;
}
return PointPremier;
}
}
public NoeudChemin RechercheChemin(Point initial, Point destination) // Retourne Le noeud contenu a la position d'arrivee ou null s'il n'y a aucun trajet. Si on va d'origine a origine, on obtiendra le trajet complet
{
boolean recherche = false;
int indexListe = 0; // On reintialise l'index de la liste
ListeNoeud = new NoeudChemin[this.LargeurTableau * this.HauteurTableau];
NoeudChemin NoeudInitial = new NoeudChemin(initial); // Premier noeud
NoeudChemin NoeudRecherche = null; // Sauvegarder dasn NoeudRecherche
AjouteNoeudOuvertListe(NoeudInitial); // ajoute le noeud premier a la liste de noeuds "ouverts"
while(!recherche && SommeNoeudOuvert() > 0) // Boucle tant qu'on est pas arrive a destination ou que tous les noeuds ont ete visites
{
NoeudChemin NoeudActuel = RechercherNoeudDepenseMin(); // On recherche le noeud ouvert aillant la depense la plus faible dans la liste
if(NoeudActuel.courrant.CompareA(destination)) // si ce noeud egal destination, on sort de la boucle et on retourne le noeud
{
NoeudRecherche = NoeudActuel;
recherche = true;
continue;
}
// Sinon on regarde les 4 noeud adjacents
NoeudActuel.estVisite = true;
for(int x = NoeudActuel.courrant.x-1; x <= NoeudActuel.courrant.x+1; x++) // [x][A][x] "[A]" est la position actuelle Rappel: les mouvements diagonaux sont illegaux
{
for(int y = NoeudActuel.courrant.y-1; y<= NoeudActuel.courrant.y+1;y++) // [-][E][-] [E] sont les noeuds a explorer
{
if(tableau[y][x] != WALL) // et si pas sur un mur
{
if((x != NoeudActuel.courrant.x-1 || y != NoeudActuel.courrant.y-1) && (x != NoeudActuel.courrant.x-1 || y != NoeudActuel.courrant.y+1)) // les mouvements ne sont pas diagonaux droites
{
if((x != NoeudActuel.courrant.x+1 || y != NoeudActuel.courrant.y-1) && (x != NoeudActuel.courrant.x+1 || y != NoeudActuel.courrant.y+1)) // les mouvements ne sont pas diagonaux gauches
{
if(y < HauteurTableau && x < LargeurTableau && y >= 0 && x >= 0) // Si le noeud n'est pas en dehors de la carte
{
if(x != NoeudActuel.courrant.x || y != NoeudActuel.courrant.y) // et si le noeud n'est l'actuel
{
Point NoeudAdjacent = new Point(x,y); // On verifie si le noeud est deja la
NoeudChemin NoeudTmp = RechercheListeNoeud(NoeudAdjacent);
if(NoeudTmp == null) // Si non, on l'ajoute en calculant l'heuristique et la depense
{
NoeudTmp = new NoeudChemin(new Point(x,y));
NoeudTmp.origine = NoeudActuel;
NoeudTmp.setDepenseG(NoeudTmp.origine.getDepenseG() + 10); // On ajoute dix a la depense du noeud origine source: http://www.policyalmanac.org/games/aStarTutorial.htm
NoeudTmp.setDepenseH(CalculHeuristique(NoeudActuel, destination));
AjouteNoeudOuvertListe(NoeudTmp); // On ajoute le noeud a la liste des noeuds "ouverts" note: Si le noeud egal destination on sort de la boucle
if(NoeudTmp.courrant.CompareA(destination))
{
NoeudRecherche = NoeudTmp;
recherche = true;
}
}
else if(!NoeudTmp.estVisite && NoeudTmp.getDepenseG() > NoeudActuel.getDepenseG()) // S'il existe et qu'il a deja ete visite et que la depense initiale plus grande que celle actuelle
{
NoeudTmp.origine = NoeudActuel;
NoeudTmp.setDepenseG(NoeudActuel.getDepenseG() + 10);
}
}
}
}
}
}
}
}
}
return NoeudRecherche;
}
}
class Point
{
public int x,y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
public int getX()
{
return this.x;
}
public int getY()
{
return this.y;
}
boolean CompareA(Point p)
{
return ((this.x == p.x) && (this.y == p.y));
}
public static int Distance(Point p1, Point p2, boolean pareil)
{
pareil = p1.CompareA(p2);
if (pareil)
{
return 1;
}
return (int) Math.sqrt((Math.pow((p2.x - p1.x), 2) + Math.pow((p2.y - p1.y), 2)));
}
}
class NoeudChemin // Chaque noeud contient la depense total du noeud (l'Algorithme A* : F = H + G)
{
private int depenseF; // Depense total du noeud (depense + depense heuristique)
private int depenseG; // depense d'un deplacement du point de depart jusqu'a un autre point donne
private int depenseH; // Estimation de la depense du point initial au point donne (heuristique)
public boolean estVisite; // Indique si le noeud a deja ete visite.
public Point courrant; // Les coordonnes x et y du noeud
public NoeudChemin origine; // Le noeud origine nous permmettra de retracer notre chemin jusqu'a notre base
public NoeudChemin(Point p)
{
courrant = p;
}
public int getDepenseG()
{
return depenseG;
}
public int getDepenseH()
{
return depenseH;
}
public int getDepenseF()
{
return depenseF;
}
public void setDepenseG(int g) // Permet de changer la depense d'un deplacement entre le point initial et le noeud courrant
{
depenseG = g;
depenseF = depenseG + depenseH;
}
public void setDepenseH(int h) // Permet de mettre a jour l'estimation de la depense pour passer du noeud courrant au point donne
{
depenseH = h;
depenseF = depenseG + depenseH;
}
}
basically I tried using the A* algorithm for the shortest path to the flag (which we do not know were it is)
Thks
