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

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

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.

It was my understanding that Dijkstra's Algorithm is A*, but without any heuristics to speed it up.

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.

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.

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.

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) [Select]

var PF = require("pathfinding");

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

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) [Select]

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.

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.