Basic A* implementation for jME

Troubleshooting General Help
1

Hi.

I just wanted to share my fairly basic pathfinder that i have implemented in jME.

It's not really pre-designed, but has rather been modified to suit my needs for the moment, and just recently got ported to 3d.

This may not be the most clever way to implement A*, very little research has gone into it, but they work. Maybe they can help someone.



Pathfinder class:

The way it works is that it runs on a separate thread. AI's call for it when they need a path, and are put in a queue. The pathfinder runs for as long as there are AI's waiting in the queue and sends the finished path back when done. When the queue is empty, it sleeps the thread.

It also handles cases when the AI has several goals to choose from and wants to find the one with the shortest path.

Cost is purely based on distance. This example needs a Brain class that calls for it.



Grid generation:

These are just a number of methods which i keep in my GameWorld class, which contains my terrain block and objects.

The navgrid is generated by creating A* nodes all over the terrain at equal distances, in a hexagonal pattern.

There are ray's cast to check that the node is not too close to an object, and moving it if too close, but it's unverified whether that works atm.

Then it goes through all the nodes and look for neighbours within a certain distance, check that the neighbour is reachable (through a collision check, and slope check). It sends multiple rays to make sure there is a "tunnel" the actor can walk through, this may have to be adjusted due to your models bounds.

I have some more stuff i want to cram in there, but don't have time or need to do that atm.



A* Node:

I Extended Sphere because i was planning to use the radius and a collision check, but currently i just check the distance to it. Makes for a good visual representation, though.

The node keeps a list of neighbours, with a maximum of 6 nodes



This implementation may not suit everyone's purpose, but could be modified as you see fit.

Tell me if you find it useful.



Classes are attached due to size.



Here are the navgrid generation methods. These you can put wherever you have your TerrainBlock. The methods are a bit clunky, feel free to improve them. You can get visual representations by removing the comments that attach them to the main node of the class. I inverted so that only broken connections are shown, rather than working ones, due to performance.

buildPathNodes() takes the distance you want between the nodes as input.

