search

godotengine / godot

Godot Engine – Multi-platform 2D and 3D game engine
https://godotengine.org
MIT License
88.68k stars 20.11k forks source link

AStarGrid2D with jumping_enabled is significantly slower than with it disabled. #91367

Closed dani-swordfish closed 1 day ago

dani-swordfish commented 4 months ago

Tested versions

Tested in 4.2.2 stable

System information

Windows 10, Godot 4.2.2 stable

Issue description

The Docs description for enabling jumping AStarGrid2D on states that is intended to speed up the algorithm, but testing showed it slowing down the calculations by a significant amount, around 4-7 times slower. https://docs.godotengine.org/en/stable/classes/class_astargrid2d.html#class-astargrid2d-property-jumping-enabled

No jumping large distance with many obstacles- average 21.42 large distance with few obstacles- average 8.35 small distance - average 0.32

Jumping large distance with many obstacles-average 149.41 large distance with few obstacles- average 33.76 small distance - average 1.52

Steps to reproduce

Open the Minimal reproduction project Use the @export variables to change the path distance and toggle jumping. Use the run speed test button to print the speed of the function to the consol.

Minimal reproduction project (MRP)

AStarGridPerformance.zip

Chaosus commented 4 months ago

~I suspect that algorithm should be faster on open-space with low amount of obstacles rather than high.~ Nvm, it's really slower, strange... The other assumption that it currently uses a recursion, and this might be slower than without (but significantly easier to develop).

10Drenth commented 2 months ago

I am encountering the same issue, if no one is working on this right now, I would like to try working on a fix.

Chaosus commented 2 months ago

I would like to try working on a fix.

You are welcome, that code was a painful to create and maintain.

10Drenth commented 2 months ago

The combination of branching and recursion definitely appears to play a large part in the lack of performance here. Some recursion can simply be rewritten to loops, but others need to perform multiple different jump checks themselves. I'll mostly be figuring out a way to reduce unnecessary branching in a way that is still somewhat maintainable :)