Created
February 19, 2023 20:47
-
-
Save Desour/e351fb7063ef10ed50549f6e1262d8b7 to your computer and use it in GitHub Desktop.
How I plan to improve minetest crafting performance
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| general remarks: | |
| * a shape is a bitmap where bit i is 0 iff slot i is "" | |
| * all recipes get a number at registration, this number is an index into an array. | |
| higher number was registered later => can be used for priority | |
| * caching should also be added later | |
| (1) PRIORITY_SHAPED | |
| * get bounds, and normalize into upper-left corner | |
| * concat all slot item names (including ""), and separate (i.e. by `\n`) | |
| * lookup recipe in a multimap | |
| (2) PRIORITY_SHAPED_AND_GROUPS | |
| alternative A: | |
| * get bounds and normalize | |
| * for each itemname: get sorted vector for shaped-with-groups recipes (as indices) that | |
| include that item (directly or as group or group-combi) and are of the same shape as the input | |
| * compute intersection (with sorted-merge) | |
| * check each recipe | |
| alternative B (meh, too complicated): | |
| * get bounds and normalize | |
| * get recipe-prefix-tree (aka fixed-length-lang NFA) for bounds (or shape?) (and first item-name?) | |
| * go through recipe-prefix-tree (at each stage: hash-lookup for itemname and all its groups) | |
| (3) PRIORITY_SHAPELESS | |
| * sort itemname-list | |
| * concat | |
| * lookup recipe in a multimap | |
| (4) PRIORITY_SHAPELESS_AND_GROUPS | |
| * for each itemname: get sorted vector for shapeless-with-groups recipes that include that item and | |
| have the same number of items as the input | |
| * compute intersection (with sorted-merge) | |
| * for each recipe: | |
| * merge input with recipe to filter out non-group items | |
| * remaining item and group list form a bipartite graph. find a matching (i.e. with hopcroft-karp) | |
| (5) PRIORITY_TOOLREPAIR | |
| * if exactly 2 items, check |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment