Java Game: A * Algorithm (cerca solo le celle davanti al carattere)
Tipo di gioco: mappa delle tessere della griglia basata su turni
Direzioni consentite: Sinistra, Avanti, Destra (per invertire le direzioni è necessario utilizzare due sinistre o due destre) - entrambe le direzioni sinistra e destra si muovono in diagonale ma cambiano la faccia della nave a seconda della faccia originale)
Slot: a seconda delle dimensioni della nave ci sono un certo numero di slot per quella particolare nave in cui l'utente può entrare per consentire alla nave di muoversi di altrettanti punti per turno (cioè 3 slot == 3 mosse per turno)
Esempio:
Posizione iniziale: 2,2
Fronte di partenza: nord
Sposta posizionata: a sinistra
Risultato finale: Posizione: 1,3; Faccia: Ovest
Problema: l'algoritmo utilizza tutte le 8 tessere per la ricerca del percorso; ma dovrebbe cercare solo le tessere che sono davanti (dipende dalla faccia della nave)
Classe nodo:
public class AStarNode {
public Position position;
public VesselFace face;
public AStarNode parent;
public double fCost, gCost, hCost;
public AStarNode(Position position, VesselFace face, AStarNode parent, double gCost, double hCost) {
this.position = position;
this.face = face;
this.parent = parent;
this.gCost = gCost;
this.hCost = hCost;
this.fCost = this.gCost + this.hCost;
}
}
Calcolo del pathfinding:
private Comparator<AStarNode> nodeSorter = new Comparator<AStarNode>() {
@Override
public int compare(AStarNode n0, AStarNode n1) {
if(n1.fCost < n0.fCost) return 1;
if(n1.fCost > n0.fCost) return -1;
return 0;
}
};
public List<AStarNode> findPath(Position start, Position goal){
List<AStarNode> openList = new ArrayList<AStarNode>();
List<AStarNode> closedList = new ArrayList<AStarNode>();
AStarNode current = new AStarNode(start, null, 0, start.distance(goal));
openList.add(current);
while(openList.size() > 0) {
Collections.sort(openList, nodeSorter);
current = openList.get(0);
if(current.position.equals(goal)) {
List<AStarNode> path = new ArrayList<AStarNode>();
while(current.parent != null) {
path.add(current);
current = current.parent;
}
openList.clear();
closedList.clear();
return path;
}
openList.remove(current);
closedList.add(current);
for(int i = 0; i < 9; i++) {
if (i == 4)continue;
int x = current.position.getX();
int y = current.position.getY();
int xi = (i % 3) - 1;
int yi = (i / 3) - 1;
int at = context.getMap().getTile(x + xi, y + yi);
if(at == 1 || at == 2) continue; // ignore rocks
Position a = new Position(x + xi, y + yi);
double gCost = current.gCost + current.position.distance(a);
double hCost = a.distance(goal);
AStarNode node = new AStarNode(a, current, gCost, hCost);
if(positionInList(closedList, a) && gCost >= node.gCost) continue;
if(!positionInList(openList, a) || gCost < node.gCost) openList.add(node);
}
}
closedList.clear();
return null;
}
private boolean positionInList(List<AStarNode> list, Position position) {
for(AStarNode n : list) {
if(n.position.equals(position)) return true;
}
return false;
}
Implementazione:
@Override
public void calculateRoute() {
Position destination = new Position(3,3); // replace with cluster
if(this.equals(destination)) {
return;
}based
path = context.getPlayerManager().findPath(this, destination);
VesselFace face = getFace();
if(path != null) {
if(path.size() > 0) {
int numberOfMoves = getVessel().has3Moves() ? 3 : 4;
Position currentPosition = this.copy();
for(int slot = 0; slot <= numberOfMoves; slot++) { //moves to enter
int positionIndex = (path.size() - 1) - (slot); //subtract slot to allow multiple moves
if(positionIndex < 0 || path.size() < slot) { // make sure it doesn't count too far
return;
}
Position pos = path.get(positionIndex).position;
Position left = MoveType.LEFT.getFinalPosition(currentPosition, face);
Position right = MoveType.RIGHT.getFinalPosition(currentPosition, face);
Position forward = MoveType.FORWARD.getFinalPosition(currentPosition, face);
if(left.equals(pos)) {
currentPosition.add(left.getX() - getX(), left.getY() - getY());
getMoves().setMove(slot, MoveType.LEFT);
switch(face) {
case NORTH:
face = VesselFace.WEST;
break;
case SOUTH:
face = VesselFace.EAST;
break;
case WEST:
face = VesselFace.SOUTH;
break;
case EAST:
face = VesselFace.NORTH;
break;
}
}else if(right.equals(pos)) {
currentPosition.add(right.getX() - getX(), right.getY() - getY());
getMoves().setMove(slot, MoveType.RIGHT);
switch(face) {
case NORTH:
face = VesselFace.EAST;
break;
case SOUTH:
face = VesselFace.WEST;
break;
case WEST:
face = VesselFace.NORTH;
break;
case EAST:
face = VesselFace.SOUTH;
break;
}
}else if(forward.equals(pos)){
currentPosition.add(forward.getX() - getX(), forward.getY() - getY());
getMoves().setMove(slot, MoveType.FORWARD);
switch(face) {
case NORTH:
face = VesselFace.NORTH;
break;
case SOUTH:
face = VesselFace.SOUTH;
break;
case WEST:
face = VesselFace.WEST;
break;
case EAST:
face = VesselFace.EAST;
break;
}
}
}
}
}
}
Uso l'istruzione switch e il metodo currentPosition.add () in modo che quando posizioni 3 mosse per quel particolare turno; sa dove dovrebbe finire. Probabilmente non è la migliore pratica.
Istruzione che aggiunge una mossa allo slot particolare
getMoves().setMove(slot, MoveType.FORWARD);
Tessere che dovrebbero essere controllate ogni turno in base alla faccia della nave:
Risposte
Questo è solo un tentativo parziale, fornendo maggiori dettagli per il commento che ho fatto.
A * cerca su un grafico di nodi che contengono lo "stato" della nave. Nella maggior parte dei tutorial (incluso il mio, mi dispiace) lo stato è solo la posizione. Ma nel tuo caso penso che lo stato sia sia la posizione che la direzione di fronte. È necessario conoscere la direzione di orientamento per calcolare le tre posizioni di fronte ad essa. E poi, dopo il movimento, avrai sia una posizione che una nuova direzione di fronte.
Nodeattualmente ha una posizione; cambiarlo per avere sia positione facing. Ecco una versione approssimativa del for(int i = 0; i < 9; i++)ciclo per trovare i vicini. Invece di passare attraverso 9 vicini, ciascuna delle 4 direzioni avrà esattamente 3 vicini. (Sì, sono 12, non 8! Perché dipende da quale direzione eri rivolto prima)
int x = current.position.getX();
int y = current.position.getY();
List<Node> neighbors = new ArrayList<Node>();
switch (current.facing) {
case NORTH:
neighbors.add(new Node(new Position(x-1, y-1), WEST, …));
neighbors.add(new Node(new Position(x, y-1), NORTH, …));
neighbors.add(new Node(new Position(x+1, y-1), EAST, …));
break;
case EAST:
neighbors.add(new Node(new Position(x+1, y-1), NORTH, …));
neighbors.add(new Node(new Position(x+1, y), EAST, …));
neighbors.add(new Node(new Position(x+1, y+1), SOUTH, …));
break;
case SOUTH:
neighbors.add(new Node(new Position(x-1, y+1), WEST, …));
neighbors.add(new Node(new Position(x, y+1), SOUTH, …));
neighbors.add(new Node(new Position(x+1, y+1), EAST, …));
break;
case WEST:
neighbors.add(new Node(new Position(x-1, y-1), NORTH, …));
neighbors.add(new Node(new Position(x-1, y), WEST, …));
neighbors.add(new Node(new Position(x-1, y+1), SOUTH, …));
break;
}
/* for each of the nodes in the neighbors list, use the same
logic you already have:
1. check if it's a rock, and ignore if it is
2. calculate g cost, store it in the node
3. calculate h cost, store it in the node
4. consider adding the node to openList
*/