[SUG] Search Bar for Level Select menu

[WillLem]

Had a go at implementing a search bar in the Level Select menu today:





It looks neat enough and works as expected, but is a little bit slow the first time a search is performed after opening the Level Select menu (about 20-30 seconds). For subsequent searches in the same session, it's much quicker (about 1-5 seconds).

This is because it's necessary to load every node label into memory before the search can be performed. I've managed to bypass some of the loading procedure (e.g. talisman icons, level preview, etc) to speed it up a bit, but it would still be nice to get it performing a bit faster.

I'm wondering whether the treeview can be stored into system memory somehow, or loaded and stored into a file which can then be called up to populate the tree so that browsing and searches could be made much quicker. It'd likely only take up a few mb, and would make the Level Select menu much snappier. That's very much a task for another day though.

For now, this is a neat enough feature that it'll be in the next SLX update (2.7.3). Implemented in Commit 61d6b68.

[Simon]

Split your post about the search into a fresh thread. This will be interesting.

You make it sound as if NL already offers level caching (node labels). What exactly does NL cache? When does NL update the cache? When NL knows that you've solved all levels in a directory, how does it remember that?

I'm envisioning a full database cache with the level's searchable fields (title, author, pack, directory, ...), personal records, and raw filenames. This will be useful in normal browsing and in the level search.

Related: Lix github #330: Cache file-search results

-- Simon

[namida]

You make it sound as if NL already offers level caching (node labels). What exactly does NL cache? When does NL update the cache? When NL knows that you've solved all levels in a directory, how does it remember that?

From memory:

