It is currently Tue Dec 10, 2013 3:34 pm

 All times are UTC

 Page 1 of 1 [ 14 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: 2D square based cell path-finding algorithim help.Posted: Sun Aug 21, 2011 9:38 am
 Novice

Joined: Sun Aug 21, 2011 9:10 am
Posts: 6
This is my second site I've been to for this issue, I'm just starting out with path finding and I've spent days reading about it and trying to get it to work in my program.

this is the original place I tried to get help, they normally get my stuff to work but I have gotten no replies on it and I feel it has wasted my time.
http://www.dreamincode.net/forums/topic/243881-pathfinding-algorithim-for-2d-cell-based-map-infinite-loop/

I have tried to implement an AStar tutorial but it failed (null paths) and my Map class has become very dirty with all the things I have tried. (keeping them there in case I find a way to get them to work)

the Map is given data from the world as the Entity (person) moves around, this removes the 'fog' of the map and the person remembers where they have been using this map.

How it is to work:
map made, the world tells it the size of the world.
world calls map.set(point in the world, the cell at that point) when the person is born or moves (should add up to 2 spaces away)
The being that this map belongs to gets hungry/thirsty/pregnant, the entity calls map.makePathTo{Food(/Water(/code(4,}path for me to follow, my location on the world)

the makePathTo{Food/Water} just call makePathToCode. 2 is water, 3 is food

the path is a ArrayList<Integer> that the entity will follow, using it's own move(int direction) method
the Entity can only move in these directions:
int World.North
int World.East
int World.South
int World.West

Someone please help me on this, it has been a big issue for me and I have lost all my nights of sleep to it in the past three weeks, this bug is holding back me releasing the game (right now, the people will die from hunger/thirst while trying to find a way back to a food/water cell... doesn't sound like a fun game does it? just sitting there and watching them die with nothing you can do about it...).

Also, I'll be uploading a beta test to one of my websites here in a day or two if I can get around to it, I'll post a link if I do.

and again, sorry for the mess in my Map class. I'll clean it after it works good.

Map.java:
Code:
/*
The Map Class, One is given to each Entity.
The Map is used to "remember" where that Entity has been

PathFinding will use this.
*/

import java.util.ArrayList;
import java.awt.Point;
import java.util.HashSet;
import java.util.Set;
import java.util.List;

public class Map
{
private PathPoint[][] blocks;
private int xSize;
private int ySize;
private ArrayList<ArrayList<Point>> uniquePoints;
private int stockD;
Map(int xSizes, int ySizes)
{
//set size then construct!
xSize = xSizes;
ySize = ySizes;
stockD = (xSize*ySize*2);
construct();
}
public int getRows()
{
return ySize;
}
public int getCols()
{
return xSize;
}
public PathPoint getTileAt(final Point loc)
{
return blocks[loc.x][loc.y];
}
public Set<PathPoint> getTilesAround(final Point location)
{
final Set<PathPoint> nearTiles;
//final int       middleRow;
//final int       middleCol;

nearTiles = new HashSet<PathPoint>();
ArrayList<PathPoint> sides = getOpenSides(blocks[location.x][location.x]);
for(int k = 0; k < sides.size(); k++)
/*
middleRow = location.getRow();
middleCol = location.getCol();

for(int row = middleRow - 1; row <= middleRow + 1; row++)
{
for(int col = middleCol - 1; col <= middleCol + 1; col++)
{
final PathPoint tile;

if(row < 0 || col < 0)
{
continue;
}

if(row >= ySize-1 || col >= xSize-1)
{
continue;
}

if(row == middleRow && col == middleCol)
{
continue;
}

tile = blocks[row][col];
}
}
*/

return (nearTiles);
}
/*
private Path getPath(PathPoint start, PathPoint goal)
{
final PathFinder finder;
final Path       path;
final List<PathPoint> tiles;
finder = new AStar(new SimpleHeuristicCalculator(getRows() * getCols()));
path   = finder.findPath(this, start.getLocationz(), goal.getLocationz());

System.out.println("pathed: "+path);

if(path == null)
{
vzy.UI.PopUp.popup("Null Path Error: Now Exiting");
System.exit(0);
}

return path;
//path.Tiles() = "Current > Goal"
}//*/
private void construct()
{
//make the blocks then fill it with new cells
blocks = new PathPoint[xSize][ySize];
for(int x = 0; x < blocks.length; x++)
for(int y = 0; y < blocks[x].length; y++)
blocks[x][y] = new PathPoint(new Point(x,y), new Cell(), stockD);

//make the uniquePoints
uniquePoints = new ArrayList<ArrayList<Point>>();
for(int k = 0; k < 5; k++)
{
if(k < 2)
uniquePoints.add(null);//why would we want walls and floors in this?
else
}
}
public void died()
{
//is the entity in the act of dieing? (because we toke so long makeing the path, it's the only way they die right now!)
}
public void close()
{
//closing method, used to keep memory low, System.gc() is called in the caller of this method.

//clear blocks
for(int x = 0; x < blocks.length; x++)
{
for(int y = 0; y < blocks[x].length; y++)
{
blocks[x][y].close();
blocks[x][y] = null;
}
blocks[x] = null;
}

//clear uniques
for(int k = 0; k < uniquePoints.size(); k++)
if(uniquePoints.get(k)!=null)
{
uniquePoints.get(k).clear();
}
uniquePoints.clear();
uniquePoints = null;
}
private void updateUnique(Cell newC, Cell oldC, Point p)
{
//if the old one is a unique cell then dump it from the list
if(oldC.getCode() > 1)
{
//find the cell first >.>
ArrayList<Point> ps = uniquePoints.get(oldC.getCode());
boolean found = false;
for(int k = 0; !found && k < ps.size(); k++)
if(ps.get(k).equals(p))
{
//now dump it.
ps.remove(k);
found = true;
}
}
//if the new one is unique, add it
if(newC.getCode() > 1)
}
public void set(java.awt.Point p, Cell c)
{
//updating Cells ^^

//if the code is different, then update the uniques!
if(blocks[p.x][p.y].cell.getCode() != c.getCode())
updateUnique(c, blocks[p.x][p.y].cell, p);

//set the cell into it's new home
blocks[p.x][p.y].cell.set(c);//copies the new cell into it's self
blocks[p.x][p.y].cell.unTake();//makes sure there is no people on it, it's for a map (maps don't show people on them!)
}
public void makePathToFood(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{

//code for food is 3, go to it.
makePathToCode(3, path, start);
}
public void makePathToWater(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{

//code for water is 2, go to it.
makePathToCode(2, path, start);
}
private PathPoint findGoal(int code, Point start, ArrayList<PathPoint> avoiders) throws World.NoGoalException
{

//I recently came up with this, after a good 80% of the pathfinding-making time passed...

//get the points that are the goals we want
ArrayList<Point> goals = uniquePoints.get(code);
{
int k = 0;
while(k < goals.size())
{
boolean good = true;
for(int j = 0; j < avoiders.size(); j++)
if(goals.get(k).equals(avoiders.get(j)))
{
good = false;
goals.remove(k);
}
if(good)
k++;
}
}
if(goals.size() <= 0)
throw new World.NoGoalException();
int shortestGoal = 0;
double shortestGoalLength = 99999.9;//should be increased?

//go through all of them and find the shortest.
for(int k = 0; k < goals.size(); k++)
if(start.distance(goals.get(k))<shortestGoalLength)
{
shortestGoalLength = start.distance(goals.get(k));
shortestGoal = k;
}

//return shortest.
return blocks[goals.get(shortestGoal).x][goals.get(shortestGoal).y];
}
private ArrayList<PathPoint> getPath(PathPoint start, PathPoint end) throws World.CanNotFindGoalException
{
/*for(int k = 0; k < blocks.length; k++)
for(int j = 0; j < blocks[k].length; j++)
blocks[k][j].clear();//*/
PathPoint current = start;
ArrayList<PathPoint> next = new ArrayList<PathPoint>();
//ArrayList<PathPoint> opened = new ArrayList<PathPoint>();
while(!current.equals(end))
{
ArrayList<PathPoint> open = getOpenSides(current);
for(int k = 0; k < open.size(); k++)
if(current.path2Home.size()==1)
{
//is start
}
else
{
if(open.get(k).path2Home == null)
{
//found start
}
else
if(open.get(k).path2Home.size() == 0)
{
//no path to home;
}
else
{
//has path to home
if((current.path2Home.size()+1) < open.get(k).path2Home.size())
{
//current is better
open.get(k).path2Home.clear();
}
}
}
if(next.size() == 0)
throw new World.CanNotFindGoalException();
current = next.get(0);
next.remove(0);
}
return current.path2Home;
}
private void path2(Point beginning, int code, ArrayList<Integer> path) throws World.DirectionException, World.NoGoalException
{
path2(beginning, code, path, new ArrayList<PathPoint>());
}
private void path2(Point beginning, int code, ArrayList<Integer> path, ArrayList<PathPoint> avoidGoals) throws World.DirectionException, World.NoGoalException
{
//We are not on it, it was worth a try :(
return;

PathPoint start = blocks[beginning.x][beginning.y];

//Find the closest goal cell
PathPoint end = findGoal(code, beginning, avoidGoals);
return;

//Path routez = getPath(start,end);
//ArrayList<PathPoint> route = routez.Tiles();
ArrayList<PathPoint> route = null;
try
{
route = getPath(start,end);
}
catch(World.CanNotFindGoalException cnfge)
{
path2(beginning, code, path, avoidGoals);
}
if(route != null)
for(int k = 0; k < (route.size()-1); k++)
//path.Tiles() = "Current > Goal"
}
public void makePathToCode(int code, ArrayList<Integer> path, Point beginning) throws World.DirectionException, World.NoGoalException
{
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-0");
return;

//Clear All cells for next path-finding
for(int x = 0; x < blocks.length; x++)
for(int y =0; y<blocks[x].length; y++)
blocks[x][y].clear();

//Set a stocknumber, a default d
int stockNum = blocks[2][2].d;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-1");

//Check if we are on it
if(blocks[beginning.x][beginning.y].cell.getCode() == code)
{

//we are on it!
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-0");
return;

//lets move once in an open direction and move back
PathPoint b = getOpenSides(blocks[beginning.x][beginning.y]).get(0);
PathPoint ac = blocks[beginning.x][beginning.y];
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-1");
return;

//add the moves into the path list
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-Done");
}
else
{
//check to see if we are one block away, will crash.
boolean oneAway = false;
ArrayList<PathPoint> test = getOpenSides(blocks[beginning.x][beginning.y]);
for(int k = 0; k < test.size(); k++)
if(test.get(k).cell.getCode() == code)
{
oneAway = true;
}
if(oneAway == false)
path2(beginning, code, path);
}
}
System.gc();

//WTF happens from here?!?!?
//after days of shearching I made my own... that kills if to far form goal.

//Find path to Start From End
//The Way we use: grow out on all open sides, growing a number on each growth of the 'wave'
/*
Example:
0 = end point.
s = start Point

6
656
65456
s543456
654323456
65432123456
6543210123456
65432123456
654323456
6543456
65456
656
6
/
{
int startNum = start.d;
return;

//our end is 0 blocks away.
int x = 0;
end.d = x;

//we are no longer on the end block, add one (we are going one away)
x++;
return;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-2");

//get all of the open blocks next to the current (end right now)
ArrayList<PathPoint> current = getOpenSides(end);
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-3");
return;

//While we have not changed the starting cell's d
{
//PathFinding, explode out from end.
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-4");

//set all d's on the current to our distance from the end, if it's a stock number (will crash without check)
for(int k = 0; (k < current.size())&&(start.d==startNum)&& !isDead; k++)
{
if(current.get(k).d == stockNum)
current.get(k).d = x;
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-5");
return;
//while we still have cells from the 'wave' in current, remove them after adding their open cells to the current
while(current.get(0).d<=x)
{
ArrayList<PathPoint> asdf = getOpenSides(current.get(0));
return;
current.remove(0);
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-6");

//the wave just went one step out from the end, time to add a counter.
x++;
}
}
return;
{

//Follow the Lowest numbered D back to home

if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-7");

//start has a number, look for one less then it, then loop
int num = start.d;//fun fact, i am start.d steps away from the end point!

//current point (p)
PathPoint p = start;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-8: Num: "+num);
return;

//while current point is not the end
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-9: p.d: "+p.d+">0?");

//we get the open sides
ArrayList<PathPoint> pp = getOpenSides(p);
return;
boolean found = false;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-10: pp.size(): "+pp.size());

//we go through the current sides of our current spot till we get closer
for(int k = 0; (k < pp.size())&&(!found)&&!isDead; k++)
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-11: pp[k].d: "+pp.get(k).d);

//if one is closer to home then we are now
if(pp.get(k).d < num)
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-12");
found = true;
return;
//add the move direction to the path list

//then we are the lowest so far ^^
p = pp.get(k);
num = p.d;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-13");

//loop till we are at the end.

/* //this is here to see the map, at each step on the way home, useless here?
{
for(int y = 0; y < ySize; y++)
{
for(int x = 0; x < xSize; x++)
{
System.out.print("["+blocks[x][y].cell.getCode()+":"+blocks[x][y].d+"]");
}
System.out.println("");
}
System.out.println("Beginning: "+beginning);
//System.exit(83);
}
///
}
}
}
}
}
return;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-3");

//we got our path, now lets clean up
for(int x = 0; x < blocks.length; x++)
for(int y =0; y<blocks[x].length; y++)
blocks[x][y].clear();
if(Main.DEBUG)
System.out.println("Map.makePathToCode-Done");

//done.
/*
Cells are in a (x,y) order
Cells have a getCode() method
Codes in cells are:
0: basic wall
1: basic floor
2: basic water
3: basic food
zero or less means you can't travel on that cell.
first cell found with the code we want is used to make a path with.
path is a list of move commands
move commands (All are int):
World.NORTH
World.EAST
World.SOUTH
World.WEST
Example:
00000
011G0
01000
0S110
00000

Path for S to G = World.NORTH,World.NORTH,World.EAST,World.EAST
*/
}
private ArrayList<PathPoint> getPathPointsAround(PathPoint p, int r)
{
return null;

//get the points around us
ArrayList<Point> ps = World.getPointsAround(p, r);
return null;

//and convert them to pathpoint, excluding the "out of bounds" ones
ArrayList<PathPoint> pp = new ArrayList<PathPoint>();
for(int k = 0; k < ps.size(); k++)
try
{
}
catch(ArrayIndexOutOfBoundsException aioobe)
{
}
return pp;
}
private int direction(Point a, Point b) throws World.DirectionException
{

//what direction would I have to go from a to b? {north,south,east, or west}

if((a.x == b.x) && (a.y+1 == b.y))
return World.NORTH;
else
if((a.x+1 == b.x) && (a.y == b.y))
return World.EAST;
else
if((a.x == b.x) && (a.y-1 == b.y))
return World.SOUTH;
else
if((a.x-1 == b.x) && (a.y == b.y))
return World.WEST;
else
throw new World.DirectionException();
}
private ArrayList<PathPoint> getOpenSides(PathPoint pp)
{
ArrayList<PathPoint> newP = new ArrayList<PathPoint>();
return null;

//add the side of the current cell to the list.
return null;
int k = 0;
while(k < newP.size())
{
//remove the walls (they are not open!)
if(newP.get(k).cell.getCode()<=0)
{
newP.remove(k);
}
else
k++;
}
return newP;
}
static class PathPoint extends Point
{
public int d;
public Cell cell;
public final int stock;
public ArrayList<PathPoint> path2Home;
PathPoint(int base)
{
this(new Point(0,0), new Cell(), base);
}
PathPoint(Point p, Cell c, int base)
{
super(p);
cell = c;
stock = base;
path2Home = new ArrayList<PathPoint>();
}
public void clear()
{
d = stock;
if(path2Home != null)
path2Home.clear();
else
path2Home = new ArrayList<PathPoint>();
}
public void close()
{
path2Home.clear();
path2Home = null;
cell.close();
cell = null;
}
public boolean canWalk()
{
return cell.getCode() > 0;
}
public Point getLocationz()
{
return this;
}
public final int hashCode()
{
return super.hashCode();
}
public final boolean equals(final Object o)
{
final boolean retVal;

if(this == o)
{
return (true);
}

if(o instanceof PathPoint)
{
final PathPoint other;

other  = (PathPoint)o;
retVal = (x==other.x) && (y==other.y);
}
else
{
retVal = false;
}

return (retVal);
}

public String toString()
{
return super.toString() + " -> " + cell.getCode();
}
}
}

Top

 Posted: Sun Aug 21, 2011 1:13 pm
 Dexterous Droid

Joined: Wed Aug 18, 2004 7:40 pm
Posts: 3751
Location: South Africa
Have you tried stepping through your path-finding code in the debugger or littering it with some System.out.println's to check what's happening? Try and give a better explanation of what's happening in your code, because reading it is a bit painful and I don't see anything obviously wrong.

You might also find this guide useful, it was helpful to me when I was implementing A*. http://www.policyalmanac.org/games/aStarTutorial.htm

_________________
Whatever the mind can conceive and believe, it can achieve

Top

 Posted: Sun Aug 21, 2011 3:13 pm
 Bibliotherapist

Joined: Wed Nov 03, 2004 1:28 pm
Posts: 6883
Location: Wilts, Englandshire
That's the one I used too. I'm glad someone posted the link, I couldn't remember it.

A* should be OK from your description of what you are trying to achieve. Is the problem that your humans can't find a path to a food area they know about or that they don't know about a food location and subsequently starve?

_________________
20 GOTO 10

Top

 Posted: Sun Aug 21, 2011 6:04 pm
 Novice

Joined: Sun Aug 21, 2011 9:10 am
Posts: 6
they would starve while trying to find a path to follow. the pathfinding needs to be faster and the way it is happening now it goes out from the start in all direction till it hits the goal that we said.

my current pathfinding does this:
makePathToCode called
reset all pathfinding parts of the pathpoints for this next pathfinding
check if we are on the goal, works if we are
then we check if we are one block away with:
Code:
boolean oneAway = false;
ArrayList<PathPoint> test = getOpenSides(blocks[beginning.x][beginning.y]);//gets the cells that we can walk to, that are also open to walk on. (not walls)
for(int k = 0; k < test.size(); k++)
if(test.get(k).cell.getCode() == code)//if one of them is the thing we want
{
oneAway = true;
//move to it.
}
if(oneAway == false)//are we one block away?
path2(beginning, code, path);

path2 is now called if we are not one/one block away form the goal
there we setup a start cell
and we get a end (goal) cell from find goal
find goal goes through uniques using the goal code to pick which unique to use the it find the closest using java.awt.Point's distance
after we have a goal we continue on with path2
which will call getpath
if get path can't find a goal it gives an error
with that error we call path2 with the current goal point in our avoided goals list
if we do get a route then we add it to the path with:
Code:
for(int k = 0; k < (route.size()-1); k++)

getpath has:
using current we loop
- get all sides of current
- go through those sides and add to next if the don't have a path or our path to them is shorter back to start
- current is set to the first of next
- remove the first of next from next
return the last current's path we have, which is the end point.

the path2 method will kill them if they are to far. (10+ blocks away)

here is the methods that I used:
path2(point, int, arraylist<integer>):
Spoiler: show
Code:
private void path2(Point beginning, int code, ArrayList<Integer> path) throws World.DirectionException, World.NoGoalException
{
path2(beginning, code, path, new ArrayList<PathPoint>());
}

path2(point, int, arraylist<integer>, arraylist<pathpoint>):
Spoiler: show
Code:
private void path2(Point beginning, int code, ArrayList<Integer> path, ArrayList<PathPoint> avoidGoals) throws World.DirectionException, World.NoGoalException
{
//We are not on it, it was worth a try :(
return;

PathPoint start = blocks[beginning.x][beginning.y];

//Find the closest goal cell
PathPoint end = findGoal(code, beginning, avoidGoals);
return;

//Path routez = getPath(start,end);
//ArrayList<PathPoint> route = routez.Tiles();
ArrayList<PathPoint> route = null;
try
{
route = getPath(start,end);
}
catch(World.CanNotFindGoalException cnfge)
{
path2(beginning, code, path, avoidGoals);
}
if(route != null)
for(int k = 0; k < (route.size()-1); k++)
//path.Tiles() = "Current > Goal"
}

findgoal(int, point, arraylist<pathpoint>):
Spoiler: show
Code:
private PathPoint findGoal(int code, Point start, ArrayList<PathPoint> avoiders) throws World.NoGoalException
{

//I recently came up with this, after a good 80% of the pathfinding-making time passed...

//get the points that are the goals we want
ArrayList<Point> goals = uniquePoints.get(code);
{
int k = 0;
while(k < goals.size())
{
boolean good = true;
for(int j = 0; j < avoiders.size(); j++)
if(goals.get(k).equals(avoiders.get(j)))
{
good = false;
goals.remove(k);
}
if(good)
k++;
}
}
if(goals.size() <= 0)
throw new World.NoGoalException();
int shortestGoal = 0;
double shortestGoalLength = 99999.9;//should be increased?

//go through all of them and find the shortest.
for(int k = 0; k < goals.size(); k++)
if(start.distance(goals.get(k))<shortestGoalLength)
{
shortestGoalLength = start.distance(goals.get(k));
shortestGoal = k;
}

//return shortest.
return blocks[goals.get(shortestGoal).x][goals.get(shortestGoal).y];
}

the part that i think needs all the work:
getpath(point, point):
Spoiler: show
Code:
private ArrayList<PathPoint> getPath(PathPoint start, PathPoint end) throws World.CanNotFindGoalException
{
/*for(int k = 0; k < blocks.length; k++)
for(int j = 0; j < blocks[k].length; j++)
blocks[k][j].clear();//*/
PathPoint current = start;
ArrayList<PathPoint> next = new ArrayList<PathPoint>();
//ArrayList<PathPoint> opened = new ArrayList<PathPoint>();
while(!current.equals(end))
{
ArrayList<PathPoint> open = getOpenSides(current);
for(int k = 0; k < open.size(); k++)
if(current.path2Home.size()==1)
{
//is start
}
else
{
if(open.get(k).path2Home == null)
{
//found start
}
else
if(open.get(k).path2Home.size() == 0)
{
//no path to home;
}
else
{
//has path to home
if((current.path2Home.size()+1) < open.get(k).path2Home.size())
{
//current is better
open.get(k).path2Home.clear();
}
}
}
if(next.size() == 0)
throw new World.CanNotFindGoalException();
current = next.get(0);
next.remove(0);
}
return current.path2Home;
}

I have older files of other ways I've tried, also, read the dreamincode topic, it has more of this is what it's doing... also
https://rapidshare.com/files/35897214/AI_Play.zip

Top

 Posted: Sun Aug 21, 2011 9:59 pm
 Dexterous Droid

Joined: Wed Aug 18, 2004 7:40 pm
Posts: 3751
Location: South Africa
Quote:
they would starve while trying to find a path to follow. the pathfinding needs to be faster and the way it is happening now it goes out from the start in all direction till it hits the goal that we said.

Are you saying the pathfinding is so slow that no path is found and your characters die? I'm finding it difficult to grasp your explanations.

Also, you're using an AStar class, where does that come into it? It seems you haven't posted the code for
Code:
finder = new AStar(new SimpleHeuristicCalculator(getRows() * getCols()));
path = finder.findPath(this, start.getLocationz(), goal.getLocationz());

The efficiency of A* depends a lot upon the heuristic that you use.

You're giving me information overload though, just state the problem as simply as you can. Sifting through all the source you've copy-pasted is time consuming and something you should be doing with the aid of a debugger and/or System.out.println()'s all over the place to let you pin down your problem. For instance, have you checked the length of your "open" vector? Is it increasing and spiralling out of control? Maybe that would point to you repeatedly adding duplicate nodes, which could be due to a bad heuristic. Have you visualised the nodes that are getting searched? Add in something to print out the values for H and K in each node. For instance, this is what my pathfinding looked like when I was ironing out kinks - I draw the F values for all explored cells.

_________________
Whatever the mind can conceive and believe, it can achieve

Top

 Posted: Mon Aug 22, 2011 2:25 am
 Novice

Joined: Sun Aug 21, 2011 9:10 am
Posts: 6
I tried using AStar but I had to change some of it to get it to work and when I changed it then it was returning null paths.
So using the 4 (including AStar) algorithms I tried to make a new one. it goes something like pic A, but I want it to be more like pic B. I have no idea what I'm doing with path-finding, I've never done anything like this before so it's all new to me. pic B is almost perfectly how I want it to go (no diagonal movements allowed).
I'll work on getting some output in the next day or two, when I do, I'll post it up. It should show what it's doing every step of the way... normally I do that but since I've been moving stuff around, deleting, re-making, repeat it's been hard to keep.

also, I posted a link to the game at the end of my last post, you could see what the game looks like it you want.

pic A (from http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm):

pic B (from http://en.wikipedia.org/wiki/A*_search_algorithm):

pic C (from same as pic B):

Top

 Posted: Mon Aug 22, 2011 6:18 pm
 Dexterous Droid

Joined: Wed Aug 18, 2004 7:40 pm
Posts: 3751
Location: South Africa
Ok, if your pathfinding is running like pic A and you're using A* then that means that you've got a problem with the heuristic you're using. The heuristic should be an estimate of the distance from a node to the destination. For most purposes, a Manhattan distance works well - that is calculated by adding together the differences of the x and y co-ordinates between the node and the goal. So H = abs(x1-x2) + abs(y1-y2).

The way A* pathfinding works is a "best first search". It expands the best candidates to efficiently search through the space. So it will try to expand nodes that are closer to the destination rather than nodes that are going away from the destination. It accomplishes this by using the heuristic. Heuristic kind of means "rule of thumb". In this case, the heuristic is making an educated guess about how "good" a node is based on the distance of that node to the destination.

From what you've said, I think you need to review that article on A*, it's the best I've come across so far. I also think you should scrap your current pathfinding and start over. After too much butchering, code becomes spaghettified to the point where it's not worth fixing. I had a look at the AI_Play demo you posted. For your project, you'll need to adjust the way the heuristic works, because there are multiple possible destinations, so the heuristic needs to loop through all destinations and return the smallest distance (the minimum of the various distances). Note that this means you need to store the locations of all resources - you must know where they are all located a priori so that you can loop through that list to find the minimum.

I suggest you do the following:

1) Make a simple path-finding that works from a fixed point to wherever the user clicks - this will let you easily test the pathfinding.
2) Instead of a path from a fixed point, let a single entity in your game find a path from its current location to where the user clicks. This lets you test that the entities are walking the path properly
3) Make a simple map with only 1 of each type of resource and let the entity find it's way to each one as his needs grow.
4) Extend #3 so that the heuristic loops through a list of all resources, and make a test map with multiple resources on it. Test again with multiple entities and see if they can find their ways to the various resources.

_________________
Whatever the mind can conceive and believe, it can achieve

Top

 Posted: Mon Aug 22, 2011 11:24 pm
 Novice

Joined: Sun Aug 21, 2011 9:10 am
Posts: 6
I tried using the AStar demo I got, but to make it compatible I some how broke it, it started to return only null paths, so I tried again using my own code and I think it follows more with the dajkstra's algorithm...

right now I'm working on adding output for what it's doing...

I think I'll scrap the method for finding a path and look at AStar stuff again and see if I can get it working...

also my findgoal will get the closest goal to the start, using ArrayList<ArrayList<PathPoint>> where I would call it like:

Code:
ArrayList<PathPoint> goals = unique.get(code); //returns all the goals of the type we want.
int shortest;
double shortestD = big number.
for(int k = 0; k < goals.size(); k++)
if(goals.get(k).distance(start)<shortestD)
{
shortest = k;
shortestD = goals.get(k).distance(start);
}
return goals.get(shortest);

If you want me to try a tutorial post it up or ask afew questions, I'll be looking for "weighted AStar" stuff in google so...

but thanks for all of your help, I'm very thankful that I can talk to someone that knows what I'm doing... my programming teacher doesn't know anything about AIs so...I'm on my own...

Top

 Posted: Tue Aug 23, 2011 8:34 am
 Bibliotherapist

Joined: Wed Nov 03, 2004 1:28 pm
Posts: 6883
Location: Wilts, Englandshire
I think you're going down the right road by starting your A* again. I understand that you'd like to improve it, but you need to get the basics working first.

There's an A* page on the Wiki (http://www.gpwiki.org/index.php/A*), it's locked at the moment, but it'll be open for editing again soon. Feel free to add any useful info you find.

_________________
20 GOTO 10

Top

 Posted: Tue Aug 23, 2011 9:45 am
 Dexterous Droid

Joined: Wed Aug 18, 2004 7:40 pm
Posts: 3751
Location: South Africa
vzybilly wrote:
If you want me to try a tutorial post it up or ask afew questions, I'll be looking for "weighted AStar" stuff in google so...

but thanks for all of your help, I'm very thankful that I can talk to someone that knows what I'm doing... my programming teacher doesn't know anything about AIs so...I'm on my own...

Well as I mentioned before, I think this is an excellent tutorial: A* Pathfinding for Beginners

Your findgoal method looks like what you need for the heuristic. I would suggest you pre-calculate the goals list, rather than recalculating it each time findgoal is called. (Unless your resources are moving around.)

Good luck!

_________________
Whatever the mind can conceive and believe, it can achieve

Top

 Posted: Wed Aug 24, 2011 2:24 am
 Novice

Joined: Sun Aug 21, 2011 9:10 am
Posts: 6
I added the debugging output, cleaned the class abit, and made a new algorithm... Testing it more but, here is what I have for everyone now.

Map class:
Spoiler: show
Code:
/*
The Map Class, One is given to each Entity.
The Map is used to "remember" where that Entity has been

PathFinding will use this.
*/

import java.util.ArrayList;
import java.awt.Point;
import java.util.HashSet;
import java.util.Set;
import java.util.List;

public class Map
{
private PathPoint[][] blocks;
private int xSize;
private int ySize;
private ArrayList<ArrayList<Point>> uniquePoints;
private int stockD;
Map(int xSizes, int ySizes)
{
//set size then construct!
xSize = xSizes;
ySize = ySizes;
stockD = (xSize*ySize*2);
construct();
}
private void construct()
{
//make the blocks then fill it with new cells
blocks = new PathPoint[xSize][ySize];
for(int x = 0; x < blocks.length; x++)
for(int y = 0; y < blocks[x].length; y++)
blocks[x][y] = new PathPoint(new Point(x,y), new Cell(), stockD);

//make the uniquePoints
uniquePoints = new ArrayList<ArrayList<Point>>();
for(int k = 0; k < 5; k++)
{
if(k < 2)
uniquePoints.add(null);//why would we want walls and floors in this?
else
}
}
public void died()
{
//is the entity in the act of dieing? (because we toke so long makeing the path, it's the only way they die right now!)
}
public void close()
{
//closing method, used to keep memory low, System.gc() is called in the caller of this method.

//clear blocks
for(int x = 0; x < blocks.length; x++)
{
for(int y = 0; y < blocks[x].length; y++)
{
blocks[x][y].close();
blocks[x][y] = null;
}
blocks[x] = null;
}

//clear uniques
for(int k = 0; k < uniquePoints.size(); k++)
if(uniquePoints.get(k)!=null)
{
uniquePoints.get(k).clear();
}
uniquePoints.clear();
uniquePoints = null;
}
private void updateUnique(Cell newC, Cell oldC, Point p)
{
//if the old one is a unique cell then dump it from the list
if(oldC.getCode() > 1)
{
//find the cell first >.>
ArrayList<Point> ps = uniquePoints.get(oldC.getCode());
boolean found = false;
for(int k = 0; !found && k < ps.size(); k++)
if(ps.get(k).equals(p))
{
//now dump it.
ps.remove(k);
found = true;
}
}
//if the new one is unique, add it
if(newC.getCode() > 1)
}
public void set(java.awt.Point p, Cell c)
{
//updating Cells ^^

//if the code is different, then update the uniques!
if(blocks[p.x][p.y].cell.getCode() != c.getCode())
updateUnique(c, blocks[p.x][p.y].cell, p);

//set the cell into it's new home
blocks[p.x][p.y].cell.set(c);//copies the new cell into it's self
blocks[p.x][p.y].cell.unTake();//makes sure there is no people on it, it's for a map (maps don't show people on them!)
}
public void makePathToFood(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{

//code for food is 3, go to it.
makePathToCode(3, path, start);
}
public void makePathToWater(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{

//code for water is 2, go to it.
makePathToCode(2, path, start);
}
private PathPoint findGoal(int code, Point start, ArrayList<PathPoint> avoiders) throws World.NoGoalException
{

//I recently came up with this, after a good 80% of the pathfinding-making time passed...

//get the points that are the goals we want
ArrayList<Point> goals = uniquePoints.get(code);
if(Main.DEBUG)
for(int k = 0; k < goals.size(); k++)
System.out.println("Goal point ("+(k+1)+"): "+goals.get(k));
{
int k = 0;
while(k < goals.size())
{
boolean good = true;
for(int j = 0; j < avoiders.size(); j++)
if(goals.get(k).equals(avoiders.get(j)))
{
good = false;
goals.remove(k);
}
if(good)
k++;
}
}
if(goals.size() <= 0)
throw new World.NoGoalException();
if(Main.DEBUG)
for(int k = 0; k < goals.size(); k++)
System.out.println("Good Goal point ("+(k+1)+"): "+goals.get(k));
int shortestGoal = 0;
double shortestGoalLength = 99999.9;//should be increased?

//go through all of them and find the shortest.
for(int k = 0; k < goals.size(); k++)
if(start.distance(goals.get(k))<shortestGoalLength)
{
if(Main.DEBUG)
System.out.println(goals.get(k)+" is shorter then "+shortestGoalLength);
shortestGoalLength = start.distance(goals.get(k));
shortestGoal = k;
}

//return shortest.
return blocks[goals.get(shortestGoal).x][goals.get(shortestGoal).y];
}
private int makeH(Point a, Point b)
{
return (int)a.distance(b);
}
private void pathAdd(PathPoint p, PathPoint parent, Point goal, ArrayList<PathPoint> list)
{
if(parent == null)
{
p.parent = null;
p.g = 0;
p.h = makeH(p,goal);
}
else
{
p.parent = parent;
p.g = parent.g + 1;
p.h = makeH(p,goal);
}
}
private int findLowestFIn(ArrayList<PathPoint> list)
{
int lowest = -1;
int lowestF = 99999;
for(int k = 0; k < list.size(); k++)
{
if(list.get(k).getF() < lowestF)
{
lowest = k;
lowestF = list.get(k).getF();
}
}
return lowest;
}
private boolean onList(ArrayList<PathPoint> list, PathPoint p)
{
boolean is = false;
for(int k = 0; (!is)&&(k < list.size()); k++)
if(p.equals(list.get(k)))
is = true;
return is;
}
private ArrayList<PathPoint> getPath(PathPoint start, PathPoint end) throws World.CanNotFindGoalException
{
ArrayList<PathPoint> open = new ArrayList<PathPoint>();
ArrayList<PathPoint> closed = new ArrayList<PathPoint>();
boolean found = false;

// 1) Add the starting square (or node) to the open list.
// 2) Repeat the following:
while((!found)&&(open.size()>0))
{
//   a) Look for the lowest F cost square on the open list. We refer to this as the current square.
int lowestF = findLowestFIn(open);
//   b) Switch it to the closed list.
PathPoint current = open.get(lowestF);
open.remove(lowestF);
ArrayList<PathPoint> sides = getOpenSides(current);
//   c) For each of the 8 squares adjacent to this current square &
for(int k = 0; k < sides.size(); k++)
{
//     * If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
if(!onList(closed, sides.get(k)))
{
//     * If it isnt on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
if(!onList(open, sides.get(k)))
{
}
else
{
//check to see if this path to that square is better, using G cost as the measure.
//A lower G cost means that this is a better path.
if(current.g+1 < sides.get(k).g)
{
//If so, change the parent of the square to the current square, and recalculate the G and F scores of the square.
sides.get(k).parent = current;
sides.get(k).g = current.g + 1;
}
}
}
}
//   d) Stop when you:
//     * Add the target square to the closed list, in which case the path has been found (see note below), or
if(onList(closed, end))
found = true;
}
//     * Fail to find the target square, and the open list is empty. In this case, there is no path.
if(!found)
throw new World.CanNotFindGoalException();
// 3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
ArrayList<PathPoint> invertedPath = new ArrayList<PathPoint>();
PathPoint current = end;
while(current.parent != null)
{
current = current.parent;
}
ArrayList<PathPoint> path = new ArrayList<PathPoint>();
for(int k = invertedPath.size()-1; k >= 0; k--)
return path;
}
private void path2(Point beginning, int code, ArrayList<Integer> path) throws World.DirectionException, World.NoGoalException
{
path2(beginning, code, path, new ArrayList<PathPoint>());
}
private void path2(Point beginning, int code, ArrayList<Integer> path, ArrayList<PathPoint> avoidGoals) throws World.DirectionException, World.NoGoalException
{
//We are not on it, it was worth a try :(
return;
if(Main.DEBUG)
System.out.println("Path2: ");

PathPoint start = blocks[beginning.x][beginning.y];

//Find the closest goal cell
PathPoint end = findGoal(code, beginning, avoidGoals);
return;

if(Main.DEBUG)
System.out.println("Start"+start);
if(Main.DEBUG)
System.out.println("end"+end);

//Path routez = getPath(start,end);
//ArrayList<PathPoint> route = routez.Tiles();
ArrayList<PathPoint> route = null;
try
{
route = getPath(start,end);
}
catch(World.CanNotFindGoalException cnfge)
{
path2(beginning, code, path, avoidGoals);
}
if(route != null)
for(int k = 0; k < (route.size()-1); k++)
//path.Tiles() = "Current > Goal"
if(Main.DEBUG)
System.out.println("End Path2");
}
public void makePathToCode(int code, ArrayList<Integer> path, Point beginning) throws World.DirectionException, World.NoGoalException
{
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-0");
return;

//Clear All cells for next path-finding
for(int x = 0; x < blocks.length; x++)
for(int y =0; y<blocks[x].length; y++)
blocks[x][y].clear();
printMap();

//Set a stocknumber, a default d
int stockNum = blocks[2][2].stock;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-1");

//Check if we are on it
if(blocks[beginning.x][beginning.y].cell.getCode() == code)
{

//we are on it!
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-0");
return;

//lets move once in an open direction and move back
PathPoint b = getOpenSides(blocks[beginning.x][beginning.y]).get(0);
PathPoint ac = blocks[beginning.x][beginning.y];
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-1");
return;

//add the moves into the path list
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-Done");
}
else
{
//check to see if we are one block away, will crash.
boolean oneAway = false;
ArrayList<PathPoint> test = getOpenSides(blocks[beginning.x][beginning.y]);
for(int k = 0; k < test.size(); k++)
if(test.get(k).cell.getCode() == code)
{
oneAway = true;
}
if(oneAway == false)
path2(beginning, code, path);
}
}
if(Main.DEBUG)
{
System.out.println("Path: ");
for(int k = 0; k < path.size(); k++)
{
int t = path.get(k);
//get dir from t;
String dir = "";
switch(t)
{
case World.North:
dir = "North";
break;
case World.East:
dir = "East";
break;
case World.South:
dir = "South";
break;
case World.West:
dir = "West";
break;
}
System.out.print(dir+",");
}
System.out.println("");
}
System.gc();
}
private ArrayList<PathPoint> getPathPointsAround(PathPoint p, int r)
{
if(Main.DEBUG)
System.out.println("getPathPointsAround: ");
return null;

//get the points around us
ArrayList<Point> ps = World.getPointsAround(p, r);
return null;

//and convert them to pathpoint, excluding the "out of bounds" ones
ArrayList<PathPoint> pp = new ArrayList<PathPoint>();
for(int k = 0; k < ps.size(); k++)
try
{
if(Main.DEBUG)
System.out.println(blocks[ps.get(k).x][ps.get(k).y]);
}
catch(ArrayIndexOutOfBoundsException aioobe)
{
}
if(Main.DEBUG)
System.out.println("");
return pp;
}
private int direction(Point a, Point b) throws World.DirectionException
{

//what direction would I have to go from a to b? {north,south,east, or west}

if((a.x == b.x) && (a.y+1 == b.y))
return World.NORTH;
else
if((a.x+1 == b.x) && (a.y == b.y))
return World.EAST;
else
if((a.x == b.x) && (a.y-1 == b.y))
return World.SOUTH;
else
if((a.x-1 == b.x) && (a.y == b.y))
return World.WEST;
else
throw new World.DirectionException();
}
private ArrayList<PathPoint> getOpenSides(PathPoint pp)
{
if(Main.DEBUG)
System.out.println("Open Sides: ");
ArrayList<PathPoint> newP = new ArrayList<PathPoint>();
return null;

//add the side of the current cell to the list.
return null;
int k = 0;
while(k < newP.size())
{
//remove the walls (they are not open!)
if(newP.get(k).cell.getCode()<=0)
{
newP.remove(k);
}
else
{
if(Main.DEBUG)
System.out.print(newP.get(k));
k++;
}
}
if(Main.DEBUG)
System.out.println("");
return newP;
}
private void printMap()
{
if(Main.DEBUG)
{
System.out.println("Map:");
for(int x = 0; x < xSize; x++)
{
for(int y = 0; y < ySize; y++)
System.out.print(blocks[x][y]);
System.out.println("");
}
System.out.println("");
}
}
static class PathPoint extends Point
{
public Cell cell;
public final int stock;
public PathPoint parent;
public int g;
public int h;
PathPoint(int base)
{
this(new Point(0,0), new Cell(), base);
}
PathPoint(Point p, Cell c, int base)
{
super(p);
cell = c;
stock = base;
clear();
}
public int getF()
{
return g+h;
}
public void clear()
{
g = stock;
h = stock;
parent = null;
}
public void close()
{
parent = null;
cell.close();
cell = null;
}
public boolean canWalk()
{
return cell.getCode() > 0;
}
public String toString()
{
String string = "{@:"+super.toString() + "; Code:" + cell.getCode()+": F:"+(g+h)+": G:"+g+"; Path2Home:[";
PathPoint t = this;
while(t.parent != null)
{
string = string + (((Point)t)+":"+t.cell.getCode()) + ">";
t = t.parent;
}
string = string + "]}";
return string;
}
}
}

Log, with Error:
Spoiler: show
Code:
\$ java Main
Main.main-0
Main.main-1
Main.main-2
Main.main-3
Main.main-Done
Map.makePathToCode-0
Map:
{@:Map\$PathPoint[x=0,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=5]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=6]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=7]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=8]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=0,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=1,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=1]; Code:2: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=2]; Code:4: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=3]; Code:3: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=9]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=1,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=2,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=1]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=2]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=3]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=4]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=9]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=3,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=1]; Code:2: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=2]; Code:4: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=3]; Code:3: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=9]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=4,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=4,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=5,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=5,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=6,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=4]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=6,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=7,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=7,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=8,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=8,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=9,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=9,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=10,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=5]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=8]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=10,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=11,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=5]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=6]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=7]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=8]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=11,y=16]; Code:0: F:884: G:442; Path2Home:[]}
{@:Map\$PathPoint[x=12,y=0]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=1]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=2]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=3]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=4]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=5]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=6]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=7]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=8]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=9]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=10]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=11]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=12]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=13]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=14]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=15]; Code:0: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=12,y=16]; Code:0: F:884: G:442; Path2Home:[]}

