เกม Java: อัลกอริทึม A * (ค้นหาเฉพาะเซลล์ที่อยู่ด้านหน้าของตัวละคร)
ประเภทเกม: แผนที่ไทล์กริดที่เปิดตาม
ทิศทางที่อนุญาต: ซ้าย, ไปข้างหน้า, ขวา (ในการย้อนกลับทิศทางคุณต้องใช้สองทางซ้ายหรือสองสิทธิ์) - ทั้งซ้ายและขวาเคลื่อนที่ในแนวทแยง แต่เปลี่ยนใบหน้าของเรือขึ้นอยู่กับใบหน้าเดิม)
สล็อต: ขึ้นอยู่กับขนาดของเรือรบมีจำนวนช่องที่แน่นอนสำหรับเรือรบนั้น ๆ สำหรับผู้ใช้ที่จะเข้าไปเพื่อให้เรือรบเคลื่อนที่ได้หลายจุดต่อเทิร์น (เช่น 3 ช่อง == 3 เคลื่อนที่ต่อเทิร์น)
ตัวอย่าง:
ตำแหน่งเริ่มต้น: 2,2
ใบหน้าเริ่มต้น: ทิศเหนือ
ย้ายตำแหน่ง: ซ้าย
ผลลัพธ์สุดท้าย: ตำแหน่ง: 1,3; ใบหน้า: ทิศตะวันตก
ปัญหา: อัลกอริทึมใช้กระเบื้องทั้ง 8 ชิ้นในการค้นหาเส้นทาง แต่ควรมองหากระเบื้องที่อยู่ด้านหน้าเท่านั้น (ขึ้นอยู่กับหน้าเรือ)
คลาสโหนด:
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;
}
}
การคำนวณ 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;
}
การนำไปใช้:
@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 และวิธี currentPosition.add () เพื่อที่ว่าเมื่อคุณวาง 3 ท่าสำหรับเทิร์นนั้น มันรู้ว่ามันควรจะจบลงตรงไหน อาจไม่ใช่แนวทางปฏิบัติที่ดีที่สุด
คำสั่งที่เพิ่มการย้ายไปยังช่องเฉพาะ
getMoves().setMove(slot, MoveType.FORWARD);
กระเบื้องที่ควรตรวจสอบทุกรอบตามหน้าเรือ:
คำตอบ
นี่เป็นเพียงความพยายามบางส่วนโดยให้รายละเอียดเพิ่มเติมสำหรับความคิดเห็นที่ฉันแสดง
A * ค้นหากราฟของโหนดที่มี "สถานะ" ของเรือ ในแบบฝึกหัดส่วนใหญ่ (รวมถึงของฉันขออภัย) สถานะเป็นเพียงตำแหน่งเท่านั้น แต่ในกรณีของคุณฉันคิดว่าสถานะเป็นทั้งตำแหน่งและทิศทางที่หันหน้าไป คุณจำเป็นต้องทราบทิศทางการหันหน้าเพื่อคำนวณตำแหน่งทั้งสามที่อยู่ข้างหน้า หลังจากนั้นคุณจะมีทั้งตำแหน่งและทิศทางใหม่
Nodeปัจจุบันมีตำแหน่ง; เปลี่ยนให้มีทั้งpositionและfacing. นี่คือเวอร์ชันคร่าวๆของการfor(int i = 0; i < 9; i++)วนซ้ำเพื่อค้นหาเพื่อนบ้าน แทนที่จะเดินผ่านเพื่อนบ้าน 9 หลังแต่ละทิศทั้ง 4 จะมีเพื่อนบ้าน 3 คน (ใช่มี 12 ไม่ใช่ 8! เพราะขึ้นอยู่กับทิศทางที่คุณหันหน้าไปก่อนหน้านี้)
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
*/