A* Pathfinding

10 posts

Flag Post

For some reason my pathfinding is not working- it goes ALL over the grid and I’m not sure why. Any help would be appreciated. All project files are here.

 
Flag Post
  • The heuristics also seem to be all over the grid.
  • The player appears to be taking the biggest heuristic possible that is lower than the heuristic tile the player was on. In the beginning, the player just chooses the highest heuristic.
  • However, when I take the path with the lowest heuristic, I end up with the correct shortest path.

I think the heuristics are correct, but the heuristic used is incorrectly chosen. I don’t know where to find that part, but if you know, you’ll need to switch it so the player chooses the lowest heuristic.

 
Flag Post

I admit that I’ve only taken the slightest glance at your findPath function, but it looks like you have a typo or are misunderstanding the splice command on line 88

Once you’ve got your algorithm working, it may be worth your while reviewing it to see if you could have written your code better, particularly in terms of control flow and excessive statements
If you’re really keen – look into binary heaps (Fibonaccci heaps if you’re ‘overly’ keen)

I hate to throw in a shameless plug, but this could be an interesting read: http://www.kongregate.com/forums/4/topics/120784

 
Flag Post
Originally posted by Dealmaster13:

I admit that I’ve only taken the slightest glance at your findPath function, but it looks like you have a typo or are misunderstanding the splice command on line 88

Once you’ve got your algorithm working, it may be worth your while reviewing it to see if you could have written your code better, particularly in terms of control flow and excessive statements
If you’re really keen – look into binary heaps (Fibonaccci heaps if you’re ‘overly’ keen)

I hate to throw in a shameless plug, but this could be an interesting read: http://www.kongregate.com/forums/4/topics/120784

Hah! I forgot the second argument in it. Also, could you possibly explain more about “control flow” and “excessive statements”? (Not trying to start anything- just always eager to learn more! )

Thanks!

 
Flag Post
Originally posted by RTL_Shadow:
Originally posted by Dealmaster13:

I admit that I’ve only taken the slightest glance at your findPath function, but it looks like you have a typo or are misunderstanding the splice command on line 88

Once you’ve got your algorithm working, it may be worth your while reviewing it to see if you could have written your code better, particularly in terms of control flow and excessive statements
If you’re really keen – look into binary heaps (Fibonaccci heaps if you’re ‘overly’ keen)

I hate to throw in a shameless plug, but this could be an interesting read: http://www.kongregate.com/forums/4/topics/120784

Hah! I forgot the second argument in it. Also, could you possibly explain more about “control flow” and “excessive statements”? (Not trying to start anything- just always eager to learn more! )

Thanks!

I think he’s just saying it could be more concise and cleaned-up. I haven’t looked at the actual code, so I can’t comment on specifics.

 
Flag Post

Also, for some odd reason if I do something like this:
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,3,0,0,0,0,
0,1,0,3,0,2,0,0,
0,0,0,3,0,0,0,0,
3,3,3,3,0,0,0,0,
0,0,0,0,0,0,0,0
Build times out and doesn’t work. But this works fine:
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,3,0,0,0,0,
0,1,0,0,0,2,0,0,
0,0,0,3,0,0,0,0,
3,3,3,3,0,0,0,0,
0,0,0,0,0,0,0,0

 
Flag Post

I’ll be happy to review this once I get back home… concerning control flow: I originally thought this was an inefficiency, but on a second look it looks like a flaw in the algorithm (although I am on my phone without indenting, so could be mistaken) where while finding the tile with the lowest F, you seem to be doing things before you even find the necessary tile

 
Flag Post
Originally posted by Dealmaster13:

I’ll be happy to review this once I get back home… concerning control flow: I originally thought this was an inefficiency, but on a second look it looks like a flaw in the algorithm (although I am on my phone without indenting, so could be mistaken) where while finding the tile with the lowest F, you seem to be doing things before you even find the necessary tile

Not quite sure what that means, because the first thing I do is find the lowest F.

 
Flag Post

I don’t know… to me it looks like you’re taking a pile of stuff out of the open list and putting them in the closed list

@author RTLShadow:

for ( var j:int = 0; j < openList.length; j++ )
{ // Look for the lowest F cost on the open list.
if ( openList[ j ].f < lowestF.f )
{
lowestF = openList[ j ];
}
currentNode = lowestF; // Make it the current square.
openList.splice( findPos( openList, currentNode), 1); // remove it from open list
closedList.push( currentNode ); // add it to the closed list

}
 
Flag Post
Originally posted by Dealmaster13:

I don’t know… to me it looks like you’re taking a pile of stuff out of the open list and putting them in the closed list

@author RTLShadow:

for ( var j:int = 0; j < openList.length; j++ )
{ // Look for the lowest F cost on the open list.
if ( openList[ j ].f < lowestF.f )
{
lowestF = openList[ j ];
}
currentNode = lowestF; // Make it the current square.
openList.splice( findPos( openList, currentNode), 1); // remove it from open list
closedList.push( currentNode ); // add it to the closed list

}

DERP! I should do that outside of the loop. Thanks! I’ll report back.

E: Works pretty good, some minor things where it’ll go diagonally instead of straight but thats probably a conditional problem. Feel free to check it if you like.