Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Help debugging AStar please


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
4 replies to this topic

#1 kujel   Members   -  Reputation: 104

Like
0Likes
Like

Posted 29 June 2012 - 11:39 PM

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 passableusing 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, 30 June 2012 - 08:28 AM.
Added source code tags


Sponsor:

#2 IADaveMark   Moderators   -  Reputation: 2531

Like
0Likes
Like

Posted 30 June 2012 - 08:29 AM

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-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#3 kujel   Members   -  Reputation: 104

Like
0Likes
Like

Posted 30 June 2012 - 08:49 AM

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, 30 June 2012 - 09:19 AM.


#4 alexjc   Members   -  Reputation: 450

Like
0Likes
Like

Posted 01 July 2012 - 03:40 AM

There was a thread on this topic posted almost exactly the same time as yours! Here was my reply:

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



I realize you wanted someone to debug your program but well... ;-)


Join us in Vienna for the Game/AI Conference 2014, on July 7-10... Don't miss it!


#5 kujel   Members   -  Reputation: 104

Like
0Likes
Like

Posted 01 July 2012 - 12:00 PM

I can give that a try, at least there is no harm in it.




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