Map.makePathToCode-1
Open Sides:
{@:Map\$PathPoint[x=4,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=5]; Code:1: F:884: G:442; Path2Home:[]}
Path2:
Goal point (1): java.awt.Point[x=1,y=3]
Goal point (2): java.awt.Point[x=1,y=3]
Good Goal point (1): java.awt.Point[x=1,y=3]
Good Goal point (2): java.awt.Point[x=1,y=3]
java.awt.Point[x=1,y=3] is shorter then 99999.9
Start{@:Map\$PathPoint[x=3,y=6]; Code:1: F:884: G:442; Path2Home:[]}
end{@:Map\$PathPoint[x=1,y=3]; Code:3: F:884: G:442; Path2Home:[]}
Open Sides:
{@:Map\$PathPoint[x=4,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=7]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=5]; Code:1: F:884: G:442; Path2Home:[]}
Open Sides:
{@:Map\$PathPoint[x=4,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=5]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=3,y=6]; Code:1: F:3: G:0; Path2Home:[]}
Open Sides:
{@:Map\$PathPoint[x=3,y=6]; Code:1: F:3: G:0; Path2Home:[]}{@:Map\$PathPoint[x=1,y=6]; Code:1: F:884: G:442; Path2Home:[]}{@:Map\$PathPoint[x=2,y=7]; Code:1: F:884: G:442; Path2Home:[]}Exception in thread "Thread-4" java.lang.StackOverflowError
at java.util.Arrays.copyOf(Arrays.java:2895)
at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:117)
at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:614)
at java.lang.StringBuilder.append(StringBuilder.java:229)
at java.awt.Point.toString(Point.java:230)
at Map\$PathPoint.toString(Map.java:542)
at java.lang.String.valueOf(String.java:2838)
~for(int k = 0; k < 339; k++)
~{
~System.out.println("   at java.lang.StringBuilder.append(StringBuilder.java:132)");
~System.out.println("   at Map\$PathPoint.toString(Map.java:546)");
~System.out.println("   at java.lang.String.valueOf(String.java:2838)");
~}

