Skip to main content ↑ ↓
Topic: Pathfinding - can someone give me some pointers? (Read 135294 times) previous topic - next topic
0 Members and 4 Guests are viewing this topic.

Pathfinding - can someone give me some pointers?

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

Re: Pathfinding - can someone give me some pointers?

Reply #1 –
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
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

Re: Pathfinding - can someone give me some pointers?

Reply #2 –
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.

Re: Pathfinding - can someone give me some pointers?

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

Re: Pathfinding - can someone give me some pointers?

Reply #4 –
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.

Re: Pathfinding - can someone give me some pointers?

Reply #5 –
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.

Re: Pathfinding - can someone give me some pointers?

Reply #6 –
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.

Re: Pathfinding - can someone give me some pointers?

Reply #7 –
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.

Re: Pathfinding - can someone give me some pointers?

Reply #8 –
Quote from: Eggbert – on

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.
 

Re: Pathfinding - can someone give me some pointers?

Reply #9 –
Quote from: Rhuan – on

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.