# Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Page 1 of 1

## 8 Replies - 1270 Views - Last Post: 21 August 2011 - 11:07 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=243881&amp;s=6adbc2ea2763b100ad818336a045b670&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 vzybilly

Reputation: -1
• Posts: 160
• Joined: 24-September 08

# Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 17 August 2011 - 07:15 AM

EDIT: Read Second Post, Then Third. I've Been working with it and got a different question.

This is my first time working with pathfinding, it was working good but then it just kinda stopped working by giving me a VERY long output and the person using the pathfinding would die from hunger before they could find food.
The code will be for a small part of the whole but it should have everything for the pathfinding.
Feel free to help improve the code.
Map.class
```/*
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;

public class Map
{
private PathPoint[][] blocks;
int xSize;
int ySize;
Map(int xSizes, int ySizes)
{
xSize = xSizes;
ySize = ySizes;
construct();
}
private void construct()
{
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());
}
public void set(java.awt.Point p, Cell c)
{
blocks[p.x][p.y].cell.set(c);
blocks[p.x][p.y].cell.unTake();
}
public void makePathToFood(ArrayList<Integer> path, Point start) throws World.DirectionException
{
makePathToCode(3, path, start);
}
public void makePathToWater(ArrayList<Integer> path, Point start) throws World.DirectionException
{
makePathToCode(2, path, start);
}
public void makePathToCode(int code, ArrayList<Integer> path, Point start) throws World.DirectionException
{
/*
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
*/

//Clean all old path data
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-0");
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-1");

PathPoint startP = blocks[start.x][start.y];
startP.start = true;
//can't compile with out setting goal.
PathPoint goal = new PathPoint();
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-2");
ArrayList<PathPoint> current = new ArrayList<PathPoint>();
{
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-3");
while(current.size()>0)
{
ArrayList<PathPoint> newP = getGoodSides(current.get(0));
current.remove(0);
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-4: got "+newP.size()+" goodsides.");
for(int k = 0; k < newP.size(); k++)
{
PathPoint p = newP.get(k);
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-5: p.cell.getCode() = "+p.cell.getCode());
if(p.cell.getCode() == code)
{
goal = p;
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-5-done");
while(current.size()>0)
{
current.remove(0);
}
k = newP.size();
}
else
{
if(p.cell.getCode() > 0)
{
//it is not a wall type
if(Main.DEBUG)
}
}
}
}
}
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-6");
//ok, we found a code we are looking for.
path.clear();
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-7");
for(int k = 0; k < goal.home.size()-1; k++)
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-8");
if(Main.DEBUG)
System.out.println("Map.MakePathToCode-9");
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-10");
}
private int direction(Point a, Point B)/> throws World.DirectionException
{
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> getGoodSides(PathPoint pp)
{
ArrayList<PathPoint> newP = new ArrayList<PathPoint>();
for(int k = 0; k < newP.size(); k++)
{
if(!newP.get(k).start)
{
//not starting point
if(newP.get(k).home.size() == 0)
{
//no path home yet.
for(int j = 0; j < pp.home.size(); j++)
}
else
{
if((pp.home.size()+1) < newP.get(k).home.size())
{
//my path is better
for(int j = 0; j < pp.home.size(); j++)
}
}
}
}
return newP;
}
private class PathPoint extends Point
{
public ArrayList<PathPoint> home;
public Cell cell;
public boolean start;
PathPoint()
{
this(new Point(0,0), new Cell());
}
PathPoint(Point p, Cell c)
{
super(p);
cell = c;
home = new ArrayList<PathPoint>();
start = false;
}
public void clear()
{
home.clear();
start = false;
}
}
}
```

The Cells in the map are:
0:wall
1:floor
2:water
3:food
4:birthing place
```0 0 0 0 0 0 0 0 0
0 2 1 1 1 1 1 2 0
0 4 1 1 1 1 1 4 0
0 3 1 1 1 1 1 3 0
0 0 0 1 1 1 0 0 0
0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0
```

now for the log that I could get:
```Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 0
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePathToCode-4: got 4 goodsides.
Map.MakePathToCode-5: p.cell.getCode() = 1
Map.MakePat
----jGRASP: process aborted by user.

```

This post has been edited by vzybilly: 17 August 2011 - 11:14 PM

Is This A Good Question/Topic? 0

## Replies To: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

### #2 vzybilly

Reputation: -1
• Posts: 160
• Joined: 24-September 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 17 August 2011 - 08:31 PM

I worked with it abit more and I changed how it found the path, how ever it need alot of improvement on the algorithm, With the changes (and stopping the infinite loop in in time) I can see that it gets a Cell that is on the path and moves to it but it seems to not be able to find the next Cell...

