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

Offline Rhuan

  • Verified
  • Low Poster
  • *
  • Posts: 73
    • 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: 1405
  • 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
  • Low Poster
  • *
  • Posts: 73
    • 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.

Online Fat Cerberus

  • miniSphere Developer
  • Verified
  • Legendary Poster
  • *
  • Posts: 2166
  • *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.11 - Cell compiler - SSJ debugger
Forum Thread | GitHub Repo

Offline Flying Jester

  • TurboSphere Developer
  • Verified
  • Legendary Poster
  • *
  • Posts: 1152
    • 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.

Offline Rhuan

  • Verified
  • Low Poster
  • *
  • Posts: 73
    • View Profile
Re: Pathfinding - can someone give me some pointers?
« Reply #5 on: May 13, 2017, 07:21:54 am »
Thanks for all of the replies, sorry for the slow turn around, life got in the way.

I've now scripted Dijkstra's Algorithm and it's working nicely, the key thing that Breadth First can't do as far as I understand that Dijkstra could do is have different movement costs for different nodes and ultimately find the cheapest route to each point - a feature I wanted.

A* is all about optimising the search to find a specific goal node which is not something I wanted at the moment as I wanted to find all possible destinations with cost below a certain amount so a player or AI can choose how to use their movement from possible options.

Offline Eggbert

  • Verified
  • Medium Poster
  • *
  • Posts: 177
    • View Profile
    • My GitHub
Re: Pathfinding - can someone give me some pointers?
« Reply #6 on: May 13, 2017, 07:12:25 pm »
I'm not sure if this will help much now, but I've been working with a pretty nice pathfinding library that I found on Github. It's designed to use CommonJS, and seems to have been written with Node in mind, but it's very platform independent. I just put in in lib/ and it worked without question or complaint.

Offline Eggbert

  • Verified
  • Medium Poster
  • *
  • Posts: 177
    • View Profile
    • My GitHub
Re: Pathfinding - can someone give me some pointers?
« Reply #7 on: May 13, 2017, 07:15:59 pm »
https://github.com/qiao/PathFinding.js/

Here it is. You can just go into your package lib directory, clone it with git (or download and unzip it) and do
Code: Javascript
  1. var PF = require("pathfinding");


http://qiao.github.io/PathFinding.js/visual/
Here's an in-browser demonstration.

Offline Rhuan

  • Verified
  • Low Poster
  • *
  • Posts: 73
    • View Profile
Re: Pathfinding - can someone give me some pointers?
« Reply #8 on: May 14, 2017, 05:50:44 pm »
https://github.com/qiao/PathFinding.js/

Here it is. You can just go into your package lib directory, clone it with git (or download and unzip it) and do
Code: Javascript
  1. var PF = require("pathfinding");


http://qiao.github.io/PathFinding.js/visual/
Here's an in-browser demonstration.
I had actually found that library some time ago - but it seemed like it had a much larger footprint than needed for what I need to do AND I couldn't see a way to make it return a set of all possible destinations, it just wanted to return the route to a goal, that said I didn't spend ages on it so may have missed stuff.

Offline Flying Jester

  • TurboSphere Developer
  • Verified
  • Legendary Poster
  • *
  • Posts: 1152
    • View Profile
Re: Pathfinding - can someone give me some pointers?
« Reply #9 on: May 14, 2017, 08:21:02 pm »
Thanks for all of the replies, sorry for the slow turn around, life got in the way.

I've now scripted Dijkstra's Algorithm and it's working nicely, the key thing that Breadth First can't do as far as I understand that Dijkstra could do is have different movement costs for different nodes and ultimately find the cheapest route to each point - a feature I wanted.

You can do this with breadth-first, but it requires explicitly storing each graph node's current movement value (instead of using the branch's length), and performing merges where you find shorter paths to existing found locations, which is much more complex than if you don't want to have differing node costs.