public void buildPathNodes(int sliceX, int sliceY)
    {
        int detailX = (int) (terrain.getSize() * terrainScale.x / sliceX);
        int detailY = (int) (terrain.getSize() * terrainScale.z / sliceY);
        int offset = 0;
        int minDistanceToObject = 10;
        //this.attachChild(pathNodeGrid);

        for (int y = 0; y < detailY; y++)
        {
            for (int x = 0; x < detailX; x++)
            {
                // create path nodes all over the terrain
                AStarNode node = new AStarNode(new Vector3f(
                        sliceX * x + offset, terrain.getHeight(
                            sliceX * x + offset, sliceY * y) + 0.5f,
                            sliceY * y),
                            1);
                node.setIndex((x+y)*y);
                // try to move the node if too close to an object
                Vector3f offsetVector = new Vector3f();
                if (checkCollisions(
                        buildingNodes, node.getLocalTranslation(), node.getLocalTranslation().add(minDistanceToObject, 0, 0)))
                            offsetVector.add(-minDistanceToObject, 0, 0);
                if (checkCollisions(
                        buildingNodes, node.getLocalTranslation(), node.getLocalTranslation().add(-minDistanceToObject, 0, 0)))
                            offsetVector.add(minDistanceToObject, 0, 0);
                if (checkCollisions(
                        buildingNodes, node.getLocalTranslation(), node.getLocalTranslation().add(0, 0, minDistanceToObject)))
                            offsetVector.add(0, 0, -minDistanceToObject);
                if (checkCollisions(
                        buildingNodes, node.getLocalTranslation(), node.getLocalTranslation().add(0, 0, -minDistanceToObject)))
                            offsetVector.add(0, 0, minDistanceToObject);
                node.setLocalTranslation(
                        node.getLocalTranslation().x + offsetVector.x, terrain.getHeight(
                            node.getLocalTranslation().x + offsetVector.x, node.getLocalTranslation().z + offsetVector.z) + 0.5f, node.getLocalTranslation().z + offsetVector.z);

                pathNodeGrid.attachChild(node);
            }
            // offset to get a hexagonal grid
            if (offset == 0) offset = sliceX / 2;
            else offset = 0;
        }

    }

    public void generateNavGrid()
    {
        Node connectionGrid = new Node("Failed Connections");

        this.attachChild(connectionGrid);

        connectionGrid.setCullHint(CullHint.Dynamic);
        int maxDistance = (int) (terrain.getSize() * terrainScale.x / 32)+6;
        int maxAngle = 25;
        // parse through all nodes to check for neighbouring nodes
        for (int i = 0; i < pathNodeGrid.getQuantity(); i++)
        {
            AStarNode currentNode = (AStarNode) pathNodeGrid.getChild(i); // grab the next node in the list
            for (int j = 0; j < pathNodeGrid.getQuantity()-1; j++)
            {
                // parse through all other nodes
                AStarNode nodeToCheck = (AStarNode) pathNodeGrid.getChild(j);
                if (nodeToCheck != currentNode) // don't want to check the current node;
                {
                    if (nodeToCheck.getLocalTranslation().distance(currentNode.getLocalTranslation()) < maxDistance) // if distance between nodes < 5
                    {
                        // normalize the vectors and find out the difference between them
                        Vector3f v = nodeToCheck.getLocalTranslation().subtract(currentNode.getLocalTranslation()).normalize();

                        float angle = FastMath.RAD_TO_DEG*(v.normalize().y); // normalize resulting vector and check the y-vector to find out the slope

                        if (angle > -maxAngle && angle < maxAngle) // check that it's not too steep
                        {
                            currentNode.lookAt(nodeToCheck.getLocalTranslation(), upAxis);
                            // do internal checks, makes sure that the connection list is not over crowded, and that the two nodes are not already connected
                            if (currentNode.checkIfConnectionAllowed(nodeToCheck)
                                    && nodeToCheck.checkIfConnectionAllowed(currentNode)
                                    && checkCollisions(buildingNodes, currentNode.getLocalTranslation(), nodeToCheck.getLocalTranslation()))
                            {
                                currentNode.addConnection(nodeToCheck);
                                nodeToCheck.addConnection(currentNode);
                                //connectionGrid.attachChild(new Line(currentNode.getName() + "<->" + nodeToCheck.getName(), new Vector3f []{currentNode.getLocalTranslation(), nodeToCheck.getLocalTranslation()}, null, debugColor, null));
                            }
                            // debug line to see failed connections
                            else if (!checkCollisions(buildingNodes, currentNode.getLocalTranslation(), nodeToCheck.getLocalTranslation()))
                            {
                                connectionGrid.attachChild(new Line(currentNode.getName() + "<->" + nodeToCheck.getName(), new Vector3f []{currentNode.getLocalTranslation(), nodeToCheck.getLocalTranslation()}, null, debugColor, null));
                            }

                            // TODO: check if this node is closer than an existing one and replace it
                        }
                    }
                }
            }
            // TODO: increase range if no node is found
            if (currentNode.getConnectedTo().size() == 0) pathNodeGrid.detachChild(currentNode);
        }
        connectionGrid.updateRenderState();
    }



Here are a few convenience methods that goes along with the nav grid generation:

