Making entities navigate routes

Solved, see below

 

@timtower
no, actually, there's a lot of good material in there.
i'll have to read up on them, thanks a lot for the info!

 

alrighty, kind of messed around and tried to make a visual representation of A* doing its thang, and i'm pretty sure it works! found a new youtube channel to follow as well

just have to refine and implement it with bukkit, but it's looking like that was exactly what i was looking for! thanks again!

Code:

import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.Collections;
import java.util.logging.Logger;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class AStar extends JPanel {
    ArrayList<Node> nodes = new ArrayList<>();
    ArrayList<Node> openList = new ArrayList<>();
    ArrayList<Node> closedList = new ArrayList<>();
 
    private static final int WINDOW_WIDTH = 1400;
    private static final int WINDOW_HEIGHT = 900;
    private static final int ROWS = 100;
    private static final int COLUMNS = 100;
    int BOX_WIDTH = (int) WINDOW_WIDTH/COLUMNS-1;
    int BOX_HEIGHT = (int) WINDOW_HEIGHT/ROWS-1;
 
    int startRow;
    int startCol;
    int endRow;
    int endCol;
 
    Node startNode = null;
    Node endNode = null;
    Node current = null;
 
    boolean complete = false;

    public static void main(String[] args ) {
        JFrame frame = new JFrame("A * Search");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        AStar astar = new AStar();
        frame.add(astar);
        frame.setSize(WINDOW_WIDTH,WINDOW_HEIGHT);
        frame.setVisible(true);
        astar.runTest();
     
    }
 
    public void runTest() {
        double sru = Math.random() * ROWS;
        double scu = Math.random() * COLUMNS;
        double eru = Math.random() * ROWS;
        double ecu = Math.random() * COLUMNS;
        startRow = (int) sru;
        startCol = (int) scu;
        endRow = (int) eru;
        endCol = (int) ecu;
     


        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLUMNS; j++) {
                if (i == startRow && j == startCol || i == endRow && j == endCol) continue;
                nodes.add(new Node(i,j));
            }
        }
        startNode = new Node(startRow,startCol);
        endNode = new Node(endRow,endCol);
        nodes.add(startNode);
        nodes.add(endNode);
        startNode.setObstacle(false);
        endNode.setObstacle(false);
        startNode.setG(0);
        startNode.setF(getHeuristic(startNode,endNode));
     
     
        System.out.println("--->SETTING NEIGHBOURS<---");

        for (Node node : nodes) {
            node.setNeighbours();
        }
     
        openList.add(startNode);
     
        while (!openList.isEmpty()) {
         
            Collections.sort(openList);
         
            current = openList.get(0);
            System.out.println("FVALUE: " + current.getF());
            System.out.println("Open: " + openList.size());
            System.out.println("Closed: " + closedList.size());
            System.out.println("Total: " + nodes.size());
         
            if (current.equals(endNode)) {
                complete = true;
                System.out.println("SOLUTION FOUND.");
                break;
            }
         
            openList.remove(current);
            closedList.add(current);
         
            System.out.println("Neighbours: " + current.getNeighbours().size());
            for (Node neighbour : current.getNeighbours()) {
                if (closedList.contains(neighbour)) continue;
                if (!openList.contains(neighbour) && !neighbour.isObstacle) openList.add(neighbour);
             
                int tGS = 0;
                tGS = current.getG() + 1;
             
                if (tGS >= neighbour.getG()) continue;
             
                neighbour.setParentNode(current);
                neighbour.setG(tGS);
                neighbour.setH(getHeuristic(neighbour,endNode));
                neighbour.setF(neighbour.getH() + neighbour.getG());
            }
            repaint();
            try {
                Thread.sleep(25);
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        int i = 0;
        for (Node node : closedList) if (node.isObstacle) i++;
        repaint();
        System.out.println("Obstacles evaluated for no damn reason: " + i);
    }
 
    @Override
    public void paintComponent(Graphics graphics) {     
        super.paintComponent(graphics);
     
        this.setBackground(Color.GRAY);
     
        graphics.setColor(Color.DARK_GRAY);
        //graphics.clearRect(0,0,WINDOW_WIDTH,WINDOW_HEIGHT);
        for (Node node : nodes) {
            if (openList.contains(node)) {
                graphics.setColor(Color.GREEN);
                graphics.fillRect(node.getColumn() * BOX_WIDTH,node.getRow() * BOX_HEIGHT,BOX_WIDTH-1,BOX_HEIGHT-1);
            }
            else if (closedList.contains(node)) {
                graphics.setColor(Color.RED);
                graphics.fillRect(node.getColumn() * BOX_WIDTH,node.getRow() * BOX_HEIGHT,BOX_WIDTH-1,BOX_HEIGHT-1);
            }
            else if (node.isObstacle) {
                graphics.setColor(Color.BLACK);
                graphics.fillRect(node.getColumn() * BOX_WIDTH,node.getRow() * BOX_HEIGHT,BOX_WIDTH-1,BOX_HEIGHT-1);
                graphics.setColor(Color.GRAY);
            }
            else {
                graphics.setColor(Color.GRAY);
                graphics.drawRect(node.getColumn() * BOX_WIDTH,node.getRow() * BOX_HEIGHT,BOX_WIDTH-1,BOX_HEIGHT-1);
            }
        }
        graphics.setColor(Color.YELLOW);
        graphics.fillRect(startNode.getColumn() * BOX_WIDTH,startNode.getRow() * BOX_HEIGHT,BOX_WIDTH-1,BOX_HEIGHT-1);
        graphics.fillRect(endNode.getColumn() * BOX_WIDTH,endNode.getRow() * BOX_HEIGHT,BOX_WIDTH-1,BOX_HEIGHT-1);
        if (current != null) {
            Node node = current;
            graphics.setColor(Color.BLUE);
            while(node.getParentNode() != null) {
                graphics.fillRect(node.getColumn() * BOX_WIDTH,node.getRow() * BOX_HEIGHT,BOX_WIDTH-1,BOX_HEIGHT-1);
                node = node.getParentNode();
            }
        }
    }
    private class Node implements Comparable<Node> {
        private Node parentNode = null;
        private ArrayList<Node> neighbours = new ArrayList<>();
        private double fValue;
        private int gValue = Integer.MAX_VALUE;
        private double hValue;
        private int row;
        private int col;
        private boolean isObstacle = false;
     
        public Node(int row, int col) {
            this.row = row;
            this.col = col;
            if (Math.random() * 1000 > 800) isObstacle = true;
        }
        public void setObstacle(boolean isObstacle) {
            this.isObstacle = isObstacle;
        }
        public int getRow() {
            return row;
        }
        public int getColumn() {
            return col;
        }
        public double getF() {
            return fValue;
        }
        public void setF(double fValue) {
            this.fValue = fValue;
        }
        public int getG() {
            return gValue;
        }
        public void setG(int gValue) {
            this.gValue = gValue;
        }
        public double getH() {
            return hValue;
        }
        public void setH(double hValue) {
            this.hValue = hValue;
        }
        public Node getParentNode() {
            return parentNode;
        }
        public void setParentNode(Node parentNode) {
            this.parentNode = parentNode;
        }
        @Override
        public int compareTo(Node f) {
            int r;
            if (f.getF() < fValue) r = 1;
            if (f.getF() > fValue) r = -1;
            else r = 0;
            return r;
        }
     
        private boolean isNeighbour(Node node) {       
              return !node.isObstacle && node != this &&
                  (row+1 == node.getRow() || row-1 == node.getRow() || row == node.getRow()) &&
                  (col+1 == node.getColumn() || col-1 == node.getColumn() || col == node.getColumn());
        }
     
        public void setNeighbours() {
            for (Node node : nodes) {
                if (isNeighbour(node)) {
                    if (!neighbours.contains(node)) neighbours.add(node);
                }
            }
        }
     
        public ArrayList<Node> getNeighbours() {
            return neighbours;
        }
    }
    private double getHeuristic(Node from, Node to) {
        return Math.abs(from.getRow()-to.getRow()) + Math.abs(from.getColumn()-to.getColumn());
        //return Math.sqrt(((from.row-from.col)*2) + ((to.row-to.col)*2));
    }
}

