Author Topic: Pathfinding - can someone give me some pointers?  (Read 451 times)

Offline Rhuan

  • Verified
  • Newbie
  • *
  • Posts: 41
    • View Profile
Pathfinding - can someone give me some pointers?
« on: January 02, 2017, 11:14:55 am »
I studied pathfinding maths about 7 or 8 years ago... I can't remember much of it at all, and I've never written any code involving pathfinding.

I'd like to write a pathfinding algorithm in sphere and don't know where to start - I've been looking around and tried reading up A* and JPS but most things I can find are pitched too high for me I could do with a simpler introduction.

Ultimately I'm looking to write something I can use in Sphere that will do the following thing:
Given:
- a weighted graph
- a starting point
- a maximum path cost
Calculate:
- all possible destinations
- the cheapest path to each destination

But for now please could I have some very introductory pointers
« Last Edit: January 02, 2017, 11:59:12 am by Rhuan »

Offline Radnen

  • Wise Warrior
  • Senior Staff
  • Legendary Poster
  • *****
  • Posts: 1404
  • Sphere Studio Developer
    • View Profile
    • Radnen's Hub
Re: Pathfinding - can someone give me some pointers?
« Reply #1 on: January 02, 2017, 03:11:55 pm »
I found this tutorial to be rather good:
https://www.raywenderlich.com/4946/introduction-to-a-pathfinding

You can even look through my code to see how it is done. I added a binary heap to sort nodes faster. This one can be a bit complicated to understand but it follows the logic in that tutorial above. This pathfinder was fast enough to run more than twenty enemies charging at the player in a small action game me and a few others did called Cellar Rush.

Edit:
For info on more of a video-game approach including different heuristic patterns, this is a good article too:
http://www.redblobgames.com/pathfinding/a-star/introduction.html
« Last Edit: January 02, 2017, 03:14:37 pm by Radnen »
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Offline Rhuan

  • Verified
  • Newbie
  • *
  • Posts: 41
    • View Profile
Re: Pathfinding - can someone give me some pointers?
« Reply #2 on: January 02, 2017, 07:07:26 pm »
Thanks Radnan, that second tutorial in particular is very helpful - I'd already seen the first one though reading it a second time it's starting to make more sense.

It seems what I need is Dijkstra’s Algorithm (as I want to find paths to all possible points) and not A* or JPS which focus on finding the shortest route to one point only.

Offline Fat Cerberus

  • miniSphere Developer
  • Verified
  • Legendary Poster
  • *
  • Posts: 2129
  • *MUNCH*
    • View Profile
Re: Pathfinding - can someone give me some pointers?
« Reply #3 on: January 02, 2017, 10:14:53 pm »
It was my understanding that Dijkstra's Algorithm is A*, but without any heuristics to speed it up.
miniSphere 4.5.10 - Cell compiler - SSJ debugger
Forum Thread | GitHub Repo

Offline Flying Jester

  • TurboSphere Developer
  • Verified
  • Legendary Poster
  • *
  • Posts: 1149
    • View Profile
Re: Pathfinding - can someone give me some pointers?
« Reply #4 on: January 03, 2017, 03:17:27 am »
Assuming this is for your Fire-Emblem-style game, where you see the list of possible movement locations and ensure that only one of those is selected, then breadth-first is most suitable. I've done this before, and it's actually easier to understand than how it would be used in regular pathfinding.

 

anything