Java Oyunu: A * Algoritması (sadece karakterin önündeki hücreleri arar)
Oyun Türü: temel alan ızgara karo haritası
İzin verilen yönler: Sol, İleri, Sağ (yönleri tersine çevirmek için iki sol veya iki hak kullanmanız gerekir) - hem sol hem de sağ çapraz hareketler ancak orijinal yüze bağlı olarak geminin yüzünü değiştirin)
Yuvalar: Geminin boyutuna bağlı olarak, geminin tur başına bu kadar noktayı hareket ettirmesine izin vermek için kullanıcının girebileceği belirli sayıda yuva vardır (yani, 3 yuva == tur başına 3 hareket)
Misal:
Başlangıç Konumu: 2,2
Başlangıç yüzü: Kuzey
Yerleştirileni Taşı: Sol
Son Sonuç: Konum: 1,3; Yüz: Batı
Problem: algoritma, yol bulmak için 8 karonun hepsini kullanır; ancak sadece öndeki karoları aramalıdır (gemi yüzüne bağlıdır)
Düğüm sınıfı:
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;
}
}
Yol bulma hesaplaması:
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;
}
Uygulama:
@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;
}
}
}
}
}
}
Switch deyimini ve currentPosition.add () yöntemini kullanıyorum, böylece belirli bir dönüş için 3 hamle yerleştirdiğinizde; nereye varması gerektiğini bilir. Muhtemelen en iyi uygulama değil.
Belirli bir yuvaya bir hareket ekleyen ifade
getMoves().setMove(slot, MoveType.FORWARD);
Gemi yüzüne göre her dönüşte kontrol edilmesi gereken karolar:
Yanıtlar
Bu sadece kısmi bir girişim, yaptığım yorum için daha fazla ayrıntı veriyor.
A *, geminin "durumunu" içeren düğümlerin grafiğini arar. Çoğu öğreticide (benimki dahil, üzgünüm) durum yalnızca konumdur. Ama senin durumunda devletin hem pozisyon hem de bakan yön olduğunu düşünüyorum. Önündeki üç konumu hesaplamak için yüz yönünü bilmeniz gerekir. Ve hareketten sonra, hem bir pozisyona hem de yeni bir yöne sahip olacaksınız.
Nodeşu anda bir pozisyonu var; ikisine de sahip olacak şekilde değiştirin positionve facing. İşte for(int i = 0; i < 9; i++)komşuları bulmak için döngünün kaba bir versiyonu . 9 komşudan geçmek yerine, 4 yönün her birinin tam olarak 3 komşusu olacaktır. (Evet, 8 değil 12 var! Çünkü daha önce hangi yöne baktığınıza bağlı)
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
*/