will post the code up here when i get it rolled out!

 

So dang close, having trouble getting the entity to move more than 1 block, and I'm still not 100% on the route that the algorithm is building, the y values can get kind of messed up a bit... I really want this thing to work :/
Edit: got it working-ish.

Code:

public class RouteFinder {
    private static final long TRAVEL_TIMEOUT = 10000;
    private static final long RETRY_TIMEOUT = 2000;
    private static final int BLOCK_ACCURACY = 2;

    ArrayList<Node> nodes = new ArrayList<>();
    private ArrayList<Node> openSet = new ArrayList<>();
    private ArrayList<Node> closedSet = new ArrayList<>();

    private ArrayList<Location> route = new ArrayList<>();

    private EntityInsentient entity;

    private int fromX;
    private int fromY;
    private int fromZ;

    int toX;
    int toY;
    int toZ;

    World world;

    public RouteFinder(EntityInsentient entity, World world) {
        this.entity = entity;
        this.world = world;
    }

    private void setRoute() {
        Node node = new Node(fromX,fromY,fromZ,this);
        node.setG(0);
        openSet.add(node);

        while (!openSet.isEmpty()) {
/*            Debugger.debug("Open: " + openSet.size());
            Debugger.debug("Closed: " + closedSet.size());*/

            Collections.sort(openSet);
            Node current = openSet.get(0);
            current.setNeighbours();

            openSet.remove(current);
            closedSet.add(current);

            if (current.isComplete()) {
                buildRoute(current);
                return;
            }
            for (Node neighbour : current.neighbours) {
                if (closedSet.contains(neighbour)) continue;
                if (!openSet.contains(neighbour)) openSet.add(neighbour);
                int tempG = current.getG() + 1;
                if (tempG >= neighbour.getG()) continue;
                neighbour.setParentNode(current);
                neighbour.setG(tempG);
                neighbour.setF();
            }
        }
        Debugger.debug("No route found");
    }

