Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: A Star Pathfinding algorithm optimization

  1. #1
    Junior Member
    Join Date
    May 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Post A Star Pathfinding algorithm optimization

    Hi anyone have any idea of how I can optimize my implementation of the A* pathfinding algorithm? Here is my code, it's made for Android but I'm guessing most of it is normal Java.
    Pathfinder class.
     
    import java.util.ArrayList;
     
     
    import com.levitas.Util;
     
    public class Pathfinder {
    	public static ArrayList<Node> Open = new ArrayList<Node>();
    	public static ArrayList<Node> Closed = new ArrayList<Node>();
    	public static ArrayList<Node> Final = new ArrayList<Node>();
    	static boolean hasFoundPath;
    	static Map nodez;
    	static final Vec2 Start = new Vec2(), End = new Vec2();
    	static Node checknext = null;
    	static int checknextI = 0;
    	static Node finalNode;
    	static boolean done = true;
     
     
    	public static Vec2[] findPath(Map map, Node start, Vec2 end)
    	{
    		done=false;
    		hasFoundPath=false;
    		checknextI = 0;
    		checknext = finalNode = null;
    		Start.inherits(start);
    		End.inherits(end);
    		nodez = map;
    		Open.clear();
    		Closed.clear();
    		Final.clear();
    		Open.add(start);
    		while(true)
    		{
    			//Loop for finding node with lowest F.
    			for(int i=0; i<Open.size(); i++)
    			{
    				if(hasFoundPath) break;
    				if(checknext==null) {checknext = Open.get(i); checknextI=i; continue;}
    				if(Open.get(i).getF()<checknext.getF()) {checknext = Open.get(i); checknextI=i;}
    			}
    			if(hasFoundPath) break;
    			Closed.add(Open.get(checknextI));
    			Open.remove(checknextI);
    			Closed.get(Closed.size()-1).spawn();
    			if(hasFoundPath) break;
    		}
    		return finalNode.getFinalPath();
    	}
    	public static int GetF(int x, int y, int G)
    	{
    		return G+((Util.pos(End.x-x)+Util.pos(End.y-y))*10);
    	}
     
    }

    Node class.
     
    class Node extends Vec2
    {
    	Node parent;
    	int G, H;
    	public Node(int x, int y, int G, Node parent)
    	{
    		this.parent = parent;
    		set(x, y);
    		this.G = G; //ADD 10/14 ON THIS!!!!!!!!!!!!!!!!!!
    		H = (Util.pos(Pathfinder.End.x-x)+Util.pos(Pathfinder.End.y-y))*10;
    	}
    	public Node()
    	{
    		this.G = 0;
    		this.parent = null;
    	}
    	public void inherit(Vec2 v)
    	{
    		this.x = v.x;
    		this.y = v.y;
    	}
    	public int getF() {
    		return G+H;
    	}
    	public Node(Vec2 v)
    	{
    		this(v.x, v.y, 0, null);
    	}
    	public void spawn()
    	{
    		if(Pathfinder.End.x==x && Pathfinder.End.y==y){Pathfinder.finalNode = this; Pathfinder.hasFoundPath=true; return;}
    		addz(x-1, y, G+10);
    		addz(x-1, y-1, G+14);
    		addz(x, y-1, G+10);
    		addz(x+1, y-1, G+14);
    		addz(x+1, y, G+10);
    		addz(x+1, y+1, G+14);
    		addz(x, y+1, G+10);
    		addz(x-1, y+1, G+14);
    	}
    	private void addz(int x, int y, int G)
    	{
    		if((Pathfinder.nodez.get(x, y))==null || Pathfinder.hasFoundPath) return;
     
    		for(int i=0; i<Pathfinder.Closed.size(); i++)
    			if(Pathfinder.Closed.get(i).x==x && Pathfinder.Closed.get(i).y==y)
    				return;
     
    		for(int i=0; i<Pathfinder.Open.size(); i++)
    			if(Pathfinder.Open.get(i).x==x && Pathfinder.Open.get(i).y==y && Pathfinder.Open.get(i).G < G)
    				return;
    			else if(Pathfinder.Open.get(i).x==x && Pathfinder.Open.get(i).y==y)
    				Pathfinder.Open.remove(i);
     
    		if(Pathfinder.nodez.get(x, y).canUse())
    			Pathfinder.Open.add(new Node(x, y, G, this));
    	}
    	public Vec2[] getFinalPath()
    	{
    		Node tmp = Pathfinder.finalNode;
    		Vec2[] returned;
    		while(true)
    		{
    			Pathfinder.Final.add(tmp);
    			tmp = tmp.parent;
    			if(tmp == null)
    				break;
    		}
    		returned = new Vec2[Pathfinder.Final.size()+1];
    		returned[0] = Pathfinder.Start;
    		for(int i=Pathfinder.Final.size()-1;i>-1;i--)
    			returned[Pathfinder.Final.size()-i] = Pathfinder.Final.get(i);
     
    		returned[returned.length-1] = Pathfinder.End;
    		Pathfinder.done = true;
    		return returned;
    	}
    }
    The Vec2 class consists of two simple coordinate points. The Map object contains an array of instances of a class that contains attributes for the two dimensional tilebased world. The only idea I have of an optimization is to use an individual two dimensional array for each attribute instead but I'm unsure of if that would help at all. Please post any thoughts on the subject. Also I appologise for any unclearities and incorrect english.


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default Re: A Star Pathfinding algorithm optimization

    If you want help, I'd suggest providing an SSCCE that demonstrates the problem. For example, are you experiencing performance issues? Are they all the time? Do you know which part of the code is bogging it down?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: A Star Pathfinding algorithm optimization

    What makes you believe it needs optimization? If you have something which suggests it is not optimal, I'd recommend profiling the code, printing out the times it takes for certain tasks to complete - quite often the result is not what you expected, so you can spend time optimizing the true bottleneck rather than spending time optimizing something that saves you a few milliseconds here or there.

  4. #4
    Junior Member
    Join Date
    May 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: A Star Pathfinding algorithm optimization

    Thanks for the fast replies, I appreciate it. I'm working on a Windows Port(Shouldn't take long). I believe it needs optimization on the grounds that it runs slowly on my Android device while every example implementation of the algorithm I've tested have run incredibly smooth taking only a few milliseconds to fully complete. On my device a path of 20 squares can take 2 seconds to calculate. I have tested rts games on the device and they all have Pathfinding algorithms that finishes in under half a second. I'll get back to you with a SSCCE.

  5. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: A Star Pathfinding algorithm optimization

    Try taking a look at A* Pathfinding for Beginners. Section 6 has some tips on how to get a faster implementation of the algorithm.

Similar Threads

  1. star design programs
    By prasansani in forum Java Theory & Questions
    Replies: 6
    Last Post: September 20th, 2011, 12:42 PM
  2. all i need is algorithm
    By coder.freak in forum Paid Java Projects
    Replies: 3
    Last Post: April 6th, 2011, 11:11 AM
  3. Swing app gui optimization
    By nik_meback in forum AWT / Java Swing
    Replies: 1
    Last Post: December 6th, 2010, 12:55 PM
  4. Replies: 2
    Last Post: November 25th, 2010, 01:59 PM
  5. algorithm
    By AmmrO in forum Algorithms & Recursion
    Replies: 13
    Last Post: September 24th, 2009, 09:18 PM

Tags for this Thread