Question about Pathfinding options

[rohan-deshpande]

Hi there, not sure if this is the right place to ask questions, but I'll try anyway.

I'm in the process of a massive update to my game, and I'm using Pathfinding.js for it. I have used it successfully in plotting the movement between two positions for units in a previous version, however, I would like to be able to use it for something else - the compilation of movement options for units.

Basically, the use case would be like this - I have a matrix and a position for a unit inside of that matrix, let's say it's 6,7 (so row 6, column 7). Now, I want to be able to pass some method this position, and an integer value, and what I get back is a list of all the possible coordinate options for that unit to move to. The final result would look something like this

http://imgur.com/JjL0mRh

Is it possible to do this with Pathfinding.js? If not I will write my own method but I thought if the lib can handle it then I shouldn't reinvent the wheel.

[imor]

Hi

In the current form Pathfinding.js doesn't find all the possible paths from a starting point. It takes a start and an end point and finds a single path between them.

If it suffices for your needs what you can do is iterate over all the possible end points and find which points are reachable by repeatedly calling into Pathfinding.js. This method will of course waste a lot of effort in repeating the same search when two paths overlap, but maybe it's all you need.

And yes, thanks for using Pathfinding.js :+1:

[rohan-deshpande]

Hmm I guess that's the problem though, I don't have the end points. I guess I could find out every single possible path in the level then only include those which have a length <= my range, but that seems like it's going to be terribly inefficient and possibly slow.

I'll give it a go though and see what the performance is like, maybe it will be faster than I thought. Thanks!

[imor]

Hi @creativelifeform

I am thinking of creating a showcase page for pathfinding. Would you mind giving me a link to your game which I can add to that page?

Regards, imor

[rohan-deshpande]

Hey Imor,

Well it's VERY far from a complete game right now, but the dev blog is http://projectgoldscript.com, not sure if it's good to feature incomplete stuff there but if you feel it's good, then go for it. I'm coding a new implementation of Pathfinding.js now, but you can see an old one here https://www.youtube.com/watch?v=ctNV7R9fr2k

[Yonaba]

Hi all, Sorry to jump into the topic. I'd like to provide some thoughts. I am maintaining a pathfinding library named Jumper, written in Lua, which was deeply inspired by Pathfinding.js.

I have been working recently on a little experiment with pathfinding. I was trying to find a way to move a unit from one target to another but with a specific limitation : the unit has a maximum stepping ability, thus can move inside a limited range. In a very learningful discussion we had on Love2d forums, we came to the conclusion that the best option here would be using Dijkstra-maps. Basically, it consists of running a Dijkstra search from a source node (the starting point for instance). When the search ends, it leaves the graph/grid annotated in a way we have all the shortests paths between the source node and every other nodes in the graph (just like a direction map). In that way, we can easily get (in almost no time) the shortest route from the starting point to any other destination.

I believe it can be an interesting solution for your problem. Basically, you will just have to run a Dijkstra search from the location of unit which is moving. Considering that unit can only move 3 cells ahead (for instance) you will loop through all surrounding cells in that range that unit and check if there is a valid path. The performance gain might be noticeable (in case that range is large enough) since every single check will not require to run a full pathfinding search, but just a very cheap lookup in the Dijkstra map.

The actual implementation of Dijkstra algorithm in Pathfinding.js cannot be used here, as it searches from a single node to another. You will need a slightly different implementation that processes the entire graph from a given source. See the pseudocode given here. I have a demo project in Lua that you can take a look at. See dijkstra-map. Hope this helps.

Regards, Roland.

[imor]

@creativelifeform You might find the following links useful: http://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007 http://leifnode.com/2013/12/flow-field-pathfinding/

[rohan-deshpande]

Hey thanks for that!

I'm currently solving my issue like this (via @okonomiyaki3000)

for(i = 0 ; i <= rangeXZ ; i++)
{
  for (j = 0; j <= i; j++)
  {
    coordinates.push(
        {row: row + (i - j) , col: col + j},
        {row: row + (i - j) , col: col - j},
        {row: row - (i - j) , col: col + j},
        {row: row - (i - j) , col: col - j}
    );
  }
}

This creates duplicates but I filter them out later, I also need to do some other checks on that array, as I'm checking against a bunch of other parameters later that are independent of this particular search.

After this has happened, I have an array of choices in terms of coordinates, when a unit makes a choice on where to go, I then pass that and the matrix to Pathfinding.js and get back their root. Works well, and it seems to be pretty much instantaneous at the moment. Not sure if my approach will cause issues later but I'll cross that bridge when I come to it.

[rohan-deshpande]

Guys, I have another question, what about allowing jumping? Is it possible? For example I want to go from position A to position C but position B is not walkable. The positions are in a straight line with no other way to get to C. If jumping was allowed, then movement from A to C would be a valid path, this would cause the player / unit to jump over B to reach C.

Is this possible?

Sorry if this question has been asked before.

[imor]

Sorry but its not currently possible in pathfinding. You can mark B as walkable and then in a post-processing step remove it.

Please don't hesitate to ask questions as it is a source of real world use cases and hence good for evolving pathfindg.

[rohan-deshpande]

Hmm that's a little bit of a problem...I'll have to figure something out then, thanks for the reply though!

For those interested, I've started a thread in /r/gamedev about this http://www.reddit.com/r/gamedev/comments/2n42lj/pattern_for_path_finding_which_includes_jumping/

Edit I'm actually going to leave this for now, as I might be overthinking things slightly. I'm going to be building a movement handler soon and then I will write a demo to really test how the path finding is working, with turns and random obstacles being put in the matrix, and random choices being selected by AI. At that point, if I feel the need to revisit this point I will, but I have a feeling it's going to be okay for now. I'll report back with the demo, probably this would be a good way to showcase the implementation of Pathfinding.js in my game @imor. I'll definitely do a video.

[imor]

Thats cool :+1: Just keep us posted

[rohan-deshpande]

Just another question, I can't seem to find any docs that outline how to weight nodes, but I can see that the visualiser has this for the A* algorithm, any info on how this works and how best to implement it?

[imor]

Like this:

var finder = new PF.AStarFinder({
    weight: weight
});

Sorry it's not there in the docs. I'll update to include it.