this is the new stuff:

Map.class:
```/*
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;

public class Map
{
private PathPoint[][] blocks;
int xSize;
int ySize;
Map(int xSizes, int ySizes)
{
xSize = xSizes;
ySize = ySizes;
construct();
}
private void construct()
{
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());
}
public void set(java.awt.Point p, Cell c)
{
blocks[p.x][p.y].cell.set(c);
blocks[p.x][p.y].cell.unTake();
}
public void makePathToFood(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{
makePathToCode(3, path, start);
}
public void makePathToWater(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{
makePathToCode(2, path, start);
}
private PathPoint findGoal(int code, Point start) throws World.NoGoalException
{
boolean found = false;
for(int j = 1; !found; j++)
{
ArrayList<PathPoint> pp = getPathPointsAround(blocks[start.x][start.y], j);
for(int k = 0; k < pp.size(); k++)
if(pp.get(k).cell.getCode()==code)
{
found = true;
return pp.get(k);
}
}
throw new World.NoGoalException();
}
public void makePathToCode(int code, ArrayList<Integer> path, Point beginning) throws World.DirectionException, World.NoGoalException
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-0");
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-1");
if(blocks[beginning.x][beginning.y].cell.getCode() == code)
{
//we are on it!
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-0");
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");
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-Done");
}
else
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-0");
PathPoint end = findGoal(code, beginning);
PathPoint start = blocks[beginning.x][beginning.y];
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-1");
{
int startNum = start.d;
int x = 0;
end.d = x;
x++;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-2");
ArrayList<PathPoint> current = getOpenSides(end);
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-3");
while(start.d==startNum)
{
//PathFinding, explode out from end.
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-4");
for(int k = 0; (k < current.size())&&(start.d==startNum); k++)
{
current.get(k).d = x;
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-5");
while(current.get(0).d==x)
{
current.remove(0);
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-6");
x++;
}
}
{
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;
PathPoint p = start;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-8");
while(p.d > 0)
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-9");
ArrayList<PathPoint> pp = getOpenSides(p);
boolean found = false;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-10");
for(int k = 0; (k < pp.size())&&(!found); k++)
if(pp.get(k).d < num)
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-11");
found = true;
p = pp.get(k);
num = p.d;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-12");
}
}
}
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-3");
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");
/*
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)
{
ArrayList<Point> ps = World.getPointsAround(p, r);
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
{
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>();
int k = 0;
while(k < newP.size())
{
if(newP.get(k).cell.getCode()<=0)
{
newP.remove(k);
}
else
k++;
}
return newP;
}
private class PathPoint extends Point
{
public int d;
public Cell cell;
PathPoint()
{
this(new Point(0,0), new Cell());
}
PathPoint(Point p, Cell c)
{
super(p);
cell = c;
d = xSize*ySize*2;
}
public void clear()
{
d = xSize*ySize*2;
}
}
}
```

and of course the log:
``` ----jGRASP exec: java Main
Main.main-0
Main.main-1
Main.main-2
Main.main-3
Main.main-4
Main.main-5
Main.main-6
Main.main-7
Main.main-8
Main.main-9
Main.main-10
Main.main-11
Main.main-12
Main.main-13
Main.main-Done
Map.makePathToCode-0
Map.makePathToCode-1
Map.makePathToCode-2-B-0
Map.makePathToCode-2-B-1
Map.makePathToCode-2-B-2
Map.makePathToCode-2-B-3
Map.makePathToCode-2-B-4
Map.makePathToCode-2-B-5
Map.makePathToCode-2-B-6
Map.makePathToCode-2-B-4
Map.makePathToCode-2-B-5
Map.makePathToCode-2-B-6
Map.makePathToCode-2-B-7
Map.makePathToCode-2-B-8
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-11
Map.makePathToCode-2-B-12
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makePathToCode-2-B-9
Map.makePathToCode-2-B-10
Map.makeP
----jGRASP: process aborted by user.

```

### #3 vzybilly

Reputation: -1
• Posts: 160
• Joined: 24-September 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 17 August 2011 - 11:18 PM

I added in afew more info bits to the log writing and I can see what it's up to. Here is what I see...

```[ ][8][ ]
[8][7][180]
[ ][8][ ]
*Moves from an 8 to the 7, then trapped.

```

This is a snippet from the log:
```Map.makePathToCode-2-B-7
Map.makePathToCode-2-B-8: Num: 8
Map.makePathToCode-2-B-9: p.d: 8>0?
Map.makePathToCode-2-B-10: pp.size(): 4
Map.makePathToCode-2-B-11: pp[k].d: 7
Map.makePathToCode-2-B-12
Map.makePathToCode-2-B-13
Map.makePathToCode-2-B-9: p.d: 7>0?
Map.makePathToCode-2-B-10: pp.size(): 4
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-11: pp[k].d: 180
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-9: p.d: 7>0?
Map.makePathToCode-2-B-10: pp.size(): 4
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-11: pp[k].d: 180
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-9: p.d: 7>0?
Map.makePathToCode-2-B-10: pp.size(): 4
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-11: pp[k].d: 180
Map.makePathToCode-2-B-11: pp[k].d: 8
Map.makePathToCode-2-B-9: p.d: 7>0?

```

I Broke my Program to get this:
```x-,y-,x+
[0:180][0:180][0:180][0:180][0:180][0:180][0:180][0:180][0:180]
[0:180][2:007][1:006][1:007][1:006][1:007][1:006][2:007][0:180]
[0:180][4:006][1:007][1:006][1:007][1:006][1:007][4:006][0:180]
[0:180][3:007][1:006][1:007][1:006][1:007][1:006][3:007][0:180]
[0:180][0:180][0:180][1:006][1:007][1:006][0:180][0:180][0:180]
[0:180][1:180][1:180][1:007][1:006][1:007][1:006][0:180][0:180]
[0:180][1:180][1:180][1:180][1:007][1:006][1:007][0:180][0:180]
[0:180][1:180][1:180][1:180][1:180][1:007][1:180][0:180][0:180]
[0:180][1:180][1:180][1:180][1:180][1:180][1:180][0:180][0:180]
[0:180][0:180][0:180][0:180][0:180][0:180][0:180][0:180][0:180]
y+
Beginning: java.awt.Point[x=5,y=7]

```

This post has been edited by vzybilly: 17 August 2011 - 11:27 PM

### #4 vzybilly

Reputation: -1
• Posts: 160
• Joined: 24-September 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 18 August 2011 - 10:46 AM

I was able to get it working after abit of thinking from seeing the data at it's core (forgot to say how to read it: [CellCode:d])
I think the algorithm needs improvement but it work, i had it running all night long (10 hours) and I woke up to no memory issues.

here is the 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;

