Improve approximate/fuzzy string matching in search

[GuyUnger]

Describe the project you are working on

NA

Describe the problem or limitation you are having in your project

It's hard to find files because Godot requires very exactly queries. In the file search the only improvement is that you can search in the middle of names Quick open allows for missing letters but it's not exactly helpful, for example here I misspell "camera" by one letter and the only result is completely unrelated:

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Two things that would improve this:

• Instead of including spaces as part of the search term, make them split the query into multiple terms.
• Allow room for typos, such as with the leuvhenstein distance

I think this would mainly be helpful for the file search and quick open. For filters for the tree, properties, and settings etc. it might not be helpful because items don't get sorted by relevance so could easily clutter the results with things that you didn't want to search for.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Examples of searches and what they should find:

"big enemy" -> "enemy_big_hit.wav" "plater" -> "player.tscn"

If this enhancement will not be used often, can it be worked around with a few lines of script?

NA

Is there a reason why this should be core and not an add-on in the asset library?

NA

[Calinou]

There have been many pull requests experimenting with fuzzy search in the Search Help dialog (for instance), but it often resulted in usability regressions in practice. It's hard to have an algorithm that always provides a straight usability upgrade, even in difficult situations (such as searches with very short strings).

Instead of including spaces as part of the search term, make them split the query into multiple terms.

This could work out well since file names rarely contain spaces, but there should preferably be a way to group them into a single search term using quotes. This will add some complexity to the implementation, so it may not be worth doing at first.

[samsface]

@Calinou Does Godot have any concept of flights/feature flags? So, we can try put this under a feature flag for those that really want it and if in practice it sucks, we can remove it?

[Calinou]

Does Godot have any concept of flights/feature flags?

No, other than creating new (pre-)release builds with a project/editor setting that can be disabled. (This was done in the past when features such as BVH culling or 2D batching were implemented.)

Also, this is the kind of feature that would need to be opt-out to get significant testing in real world projects, rather than opt-in.

[samsface]

Ok cool, I'll open a PR for this soon 🔜