Changing A* path finding into HPA* - Java

Question

I have implemented an A* algorithm for a simple 2d grid based game. However the algorithm slows the game down a lot and I recently learned about HPA* which is meant to try and solve this issue to an extent.

I can't really find any coding examples of it in place that are useful to me since I am coding in Java and I'm a bit confused about where to begin with adapting my initial code.

My code is below if anyone wants to have a look. I really just want to somehow adapt the code so that the path will be split into grids so that i'll be calcuating a path of maybe 5 aquares length as opposed to one that would be 20 aquares long and slow down the game.

  if (shortestPath == null) {

     openLocations.add(playerLocation);

        // While the goal has not been found yet
        while (openLocations.size() != 0 || pathFound != true) {
            // get the first node from the open list
            Node current = openLocations.get(0);
            shortestPath = reconstructPath(current);

            // check if current node is the goal node
            if (current.getX() == goalLocation.getX()
                    && current.getY() == goalLocation.getY()
                    //|| shortestPath.getWayPointPath().size() > GameInfo.getPathLength() + GameInfo.getPathCounter()
                    //|| shortestPath.getWayPointPath().size() >= 5
                    ) {
                shortestPath = reconstructPath(current);
                pathFound = true;

                for(Node node: shortestPath.getWayPointPath())
                 totalClosedLocations.add(node);

                // path has been found
                break;
            }

            // move current node to the already searched (closed) list
            openLocations.remove(current);
            closedLocations.add(current);

            // set the current nodes neighbours
            current = setNeighbours(current);

            // Now it's time to go through all of the current nodes
            // neighbours and see if they should be the next step
            for (Node neighbor : current.getNeighborList()) {
                boolean neighborIsBetter;

                // if we have already searched this Node, don't bother and
                // continue to the next one
                if (closedLocations.contains(neighbor)) {
                    continue;
                }

                boolean found = false;
                for (Node neighbournode : closedLocations) {
                    if (neighbournode.getX() == neighbor.getX()
                            && neighbournode.getY() == neighbor.getY()) {
                        found = true;
                        continue;
                    }
                }

                if (found)
                    continue;

                Node movable = new Node(neighbor.getX(), neighbor.getY(), 
                        neighbor.getCategory(), neighbor.getItype(), neighbor.getId());

                if (grid[movable.getX()][movable.getY()].size() > 0) {
                    // check to make sure that the square is not of category
                    // 4(immovable object) or category 3(enemy)
                    if ((grid[movable.getX()][movable.getY()].get(0).category == 4 && grid[movable
                            .getX()][movable.getY()].get(0).itype == 0)
                            && grid[movable.getX()][movable.getY()].get(0).obsID != goalLocation.getId()
                            ) {
                        // You cannot move on this square
                        neighbor.setMoveable(false);
                    } else {
                        // You can move on this square. Set parent location
                        // as the players current position.
                        movable.setParent(playerLocation);
                    }
                }

                // also just continue if the neighbor is an obstacle
                if (neighbor.getMoveable()) {

                    // calculate how long the path is if we choose this
                    // neighbor
                    // as the next step in the path
                    float neighborDistanceFromStart = (current
                            .getDistanceFromStart() + getDistanceBetween(
                            current, neighbor));

                    // add neighbor to the open list if it is not there
                    if (!openLocations.contains(neighbor)) {
                        openLocations.add(neighbor);
                        neighborIsBetter = true;
                        // if neighbor is closer to start it could also be
                        // better
                    } else if (neighborDistanceFromStart < current
                            .getDistanceFromStart()) {
                        neighborIsBetter = true;
                    } else {
                        neighborIsBetter = false;
                    }
                    // set neighbors parameters if it is better
                    if (neighborIsBetter) {
                        neighbor.setParent(current);
                        neighbor.setDistanceFromStart(neighborDistanceFromStart);
                        neighbor.setHeuristicDistanceFromGoal(heuristicStar
                                .getEstimatedDistanceToGoal(
                                        neighbor.getX(), neighbor.getY(),
                                        goalLocation.getX(),
                                        goalLocation.getY()));
                    }
                }

            }
        }

        System.out.println("====================");
    }

Answer 1

Let's say: you implement a crawl-like game and have a maze, hero and a lot of monsters...

after the hero made it's move it' the monsters turn and they may move, move toward the hero (a*star). i guess you calculate that path for each monster at every turn?!? right? ok, then something is very wrong:

let each monster keep his path. if the monster is very far away, you don't have to search a shortest path, because even if you hero had moved, the shortest path would be mostly the same (only the last few steps are different). then, maybe if the monster has moved 10 turns you can recalculate the path. this way you speed up the calculation time by the factor 10 - considering that longer paths take far time than shorter paths you can do some more optimizing

if the distance is far away, you can recalculate the path every 5 steps, maybe and if it's really close it's required to recalculate the path every turn, but don't worry... if it's a short path it doesnt take much time to calculate!

sorry - no code added...

ok, let's continue: here is a simple maze/map:

you start at upper/left and want to go to the end (not A, not B , you want to go to the end!)...

if you don't calculate the whole path, you will never find the way, because all other paths seem to be shorter, especially when you use heuristics in the search!!!

so - there is no way to not make full path search!

optimization: finding the neighbours is very often a bottle neck: when you create a field, set the neighbours for each field!

public class Test {

    public Field[][] field;
    public void doSomeTest(){

        field = new Field[25][25]
        MazeGenerator.createMaze(field); //this makes your map = this sets the fields passable or not
        for (int dy == 0; dy < 25; dy ++){
            for (int dx == 0; dx < 25; dx ++){
                createNeighbours(field[dx][dy]);                    
            }
        }

    }

    public void createNeigbours(Field f){

        //north
        if (isPassable(f.xpos, f.ypos-1) f.neighbours.add(field[xpos][ypos-1]); 

        //east
        if (isPassable(f.xpos+1, f.ypos) f.neighbours.add(field[xpos+1][ypos]);

        //south
        if (isPassable(f.xpos, f.ypos+1) f.neighbours.add(field[xpos][ypos+1]);

        //west
        if (isPassable(f.xpos-1, f.ypos) f.neighbours.add(field[xpos-1][ypos]);

    }

    public boolean isPassable(int xpos, int ypos){

        if (xpos <= 0) return false; //outside [maybe you even have a border, then xpos <= 1
        if (ypos <= 0) return false; //outside
        if (xpos >= Map.width) return false; //outside
        if (ypos >= Map.height) return false; //outside
        if (field[xpos][ypos].isBlocked) return false; //blocked

        return true;
    }
}

public class Field{

    public final int xpos;
    public final int ypos;
    public boolean isBlocked = false; // this makes your map

    public ArrayList<Field> neigbours = new ArrayList<Field>();

    public Field(int xpos, int ypos){
        this.xpos = xpos;
        this.ypos = ypos;
    }

    public List<Field> getNeighbours(){
        return neigbours ;
    }
}

the code above only explains how to create neighbours at the moment you create the field... but if you expand a node (a*) you can get the neighbours very fast and without calculation time (think how often you create objects in your code)