Best path to node

As I was testing jme3 I searched for artificial intelligence classes and found nothing. I don’t know if you want these features in jme but well, I liked the work I saw here and I will try to give you a hand sometimes :slight_smile:



I dusted off some notes from college and I’ve coded a PathFinding A* class that works on a Graph class. The most expensive operation is the tree ordering with O(logn) cost so the overall cost is O(m logn).

Personally I think hashCode, equals and heuristics can be reviewed with better ideas but it’s working.



I’m open to your comments, improvements… whatever :slight_smile:





PathFinding Class

[java]

package ai;



import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Comparator;

import java.util.Deque;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.TreeSet;



import com.jme3.scene.Spatial;





public class PathFinding {





private Heuristic heuristics = null;





public PathFinding(Heuristic heuristics){



this.heuristics = heuristics;

}



public void reconstructPath(HashMap<Graph, Graph> cameFrom, Graph node, Deque<Graph> path){

Graph g = cameFrom.get(node);



if (g != null){

path.addLast(node);

reconstructPath(cameFrom, g, path);

}else{



path.addLast(node);

}

}



public List<Graph> listFromDescendingDeque(Deque<Graph> deque){

Iterator<Graph> it = deque.descendingIterator();

ArrayList<Graph> list = new ArrayList<Graph>();

while(it.hasNext()){

list.add(it.next());

}



return list;

}





public List<Graph> findBestPath(Graph start,Graph end){



//algorithm vars

HashSet<Graph> visited = new HashSet<Graph>();

Comparator<Graph> wrapperComparator = new Comparator<Graph>() {



@Override

public int compare(Graph arg0, Graph arg1) {



return (int)(heuristics.f(arg0, arg1)100);

}

};

TreeSet<Graph> remaining = new TreeSet<Graph>(wrapperComparator);

HashMap<Graph, Graph> cameFrom = new HashMap<Graph, Graph>();

Deque<Graph> path = new ArrayDeque<Graph>();



HashMap<Graph, Float> gScore = new HashMap<Graph, Float>();

HashMap<Graph, Float> hScore = new HashMap<Graph, Float>();

HashMap<Graph, Float> fScore = new HashMap<Graph, Float>();



remaining.add(start);

gScore.put(start, new Float(0f));

hScore.put(start,heuristics.f(start, end));

fScore.put(start, hScore.get(start) + gScore.get(start));



//in-loop vars

Graph actualNode = null;

boolean tentativeBetter = false;

Float tentativeGScore = null;





//while there are remaining nodes

while(remaining.size() > 0){

actualNode = remaining.pollFirst();







if (actualNode.equals(end)){

reconstructPath(cameFrom, end,path);

return listFromDescendingDeque(path);

}

visited.add(actualNode);



//for each neighbour

for(Graph neighbour:actualNode.getNeighbours()){



if (!visited.contains(neighbour)){

tentativeGScore = gScore.get(actualNode) + heuristics.f(actualNode, neighbour);



if (!remaining.contains(neighbour)){

remaining.add(neighbour);

tentativeBetter = true;

}else if (tentativeGScore < gScore.get(neighbour)){

tentativeBetter = true;

}else{

tentativeBetter = false;

}



if (tentativeBetter){

if (cameFrom.get(neighbour) != null){

if (fScore.get(actualNode) < fScore.get(cameFrom.get(neighbour))){

cameFrom.put(neighbour, actualNode);

}

}else{

cameFrom.put(neighbour, actualNode);

}

gScore.put(neighbour,tentativeGScore );

hScore.put(neighbour,heuristics.f(neighbour, end) );

fScore.put(neighbour,gScore.get(neighbour)+hScore.get(neighbour) );

}

}



}





}



return null;

}





}

[/java]



Graph Class

[java]

package ai;



import java.util.List;



import com.jme3.math.FastMath;

import com.jme3.math.Vector3f;





