Java-Spiel: A * -Algorithmus (Suche nur nach Zellen vor dem Charakter)

Jan 08 2021

Spieltyp: Rasterplättchenkarte, die gedreht wird

Zulässige Richtungen: Links, Vorwärts, Rechts (um Richtungen umzukehren, müssen Sie entweder zwei Links oder zwei Rechte verwenden) - sowohl links als auch rechts bewegen sich diagonal, ändern jedoch das Gesicht des Schiffes je nach Originalgesicht)

Slots: Abhängig von der Schiffsgröße gibt es eine bestimmte Anzahl von Slots für dieses bestimmte Schiff, die der Benutzer betreten kann, damit sich das Schiff so viele Spots pro Runde bewegen kann (dh 3 Slots == 3 Züge pro Runde).

Beispiel:

Startposition: 2,2

Startfläche: Norden

Platzieren verschieben: Links

Endergebnis: Position: 1,3; Gesicht: West


Problem: Der Algorithmus verwendet alle 8 Kacheln zur Pfadfindung. sollte aber nur nach den Kacheln suchen, die vorne sind (abhängig von der Schiffsfläche)

Knotenklasse:

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

Pfadfindungsberechnung:

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

Implementierung:

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

Ich benutze die switch-Anweisung und die currentPosition.add () -Methode, damit, wenn Sie 3 Züge für diese bestimmte Runde platzieren; es weiß, wo es enden sollte. Wahrscheinlich nicht die beste Vorgehensweise.

Anweisung, die dem bestimmten Slot eine Verschiebung hinzufügt

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

Kacheln, die in jeder Runde anhand der Schiffsfläche überprüft werden sollten:

Antworten

amitp Jan 09 2021 at 02:47

Dies ist nur ein Teilversuch, der mehr Details für den Kommentar enthält, den ich gemacht habe.

A * durchsucht eine Grafik von Knoten, die den "Zustand" des Schiffes enthalten. In den meisten Tutorials (einschließlich meiner, sorry) ist der Status nur die Position. Aber in Ihrem Fall denke ich, dass der Staat sowohl die Position als auch die Blickrichtung ist. Sie müssen die Blickrichtung kennen, um die drei Positionen davor zu berechnen. Und dann haben Sie nach dem Umzug sowohl eine Position als auch eine neue Blickrichtung.

Nodehat derzeit eine Position; Ändern Sie es, um beide positionund zu haben facing. Hier ist eine grobe Version der for(int i = 0; i < 9; i++)Schleife, um die Nachbarn zu finden. Anstatt durch 9 Nachbarn zu gehen, hat jede der 4 Richtungen genau 3 Nachbarn. (Ja, es gibt 12, nicht 8! Es hängt davon ab, in welche Richtung Sie zuvor blickten.)

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