Need to reinstantiate Grid when making multiple searches

[MattTarquin]

I am using PF on a basic game server running on node.

Path finding returns empty results when making a second call to finder.findPath() when passing in the same grid instance.

Currently I have a function that initialises the map, this contains:

this.PF = new pathFinder.AStarFinder({allowDiagonal: true});
this.PFGrid = new pathFinder.Grid(map.structure);

Then I have a move player function which contains the following:

this.PF.findPath(player.location.x, player.location.z, x, z, this.PFGrid);

This works the first time it is run, however subsequent calls simply return an empty array (as if a path couldnt be found). This is even true when testing using the following:

this.PF.findPath(0, 0, 2, 2, this.PFGrid);  //works and returns path
this.PF.findPath(0, 0, 2, 2, this.PFGrid); // returns empty path

This is fixed by reinstantiating the grid before each call, using the same finder seems to be fine. This is a socket IO/Node/Multiplayer game and I need to save processing power wherever possible. Would it be possible to tell me if this is the desired functionality and if it is not that you can recreate this issue?

[imor]

It is expected that you reinstantiate the grid object each time because the grid object becomes dirty after a call to findPath.

[TravisGesslein]

WTF? What could ever be the reason for that? Why should you recreate all the nodes, set every obstacle to not-walkable, etc, when the grid will mostly stay the same? That's the most memory and performance wasting thing I've ever seen. Wow, this library actually looked really nice but this is an absolute deal breaker.

I'm actually completely befuddled how you could ever think it would be a good idea to design it like that. If you have just a 10x10 sized grid the memory will be bombarded with 100 times whatever amount of memory it takes to instantiate a node and some other overhead, and go through the processing required to set that up. This is really silly when you need to search dozens or hundreds of paths on the same grid. Not to mention when you use more realistic grid sizes ( I have several maps with like ~100x30 in my game for example).

I mean this could be OK if the library was just for examining and testing different algorithms, but the description on the entry page says that it's designed to be easily integratable into web games. Well nice, have fun with the garbage collection when using this library in this state.

[rohan-deshpande]

Have you got any benchmarks to test the performance impact behind your claims?

If you do, please share them. If not, please GTFO and write your own library which performs better before hating on the hard, open source, work of others.

[TravisGesslein]

@rohan-deshpande Listen man, you can search my entire internet posting history and you will find out that I have never ever insulted the work of someone else. I am telling you this to demonstrate to you the level of bewilderment I was in when I found out was going on.

This is just bad on a technical level all around, and if you're asking me for a benchmark to show you why bombarding the garbage collector with potentially hundreds of kilobytes of data (and if you've looked at the implementation of the library, the resulting code of looping over each grid element and initializing a node) every time you make a single QUERY in a small grid, well, I'll have to disappoint because I'm absolutely not in the mood for proving the trivial. This is not an exaggeration by the way, eye-balling the code it looks to me like the nodes start out with AT LEAST 20-24 byte of data but are blown up way beyond that if they are touched by the algorithm, with the resulting size probably depending on the pathfinder used. This means you would have a just short of 100 KB grid by just having a 64x64 grid which is pretty tiny for many game applications (including mine, where lots of them go way beyond that).

For the record, I'm posting this out of great disappointment in an otherwise great library, and to reiterate, out of a state of utter confusion (my mind is still blown), not because I want to insult anyone. Needless to say despite this flaw the library is awesome for just existing, but you're not going to find it in a game of anyone aware of this flaw.

[rohan-deshpande]

What you're saying may indeed be valid, but you can definitely say it without coming off like an ass, and even better still, contributing to the repo by forking a fix for these issues and making a PR.

FWIW I'm using Pathfinding.js in a portion of my engine that is built on top of Three JS. I've not noticed any performance issues coming from Pathfinding at all.

[Yonaba]

Hi all,

I would like to provide some input, and a small suggestion. I am maintaining a pathfinding library written in Lua, named Jumper, which were inspired by Pathfinding.js.

What I am doing is, internally, during a search, I keep track of all nodes which have been examined and modified in an array list. Then, right before starting a new search, the pathfinder class will go through this clear and clear only these nodes (see here).

In that way, I do not need to re-instantiate the entire grid, but just the nodes which have been modified during the previous search. Of course, there is a trade-off : keeping track of those previously modified nodes requires some extra-space. But well, it works really fine.

[imor]

@Heishe Your disappointment is understandable. But please do understand that all the contributors to any open source project give away their work for free. So if something isn't working it is possibly just because nobody found the time or willingness to do it, or did not find it to be a problem in the first place. If you have the technical chops to fix this situation, I'd encourage you to go ahead and do it. That was how I became a maintainer of this project - by contributing something that the original author thought was useful. Who knows, you could be the next maintainer :)

PS - Please refer to the issues #33 and #99 for more background on this issue.