Skip to main content
GameDev.net gamedev.net
🔒 Locked 🤖 Godot

Help debugging AStar please

Started by kujel Jun 30, 2012 at 5:39 AM 3 replies 2.2k views
Original Post
kujel
kujel
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 open;
List closed;
List 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();
closed = new List();
}
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 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();
createPath();
return path;
}
public void createPath()
{
path = new List();
while (current.Moves != 0)
{
path.Add(new VectorInt(current.X*scale, current.Y*scale));
current = current.Parent;
}
}
}
}[/source]
IADaveMark
IADaveMark
Question #1: Have you traced and stepped through your own code?
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit<
kujel
kujel
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.
alexjc
alexjc
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]

Join us in Vienna for the nucl.ai Conference 2015, on July 20-22... Don't miss it!
kujel
kujel
I can give that a try, at least there is no harm in it.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.