Jump to content

  • Log In with Google      Sign In   
  • Create Account

A* algorithm by pixel: Failed to create diagonal path in 3x3 grid.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 tom_mai78101   Members   -  Reputation: 572

Like
0Likes
Like

Posted 20 February 2012 - 01:35 AM

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) :

Posted Image

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][i] = new Square(count++, this);
	this.squares[j][i].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[i].length; j++)
	if(squares[i][j].flag == Square.FINISH)
	 goal = squares[i][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.

Sponsor:

#2 Postie   Members   -  Reputation: 1003

Like
0Likes
Like

Posted 20 February 2012 - 05:46 PM

Your A* implementation is a little unconventional. Skimming through the code I've noticed the following things:
  • 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.
  • Similarly, you shouldn't ever be removing entries from the closed list.
  • Neither should you be removing the neighbouring squares from the open list in the neighbour checking loop.
  • 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.
  • Why do you recalculate the goal square in findBestPath()?

Incidentally, what's your getcost() function look like?
Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#3 tom_mai78101   Members   -  Reputation: 572

Like
0Likes
Like

Posted 28 February 2012 - 11:11 AM

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.

  • Similarly, you shouldn't ever be removing entries from the closed list.
  • Neither should you be removing the neighbouring squares from the open list in the neighbour checking loop.
  • 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(); 
}


#4 tom_mai78101   Members   -  Reputation: 572

Like
0Likes
Like

Posted 14 March 2012 - 11:56 PM

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

#5 SuperVGA   Members   -  Reputation: 1118

Like
0Likes
Like

Posted 15 March 2012 - 05:04 AM

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 1.0 * (Math.abs(x - goal.x) + Math.abs(y - goal.y));
(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)

Math.sqrt( (goal.x-x)*(goal.x-x) + (goal.y-y)*(goal.y-y) );

#6 Postie   Members   -  Reputation: 1003

Like
0Likes
Like

Posted 18 March 2012 - 05:03 AM

First of all, sorry for not responding earlier. This post dropped off my radar and I forgot to follow it up.

You should only be removing items from the open list when you traverse them. That is, at the very top of the processing loop you search the open list for the node with the lowest cost. Once you find it, you remove it from the open list, then test to see if that node is in the closed list. If it is, then you loop back to the start and find the next node. Otherwise, you add the node to the closed list, and proceed with the rest of the processing using that node. You should never remove nodes from the closed list, as this represents nodes that you've already visited.

Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS