Pathfinding is really slow - any ideas?

Questions
1

I’m working on a little game that has a tilemap like this.

map
map865×672 52.7 KB

I’m using Jumper to pathfind - from the bat to the knight. The map of walkable tiles I’m using looks like this:

111111111111111111
100001000000000001
100001001000010001
111011001111110001
100000000000000001
100000000000000000
100000000000000001
111111111111111111

Now I’m running something like this:

	-- Value for walkable tiles
	local walkable = 0

	-- Creates a grid object
	local grid = Grid(map)
	-- Creates a pathfinder object
	self.finder = Pathfinder(grid, 'JPS', walkable)

	local start = {11, 5}
	local target = {12, 10}

	local before = socket.gettime()
	local path, length = self.finder:getPath(start[1], start[2], target[1], target[2])
	local after = socket.gettime()
	print((after - before)*1000)

Running getPath() takes 60 milliseconds, which is about an order of magnitude slower than I would like.
Does anyone have a working example of path finding a simple tilemap like this without a noticable hiccup?

2 Likes
2

Try this https://github.com/JCash/defoldexamples/tree/master/main/astar

I don’t know how long exactly it takes only that it’s an existing path finding example for Defold. If you drag the blue and red dots around on the example page it seems fast enough https://jcash.github.io/demos/defold/astar/DefoldExamples/index.html

2 Likes
3

I used Jumper for Hammerwatch Coliseum and didn’t have any perf problems until we had over 100 enemies and had to do some trickeries to allow that, so not sure why yours doesn’t work.

Maybe you can try to find what the bottleneck is in more detail?

2 Likes
4

I would personally go with a simple A*, its not that hard, especially with a simple tilemap like that. Still don’t know what Jumper offers.

/A

1 Like
5

I have never used Jumper before; but is it possible to run the Grid function beforehand, like during init of the scene to save time?
Jumper may be capable of doing what you need if you get it loading everything it can before the pathfinding function is called.
If you can’t get it worked out then I would use A*, and if you have thousands of nodes then A* with a heap as suggested in the GitHub link Pkeod posted.

1 Like
6

I am runnign the grid setup only once - in init. And I’m benchmarking just the pathfinding function. But I’ll have a look at the link Pkeod posted.

7

Well, Jumper has a few interesting pathfinding algorithms, and it might be faster on more complex tilemaps. I just ran my same example using the simpler astar implementation that Pkeod linked. Jumper took 46.8 ms to find a path - while the simple implementation took 4.9 ms.
So that’s a win.

2 Likes
8

Also check out Moku, a pathfinding/auto-tiling library, by @dakasha.

1 Like
9

I did try it out using the same example tilemap - it was also unreasonably slow. Which surprised me, since pathfinding such a simple tilemap should be really straight forward with anything other then a naive pathfinding algorithm. Which made me curious, and I tried out Jumper.

Maybe I’m not doing it right - I’ll allow for that. But it’s hard for me to properly profile why it’s being slow, with the current profiler - unless I can add my own profiling scopes. Right now, I’m not able to dig especially deeper into the profiler to find the root cause of the issue.

1 Like
10

You should probably be testing much more complicated, larger maps too. The other options may be more optimized for those situations. Though if you are planning to only use small simple maps then the A* method is fine if it’s fast enough.

Although anything which make a frame to take longer than 16ms is a no go.

11

I agree that pathfinding should be fast, but there’s always the option of dividing the work over multiple frames. A coroutine is very well suited for this.

4 Likes
12

There are C++ pathfinding libraries, they can be easily converted into a native extension for Defold. That will give you a good boost in performance.

2 Likes
13

I took a peek at our source code to see if I did something that might help you get Jumper working - if you still want that, and I did find a few things where some of them might be helpful regardless of using Jumper or not.

  • I call the pathfinding from a coroutine and spread it out over several frames if needed. This required some small changes in the Jumper code and also a lot of tweaking around what “if needed” really means. I was pretty strict and only allowed the pathfinder to iterate around 10 times (so 10 changes of the frontier in JPS) in each frame since it was ok for me that it took several frames for enemies to find their path.
  • Enemies do not pathfind immediately, they send a request that is queued and that queue is executed sequentially and the pathfinding result is sent as a message to the pathfinding enemy. Combined with above this means an enemy can wait quite long for a pathfinding result - but that was ok for us. How often the path is “renewed” (that is how often the enemy will do another pathfind) depends on how close the enemy is to the player.
  • Since we have a lot of enemies moving in groups in a static, rather small grid I cache the pathfinding result of each start/end pair so the next time someone wants to pathfind the same path they get the cached result. This gave a huge performance boost for us, but does of course have a memory trade off.

Hope it helps!

6 Likes