un-edited log(you have been worned):
Spoiler: show
you sure?: [spoiler]
Code:
Your message contains 102193 characters. The maximum number of allowed characters is 60000.

Sorry :(
[/spoiler]

I'll try running it in jGRASP now and see what I can do about the error...

also, the Map in the log, if you want to look at it in excel here is a link https://rapidshare.com/files/1025642337/map.xls

new error:
Code:
at java.util.Arrays.copyOf(Arrays.java:2772)
at java.util.Arrays.copyOf(Arrays.java:2746)
at java.util.ArrayList.ensureCapacity(ArrayList.java:187)
at Map.path2(Map.java:324)

Top

 Posted: Wed Aug 24, 2011 11:07 am
 Dexterous Droid

Joined: Wed Aug 18, 2004 7:40 pm
Posts: 3751
Location: South Africa
If you're running out of memory, it's most likely because you're repeatedly adding nodes to the open list that are already on there. I'm going to post the simplest version of a working A* path-finding thing I made in Java. Read the code carefully to understand what's happening and then apply the same ideas to your project.

The most basic step of running path-finding is setting up your nodes to be able to trace the progress of the search.
Code:
class Node implements Comparable<Node>{
public boolean isOccupied=false; //is this node impassable
public int g=99999; //distance so far
public int h=0; //heuristic
public int x=0, y=0;
public Node prev; //storing the previous node in the path allows us to calculate the final path by starting at the goal and reading out the previous nodes until we hit the start
public boolean closed=false; //is this node in the closed list? it's simpler and faster to mark nodes as closed than maintain a closed list
public void reset(){ //this will reset the internal values, this must be called before a new path-finding attempt
g=99999; h=0; isPath=false; closed=false;
}
public Node(){}
public Node(int x, int y){this.x=x; this.y=y;}
//the following is important! if you make the nodes comparable then you can use a priority queue for your open list, which is much more efficient and also solves some other problems.
public boolean equals(Node b){ //returns whether these are in fact the same node
if (b.x==x && b.y==y) return true;
else return false;
}
public int compareTo(Node o) { //returns the difference between the total costs of the two nodes
return (g+h-o.g-o.h);
}
}

And then path-finding is done like this:

Code:
public Node[][] AStarMap = new Node[17][13];

private int getManhattan(int x1, int y1, int x2, int y2){
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

public void findPath() {

Point2D.Float destination = p.getPosition(); //destination
Point2D.Float op = getPosition(); //our position

//populate the AStarMap
for (int i=0; i<AStarMap.length; i++){
for (int j=AStarMap[i].length-1; j>=0; j--){
AStarMap[i][j].reset();
AStarMap[i][j].isOccupied = /*someway of telling if block is occupied*/;
AStarMap[i][j].closed = AStarMap[i][j].isOccupied; //close all nodes that are impassable
AStarMap[i][j].x = i;
AStarMap[i][j].y = j;
}
}

Node goal = AStarMap[(int)destination.x/64][(int)destination.y/64]; //64 is the tilesize
Node start= AStarMap[(int)op.x/64][(int)op.y/64];
goal.isPath = true; //these two nodes are obviously part of the correct final path
start.isPath = true;
start.g=0;
start.h=getManhattan(start.x, start.y, goal.x, goal.y);
goal.prev = start;
PriorityQueue<Node> openList = new PriorityQueue<Node>();
while (!openList.isEmpty()){
//get node with lowest f-val (top item), and put it in the closed list
Node top = openList.poll(); //this is the huge advantage of using a priority queue
if (top.closed) continue;
else top.closed = true; // as soon as a node has been processed, MARK it as closed
//if we pop the goal node then stop and trace back the path
if (top.equals(goal)){ //popping the goal node means we've successfully found a path
Node toAdd = goal; //start at the goal and trace backwards
do{
toAdd = toAdd.prev;  //move the pointer to the previous node in the path
}while (toAdd!=start);   //keep on tracing the path until we hit the beginning
break; //break from the loop once we've traced the path
}
//add in adjacent nodes to the open list, if they're not closed
// calculate their g and h values before adding them to the open list
// and also setting their prev pointer to the current node for tracing
if (top.x>0 && !AStarMap[top.x-1][top.y].closed && ((AStarMap[top.x][top.y].g+1) < AStarMap[top.x-1][top.y].g)){
AStarMap[top.x-1][top.y].g = AStarMap[top.x][top.y].g+1;
AStarMap[top.x-1][top.y].h = getManhattan(top.x-1, top.y, goal.x, goal.y);
AStarMap[top.x-1][top.y].prev = top;
}

if (top.y>0 && !AStarMap[top.x][top.y-1].closed && ((AStarMap[top.x][top.y].g+1) < AStarMap[top.x][top.y-1].g)){
AStarMap[top.x][top.y-1].g = AStarMap[top.x][top.y].g+1;
AStarMap[top.x][top.y-1].h = getManhattan(top.x, top.y-1, goal.x, goal.y);
AStarMap[top.x][top.y-1].prev = top;
}

if ((top.x<AStarMap.length-1) && !AStarMap[top.x+1][top.y].closed && ((AStarMap[top.x][top.y].g+1) < AStarMap[top.x+1][top.y].g)){
AStarMap[top.x+1][top.y].g = AStarMap[top.x][top.y].g+1;
AStarMap[top.x+1][top.y].h = getManhattan(top.x+1, top.y, goal.x, goal.y);
AStarMap[top.x+1][top.y].prev = top;
}

if ((top.y<AStarMap[0].length-1) && !AStarMap[top.x][top.y+1].closed && ((AStarMap[top.x][top.y].g+1) < AStarMap[top.x][top.y+1].g)){
AStarMap[top.x][top.y+1].g = AStarMap[top.x][top.y].g+1;
AStarMap[top.x][top.y+1].h = getManhattan(top.x, top.y+1, goal.x, goal.y);
AStarMap[top.x][top.y+1].prev = top;
}
}

foundPath = path;
}

_________________
Whatever the mind can conceive and believe, it can achieve

Top

 Posted: Wed Aug 24, 2011 2:31 pm
 Novice

Joined: Sun Aug 21, 2011 9:10 am
Posts: 6
I got it working, the error was in Map.path2:

working code:
Code:
try
{
while(true)
{
route.remove(0);
}
}
catch(ArrayIndexOutOfBoundsException aioobe)
{
}
catch(IndexOutOfBoundsException ioobe)
{
}

I think it was something like this before:
Code:
try
{
while(true)
}
catch(ArrayIndexOutOfBoundsException aioobe)
{
}

Thanks to all of you, I'll post a link with the first release in afew days, and again thanks.

Top

 Posted: Wed Aug 24, 2011 2:36 pm
 Dexterous Droid

Joined: Wed Aug 18, 2004 7:40 pm
Posts: 3751
Location: South Africa
Cool. Well done.

_________________
Whatever the mind can conceive and believe, it can achieve

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 14 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: Majestic-12 [Bot] and 3 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ Forums    Forum Rules and Posting Guidelines Wiki Discussion    Help    Content Issues Game Programming Discussion    C and C++ Game Programming    Java Game Programming    Language Agnostic Programming    .NET Game Programming    VB Game Programming    Mobile Game Programming    Web-Based Game Programming    Other Languages    OpenGL Development    Direct X Development Game Development Discussion    Game Design    Game Media Off-Topic Discussion    Announcements    Off-Topic    Community Projects    News