Trò chơi Java: Thuật toán A * (chỉ tìm kiếm các ô phía trước ký tự)
Loại trò chơi: bản đồ ô lưới được quay dựa trên
Chỉ đường được phép: Trái, Tiến, Phải (để đảo ngược hướng, bạn phải sử dụng hai đòn bẩy hoặc hai quyền) - cả trái và phải di chuyển theo đường chéo nhưng thay đổi mặt tàu tùy thuộc vào mặt ban đầu)
Khe cắm: Tùy thuộc vào kích thước con tàu, có một số khe cắm nhất định cho con tàu cụ thể đó để người dùng nhập vào để cho phép con tàu di chuyển nhiều điểm đó mỗi lượt (tức là 3 chỗ trống == 3 lần di chuyển mỗi lượt)
Thí dụ:
Vị trí bắt đầu: 2,2
Xuất phát mặt: Bắc
Di chuyển Đã đặt: Trái
Kết quả cuối cùng: Vị trí: 1,3; Mặt: Tây
Vấn đề: thuật toán sử dụng tất cả 8 ô để tìm đường; nhưng chỉ nên tìm gạch ở phía trước (phụ thuộc vào mặt tàu)
Lớp nút:
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;
}
}
Tính toán tìm đường:
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;
}
Thực hiện:
@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;
}
}
}
}
}
}
Tôi sử dụng câu lệnh switch và phương thức currentPosition.add () để khi bạn đặt 3 nước đi cho lượt cụ thể đó; nó biết nó sẽ kết thúc ở đâu. Có lẽ không phải là phương pháp hay nhất.
Câu lệnh thêm một động thái vào vị trí cụ thể
getMoves().setMove(slot, MoveType.FORWARD);
Các viên gạch cần được kiểm tra mỗi lượt dựa trên mặt tàu:
Trả lời
Đây chỉ là một nỗ lực một phần, cung cấp thêm chi tiết cho nhận xét tôi đã thực hiện.
A * tìm kiếm trên biểu đồ các nút có chứa "trạng thái" của con tàu. Trong hầu hết các hướng dẫn (kể cả của tôi, xin lỗi) trạng thái chỉ là vị trí. Nhưng trong trường hợp của bạn, tôi nghĩ trạng thái vừa là vị trí vừa là hướng đối mặt. Bạn cần biết hướng quay mặt để tính toán ba vị trí phía trước nó. Và sau khi di chuyển, bạn sẽ có cả một vị trí và một hướng đối mặt mới.
Nodehiện đang có một chức vụ; thay đổi nó để có cả hai positionvà facing. Đây là phiên bản sơ bộ của for(int i = 0; i < 9; i++)vòng lặp để tìm hàng xóm. Thay vì đi qua 9 láng giềng, mỗi 4 hướng sẽ có đúng 3 láng giềng. (Đúng, có 12, không phải 8! Vì nó phụ thuộc vào hướng bạn đang đối mặt trước đó)
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
*/