[BEHAVIOR] EasyStar.js pathfinding for tilemap

Post your completed addons to share with the community

Post » Wed Jun 07, 2017 1:39 am

Glad to hear!

I had to find a way to differentiate pathfinding calls from one another. The "tag" system seemed like the best choice and was actually quite straightforward to implement using EasyStarJS.
B
74
S
31
G
26
Posts: 994
Reputation: 20,198

Post » Thu Jun 08, 2017 11:27 am

Hello, I find this behavior very useful for my project but I see something happening:

Image

Is this solved or do you intend to solve it?
That is, should not you choose the shortest route without making those changes on the route?
B
30
S
13
G
21
Posts: 838
Reputation: 14,656

Post » Thu Jun 08, 2017 2:46 pm

It's unfortunately out of my control. The pathfinding algorithm comes from an external library. This plugin simply expose its API so you can use it in Construct. However, the version of the library that the plugin uses is quite outdated. Maybe this particular problem was fixed in a more recent version, but I can't be sure unless I try a newer version.
B
74
S
31
G
26
Posts: 994
Reputation: 20,198

Post » Thu Jun 08, 2017 3:20 pm

Magistross wrote:It's unfortunately out of my control. The pathfinding algorithm comes from an external library. This plugin simply expose its API so you can use it in Construct. However, the version of the library that the plugin uses is quite outdated. Maybe this particular problem was fixed in a more recent version, but I can't be sure unless I try a newer version.


Wow! I'm really impressed by the speed of the algorithm!

I would love to use this in my game, rather than writing my own. Any chance that it would be an easy update to get the newer version running in the plugin?
www.simbucket.com - HTML5 Science Simulations / https://www.airconsole.com/#!play=com.n ... obotrumble - Robot Rumble on AirConsole
B
50
S
15
G
25
Posts: 424
Reputation: 17,296

Post » Thu Jun 08, 2017 6:22 pm

Updated the plugin using the 0.4.1 version of EasyStarJS. Since I practically did this on my lunch break at work, absolutely NO testing whatsoever was done so please try it and report your success here. :)

https://magistross.github.io/files/easy ... p_1_02.zip
B
74
S
31
G
26
Posts: 994
Reputation: 20,198

Post » Thu Jun 08, 2017 9:44 pm

Magistross wrote:Updated the plugin using the 0.4.1 version of EasyStarJS. Since I practically did this on my lunch break at work, absolutely NO testing whatsoever was done so please try it and report your success here. :)

https://magistross.github.io/files/easy ... p_1_02.zip


Sweet!

Thanks for putting this together so quickly. I will test it out as soon as I can next week. I have to get through another project tomorrow.
www.simbucket.com - HTML5 Science Simulations / https://www.airconsole.com/#!play=com.n ... obotrumble - Robot Rumble on AirConsole
B
50
S
15
G
25
Posts: 424
Reputation: 17,296

Post » Thu Jun 08, 2017 9:45 pm

@Magistross

Ty so much for updating.
B
33
S
18
G
28
Posts: 2,493
Reputation: 20,950

Post » Fri Jun 09, 2017 2:22 pm

cjbruce wrote:
Magistross wrote:Updated the plugin using the 0.4.1 version of EasyStarJS. Since I practically did this on my lunch break at work, absolutely NO testing whatsoever was done so please try it and report your success here. :)

https://magistross.github.io/files/easy ... p_1_02.zip


Sweet!

Thanks for putting this together so quickly. I will test it out as soon as I can next week. I have to get through another project tomorrow.


Based on a minor tweak to the example .capx (I had to put the "destroy" under the "On path 'test' found", rather than every tick) and 10 minutes of testing, it appears to work great!

Attempt at optimization for garbage collection:
Although the example was only using about 125 objects and 6% CPU time on my Surface Pro 4, I thought I would try to optimize garbage collection by not destroying and creating new nodes every time a path was found. Instead, I created a grid of nodes on start of layout and set them all as invisible. When a path is found, I set only the path nodes to visible.

Result:
With this "optimization", CPU usage was insignificant, but frame rate dropped to an unplayable 25 fps, with a noticeable pause in pathfinding. I assume this frame rate drop is happening because of a GPU bottleneck, but I had no idea that it would be so dramatic.

Conclusion:
-Having a node object for every grid tile is more computationally expensive than just creating and destroying nodes as needed for a 28 x 16 grid.
-Better yet, don't put any node objects on screen at all. Instead of actual objects, compute direction based on the nearest tilemap square.

Further work:
I need to play around with things now to figure out how to get AIs to follow the path. I will be working in 3D with physics, so path following will be a bit more complicated, but EasyStar.js seems to be rock solid. Thank you! Thank you for putting this together -- you saved me a ton of time!
www.simbucket.com - HTML5 Science Simulations / https://www.airconsole.com/#!play=com.n ... obotrumble - Robot Rumble on AirConsole
B
50
S
15
G
25
Posts: 424
Reputation: 17,296

Post » Fri Jun 09, 2017 3:27 pm

The second example capx is probably a better starting point to understanding how to use the behavior.

The first example is more like a proof of concept, it's definitely not something you should do in a game you plan to release for mobile/tablet. Creating and destroying objects every tick, all the while doing strenuous pathfinding calculations, is absolutely not optimal.
B
74
S
31
G
26
Posts: 994
Reputation: 20,198

Post » Fri Jun 09, 2017 4:09 pm

Magistross wrote:The second example capx is probably a better starting point to understanding how to use the behavior.

The first example is more like a proof of concept, it's definitely not something you should do in a game you plan to release for mobile/tablet. Creating and destroying objects every tick, all the while doing strenuous pathfinding calculations, is absolutely not optimal.


Agreed. I'm already working with Q3D for rendering and 3D physics, so both CPU and GPU optimization are super-important. I don't really care that enemies follow the shortest path, just as long as they follow *any* path that gets them where they need to go. EasyStar.js does a great job with this optimization.

I will try to get a version working with this with 3D physics next week.
www.simbucket.com - HTML5 Science Simulations / https://www.airconsole.com/#!play=com.n ... obotrumble - Robot Rumble on AirConsole
B
50
S
15
G
25
Posts: 424
Reputation: 17,296

PreviousNext

Return to Completed Addons

Who is online

Users browsing this forum: No registered users and 8 guests