Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

AStar Pathfinder Output is Wrong

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm building a plugin for a game(RuneScape/RuneLite) to be used to display the shortest/best path to a target.
Pathfinding works great in Dijkstra/Greedy-AStar but I want to limit it to look in the region it's headed/or just not look all over the place to make pathfinding faster (under 300ms).

What's the problem? My AStar Algorithm, I think the Heuristic Calculation is wrong or needs modification. Any help will be greatly appreciated.

Note: Here's the whole map & pathfinder source code: https://easyupload.io/9gjjwq

This is what the correct path looks like: (Generated using Greedy AStar/Dijkstra. Took 1.1s)

Dijikstra (Correct Path)



This is what my AStar algorithm (Code shown below) outputs (Generated in 83ms):

AStar (Incorrect)



You can move in 8 directions: N, E, W, S, NE, NW, SE, SW. So I use the Diagonal Heuristic method from the Stanford Website.

AStar Pathfinding class:



Direction Enum class (used to loop through directions and check they're blocked):



AStarNode (Node class):

 
Jake Martins
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Bump.

Any Help Would GREATLY be appreciated!
 
Jake Martins
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
-- Solved --
 
reply
    Bookmark Topic Watch Topic
  • New Topic