search

roy-t / AStar

A fast 2D path finding library based on the A* algorithm. Works with both grids and graphs. Supports any .NET variant that supports .NETStandard 2.0 or higher. This library has no external dependencies. The library is licensed under the MIT license.
http://roy-t.nl
MIT License
338 stars 60 forks source link

Noticed inconsistancy with path times (same path) #2

Closed SimonDarksideJ closed 7 years ago

SimonDarksideJ commented 7 years ago

Done some more random testing, then tried some repeated path testing and seeing some inconsistencies.

Attached a quick video to demonstrate.

Showing times for the same path, resolved repeatedly.

Times range from 0.11 to 2.0 for repeatedly checking the same path. Should possibly have some caching or checks. However, the spikes are a slight concern.

Not sure if it's an issue or not, or just scope for improvement.

Just an observation for now.

roy-t commented 7 years ago

Unfortunately I do not see the video attached so I cannot really see what happened. But I see the same

Note the times displayed in the window are in milliseconds (so 0.11 is really fast) and are just there to give you a sort-of indication. Its notoriously difficult to measure times correctly but the implementation is fully deterministic (no randomness) so every time you execute it the exact same instructions are performed.

I'd attribute the large differences you see to warm-up times and to Windows doing something else. Its all running in the UI thread so the priority is not very high. The viewer needs a lot of improvements :).

To get a better idea of the true speed of the algorithm try the benchmark project and add your own benchmark. It uses Benchmarks.net and performs all kinds of tricks to makes sure its not interrupted, the CPU is not throttled down, etc.. You can see the results of the benchmark that I ran on the bottom of the project page (https://github.com/roy-t/AStar)

Adding caching is a great idea. As long as you don't change any of the weights previously computed paths stay valid. I'm going to open a new ticket for that.

I'll keep this issue open to give you a chance to attach the video again and to see if you agree with my assessment. Again, your feedback is greatly appreciated!