public AStarNode getClosestNode(Vector3f loc)
    {
        AStarNode closestNode = null;
        float distance = 200;
        for (int i = 0; i < pathNodeGrid.getQuantity(); i++)
        {
            AStarNode currentNode = (AStarNode) pathNodeGrid.getChild(i);
            if (currentNode.getLocalTranslation().distance(loc) < distance)
            {
                closestNode = currentNode;
                distance = currentNode.getLocalTranslation().distance(loc);
            }
        }
        return closestNode;
    }

    public boolean checkCollisions(Node collisionNodes, Vector3f node1, Vector3f node2)
    {
        float distance = node1.distance(node2);
        Vector3f direction = node2.subtract(node1).normalize();
        Vector3f offsetVector = new Vector3f();
        CollisionDetection collision = new CollisionDetection(null, collisionNodes);
        Ray testRay;
        for (int x = -1; x < 2; x++)
        {
            for(int y = 0; y < 3; y++)
            {
                offsetVector.set(direction.x * x*4, y*2, direction.z * x*4);
                testRay = new Ray(node1.add(offsetVector), direction);
                if (collision.ProcessBoundCollisions(testRay, (int) distance)) return false;
            }
        }
        return true;
    }

2

wow seems like every where u turn some has one of these:



another one with very nice test

mesh navigation

3

@rickard: Thanks for sharing! That is something I can really use and will test it as soon as possible.





@mcbeth: "very constructive!"


4
ttrocha said:

@mcbeth: "very constructive!"


well........I do what can............might be good idea to add these to the wiki as well or a sticky on this board
5

@RIckard:

Could you post a complete test where you got it work. Or at least provided somegow this brain-class.

That would be really nice and much easier to get it work.



Thx in advance,



Tom

6

Attaching the whole Brain class would probably just add more confusion, but i'll try to supply the relevant methods when i get the time.

7

It is just because it is used in your example code (pathfinder.java)! Of course I have to take a deeper look into the whole but the compilation problem made me thought it is somehow needed…

8

Here are the methods used in the Brain class with regards to the pathfinder. The rest is very app specific. What my Brain does when it receives the path, is just to get the first segment. The connected Actor then rotates and walks in that direction (for a quick test, use .lookAt(target) ). So you will need some movement code, and a method that checks whether the AI is close enough to a node, and removes it from the list.



This method is used by the pathfinder to get the whereabouts of the AI. If it hasn't had a path before, it will call and check which nodes is closest to its position.

public AStarNode getTargetNode()
    {
        if (targetNode == null)
        {
            targetNode = gameWorld.getClosestNode(body.getLocalTranslation());
        }
        return targetNode;
    }



This one just requests a path from the pathfinder:

public void requestPathfinding(ArrayList nodes)
    {
        isWaitingForPath = true;
        pathfinder.addToQueue(this, nodes);
    }



this method is used by the pathfinder to deliver the path. Since it operates on a different thread, you need to be careful in which order you do things.

public void setPath(ArrayList<AStarNode> finalPath)
    {
        clearPath();
        if (finalPath != null)
        {
            System.out.println("Received path. Length: " + finalPath.size());
            pathList.addAll(0, finalPath);
            targetNode = pathList.get(0);
        }
        isWaitingForPath = false;
    }



Hope this helps.
9

Hello again.

I've received a couple of messages asking me about the Brain class that is utilizing the Pathfinder. I'm afraid it's too messy and game specific for me to show, or explain further than i've already done. I've however rewritten the Pathfinder class to not reference to the Brain class, and removed the queue system, in hopes it will cause less of a confusion.

Be warned though, it's untested, and still requires that you make some kind of system that parses the data given by the pathfinder.

It's retained it's own thread, and the isPathfinderDone() boolean can be used to tell when the Pathfinder has a path that is ready to be collected by the parser.

Since it doesn't have a queue system anymore, you probably need to instance it to each user, or maybe isPathfinderDone() can be used if several actor's need to use the same one.

Hope it helps.



Best regards,

Rickard



import com.jme.scene.Node;
import java.util.ArrayList;

public class Pathfinder1 implements Runnable
{
    private ArrayList <AStarNode> openList = new ArrayList <AStarNode>();
    private ArrayList <AStarNode> closedList = new ArrayList <AStarNode>();
    private ArrayList <AStarNode> tempPath = new ArrayList <AStarNode>();
    private ArrayList <AStarNode> finalPath = new ArrayList <AStarNode>();
    private ArrayList<AStarNode> pathList = new ArrayList<AStarNode>();
    private AStarNode start, goal;
    int totalCost = 0;
    public double H;
    Thread th ;
   