When starting up NL, it loads the structure of all packs. To do this it recursively iterates through the "levels" directory and any subdirectories thereof. If a subdirectory contains a "levels.nxmi" file, then only levels and sub-subfolders specified within it are loaded. If it does not, all subdirectories and NXLV files are loaded. Note again that it is only loading the structure at this point - in other words, it will have the map of "the levels folder contains Orig, which contains 4 sub folders, the names of them as ranks are Fun, Tricky, Taxing, Mayhem, which contain 30 levels each, these are the order and filenames of the levels" but not anything about the contents of those level files - just their order and filenames. (I believe that sorting by level title occurs later, in the case that no levels.nxmi file is present to handle this; however it might also just be that they're sorted by filename, or possibly also that in this specific situation, it does load data from the level files.)

Progress data and records (from settings/userdata.nxmi) is then loaded against the entries in this tree, based on file path. There's no specific pack data; "pack completed" is determined solely on the basis of "every level in the pack is completed". This data is saved frequently while NL is running - generally, any time you transition between two "screens", it gets saved.

The full data (title, skillset, etc) for the level is only loaded when (for NXLV files directly in the "levels" dir) the Level Select menu is opened, or (for NXLV files in subfolders) when the subfolder's node in the tree is expanded - which may either be because the user clicks on it, or because the level already selected when NL starts happens to be inside the subfolder (or a parent thereof) in question. Once it is loaded, it's cached in memory (I believe this gets invalidated if NL specifically detects that the file has been modified, but I could be wrong).

It's done this way because actually getting the full stats etc for the Level Select menu is somewhat intensive. NL basically does everything it would normally do to load and display a level, when loading a level for this - this is pretty much necessary to get a preview image and accurate stats (eg. it needs to account for things like "if the level data specifies 20 lemmings, but the level contains no entrances and only 5 preplaced lemmings, the actual lemming count is 5"). But it's also easier to load all this data in one go than to load the level multiple times to get different bits of data.

I do recall at some point, NL had a shortcut where it would bypass the normal level loading code and specifically just look for the TITLE line in a level file. It may be the case that NL still does this for generating (and ordering, where no levels.nxmi file exists) the title data in the cache.

This cache is not saved to disk at any point. When NL exits, it's gone, and must be generated again next time NL runs.

Again, this is from memory, and may not be 100% accurate. It should at least be very close, though.

[WillLem]

Split your post about the search into a fresh thread. This will be interesting.

Done.

You make it sound as if NL already offers level caching (node labels). What exactly does NL cache? When does NL update the cache? When NL knows that you've solved all levels in a directory, how does it remember that?

What namida said. There are nuances, but he pretty much covered it spot on.

I'm envisioning a full database cache with the level's searchable fields (title, author, pack, directory, ...), personal records, and raw filenames. This will be useful in normal browsing and in the level search.

AFAIK: The only way to achieve this currently would be to get a database snapshot of the entire tree. And, the only way to do that is to expand every node so that NL/SLX can do its thing and create that snapshot. And, as namida said, the snapshot then isn't remembered between sessions.

To be fair, it makes makes sense that it isn't remembered because files can be changed between sessions without the program being open; it's necessary, then, for NL/SLX to rebuild the snapshot each time so that everything is up-to-date.

Could we take a snapshot and then only update what needs to be updated in the snapshot? Probably, but a full scan of the tree would still be necessary, and the most useful (and least intensive) time to do it is when the Level Select menu is open, the tree is being browsed, and nodes are being expanded. A short delay after clicking a node vs. a long delay when opening the Level Select menu is preferable, especially since the user (and indeed the program itself) is unlikely to need access to every bit of available tree data in that one browsing session.

So, astonishingly, the codebase is actually quite well optimised for loading, displaying, browsing and saving level data. A while ago I spent about two weeks just looking for ways to optimise it further, and - to my credit - I did manage to achieve some small gains, but mostly I just came to the realization that things had already been pushed as far as possible, and that in spite of the obvious flaws, there are in fact very good reasons for the way that things are done.

That's not to say it's not worth pursuing further - of course it is! I just think that I'm better off working with what's already there rather than implementing something new that doesn't play nicely. For instance:

I do recall at some point, NL had a shortcut where it would bypass the normal level loading code and specifically just look for the TITLE line in a level file. It may be the case that NL still does this for generating (and ordering, where no levels.nxmi file exists) the title data in the cache.

If this is still happening, that's very useful. Depending on how quick this is to do, this could definitely be harnessed for search purposes. And, if it is a quick process, the cache could be updated on closing the program.

However, the results would still need mapping to tree nodes somehow. All it takes is for a user to add a single level, and the database needs to be updated. And, as we've established, the only way to do that currently is to open the tree and expand the relevant nodes. Even if we implement some clever node-to-level mapping which is also cached, updating that would require the same thing; expanding the tree in order to match nodes to levels, thus negating any potential gains.

The point being: anything that's implemented for search purposes needs to entirely play nicely with the existing flow; adding something that doesn't already have procedures in place to support it is particularly problematic here. For other parts of the program, sure, I'm as happy to hack stuff in as the next hobbyist programmer, but for the Level Select menu it's a different ballgame.


So... the best idea I can come up with regarding all this is to reverse-engineer the structural routing that namida mentioned, when performing a search. Something like this:

1) User searches for "Mary"
2) The program performs a FIF through all .nxlv files to find matches for "TITLE *Mary*"
3) For each .nxlv file found, we then need to see if it's in a directory with a "levels.nxmi" file
4) We then need to know its parent directory, and whether that has a "levels.nxmi" file
5) Repeat step 4 until we're at the pack's base directory - we'll know that if there's an "info.nxmi" file, or if it's the last subdirectory before we hit "\levels\"
6) During steps 3-5, we've gathered the group title (if there is one, e.g. "Taxing") and the pack title (if there is one, e.g. "Lemmings") and stored it alongside each search result for "Mary"
7) User chooses "Mary Poppins' land" from the list of search results
8) For that search result, we know it's parent pack and subgroup, so we can find those in the tree and expand the relevant nodes until we find the relevant level

In theory, the above would work, and it would be fast (<3 seconds even for a large number of levels). We'd need to account for levels that aren't in subgroups, or that don't have associated "levels.nxmi" or "info.nxmi" files; for those, we'd look at the name of the folder. And, this is already what happens in NL/SLX for tree sorting purposes anyway; good, because part of the goal is to harness existing logic.

At present, I don't have any better ideas that that. Suggestions welcome.

[WillLem]

With all that said, I just tested the release build with the current Search function (which programmatically expands all tree nodes and searches the node data for results), and it took about 7 seconds to find all results for "Mary" in a very large (1000+) selection of levels. So, it's not that bad!

When I wrote the OP I was basing the findings on the Debug build run from within the Delphi IDE, which is typically a lot slower (particularly when performing searches for files, loading stuff, etc).