search

ShortestPathLab / posthoc-app

Posthoc is a way to build simple and effective visualisations ✨ for sequential decision-making algorithms, such as search.
http://posthoc-app.pathfinding.ai/
25 stars 5 forks source link

Performance improvements #42

Closed dharabor closed 2 months ago

dharabor commented 6 months ago

Running the Grid A* example takes quite a long time to finish the search. I have a few thoughts about this.

(1) During playback we probably don't want to draw each individual event. We could simply draw the result of each expansion event. This would reduce the number of draw updates by quite a bit.

(2) Another way to jump ahead is to "expand in bulk"; i.e., show the result of expanding all nodes until the f-value increases. Then we could see the "f-layers", which is a pedagogical visualisation used to explain how search works to beginners (e.g., see FIT5222 Week 1 material on UCS). For practical reasons, these examples are usually small with details abstracted away. We could show them per instance!

(3) I notice the "Steps" panel scrolls during playback, suggesting we still write every event there but simply do not render it. I propose we only keep an internal pointer of which event we're up to and then jump directly to that point when the playback stops. This change may require changing how we process the search trace (e.g., we may need to stream it incrementally).

dharabor commented 6 months ago

Superset of #13

dharabor commented 5 months ago

The StarCraft example is very slow. It seems to load 4 traces and one map and then proceeds to display everything, which takes quite a long time. Another problem is that the bounding boxes for different areas of the map follow the cursor and are always drawn. It's slow and interferes with the ability to inspect the visualisation.

Proposals:

  1. Draw only the map
  2. Set the search trace pointer to the first event of the first layer.
  3. Hide other layers by default.
  4. Hide the bounding boxes and avoid unnecessary compute behind the scenes.
spaaaacccee commented 2 months ago

In 79b81b740c3c655db8848e060e5d2e5d0b86a50f, we have several ways to jump ahead in the search, including setting up and stepping to breakpoints, increasing the playback speed, and navigating through steps in the search graph view. Through a compensation mechanism, the playback speed should be constant regardless of lag.

In 7f5d76ba75fb428e25ca5d488c006d082bdc7d05, we updated the default starcraft example to have 1 map and two traces (heat query and trace paths) for faster loading.