public class Graph {



private String name;

private Vector3f pos;

private List<Graph> neighbours;







public Graph(String name, Vector3f pos, List<Graph> neighbours) {



super();

this.name = name;

this.pos = pos;

this.neighbours = neighbours;

}

public Graph( Vector3f pos, List<Graph> neighbours) {



super();

this.pos = pos;

this.neighbours = neighbours;

}





public Vector3f getPos() {



return pos;

}



public void setPos(Vector3f pos) {



this.pos = pos;

}



public List<Graph> getNeighbours() {



return neighbours;

}



public void setNeighbours(List<Graph> neighbours) {



this.neighbours = neighbours;

}



public String toString(){

String s = “”;

if (name != null && name.length() > 0){

s += “Name:”+name+" “;

}

s += “Pos:”+getPos()+“Neighbours: “;

for(Graph gn:getNeighbours()){

if (gn.getName() != null && gn.getName().length() > 0){

s +=gn.getName()+”,”;

}else{

s +=gn.getPos()+”,";

}

}



return s;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}



@Override

public int hashCode() {



final int prime = 31;

int result = 1;

Vector3f v1 = getPos();

Float x = FastMath.floor(v1.x);x = (x < 0)?x
-101:x100;

Float y = FastMath.floor(v1.y);y = (y < 0)?y
-101:y100;

Float z = FastMath.floor(v1.z);z = (z < 0)?z
-101:z100;

String val = String.format("%d%d%d", (int)x.floatValue(),(int)y.floatValue(),(int)z.floatValue());

result = new Integer((int) (Long.valueOf(val) % prime
prime));

return result;

}



@Override

public boolean equals(Object obj) {



if (this == obj) {

return true;

}

if (obj == null) {

return false;

}

if (!(obj instanceof Graph)) {

return false;

}



Graph other = (Graph) obj;





if (getPos() == null) {

if (other.getPos() != null) {

return false;

}

} else{

Vector3f v1 = getPos();

Vector3f v2 = ((Graph)obj).getPos();

Float x = FastMath.floor(v1.x);x = (x < 0)?x*-101:x100;

Float y = FastMath.floor(v1.y);y = (y < 0)?y
-101:y100;

Float z = FastMath.floor(v1.z);z = (z < 0)?z
-101:z100;

String val = String.format("%d%d%d", (int)x.floatValue(),(int)y.floatValue(),(int)z.floatValue());

Float x2 = FastMath.floor(v2.x);x2 = (x2 < 0)?x2
-101:x2100;

Float y2 = FastMath.floor(v2.y);y2 = (y2 < 0)?y2
-101:y2100;

Float z2 = FastMath.floor(v2.z);z2 = (z2 < 0)?z2
-101:z2*100;

String val2 = String.format("%d%d%d", (int)x2.floatValue(),(int)y2.floatValue(),(int)z2.floatValue());

if (!val.equals(val2)) {

return false;

}

}

return true;

}



}

[/java]



Heuristic interface

[java]

package ai;







public interface Heuristic {





public float f(Graph s1,Graph s2);



}

[/java]



Heuristic default Implementation

[java]

package ai;



import com.jme3.math.Vector3f;





public class HeuristicDefaultImpl implements Heuristic {



@Override

public float f(Graph s1, Graph s2) {



Vector3f v1 = s1.getPos();

Vector3f v2 = s2.getPos();



return v2.distance(v1);

}



}[/java]

I think most forms of AI quickly become too specific to be part of the core jME3 engine, but considering the share amount of different pathfinding implementations presented on this forum alone, I think it’d be a good idea to start something like a shared repository. But more on that later.



For your reference, here are some other pathfinding / A* topics well worth looking into:

http://hub.jmonkeyengine.org/groups/user-code-projects/forum/topic/pathfinding-system-with-test-environment/

http://hub.jmonkeyengine.org/groups/ai/forum/topic/basic-a-implementation-for-jme/

http://hub.jmonkeyengine.org/groups/free-announcements/forum/topic/astar-pathfinder-with-jme

http://hub.jmonkeyengine.org/groups/free-announcements/forum/topic/pathfinding-comparison-app-fringe-and-beam/



I think the only jME3-specific code among these is the top post by @normen. The last one is definitely only for jME2, but it’s certainly an interesting project. Definitely worth digging into I’d say.

My bad… I didn’t think to search at the forums…



I did this as part of an idea I came up.Creating behaviours that trigger actions along a path, so we need a bestPath algorithm to go there using the already implemented AnimationPath.



This could be used to trigger NPC’s at role games, or to make patrolling routes for action games… there are lots of examples and I think it is a pain in the ass program this from scrap for people making games :). At least they will have something to work with.

If you navigation Graph is static what about Dijkstra’s Algorithm? That way you could do all expensive operations befroe you need them.

Graph is static if you want, you can pass a Vector3f reference from a Geometry and it will be updated automatically. It only makes sense to pre-calculate paths if you have a static game map and you know all possible paths your objects will take.Also Dijkstra’s a special case of A* where you watch over ALL neighbours in the current node so it’s more efficient and faster using A* that only check neighbours that have better heuristics than the current node :).



I have read about modifications in A* so you don’t have to compute the entire tree. The next step from this I think it’s that algorithm.



Also it would be nice to lauch the path finding algorithm in a separate thread.



BTW. Sorry but I don’t have chances to practice english writing. If you don’t understand something tell me please :slight_smile: