🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Help debugging AStar please
I've got an implimentation for AStar and it works for the most part but when the path gets really close to the target point it starts to cirlce for a bit before actually settling on the target. I've looked my code over for a while but I can't seem to see where the problem is. Any help spotting my problem would be awesome thanks.
Here is my source code:
[source lang="csharp"]//MapGraph is a 2D array of booleans, false denotes impassable and true passable
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
namespace WindowsGameLibrary1
{
public class AeeStar
{
class PathNode
{
int x, y, moves, dist;
PathNode parent;
public PathNode(int x, int y, int moves, int dist, PathNode parent = null)
{
this.x = x;
this.y = y;
this.moves = moves;
this.dist = dist;
this.parent = parent;
}
public int X
{
get { return x; }
set { x = value; }
}
public int Y
{
get { return y; }
set { y = value; }
}
public int Moves
{
get { return moves; }
set { moves = value; }
}
public int Dist
{
get { return dist; }
set { dist = value; }
}
public int finalCost()
{
return moves + dist;
}
public PathNode Parent
{
get { return parent; }
set { parent = value; }
}
}
int x1, y1, x2, y2, scale;
MapGraph mg;
PriorityQueue<PathNode> open;
List<PathNode> closed;
List<VectorInt> path;
PathNode current, up, left, right, down;
bool exists;
int max;
public AeeStar(MapGraph mg, int scale = 60, int max = 1000)
{
this.mg = mg;
this.scale = scale;
this.max = max;
open = new PriorityQueue<PathNode>();
closed = new List<PathNode>();
}
public int calcDist(int x1, int y1, int x2, int y2)
{
return DistanceCalculator.calcDistance(new Vector2(x1, y1), new Vector2(x2, y2));
}
public void setUp()
{
if (current.Y-1 > 0)
{
if (mg.getCell(current.X, current.Y - 1) == false)
{
up = null;
}
else
{
up = new PathNode(current.X, current.Y - 1, current.Moves + 1, calcDist(current.X, current.Y - 1, x2, y2), current);
}
}
}
public void setLeft()
{
if (current.X-1 > 0)
{
if (mg.getCell(current.X - 1, current.Y) == false)
{
left = null;
}
else
{
left = new PathNode(current.X - 1, current.Y, current.Moves + 1, calcDist(current.X - 1, current.Y, x2, y2), current);
}
}
}
public void setRight()
{
if (current.X+1 < mg.Size.X - 1)
{
if (mg.getCell(current.X + 1, current.Y) == false)
{
right = null;
}
else
{
right = new PathNode(current.X + 1, current.Y, current.Moves + 1, calcDist(current.X + 1, current.Y, x2, y2), current);
}
}
}
public void setDown()
{
if (current.Y+1 < mg.Size.Y - 1)
{
if (mg.getCell(current.X, current.Y + 1) == false)
{
down = null;
}
else
{
down = new PathNode(current.X, current.Y + 1, current.Moves + 1, calcDist(current.X, current.Y + 1, x2, y2), current);
}
}
}
public List<VectorInt> findPath(int x1, int y1, int x2, int y2)
{
this.x1 = x1/scale;
this.y1 = y1/scale;
this.x2 = x2/scale;
this.y2 = y2/scale;
exists = false;
open.enqueue((new PathNode(x1 / scale, y1 / scale, 0, calcDist(x1 / scale, y1 / scale, x2 / scale, y2 / scale))), calcDist(x1 / scale, y1 / scale, x2 / scale, y2 / scale));
int searches = 0;
while (open.Count > 0 && searches < max)
{
current = open.dequeue();
setUp();
if (up != null)
{
open.enqueue(up, up.finalCost());
}
setLeft();
if (left != null)
{
open.enqueue(left, left.finalCost());
}
setRight();
if (right != null)
{
open.enqueue(right, right.finalCost());
}
setDown();
if (down != null)
{
open.enqueue(down, down.finalCost());
}
for (int i = 0; i < closed.Count; i++)
{
if (closed.X == current.X && closed.Y == current.Y && closed.finalCost() > current.finalCost())
{
closed = current;
exists = true;
}
}
if (!exists)
{
closed.Add(current);
}
if (current.X == x2 && current.Y == y2)
{
break;
}
searches++;
}
//path = new List<VectorInt>();
createPath();
return path;
}
public void createPath()
{
path = new List<VectorInt>();
while (current.Moves != 0)
{
path.Add(new VectorInt(current.X*scale, current.Y*scale));
current = current.Parent;
}
}
}
}[/source]
Here is my source code:
[source lang="csharp"]//MapGraph is a 2D array of booleans, false denotes impassable and true passable
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
namespace WindowsGameLibrary1
{
public class AeeStar
{
class PathNode
{
int x, y, moves, dist;
PathNode parent;
public PathNode(int x, int y, int moves, int dist, PathNode parent = null)
{
this.x = x;
this.y = y;
this.moves = moves;
this.dist = dist;
this.parent = parent;
}
public int X
{
get { return x; }
set { x = value; }
}
public int Y
{
get { return y; }
set { y = value; }
}
public int Moves
{
get { return moves; }
set { moves = value; }
}
public int Dist
{
get { return dist; }
set { dist = value; }
}
public int finalCost()
{
return moves + dist;
}
public PathNode Parent
{
get { return parent; }
set { parent = value; }
}
}
int x1, y1, x2, y2, scale;
MapGraph mg;
PriorityQueue<PathNode> open;
List<PathNode> closed;
List<VectorInt> path;
PathNode current, up, left, right, down;
bool exists;
int max;
public AeeStar(MapGraph mg, int scale = 60, int max = 1000)
{
this.mg = mg;
this.scale = scale;
this.max = max;
open = new PriorityQueue<PathNode>();
closed = new List<PathNode>();
}
public int calcDist(int x1, int y1, int x2, int y2)
{
return DistanceCalculator.calcDistance(new Vector2(x1, y1), new Vector2(x2, y2));
}
public void setUp()
{
if (current.Y-1 > 0)
{
if (mg.getCell(current.X, current.Y - 1) == false)
{
up = null;
}
else
{
up = new PathNode(current.X, current.Y - 1, current.Moves + 1, calcDist(current.X, current.Y - 1, x2, y2), current);
}
}
}
public void setLeft()
{
if (current.X-1 > 0)
{
if (mg.getCell(current.X - 1, current.Y) == false)
{
left = null;
}
else
{
left = new PathNode(current.X - 1, current.Y, current.Moves + 1, calcDist(current.X - 1, current.Y, x2, y2), current);
}
}
}
public void setRight()
{
if (current.X+1 < mg.Size.X - 1)
{
if (mg.getCell(current.X + 1, current.Y) == false)
{
right = null;
}
else
{
right = new PathNode(current.X + 1, current.Y, current.Moves + 1, calcDist(current.X + 1, current.Y, x2, y2), current);
}
}
}
public void setDown()
{
if (current.Y+1 < mg.Size.Y - 1)
{
if (mg.getCell(current.X, current.Y + 1) == false)
{
down = null;
}
else
{
down = new PathNode(current.X, current.Y + 1, current.Moves + 1, calcDist(current.X, current.Y + 1, x2, y2), current);
}
}
}
public List<VectorInt> findPath(int x1, int y1, int x2, int y2)
{
this.x1 = x1/scale;
this.y1 = y1/scale;
this.x2 = x2/scale;
this.y2 = y2/scale;
exists = false;
open.enqueue((new PathNode(x1 / scale, y1 / scale, 0, calcDist(x1 / scale, y1 / scale, x2 / scale, y2 / scale))), calcDist(x1 / scale, y1 / scale, x2 / scale, y2 / scale));
int searches = 0;
while (open.Count > 0 && searches < max)
{
current = open.dequeue();
setUp();
if (up != null)
{
open.enqueue(up, up.finalCost());
}
setLeft();
if (left != null)
{
open.enqueue(left, left.finalCost());
}
setRight();
if (right != null)
{
open.enqueue(right, right.finalCost());
}
setDown();
if (down != null)
{
open.enqueue(down, down.finalCost());
}
for (int i = 0; i < closed.Count; i++)
{
if (closed.X == current.X && closed.Y == current.Y && closed.finalCost() > current.finalCost())
{
closed = current;
exists = true;
}
}
if (!exists)
{
closed.Add(current);
}
if (current.X == x2 && current.Y == y2)
{
break;
}
searches++;
}
//path = new List<VectorInt>();
createPath();
return path;
}
public void createPath()
{
path = new List<VectorInt>();
while (current.Moves != 0)
{
path.Add(new VectorInt(current.X*scale, current.Y*scale));
current = current.Parent;
}
}
}
}[/source]
Yeah but I couldn't see the problem still. I set break points at the exit conditions as well as when creating new nodes. I wish I could just log the data and comb through it after a run through. Normally I don't ask others to help me spot bugs but I've been told AStar is a tricky bugger to debug.
There was a thread on this topic posted almost exactly the same time as yours! Here was my reply:
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif][background=rgb(250, 251, 252)]Assuming you're doing this for learning purposes, and not reusing an existing piece of code... My best advice is to write some unit tests incrementally and check all your assumptions. I've found that unit tests provide amazing support for learning new algorithms, languages, and writing new code in general :-)[/background]
[/font]
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif][background=rgb(250, 251, 252)]I realize you wanted someone to debug your program but well... ;-) [/background]
[/font][/quote]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement