Sign in to follow this  
kujel

Help debugging AStar please

Recommended Posts

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[i].X == current.X && closed[i].Y == current.Y && closed[i].finalCost() > current.finalCost())
{
closed[i] = 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] Edited by IADaveMark
Added source code tags

Share this post


Link to post
Share on other sites
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. Edited by kujel

Share this post


Link to post
Share on other sites
There was a thread on this topic posted almost exactly the same time as yours! Here was my reply:

[quote][color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif][size=4][left][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][/left][/size][/font][/color]

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif][size=4][left][background=rgb(250, 251, 252)]I realize you wanted someone to debug your program but well... ;-) [/background][/left][/size][/font][/color][/quote]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this