public class Map
{
private PathPoint[][] blocks;
int xSize;
int ySize;
Map(int xSizes, int ySizes)
{
xSize = xSizes;
ySize = ySizes;
construct();
}
private void construct()
{
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());
}
public void set(java.awt.Point p, Cell c)
{
blocks[p.x][p.y].cell.set(c);
blocks[p.x][p.y].cell.unTake();
}
public void makePathToFood(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{
makePathToCode(3, path, start);
}
public void makePathToWater(ArrayList<Integer> path, Point start) throws World.DirectionException, World.NoGoalException
{
makePathToCode(2, path, start);
}
private PathPoint findGoal(int code, Point start) throws World.NoGoalException
{
boolean found = false;
for(int j = 1; !found; j++)
{
ArrayList<PathPoint> pp = getPathPointsAround(blocks[start.x][start.y], j);
for(int k = 0; k < pp.size(); k++)
if(pp.get(k).cell.getCode()==code)
{
found = true;
return pp.get(k);
}
}
throw new World.NoGoalException();
}
public void makePathToCode(int code, ArrayList<Integer> path, Point beginning) throws World.DirectionException, World.NoGoalException
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-0");
for(int x = 0; x < blocks.length; x++)
for(int y =0; y<blocks[x].length; y++)
blocks[x][y].clear();
int stockNum = blocks[2][2].d;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-1");
if(blocks[beginning.x][beginning.y].cell.getCode() == code)
{
//we are on it!
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-0");
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");
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-A-Done");
}
else
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-0");
PathPoint end = findGoal(code, beginning);
PathPoint start = blocks[beginning.x][beginning.y];
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-1");
{
int startNum = start.d;
int x = 0;
end.d = x;
x++;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-2");
ArrayList<PathPoint> current = getOpenSides(end);
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-3");
while(start.d==startNum)
{
//PathFinding, explode out from end.
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-4");
for(int k = 0; (k < current.size())&&(start.d==startNum); k++)
{
if(current.get(k).d == stockNum)
current.get(k).d = x;
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-5");
while(current.get(0).d<=x)
{
current.remove(0);
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-6");
x++;
}
}
{
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;
PathPoint p = start;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-8: Num: "+num);
while(p.d > 0)
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-9: p.d: "+p.d+">0?");
ArrayList<PathPoint> pp = getOpenSides(p);
boolean found = false;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-10: pp.size(): "+pp.size());
for(int k = 0; (k < pp.size())&&(!found); k++)
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-11: pp[k].d: "+pp.get(k).d);
if(pp.get(k).d < num)
{
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-12");
found = true;
p = pp.get(k);
num = p.d;
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-13");
/*
{
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);
}
//*/
}
}
}
}
}
if(Main.DEBUG)
System.out.println("Map.makePathToCode-3");
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");
/*
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)
{
ArrayList<Point> ps = World.getPointsAround(p, r);
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
{
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>();
int k = 0;
while(k < newP.size())
{
if(newP.get(k).cell.getCode()<=0)
{
newP.remove(k);
}
else
k++;
}
return newP;
}
private class PathPoint extends Point
{
public int d;
public Cell cell;
PathPoint()
{
this(new Point(0,0), new Cell());
}
PathPoint(Point p, Cell c)
{
super(p);
cell = c;
d = xSize*ySize*2;
}
public void clear()
{
d = xSize*ySize*2;
}
}
}
```

### #5 vzybilly

Reputation: -1
• Posts: 160
• Joined: 24-September 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 19 August 2011 - 04:43 AM

I made the pathfinding code in my map class by my self after getting lost in pages of pages of google searches on multiple things (afew days spent)

There has to be a way to speed this up, the way I'm doing it now is I'm exploding out from the end point and continuing till i hit the current point, very cost heavy, lagg will kill a person (from hunger and/or thirst, which those are pathfinded to fix) when they are looking for a code of 4 (first and most common reason to pathfind).

the 'game' I'm making is almost ready for it's first release, this is a big error in the game and once fixed the game will be released in the next week or two (need to add some touch-ups at spots to easy the starting of)

I could slow down the time passing to compensate for this but people living for years and never having to eat or drink anything till they are 60 doesn't sound good does it?

well, back to the code, I have commented it all over the place to get it ready for release so it should be easy to read, if you have a spot that needs more then let me know and I'll add in more comments

Any improvement is greatly needed and thanked, and thank you for taking your time to try and help, also the Map class should have everything for the pathfinding, if it doesn't ask and I might post up some from other classes but I don't want to post all of it since all of it is my work and I would like to keep most of it private to me, thanks for understanding (the whole Map.java will be shown, with comments thanking the people that have help me), also sorry for the big long rant, I haven't been able to get much sleep (up for over 30 hours today... about to go to sleep...) for the past 3 week because of this program, hopefully you'll understand...

the code, Map.java:
```/*
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;

public class Map
{
private PathPoint[][] blocks;
private int xSize;
private int ySize;
private ArrayList<ArrayList<Point>> uniquePoints;
Map(int xSizes, int ySizes)
{
//set size then construct!
xSize = xSizes;
ySize = ySizes;
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());

//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) 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(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];
}
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
{

//We are not on it, it was worth a try :(/>
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-0");
return;

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

PathPoint start = blocks[beginning.x][beginning.y];
if(Main.DEBUG)
System.out.println("Map.makePathToCode-2-B-1");

//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
wastefull, yes? some of them are out past 30! future worlds will be giant 500X500 or bigger, this would kill everything.
*/
{
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;
}
private class PathPoint extends Point
{
public int d;
public Cell cell;
PathPoint()
{
this(new Point(0,0), new Cell());
}
PathPoint(Point p, Cell c)
{
super(p);
cell = c;
d = xSize*ySize*2;
}
public void clear()
{
d = xSize*ySize*2;
}
public void close()
{
cell.close();
cell = null;
}
}
}
```

This post has been edited by vzybilly: 19 August 2011 - 10:33 PM

### #6 macosxnerd101

• Self-Trained Economist

Reputation: 9037
• Posts: 33,523
• Joined: 27-December 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 19 August 2011 - 06:28 AM

### #7 vzybilly

Reputation: -1
• Posts: 160
• Joined: 24-September 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 19 August 2011 - 10:31 PM

macosxnerd101, on 19 August 2011 - 07:28 AM, said:

Would you be able to delete this whole topic?
-thanks

### #8 macosxnerd101

• Self-Trained Economist

Reputation: 9037
• Posts: 33,523
• Joined: 27-December 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 19 August 2011 - 10:33 PM

No. We do not delete topics unless they violate the rules, as yours does not.

### #9 vzybilly

Reputation: -1
• Posts: 160
• Joined: 24-September 08

## Re: Pathfinding Algorithim for 2D Cell based Map - Infinite Loop?

Posted 21 August 2011 - 11:07 AM

a link to my pre-release of this program.
https://rapidshare.c...214/AI_Play.zip