जावा गेम: ए * एल्गोरिथम (चरित्र के सामने केवल कोशिकाएं खोज रहा है)

Question

गेम का प्रकार: ग्रिड टाइल नक्शा जो आधारित है

अनुमति दी गई दिशा: बाएं, आगे, दाएं (दिशाओं को उलटने के लिए या तो आपको दो लेफ्ट या दो अधिकारों का उपयोग करना होगा) - बाएं और दाएं दोनों तिरछे चलते हैं लेकिन मूल चेहरे के आधार पर जहाज का चेहरा बदलते हैं)

स्लॉट: जहाज के आकार के आधार पर उपयोगकर्ता के लिए उस विशेष जहाज के लिए स्लॉट की एक निश्चित संख्या होती है, जिससे जहाज को उस स्थान पर जाने की अनुमति दी जा सके, जो प्रति मोड़ पर कई धब्बे (यानी। 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;
    }
  
}  

पाथफाइंग गणना:

    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;
                        }
                    }
                }
            }
        }
    }

मैं स्विच स्टेटमेंट और currentPosition.add () विधि का उपयोग करता हूं ताकि जब आप उस विशेष मोड़ के लिए 3 चालें रखें; यह जानता है कि इसे कहां समाप्त होना चाहिए। शायद सबसे अच्छा अभ्यास नहीं।

वह कथन जो विशेष स्लॉट में एक चाल जोड़ता है

getMoves().setMove(slot, MoveType.FORWARD);

टाइलें जिन्हें जहाज के चेहरे के आधार पर हर मोड़ पर जाँचना चाहिए:

Answer 1

यह केवल एक आंशिक प्रयास है, जो मैंने की गई टिप्पणी के लिए अधिक विवरण दिया है।

ए * नोड्स के एक ग्राफ पर खोज करता है जिसमें जहाज का "राज्य" होता है। अधिकांश ट्यूटोरियल में (मेरा, खेद सहित) राज्य केवल स्थिति है। लेकिन आपके मामले में मुझे लगता है कि स्थिति और सामना करने की दिशा दोनों है। आपको इसके सामने तीन पदों की गणना करने के लिए सामना करने की दिशा जानना आवश्यक है। और फिर इस कदम के बाद, आपके पास एक स्थिति और एक नई दिशा का सामना करना पड़ेगा।

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
    */