[1.12.2] [SOLVED] A* JUnit Tests + Performance improvements

[Bektor]

Hi there,

 

I've implemented myself the A* algorithm (mainly just for the purpose of learning) as seen below and looking for a way to test the code with JUnit and improvements.

I'm also looking for reviews on best-practice and performance!

 

Just to note, the implementation works in 2D space within the 3D world of Minecraft.

 

public class AStar {
    
    /**
     * A {@link HashSet} of {@link Node} which holds all nodes which have been examined.
     * Some may refer to this as the <code>interior</code>.
     */
    private HashSet<Node> closedSet = new HashSet<>();
    
    /**
     * A {@link PriorityQueue} of {@link Node} which holds all candidates for the algorithm to explore.
     * Some may refer to this as the <code>openList</code>.
     */
    private PriorityQueue<Node> frontier = new PriorityQueue<>(
            (firstNode, secondNode) -> {
                if(firstNode.priority > secondNode.priority) return 1;
                if(firstNode.priority < secondNode.priority) return -1;
                return 0;
            });
    
    /**
     * A {@link HashSet} of {@link BlockPos} which holds all blocks the algorithm can move through.
     */
    private HashSet<BlockPos> passableBlocks = new HashSet<>();
    
    /**
     * Initialises this class with a list containing the 'level' the algorithm
     * uses to find the way.
     * 
     * @param passableBlocks All blocks the algorithm can use.
     */
    public AStar(HashSet<BlockPos> passableBlocks) {
        this.passableBlocks.addAll(passableBlocks);
    }
    
    /**
     * A* implementation
     * 
     * @param start
     * @param end
     * @return null if no path was found or the path as a list
     */
    public List<Node> getShortestPath(BlockPos start, BlockPos end) {
        if(start == null || end == null || !passableBlocks.contains(start) || !passableBlocks.contains(end))
            return null;
        
        this.frontier.add(new Node(start, null, 0, this.computeHeuristic(start, end)));
        
        while(!this.frontier.isEmpty()) {
            Node current = this.frontier.poll();
            if(current.location.equals(end)) {
                List<Node> path = new ArrayList<>();
                while(current.parent != null) {
                    path.add(current);
                    current = current.parent;
                }
                this.frontier.clear();
                this.closedSet.clear();
                return path;
            }
            this.closedSet.add(current);
            
            this.getAdjacentNodes(current, end);
        }
        
        return null;
    }
    
    /**
     * The heuristic algorithm to calculate the cost from a
     * <code>start</code> {@link Node} to the <code>end</code> {@link Node}.
     * <br>The Manhatten distance is used for this calculation to create
     * an overestimated heuristics for better search algorithms.
     * 
     * @param start The coordinates of the starting {@link Node}.
     * @param end The coordinates of the ending {@link Node}.
     * @return The calculated cost to get from the <code>start</code> point to the <code>end</code> point.
     */
    private int computeHeuristic(BlockPos start, BlockPos end) {
        return Math.abs(start.getX() - end.getX()) + Math.abs(start.getY() - end.getY());
    }
    
    private void getAdjacentNodes(Node node, BlockPos end) {
        // Create the set containing all neighbouring blocks
        BlockPos[] neighbourBlocks = new BlockPos[] {
                node.location.offset(EnumFacing.WEST),  // x+1, y+0
                node.location.offset(EnumFacing.EAST),  // x-1, y+0
                node.location.offset(EnumFacing.NORTH), // x+0, y+1
                node.location.offset(EnumFacing.SOUTH)  // x+0, y-1
        };
        
        for(BlockPos neighbourBlock : neighbourBlocks) {
            Node neighbour = new Node(neighbourBlock, node);
            if(this.closedSet.contains(neighbour) || !this.passableBlocks.contains(neighbourBlock)) continue;
            if(!this.frontier.contains(neighbour)) this.frontier.add(neighbour);
            float distance = node.distance + this.computeHeuristic(neighbour.location, end);
            
            if(distance >= neighbour.distance)
                continue;
            neighbour.setDistance(distance);
        }
    }
    
    /**
     * Represents the location ("node") of a graph within the A* algorithm.
     */
    public class Node {
        
        /**
         * The location of this node in the world.
         */
        private BlockPos location = null;
        
        /**
         * The previous node or the node we came from.
         */
        private Node parent = null;
        
        /**
         *  also w or d or l or length
         */
        private float cost = 0.f;
        /** 
         * also g or d or 'cost so far'
         */
        private float distance = 0.f;
        /**
         *  also f
         */
        private float priority = 0.f;
        
        /**
         * Default constructor.
         */
        public Node() {
            this.location = null;
            this.parent = null;
            this.cost = 0.f;
            this.distance = 0.f;
            this.priority = 0.f;
        }
        
        /**
         * Creates a {@link Node} at the given location.
         * 
         * @param pos The location of the {@link Node} in the world.
         */
        public Node(BlockPos pos) {
            this.location = pos;
        }
        
