Jump to content

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


Bektor

Recommended Posts

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 by Bektor

Developer of Primeval Forest.

Link to comment
Share on other sites

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 by jabelar

Check out my tutorials here: http://jabelarminecraft.blogspot.com/

Link to comment
Share on other sites

You want a performance improvement on A*?

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

Apparently I'm a complete and utter jerk and come to this forum just like to make fun of people, be confrontational, and make your personal life miserable.  If you think this is the case, JUST REPORT ME.  Otherwise you're just going to get reported when you reply to my posts and point it out, because odds are, I was trying to be nice.

 

Exception: If you do not understand Java, I WILL NOT HELP YOU and your thread will get locked.

 

DO NOT PM ME WITH PROBLEMS. No help will be given.

Link to comment
Share on other sites

22 hours ago, 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.

 

20 hours ago, Draco18s said:

You want a performance improvement on A*?

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

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.

Developer of Primeval Forest.

Link to comment
Share on other sites

2 hours ago, 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.

You need to supply a fake world.

And that won't be easy.

Apparently I'm a complete and utter jerk and come to this forum just like to make fun of people, be confrontational, and make your personal life miserable.  If you think this is the case, JUST REPORT ME.  Otherwise you're just going to get reported when you reply to my posts and point it out, because odds are, I was trying to be nice.

 

Exception: If you do not understand Java, I WILL NOT HELP YOU and your thread will get locked.

 

DO NOT PM ME WITH PROBLEMS. No help will be given.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Announcements



  • Recently Browsing

    • No registered users viewing this page.
  • Posts

    • They were already updated, and just to double check I even did a cleanup and fresh update from that same page. I'm quite sure drivers are not the problem here. 
    • i tried downloading the drivers but it says no AMD graphics hardware has been detected    
    • Update your AMD/ATI drivers - get the drivers from their website - do not update via system  
    • As the title says i keep on crashing on forge 1.20.1 even without any mods downloaded, i have the latest drivers (nvidia) and vanilla minecraft works perfectly fine for me logs: https://pastebin.com/5UR01yG9
    • Hello everyone, I'm making this post to seek help for my modded block, It's a special block called FrozenBlock supposed to take the place of an old block, then after a set amount of ticks, it's supposed to revert its Block State, Entity, data... to the old block like this :  The problem I have is that the system breaks when handling multi blocks (I tried some fix but none of them worked) :  The bug I have identified is that the function "setOldBlockFields" in the item's "setFrozenBlock" function gets called once for the 1st block of multiblock getting frozen (as it should), but gets called a second time BEFORE creating the first FrozenBlock with the data of the 1st block, hence giving the same data to the two FrozenBlock :   Old Block Fields set BlockState : Block{minecraft:black_bed}[facing=east,occupied=false,part=head] BlockEntity : net.minecraft.world.level.block.entity.BedBlockEntity@73681674 BlockEntityData : id:"minecraft:bed",x:3,y:-60,z:-6} Old Block Fields set BlockState : Block{minecraft:black_bed}[facing=east,occupied=false,part=foot] BlockEntity : net.minecraft.world.level.block.entity.BedBlockEntity@6d1aa3da BlockEntityData : {id:"minecraft:bed",x:2,y:-60,z:-6} Frozen Block Entity set BlockState : Block{minecraft:black_bed}[facing=east,occupied=false,part=foot] BlockPos{x=3, y=-60, z=-6} BlockEntity : net.minecraft.world.level.block.entity.BedBlockEntity@6d1aa3da BlockEntityData : {id:"minecraft:bed",x:2,y:-60,z:-6} Frozen Block Entity set BlockState : Block{minecraft:black_bed}[facing=east,occupied=false,part=foot] BlockPos{x=2, y=-60, z=-6} BlockEntity : net.minecraft.world.level.block.entity.BedBlockEntity@6d1aa3da BlockEntityData : {id:"minecraft:bed",x:2,y:-60,z:-6} here is the code inside my custom "freeze" item :    @Override     public @NotNull InteractionResult useOn(@NotNull UseOnContext pContext) {         if (!pContext.getLevel().isClientSide() && pContext.getHand() == InteractionHand.MAIN_HAND) {             BlockPos blockPos = pContext.getClickedPos();             BlockPos secondBlockPos = getMultiblockPos(blockPos, pContext.getLevel().getBlockState(blockPos));             if (secondBlockPos != null) {                 createFrozenBlock(pContext, secondBlockPos);             }             createFrozenBlock(pContext, blockPos);             return InteractionResult.SUCCESS;         }         return super.useOn(pContext);     }     public static void createFrozenBlock(UseOnContext pContext, BlockPos blockPos) {         BlockState oldState = pContext.getLevel().getBlockState(blockPos);         BlockEntity oldBlockEntity = oldState.hasBlockEntity() ? pContext.getLevel().getBlockEntity(blockPos) : null;         CompoundTag oldBlockEntityData = oldState.hasBlockEntity() ? oldBlockEntity.serializeNBT() : null;         if (oldBlockEntity != null) {             pContext.getLevel().removeBlockEntity(blockPos);         }         BlockState FrozenBlock = setFrozenBlock(oldState, oldBlockEntity, oldBlockEntityData);         pContext.getLevel().setBlockAndUpdate(blockPos, FrozenBlock);     }     public static BlockState setFrozenBlock(BlockState blockState, @Nullable BlockEntity blockEntity, @Nullable CompoundTag blockEntityData) {         BlockState FrozenBlock = BlockRegister.FROZEN_BLOCK.get().defaultBlockState();         ((FrozenBlock) FrozenBlock.getBlock()).setOldBlockFields(blockState, blockEntity, blockEntityData);         return FrozenBlock;     }  
  • Topics

×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use.