java - A* algorithm not looking every where -
my problem right a* algorithm in java can find path if goes top down , left right. want code able check top bottom left right before deciding move not bottom , right. can guys me? code
public class pathfinder extends astar<pathfinder.node>{ private int[][] map; public static class node{ public int x; public int y; node(int x, int y){ this.x = x; this.y = y; } public string tostring(){ return "(" + x + ", " + y + ") "; } } public pathfinder(int[][] map){ this.map = map; } protected boolean isgoal(node node){ return (node.x == map[0].length - 1) && (node.y == map.length - 1); } protected double g(node from, node to){ if(from.x == to.x && from.y == to.y) return 0.0; if(map[to.y][to.x] == 1) return 1.0; return double.max_value; } protected double h(node from, node to){ /* use manhattan distance heuristic. */ return new double(math.abs(map[0].length - 1 - to.x) + math.abs(map.length - 1 - to.y)); } protected list<node> generatesuccessors(node node){ list<node> ret = new linkedlist<node>(); int x = node.x; int y = node.y; if(y < map.length - 1 && map[y+1][x] == 1) ret.add(new node(x, y+1)); if(x < map[0].length - 1 && map[y][x+1] == 1) ret.add(new node(x+1, y)); return ret; } public static void main(string [] args){ int [][] map = new int[][]{ {1, 0, 1, 0, 1, 0 ,1 ,0, 1, 0 ,1, 0}, {1, 1, 1, 1, 1, 1, 1 ,1 ,1 ,1, 1 ,1}, {1, 1, 1, 0, 1, 1 ,1, 1, 1 ,0, 1 ,0}, {0, 1, 1, 1, 1, 1 ,0, 1, 0, 1, 1 ,1}, {0, 0, 1, 1, 1, 0 ,1, 1 ,1, 1, 0 ,0}, {0, 1, 0, 1, 0, 0, 1, 1, 1, 1 ,1, 1}, {1, 1, 1, 1, 1, 1, 1 ,0 ,1 ,0, 1, 0}, {1, 0, 0, 0, 1, 0 ,1, 1 ,1 ,0 ,1 ,1}, {1, 1, 0, 1, 1, 0 ,1 ,0 ,1, 1, 1, 0}, {1, 1, 1, 1, 0, 1, 1 ,1 ,0 ,1, 1 ,1}, {1, 0, 1, 1, 1, 1, 0, 1, 1 ,0 ,1, 0}, {1, 0, 1, 0, 1, 1, 0 ,1, 0, 1, 1 ,1} }; pathfinder pf = new pathfinder(map); system.out.println("find path top left corner right bottom one."); for(int = 0; < map.length; i++){ for(int j = 0; j < map[0].length; j++) system.out.print(map[i][j] + " "); system.out.println(); } long begin = system.currenttimemillis(); list<node> nodes = pf.compute(new pathfinder.node(0,0)); long end = system.currenttimemillis(); system.out.println("time = " + (end - begin) + " ms" ); system.out.println("expanded = " + pf.getexpandedcounter()); system.out.println("cost = " + pf.getcost()); if(nodes == null) system.out.println("no path"); else{ system.out.print("path = "); for(node n : nodes) system.out.print(n); system.out.println(); } } } and other class
public abstract class astar<t>{ private class path implements comparable{ public t point; public double f; public double g; public path parent; /** * default c'tor. */ public path(){ parent = null; point = null; g = f = 0.0; } /** * c'tor copy object. * * @param p path object clone. */ public path(path p){ this(); parent = p; g = p.g; f = p.f; } /** * compare object using total cost f. * * @param o object compare to. * @see comparable#compareto() * @return <code>less 0</code> object smaller * <code>0</code>; * <code>0</code> object same. * <code>bigger 0</code> object bigger * o. */ public int compareto(object o){ path p = (path)o; return (int)(f - p.f); } /** * last point on path. * * @return last point visited path. */ public t getpoint(){ return point; } /** * set */ public void setpoint(t p){ point = p; } } /** * check if current node goal problem. * * @param node node check. * @return <code>true</code> if goal, <code>false</else> otherwise. */ protected abstract boolean isgoal(t node); /** * cost operation go <code>to</code> * <code>from</from>. * * @param node leaving. * @param node reaching. * @return cost of operation. */ protected abstract double g(t from, t to); /** * estimated cost reach goal node. * admissible heuristic never gives cost bigger real * one. * <code>from</from>. * * @param node leaving. * @param node reaching. * @return estimated cost reach object. */ protected abstract double h(t from, t to); /** * generate successors given node. * * @param node node want expand. * @return list of possible next steps. */ protected abstract list<t> generatesuccessors(t node); private priorityqueue<path> paths; private hashmap<t, double> mindists; private double lastcost; private int expandedcounter; /** * check how many times node expanded. * * @return counter of how many times node expanded. */ public int getexpandedcounter(){ return expandedcounter; } /** * default c'tor. */ public astar(){ paths = new priorityqueue<path>(); mindists = new hashmap<t, double>(); expandedcounter = 0; lastcost = 0.0; } /** * total cost function reach node <code>to</code> * <code>from</code>. * * total cost defined as: f(x) = g(x) + h(x). * @param node leaving. * @param node reaching. * @return total cost. */ protected double f(path p, t from, t to){ double g = g(from, to) + ((p.parent != null) ? p.parent.g : 0.0); double h = h(from, to); p.g = g; p.f = g + h; return p.f; } /** * expand path. * * @param path path expand. */ private void expand(path path){ t p = path.getpoint(); double min = mindists.get(path.getpoint()); /* * if better path passing point exists * don't expand it. */ if(min == null || min.doublevalue() > path.f.doublevalue()) mindists.put(path.getpoint(), path.f); else return; list<t> successors = generatesuccessors(p); for(t t : successors){ path newpath = new path(path); newpath.setpoint(t); f(newpath, path.getpoint(), t); paths.offer(newpath); } expandedcounter++; } /** * cost reach last node in path. * * @return cost found path. */ public double getcost(){ return lastcost; } /** * find shortest path goal starting * <code>start</code>. * * @param start initial node. * @return list of nodes initial point goal, * <code>null</code> if path doesn't exist. */ public list<t> compute(t start){ try{ path root = new path(); root.setpoint(start); /* needed if initial point has cost. */ f(root, start, start); expand(root); for(;;){ path p = paths.poll(); if(p == null){ lastcost = double.max_value; return null; } t last = p.getpoint(); lastcost = p.g; if(isgoal(last)){ linkedlist<t> retpath = new linkedlist<t>(); for(path = p; != null; = i.parent){ retpath.addfirst(i.getpoint()); } return retpath; } expand(p); } } catch(exception e){ e.printstacktrace(); } return null; } }
you need to:
- change
generatesuccessorsaddnode(x-1,y),node(x, y-1)list - change
expandmaintain set of visited nodes make sure don't visit node twice.
Comments
Post a Comment