        /**
         * Creates a copy of the given {@link Node}.
         * 
         * @param node The {@link Node} to copy.
         */
        public Node(Node node) {
            this.location = node.location;
            this.parent = node.parent;
            this.cost = node.cost;
            this.distance = node.distance;
            this.priority = node.priority;
        }
        
        /**
         * Creates a new {@link Node}.
         * 
         * @param pos The location of the {@link Node} in the world.
         * @param parent The previous {@link Node}.
         */
        public Node(BlockPos pos, Node parent) {
            this(pos, parent, 0.f, 0.f);
        }
        
        /**
         * Creates a new {@link Node}.
         * 
         * @param pos The location of the {@link Node} in the world.
         * @param parent The previous {@link Node}.
         * @param cost The cost to "move" through this {@link Node}.
         * @param distance The cost of all {@link Node}s from the start point to this {@link Node}.
         */
        public Node(BlockPos pos, Node parent, float cost, float distance) {
            this.location = pos;
            this.parent = parent;
            this.setCost(cost);
            this.setDistance(distance);
            this.setPriority();
        }
        
        private void setCost(float cost) {
            this.cost = cost;
        }
        
        private void setDistance(float distance) {
            this.distance = distance;
        }
        
        private void setPriority() {
            this.priority = this.distance + this.cost;
        }
        
        // TODO: research on hashCode & implement this & equals
    }
}

 

Note: I know that the memory usage could be improved by just using one list, but I'm not sure about the impact in performance this change would mean nor how I could implement this with my PriorityQueue.

 

Thx in advance.

Bektor

Edited January 21, 2018 by Bektor

[jabelar]

Well here are some general best practices about performance optimization, which may not all apply to your case but worth thinking about:

1) Profile before spending a lot of time with optimizations. Don't spend time optimizing stuff that doesn't have significant impact in overall performance. I often see people make some clever, usually less "readable" and more bug-prone, optimization where it isn't needed. You want readability and simplicity (for avoiding bugs) in your code when you can, so only compromise that where performance requires it.

 

2) When nesting conditions or loops, when having conditions that && together always test the least likely (or the thing most likely to cause you to exit) thing first. For example, testing if world is remote and then testing if player is holding sword is backwards because it would be much better to exit quickly the 99.9% time the player is not holding the sword. Basically always look for ways to exit loops and methods as early as possible.

 

3) When testing conditions that || together always test the most likely (or the thing most likely to cause you to continue). In the previous example, if you wanted to continue if the world was remote or the player was holding the sword you should test for world is remote first.

 

4) In inner loops it is usually where it is worth coding super optimized. For example, in your code where you have the offsets for each of the enum facing, there may be a benefit for just directly adding 1 instead. Modern compilers are super optimized though so you should experiment. But I generally feel that you want to "flatten" the inner loop so call as few methods and conversions as possible.

Edited January 18, 2018 by jabelar

[Draco18s]

You want a performance improvement on A*?

Jump Point Search. The [2] reference is a great resource as well.

[Bektor]

  On 1/18/2018 at 4:55 PM, jabelar said:

Well here are some general best practices about performance optimization, which may not all apply to your case but worth thinking about:

1) Profile before spending a lot of time with optimizations. Don't spend time optimizing stuff that doesn't have significant impact in overall performance. I often see people make some clever, usually less "readable" and more bug-prone, optimization where it isn't needed. You want readability and simplicity (for avoiding bugs) in your code when you can, so only compromise that where performance requires it.

 

2) When nesting conditions or loops, when having conditions that && together always test the least likely (or the thing most likely to cause you to exit) thing first. For example, testing if world is remote and then testing if player is holding sword is backwards because it would be much better to exit quickly the 99.9% time the player is not holding the sword. Basically always look for ways to exit loops and methods as early as possible.

 

3) When testing conditions that || together always test the most likely (or the thing most likely to cause you to continue). In the previous example, if you wanted to continue if the world was remote or the player was holding the sword you should test for world is remote first.

 

4) In inner loops it is usually where it is worth coding super optimized. For example, in your code where you have the offsets for each of the enum facing, there may be a benefit for just directly adding 1 instead. Modern compilers are super optimized though so you should experiment. But I generally feel that you want to "flatten" the inner loop so call as few methods and conversions as possible.

Expand  

 

  On 1/18/2018 at 6:23 PM, Draco18s said:

You want a performance improvement on A*?

Jump Point Search. The [2] reference is a great resource as well.

Expand  

Thx for the answers. Those things should definitly help.

 

Thought I'm also looking into how it is possible to

• test an A* algorithm in general using JUnit.
• test this specific A* algorithm using JUnit to avoid the need of starting Minecraft.

[Draco18s]

  On 1/19/2018 at 3:03 PM, Bektor said:

 

Thought I'm also looking into how it is possible to

• test an A* algorithm in general using JUnit.
• test this specific A* algorithm using JUnit to avoid the need of starting Minecraft.

Expand  

You need to supply a fake world.

And that won't be easy.