    Node pathNodes;
    boolean isDone;

    public Pathfinder1(Node nodes, AStarNode start, AStarNode goal)
    {
        isDone = false;
        openList.clear();
        closedList.clear();
        tempPath.clear();
        this.start = start;
        this.goal = goal;
        pathNodes = nodes;
        finalizeLayout();
        finalPath.clear();
        th = new Thread (this);
        th.start ();
    }
   
    public void run()
    {
        //long startTime = System.currentTimeMillis();
        tempPath.clear();

        if (goal.getCost() < 0 || goal == null || start == null) // if node is invalid or blocked
        {
            System.out.println("can't pathfind!");
            System.out.println("Start: " + start);
            System.out.println("Goal: " + goal);
            finalizeLayout();
        }

        H = (int)start.getLocalTranslation().distance(goal.getLocalTranslation()); // find out estimated distance between start and goal

        openList.add(start);
        start.setIsInOpenList(true);
        start.calculateG(goal);
        AStarNode node;

        for (int i = 0; i < openList.size(); i++)
        {
            node = openList.get(i); // get the next node in the open list

            for (int j = 0; j < openList.size(); j++) // see if any node has a lower F value
            {
                AStarNode node2 = openList.get(j);
                if (node2 != node && node2.getF() < node.getF()) node = node2;
            }

            // check neighbours
            ArrayList <AStarNode> connectsTo = node.getConnectedTo();
            for (int k = 0; k < connectsTo.size(); k++)
            {
                AStarNode neighbour = connectsTo.get(k);
                // if it's possible to reach a node from this node and it's cheaper than the previous path, update with new path
                if (neighbour.isInOpenList() || neighbour.isInClosedList())
                {
                    if (neighbour.getG() > node.getG() + neighbour.getCost()) neighbour.setParentNode(node);
                }
                else if (!goal.isInClosedList()) // if it's not the goal node that has been added
                {
                    openList.add(neighbour);
                    neighbour.setIsInOpenList(true);
                    neighbour.setIsInClosedList(false);
                    neighbour.setParentNode(node);
                    neighbour.calculateG(goal); // not necessary?
                    i = -1; // must restart search in openlist when adding new element
                }
            }
            if (node == null)System.out.println("adding null node to closedList");
            closedList.add(node);
            node.setIsInClosedList(true);
            openList.remove(node);
            node.setIsInOpenList(false);
        }

        tempPath.add(goal); // add goal node to final path
        node = goal;
        while (node != start) // while the node is not the same as the starting node, add parents of each node to the path
        {
            if (node.getParent() == null) // should not happen!
            {
                System.out.println("null parent @: " + node.getName());
                break;
            }
            node = node.getParentNode();
            tempPath.add(0, node);
            pathList.add(node); // adding node to list for debug purposes
        }
        // if the current path is shorter than finalPath or finalpath is 0, current path is the best one
        if (tempPath.size() < finalPath.size() || finalPath.size() == 0)
        {
            finalPath.clear();
            finalPath.addAll(tempPath);
        }
        isDone = true;
        //System.out.println("Total time used: " + (System.currentTimeMillis() - startTime));
        finalizeLayout();
    }

    public ArrayList <AStarNode> getPath(){
        isDone = false;
        return finalPath;
    }

    public boolean isPathfinderDone(){
        return isDone;
    }
   
    public void finalizeLayout()
    {
        for (int i = 0; i < pathNodes.getQuantity(); i++)
        {
            AStarNode a = (AStarNode) pathNodes.getChild(i);
            a.setParentNode(null);
            a.setIsInClosedList(false);
            a.setIsInOpenList(false);
        }
        tempPath.clear();
        openList.clear();
        closedList.clear();
        pathList.clear();
    }
}