Grid::clone() is slow

[MaksJS]

I've made my own benchmarks and it appears that the algorithm is fast but clone method is really slow

Would it be possible to search for a path without cloning the grid ?

[yi]

I had used Pathfinding.js on a server side real-time game app, and found the same issue. So I've rewritten most the the code and use a bit buffer to replace the Array map container which significantly improve the performance. fyi: https://github.com/yi/node-path-finding

[qiao]

@MaksJS The only scenario in which the clone method is useful is when you have to apply the pathfinding onto the same map layout(same walkable/un-walkable configuration). This kind of scenario is rare since in most games, the map is constantly changing, and you have to rebuild a new grid each time the map changes. And to rebuild the grid, it's better to create a fresh new Grid instance and assign the walkability of the nodes, instead of cloning from the old one and then modifying the clone.

[qiao]

@yi Nice bit hacking. It's a pity that Buffer is nodejs exclusive. I plan to have some experiments on using the ArrayBuffer, and fall back to the vanilla Array on unsupported platforms.

[MaksJS]

@yi Wow, we're exactly in the same case, i'm also developing a real-time game :+1: I'll try your module, thanks for sharing this !!

@qiao Ok, thanks for the details, i'll try to benchmark with a new instance instead of a clone. About performance, have you tried to use typed arrays ? They are available in Chrome, Firefox, Safari, Opera and IE 10

[MaksJS]

If it can helps you, here's my benchmark :

# PathFinding.js
for algorithm in ['BestFirstFinder', 'AStarFinder', 'JumpPointFinder', 'BreadthFirstFinder', 'DijkstraFinder', 'BiAStarFinder', 'BiBestFirstFinder', 'BiDijkstraFinder', 'BiBreadthFirstFinder']
  pathfinder = new PF[algorithm]
  console.time('benchmark-pathfinding.js-' + algorithm)
  pathfinder.findPath(5, 0, 16, 4, room.map.grid.clone()) for [0...1000]
  console.timeEnd('benchmark-pathfinding.js-' + algorithm)
# grid.clone() test
console.time('grid.clone method')
room.map.grid.clone() for [0...1000]
console.timeEnd('grid.clone method')

The result :

benchmark-pathfinding.js-BestFirstFinder: 220ms
benchmark-pathfinding.js-AStarFinder: 180ms
benchmark-pathfinding.js-JumpPointFinder: 190ms
benchmark-pathfinding.js-BreadthFirstFinder: 210ms
benchmark-pathfinding.js-DijkstraFinder: 220ms
benchmark-pathfinding.js-BiAStarFinder: 190ms
benchmark-pathfinding.js-BiBestFirstFinder: 190ms
benchmark-pathfinding.js-BiDijkstraFinder: 210ms
benchmark-pathfinding.js-BiBreadthFirstFinder: 210ms
grid.clone method: 150ms

Node.js profiling log :

   2530    3.1%  LazyCompile: *Grid.clone c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Grid.js:194
   2516   99.4%    LazyCompile: *namespace.Socket.Server.Game.pathfinding c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\socket\server\Game.coffee:392
   2516  100.0%      LazyCompile: namespace.Character.AI._reachAPlayer c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\character\AI.coffee:144
   2516  100.0%        Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\db\schema\horde.coffee:1
   2516  100.0%          Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:264
   1991   79.1%            LazyCompile: ~render c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:249
    525   20.9%            LazyCompile: render c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:249

   2122    2.6%  LazyCompile: *Node c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Node.js:10
   1152   54.3%    LazyCompile: *Grid._buildNodes c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Grid.js:38
   1152  100.0%      LazyCompile: *Grid.clone c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Grid.js:194
   1141   99.0%        LazyCompile: *namespace.Socket.Server.Game.pathfinding c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\socket\server\Game.coffee:392
   1141  100.0%          LazyCompile: namespace.Character.AI._reachAPlayer c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\character\AI.coffee:144
   1141  100.0%            Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\db\schema\horde.coffee:1
    970   45.7%    LazyCompile: *Grid.clone c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Grid.js:194
    958   98.8%      LazyCompile: *namespace.Socket.Server.Game.pathfinding c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\socket\server\Game.coffee:392
    958  100.0%        LazyCompile: namespace.Character.AI._reachAPlayer c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\character\AI.coffee:144
    958  100.0%          Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\db\schema\horde.coffee:1
    958  100.0%            Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:264

   2091    2.6%  Builtin: A builtin from the snapshot {4}
   1080   51.6%    LazyCompile: *Grid.clone c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Grid.js:194
   1074   99.4%      LazyCompile: *namespace.Socket.Server.Game.pathfinding c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\socket\server\Game.coffee:392
   1074  100.0%        LazyCompile: namespace.Character.AI._reachAPlayer c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\character\AI.coffee:144
   1074  100.0%          Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\db\schema\horde.coffee:1
   1074  100.0%            Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:264
    919   44.0%    LazyCompile: *Grid._buildNodes c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Grid.js:38
    919  100.0%      LazyCompile: *Grid.clone c:\Users\Maxence\Dropbox\fantasy-universe\beta\node_modules\pathfinding\src\core\Grid.js:194
    913   99.3%        LazyCompile: *namespace.Socket.Server.Game.pathfinding c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\socket\server\Game.coffee:392
    913  100.0%          LazyCompile: namespace.Character.AI._reachAPlayer c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\character\AI.coffee:144
    913  100.0%            Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\db\schema\horde.coffee:1
     66    3.2%    LazyCompile: *namespace.Socket.Server.Game.pathfinding c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\socket\server\Game.coffee:392
     66  100.0%      LazyCompile: namespace.Character.AI._reachAPlayer c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\character\AI.coffee:144
     66  100.0%        Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\db\schema\horde.coffee:1
     66  100.0%          Function: ~<anonymous> c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:264
     50   75.8%            LazyCompile: ~render c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:249
     16   24.2%            LazyCompile: render c:\Users\Maxence\Dropbox\fantasy-universe\beta\app\assets\javascripts\network\Server.coffee:249

As you can see, grid.clone() method is a bottleneck in my AI (a timer => AI => _reachAPlayer => Socket.Server.Game.pathfinding => Grid.clone => Grid._buildNodes)

[qiao]

@MaksJS I have done some experiments and confirmed that the bottleneck is instantiating a large number of Node and storing them in a two-dimensional matrix. By using a compact representation of the nodes, such as encoding them into a 32 bit integer like @yi did, will dramatically improve the performance. Also, storing them in a one-dimensional typed array instead of a two-dimensional matrix will also improve the index speed.

But these modifications will introduce greater complexity, need fair amounts of work and will break the visualization(The visualization is implemented by intercepting the setters and getters of the nodes' properties). I'll think about the trade-off for some time.

[artch]

It is indeed very important subject for me also. Many cases assume that we need to solve several routes on the same map, for example, when trying to determine the nearest object across several given ones. And thus, each time we need to clone the grid, this greatly reduces overall performance.