I have trouble creating a path, either it's closed or best, from going downwards (south) and / or diagonally downwards (southeast / southwest).

Here's a picture displaying the current state of my program (bugged, and inaccurately displayed) :



I have set Square 1 as my starting point, and Square 9 as my finishing point. From Square 1 to Square 9, I set the default colors to different hues of dark red. From Square 1 to Square 3, those are the squares added into the "best" array list selected out, and marked as white to distinguish as the "best path" from starting point to finishing point.

I expected to have Square 1, Square 2, Square 5, Square 6, and Square 9 (Or 1, 4, 5, 8, and 9) be marked white, and all three of the squares are added to the "best" array list. The picture above is not what I wanted.

I'm asking for help in determining where my bug occurred, where the "best" path is unabled to be generated correctly. One major problem is that my source code is pretty huge when considering how jumpy my code is.

Currently, I'm reading through my codes to try and figure out where it's not working.

Source code, place where I suspect it's where the bug is located at. I probably narrowed it down quite a lot:


package core;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
public class Grid
{
public List<Square> grids = new ArrayList<Square>();
public List<Square> exists = new ArrayList<Square>();
public int size = 9;
public int width;
public int height;
public Square target = new Square(0, this);
// =======================================================
public int rows = 0;
public int columns = 0;
public Square goal;
public Square[][] squares;
public List<Square> opened = new ArrayList<Square>();
public List<Square> closed = new ArrayList<Square>();
public List<Square> best = new ArrayList<Square>();
int xStart = 0;
int yStart = 0;
int xFinish = 2;
int yFinish = 2;

public Grid(int rows, int columns)
{
this.rows = rows;
this.columns = columns;
this.squares = new Square[rows][columns];
int count = 0;
for(int j = 0; j < rows; j++)
{
for(int i = 0; i < columns; i++)
{
this.squares[j] = new Square(count++, this);
this.squares[j].setCoordinate(j, i);
}
}
squares[xStart][yStart].setFlag(Square.START);
squares[xFinish][yFinish].setFlag(Square.FINISH);
this.goal = squares[xFinish][yFinish];
for(int ro = 0; ro < squares.length; ro++)
for(int c = 0; c < squares[ro].length; c++)
squares[ro][c].checkAdjacencies();
}

public void findingPath()
{
Set<Square> adjacSet = squares[xStart][yStart].adjacencies;
for(Square adjacent : adjacSet)
{
adjacent.parent = squares[xStart][yStart];
if(adjacent.flag != Square.START)
opened.add(adjacent);
}
}

public Square findBestPath()
{
Square best = null;
Square goal = null;
for(int i = 0; i < squares.length; i++)
for(int j = 0; j < squares.length; j++)
if(squares[j].flag == Square.FINISH)
goal = squares[j];
for(Square square : opened)
{
if(best == null || square.getCost(goal) < best.getCost(goal))
{
best = square;
}
}
return best;
}

// ============================================
private void populateBestList(Square square)
{
best.add(square);
if(square.parent.flag != Square.START)
populateBestList(square.parent);
return;
}
boolean testFlag = false;

public void tick()
{
if(testFlag == false)
{
findingPath();
testFlag = true;
}
if(opened.size() > 0)
{
Square best = findBestPath();
opened.remove(best);
closed.add(best);
if(best.flag == Square.FINISH)
{
populateBestList(goal);
return;
}
else
{
Set<Square> neighbors = best.adjacencies;
for(Square neighbor : neighbors)
{
if(opened.contains(neighbor))
{
Square temp = new Square(neighbor.id, this);
temp.setCoordinate(neighbor.x, neighbor.y);
temp.parent = best;
if(temp.getCost(goal) >= neighbor.getCost(goal))
continue;
}
if(closed.contains(neighbor))
{
Square temp = new Square(neighbor.id, this);
temp.setCoordinate(neighbor.x, neighbor.y);
temp.parent = best;
if(temp.getCost(goal) >= neighbor.getCost(goal))
continue;
}
neighbor.parent = best;
opened.remove(neighbor);
closed.remove(neighbor);
opened.add(0, neighbor);
}
}
}
if(opened.size() <= 0)
{
Square temp = null;
for(Square t : best)
if(t.flag == Square.FINISH)
temp = t;
while(temp != null)
{
temp = temp.parent;
}
}
}

public void render(int[] pixels)
{
for(Square object : closed)
{
pixels[object.x + object.y * width] = object.color;
}
}
}


Thanks for your help in reading this thread in advance.

Sorry for not replying a week ago. Been busy with real life.

Your closed list logic is a little off. You should test to see if a neighbour is in the closed list, and if it is, ignore it and move on, since the closed list represents tiles you've already visited.

1. Similarly, you shouldn't ever be removing entries from the closed list.
   
2. Neither should you be removing the neighbouring squares from the open list in the neighbour checking loop.
   
3. It also seems that if the cost function test fails in the part where you check to see if the neighbour is in the open list, it will end up adding the neighbour to the open list again a little bit later in the code.
   

I guess Points 1 and 2 are valid. Under what scenarios should I remove a neighbor or a grid from the opened list and/or closed list?

As for the cost function test, I'm not clearly in the picture on the subject of creating a condition that evaluates whether the neighbor is allowed to be in the open list while not determining whether that same neighbor satisfies itself being in the closed list.

What I'm saying is that, there may be two or more possible solutions. For example, I expected two different solutions, so I couldn't create a more specific condition when calculating the cost for the squares and parents individually. My hypothesis is, if I used "greater than or equals to" condition, I might be able to satisfy all conditions in this situation, but I didn't. I'm all ears on the cost function test problem, and how I should rethink my logic on this part.

4. Why do you recalculate the goal square in findBestPath()?

Shouldn't it be included in the total cost from a parent square to the target square?

Incidentally, what's your getcost() function look like?

Here you go!


private double getLocalCost(Square goal){
if (this.flag == Square.START)
return 0.0;
localCost = 1.0 * (Math.abs(x - goal.x) + Math.abs(y - goal.y));
return localCost;
}

public double getParentCost(){
if (this.flag == Square.START)
return 0.0;
if (parentCost == 0.0)
parentCost = 1.0 + 0.5 * (this.parent.getParentCost() - 1.0);
return parentCost;
}

public double getCost(Square goal){
if (this.flag == Square.START)
return 0.0;
return getLocalCost(goal) + getParentCost();
}


2 week bump, requesting @Postie. If anyone else would like to help out, I'll gladly read it.

Hi tom_mai.

Have a look at your local cost function. Much like the silly Pi=4 topic which szecs presented on GameDev some time ago,
(in which the circle is thought to have the same circumference as its bounding square), the fastest way to the diagonally opposite corner is just as well along the edges as it is across:

Right, Right, Down Down
you'd like it to be
Right, Down, Right, Down

It's the same cost, so it's not an advantage to pick the latter over the former.

Your local cost function is [color=#006666]1.0[color=#000000] [color=#666600]*[color=#000000] [color=#666600]([color=#660066]Math[color=#666600].[color=#000000]abs[color=#666600]([color=#000000]x [color=#666600]-[color=#000000] goal[color=#666600].[color=#000000]x[color=#666600])[color=#000000] [color=#666600]+[color=#000000] [color=#660066]Math[color=#666600].[color=#000000]abs[color=#666600]([color=#000000]y [color=#666600]-[color=#000000] goal[color=#666600].[color=#000000]y[color=#666600]));
(why the multiplication by the way?)

And that's not the same as the direct distance across. (Cost function still makes sense, though. if the agent cannot move diagonally)
If you want it to go across, get the actual distance between the centers of each square: (Pythagoras is your friend)

[color=#800080]Math[color=#666600].sqrt[color=#666600]( [color=#666600]([color=#000000]goal[color=#666600].[color=#000000]x-x[color=#666600])*[color=#666600]([color=#000000]goal[color=#666600].[color=#000000]x-x[color=#666600])[color=#000000] [color=#666600]+[color=#000000] [color=#666600][color=#666600]([color=#000000]goal[color=#666600].[color=#000000]y-y[color=#666600])*[color=#666600]([color=#000000]goal[color=#666600].[color=#000000]y-y[color=#666600]) );