    private void buildRoute(Node node) {
        Node current = node;
        while (current.getParentNode() != null) {
            route.add(new Location(world,current.getX(),current.getY(),current.getZ()));
            current = current.getParentNode();
        }
      
        Collections.reverse(route);

        for (Location location : route) {
            Debugger.debug("X: " + location.getX() + " Y: " + location.getY() + " Z: " + location.getZ());
        }
    }

    public void moveEntity(Location to) {
        this.fromX = (int) entity.locX;
        this.fromY = (int) entity.locY;
        this.fromZ = (int) entity.locZ;

        this.toX = to.getBlockX();
        this.toY = to.getBlockY();
        this.toZ = to.getBlockZ();

        new BukkitRunnable() {
            public void run() {

                setRoute();

                for (Location go : route) {
                    long timeout = System.currentTimeMillis() + TRAVEL_TIMEOUT;
                    long retryTravel = System.currentTimeMillis() + RETRY_TIMEOUT;

                    Debugger.debug("Going to " + go.getX() + "," + go.getY() + "," + go.getZ());

                    int entityX;
                    int entityY;
                    int entityZ;

                    int goToX = go.getBlockX();
                    int goToY = go.getBlockY();
                    int goToZ = go.getBlockZ();

                    boolean arrived = false;
                    entity.getNavigation().a(goToX,goToY,goToZ,1D);
                    while (!arrived) {

                        entityX = (int) entity.locX;
                        entityY = (int) entity.locY;
                        entityZ = (int) entity.locZ;


                        if (entityX >= goToX - BLOCK_ACCURACY && entityX <= goToX + BLOCK_ACCURACY
                                && entityY >= goToY - BLOCK_ACCURACY && entityY <= goToY + BLOCK_ACCURACY
                                && entityZ >= goToZ - BLOCK_ACCURACY && entityZ <= goToZ + BLOCK_ACCURACY) {
                            arrived = true;
                            Debugger.debug("Point reached!");
                        }

                        if (System.currentTimeMillis() >= timeout) {
                            Debugger.debug("Timeout reached!");
                            cancel();
                            return;
                        }

                        if (System.currentTimeMillis() >= retryTravel) {
                            entity.getNavigation().a(goToX,goToY,goToZ,1D);
                            retryTravel = System.currentTimeMillis() + RETRY_TIMEOUT;
                            Debugger.debug("Retrying route... ");
                        }

                        try {
                            Thread.sleep(10);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                }
                cancel();
                Debugger.debug("ROUTE COMPLETE!");
            }
        }.runTaskAsynchronously(WolfPack.getPlugin());
    }
}

Code:

 class Node implements Comparable<Node> {
     private Node parentNode = null;
     ArrayList<Node> neighbours = new ArrayList<>();

     private int f;
     private int g = Integer.MAX_VALUE;
     private int h;

     private int x;
     private int y;
     private int z;

    private RouteFinder finder;

     Node(int x, int y, int z, RouteFinder finder) {
        this.x = x;
        this.y = y;
        this.z = z;

        this.finder = finder;
        finder.nodes.add(this);
        setHeuristic();
    }

    private boolean nodeExistsAt(int x, int y, int z) {
        for (Node node : finder.nodes) if (node.x == x && node.y == y && node.z == z) return true;
        return false;
    }

    private boolean isObstacle(int x, int y, int z) {
        World world = finder.world;

        return (world.getBlockAt(x,y+1,z).getType() != Material.AIR ||
                world.getBlockAt(x,y+1,z).getType() == Material.LONG_GRASS) ||
                (world.getBlockAt(x,y,z).getType() == Material.AIR &&
                        world.getBlockAt(x,y-1,z).getType() == Material.AIR &&
                        world.getBlockAt(x,y-2,z).getType() == Material.AIR &&
                        world.getBlockAt(x,y-3,z).getType() == Material.AIR);
    }

    private void setHeuristic() {
        h = Math.abs(x - finder.toX) + Math.abs(y - finder.toY) + Math.abs(z - finder.toZ);
    }

    void setF() {
        f = g + h;
    }

    int getG() {
        return g;
    }

    void setG(int g) {
        this.g = g;
    }

    boolean isComplete() {
        return x == finder.toX && y == finder.toY && z == finder.toZ;
    }

    void setParentNode(Node node) {
        this.parentNode = node;
    }

     Node getParentNode() {
         return parentNode;
     }

     public int getX() {
         return x;
     }

     int getY() {
         return y;
     }

     public int getZ() {
         return z;
     }

     void setNeighbours() {
        for (int i = -1; i < 2; i++) {
            for (int j = -1; j < 2; j++) {
                for (int k = -1; k < 2; k++) {
                    int cX = x + i;
                    int cY = y + k;
                    int cZ = z + j;

                    if (isObstacle(cX,cY,cZ)) {
                        Debugger.debug("Obstacle at: " + cX + "," + cY + "," + cZ);
                    }

                    if (!nodeExistsAt(cX,cY,cZ) && !isObstacle(cX,cY,cZ)) {
                        Node node = new Node(cX,cY,cZ,finder);
                        neighbours.add(node);
                    }
                }
            }
        }
    }

     @Override
    public int compareTo(@Nonnull Node node) {
         return Integer.compare(f, node.f);
    }
}

Also, can add this in the while (!arrived) loop to ensure that the entity will make it...
Also, have to hash out the water situation, they don't like that very much

Code:

                        if (System.currentTimeMillis() >= teleportTravel) {
                            new BukkitRunnable() {
                                @Override
                                public void run() {
                                    entity = (EntityInsentient) entity.teleportTo(go,false);
                                }
                            }.runTask(WolfPack.getPlugin());
                            teleportTravel = System.currentTimeMillis() + TELEPORT_TIMEOUT;
                            Debugger.debug("Teleporting entity...");
                        }