Rework the preset menu system to permit submenus.

To do this, I've completely replaced the API between mid-end and front
end, so any downstream front end maintainers will have to do some
rewriting of their own (sorry). I've done the necessary work in all
five of the front ends I keep in-tree here - Windows, GTK, OS X,
Javascript/Emscripten, and Java/NestedVM - and I've done it in various
different styles (as each front end found most convenient), so that
should provide a variety of sample code to show downstreams how, if
they should need it.

I've left in the old puzzle back-end API function to return a flat
list of presets, so for the moment, all the puzzle backends are
unchanged apart from an extra null pointer appearing in their
top-level game structure. In a future commit I'll actually use the new
feature in a puzzle; perhaps in the further future it might make sense
to migrate all the puzzles to the new API and stop providing back ends
with two alternative ways of doing things, but this seemed like enough
upheaval for one day.

56 files changed, 814 insertions, 346 deletions

diff --git a/PuzzleApplet.java b/PuzzleApplet.java
index 0b0648c..512aede 100644
--- a/PuzzleApplet.java
+++ b/PuzzleApplet.java
@@ -28,6 +28,9 @@ public class PuzzleApplet extends JApplet implements Runtime.CallJavaCB {
     private JFrame mainWindow;
 
     private JMenu typeMenu;
+    private JMenuItem[] typeMenuItems;
+    private int customMenuItemIndex;
+
     private JMenuItem solveCommand;
     private Color[] colors;
     private JLabel statusBar;
@@ -219,17 +222,17 @@ public class PuzzleApplet extends JApplet implements Runtime.CallJavaCB {
     }
 
     private JMenuItem addMenuItemCallback(JMenu jm, String name, final String callback, final int arg) {
-        return addMenuItemCallback(jm, name, callback, new int[] {arg});
+        return addMenuItemCallback(jm, name, callback, new int[] {arg}, false);
     }
 
     private JMenuItem addMenuItemCallback(JMenu jm, String name, final String callback) {
-        return addMenuItemCallback(jm, name, callback, new int[0]);
+        return addMenuItemCallback(jm, name, callback, new int[0], false);
     }
 
-    private JMenuItem addMenuItemCallback(JMenu jm, String name, final String callback, final int[] args) {
+    private JMenuItem addMenuItemCallback(JMenu jm, String name, final String callback, final int[] args, boolean checkbox) {
         JMenuItem jmi;
-        if (jm == typeMenu)
-            typeMenu.add(jmi = new JCheckBoxMenuItem(name));
+        if (checkbox)
+            jm.add(jmi = new JCheckBoxMenuItem(name));
         else
         jm.add(jmi = new JMenuItem(name));
         jmi.addActionListener(new ActionListener() {
@@ -261,12 +264,29 @@ public class PuzzleApplet extends JApplet implements Runtime.CallJavaCB {
         } else {
             typeMenu.setVisible(true);
         }
-        addMenuItemCallback(typeMenu, "Custom...", "jcallback_config_event", CFG_SETTINGS);
+        typeMenuItems[customMenuItemIndex] =
+            addMenuItemCallback(typeMenu, "Custom...",
+                                "jcallback_config_event",
+                                new int[] {CFG_SETTINGS}, true);
     }
 
-    private void addTypeItem(String name, final int ptrGameParams) {
+    private void addTypeItem
+        (JMenu targetMenu, String name, int newId, final int ptrGameParams) {
+
         typeMenu.setVisible(true);
-        addMenuItemCallback(typeMenu, name, "jcallback_preset_event", ptrGameParams);
+        typeMenuItems[newId] =
+            addMenuItemCallback(targetMenu, name,
+                                "jcallback_preset_event",
+                                new int[] {ptrGameParams}, true);
+    }
+
+    private void addTypeSubmenu
+        (JMenu targetMenu, String name, int newId) {
+
+        JMenu newMenu = new JMenu(name);
+        newMenu.setVisible(true);
+        typeMenuItems[newId] = newMenu;
+        targetMenu.add(newMenu);
     }
 
     public int call(int cmd, int arg1, int arg2, int arg3) {
@@ -279,8 +299,20 @@ public class PuzzleApplet extends JApplet implements Runtime.CallJavaCB {
                 if ((arg2 & 4) != 0) solveCommand.setEnabled(true);
                 colors = new Color[arg3];
                 return 0;
-            case 1: // Type menu item
-                addTypeItem(runtime.cstring(arg1), arg2);
+            case 1: // configure Type menu
+                if (arg1 == 0) {
+                    // preliminary setup
+                    typeMenuItems = new JMenuItem[arg2 + 2];
+                    typeMenuItems[arg2] = typeMenu;
+                    customMenuItemIndex = arg2 + 1;
+                    return arg2;
+                } else if (xarg1 != 0) {
+                    addTypeItem((JMenu)typeMenuItems[arg2],
+                                runtime.cstring(arg1), arg3, xarg1);
+                } else {
+                    addTypeSubmenu((JMenu)typeMenuItems[arg2],
+                                   runtime.cstring(arg1), arg3);
+                }
                 return 0;
             case 2: // MessageBox
                 JOptionPane.showMessageDialog(this, runtime.cstring(arg2), runtime.cstring(arg1), arg3 == 0 ? JOptionPane.INFORMATION_MESSAGE : JOptionPane.ERROR_MESSAGE);
@@ -432,10 +464,11 @@ public class PuzzleApplet extends JApplet implements Runtime.CallJavaCB {
                 dlg = null;
                 return 0;
             case 13: // tick a menu item
-                if (arg1 < 0) arg1 = typeMenu.getItemCount() - 1;
-                for (int i = 0; i < typeMenu.getItemCount(); i++) {
-                    if (typeMenu.getMenuComponent(i) instanceof JCheckBoxMenuItem) {
-                        ((JCheckBoxMenuItem)typeMenu.getMenuComponent(i)).setSelected(arg1 == i);
+                if (arg1 < 0) arg1 = customMenuItemIndex;
+                for (int i = 0; i < typeMenuItems.length; i++) {
+                    if (typeMenuItems[i] instanceof JCheckBoxMenuItem) {
+                        ((JCheckBoxMenuItem)typeMenuItems[i]).setSelected
+                            (arg1 == i);
                     }
                 }
                 return 0;
diff --git a/blackbox.c b/blackbox.c
index 629b7ec..b334cf7 100644
--- a/blackbox.c
+++ b/blackbox.c
@@ -1505,7 +1505,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Black Box", "games.blackbox", "blackbox",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/bridges.c b/bridges.c
index de7403e..6975208 100644
--- a/bridges.c
+++ b/bridges.c
@@ -3224,7 +3224,7 @@ static void game_print(drawing *dr, const game_state *state, int ts)
 const struct game thegame = {
     "Bridges", "games.bridges", "bridges",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/cube.c b/cube.c
index c22e299..a30dc10 100644
--- a/cube.c
+++ b/cube.c
@@ -1737,7 +1737,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Cube", "games.cube", "cube",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/devel.but b/devel.but
index 9befcad..a38fdda 100644
--- a/devel.but
+++ b/devel.but
@@ -391,8 +391,9 @@ with the default values, and returns a pointer to it.
 
 \c int (*fetch_preset)(int i, char **name, game_params **params);
 
-This function is used to populate the \q{Type} menu, which provides
-a list of conveniently accessible preset parameters for most games.
+This function is one of the two APIs a back end can provide to
+populate the \q{Type} menu, which provides a list of conveniently
+accessible preset parameters for most games.
 
 The function is called with \c{i} equal to the index of the preset
 required (numbering from zero). It returns \cw{FALSE} if that preset
@@ -406,6 +407,33 @@ returns \cw{TRUE}.
 If the game does not wish to support any presets at all, this
 function is permitted to return \cw{FALSE} always.
 
+If the game wants to return presets in the form of a hierarchical menu
+instead of a flat list (and, indeed, even if it doesn't), then it may
+set this function pointer to \cw{NULL}, and instead fill in the
+alternative function pointer \cw{preset_menu}
+(\k{backend-preset-menu}).
+
+\S{backend-preset-menu} \cw{preset_menu()}
+
+\c struct preset_menu *(*preset_menu)(void);
+
+This function is the more flexible of the two APIs by which a back end
+can define a collection of preset game parameters.
+
+This function simply returns a complete menu hierarchy, in the form of
+a \c{struct preset_menu} (see \k{midend-get-presets}) and further
+submenus (if it wishes) dangling off it. There are utility functions
+described in \k{utils-presets} to make it easy for the back end to
+construct this menu.
+
+If the game has no need to return a hierarchy of menus, it may instead
+opt to implement the \cw{fetch_preset()} function (see
+\k{backend-fetch-preset}).
+
+The game need not fill in the \c{id} fields in the preset menu
+structures. The mid-end will do that after it receives the structure
+from the game, and before passing it on to the front end.
+
 \S{backend-encode-params} \cw{encode_params()}
 
 \c char *(*encode_params)(const game_params *params, int full);
@@ -2743,8 +2771,8 @@ these parameters until further notice.
 
 The usual way in which the front end will have an actual
 \c{game_params} structure to pass to this function is if it had
-previously got it from \cw{midend_fetch_preset()}
-(\k{midend-fetch-preset}). Thus, this function is usually called in
+previously got it from \cw{midend_get_presets()}
+(\k{midend-get-presets}). Thus, this function is usually called in
 response to the user making a selection from the presets menu.
 
 \H{midend-get-params} \cw{midend_get_params()}
@@ -2966,34 +2994,63 @@ One of the major purposes of timing in the mid-end is to perform
 move animation. Therefore, calling this function is very likely to
 result in calls back to the front end's drawing API.
 
-\H{midend-num-presets} \cw{midend_num_presets()}
+\H{midend-get-presets} \cw{midend_get_presets()}
 
-\c int midend_num_presets(midend *me);
+\c struct preset_menu *midend_get_presets(midend *me, int *id_limit);
 
-Returns the number of game parameter presets supplied by this game.
-Front ends should use this function and \cw{midend_fetch_preset()}
-to configure their presets menu rather than calling the back end
-directly, since the mid-end adds standard customisation facilities.
-(At the time of writing, those customisation facilities are
-implemented hackily by means of environment variables, but it's not
-impossible that they may become more full and formal in future.)
+Returns a data structure describing this game's collection of preset
+game parameters, organised into a hierarchical structure of menus and
+submenus.
 
-\H{midend-fetch-preset} \cw{midend_fetch_preset()}
+The return value is a pointer to a data structure containing the
+following fields (among others, which are not intended for front end
+use):
 
-\c void midend_fetch_preset(midend *me, int n,
-\c                          char **name, game_params **params);
+\c struct preset_menu {
+\c     int n_entries;
+\c     struct preset_menu_entry *entries;
+\c     /* and other things */
+\e     iiiiiiiiiiiiiiiiiiiiii
+\c };
 
-Returns one of the preset game parameter structures for the game. On
-input \c{n} must be a non-negative integer and less than the value
-returned from \cw{midend_num_presets()}. On output, \c{*name} is set
-to an ASCII string suitable for entering in the game's presets menu,
-and \c{*params} is set to the corresponding \c{game_params}
-structure.
+Those fields describe the intended contents of one particular menu in
+the hierarchy. \cq{entries} points to an array of \cq{n_entries}
+items, each of which is a structure containing the following fields:
+
+\c struct preset_menu_entry {
+\c     char *title;
+\c     game_params *params;
+\c     struct preset_menu *submenu;
+\c     int id;
+\c };
 
-Both of the two output values are dynamically allocated, but they
-are owned by the mid-end structure: the front end should not ever
-free them directly, because they will be freed automatically during
-\cw{midend_free()}.
+Of these fields, \cq{title} and \cq{id} are present in every entry,
+giving (respectively) the textual name of the menu item and an integer
+identifier for it. The integer id will correspond to the one returned
+by \c{midend_which_preset} (\k{midend-which-preset}), when that preset
+is the one selected.
+
+The other two fields are mutually exclusive. Each \c{struct
+preset_menu_entry} will have one of those fields \cw{NULL} and the
+other one non-null. If the menu item is an actual preset, then
+\cq{params} will point to the set of game parameters that go with the
+name; if it's a submenu, then \cq{submenu} instead will be non-null,
+and will point at a subsidiary \c{struct preset_menu}.
+
+The complete hierarchy of these structures is owned by the mid-end,
+and will be freed when the mid-end is freed. The front end should not
+attempt to free any of it.
+
+The integer identifiers will be allocated densely from 0 upwards, so
+that it's reasonable for the front end to allocate an array which uses
+them as indices, if it needs to store information per preset menu
+item. For this purpose, the front end may pass the second parameter
+\cq{id_limit} to \cw{midend_get_presets} as the address of an \c{int}
+variable, into which \cw{midend_get_presets} will write an integer one
+larger than the largest id number actually used (i.e. the number of
+elements the front end would need in the array).
+
+Submenu-type entries also have integer identifiers.
 
 \H{midend-which-preset} \cw{midend_which_preset()}
 
@@ -3005,6 +3062,10 @@ no preset matches. Front ends could use this to maintain a tick
 beside one of the items in the menu (or tick the \q{Custom} option
 if the return value is less than zero).
 
+The returned index value (if non-negative) will match the \c{id} field
+of the corresponding \cw{struct preset_menu_entry} returned by
+\c{midend_get_presets()} (\k{midend-get-presets}).
+
 \H{midend-wants-statusbar} \cw{midend_wants_statusbar()}
 
 \c int midend_wants_statusbar(midend *me);
@@ -3535,6 +3596,63 @@ single element (typically measured using \c{sizeof}). \c{rs} is a
 \c{random_state} used to generate all the random numbers for the
 shuffling process.
 
+\H{utils-presets} Presets menu management
+
+The function \c{midend_get_presets()} (\k{midend-get-presets}) returns
+a data structure describing a menu hierarchy. Back ends can also
+choose to provide such a structure to the mid-end, if they want to
+group their presets hierarchically. To make this easy, there are a few
+utility functions to construct preset menu structures, and also one
+intended for front-end use.
+
+\S{utils-preset-menu-new} \cw{preset_menu_new()}
+
+\c struct preset_menu *preset_menu_new(void);
+
+Allocates a new \c{struct preset_menu}, and initialises it to hold no
+menu items.
+
+\S{utils-preset-menu-add_submenu} \cw{preset_menu_add_submenu()}
+
+\c struct preset_menu *preset_menu_add_submenu
+\c     (struct preset_menu *parent, char *title);
+
+Adds a new submenu to the end of an existing preset menu, and returns
+a pointer to a newly allocated \c{struct preset_menu} describing the
+submenu.
+
+The string parameter \cq{title} must be dynamically allocated by the
+caller. The preset-menu structure will take ownership of it, so the
+caller must not free it.
+
+\S{utils-preset-menu-add-preset} \cw{preset_menu_add_preset()}
+
+\c void preset_menu_add_preset
+\c     (struct preset_menu *menu, char *title, game_params *params);
+
+Adds a preset game configuration to the end of a preset menu.
+
+Both the string parameter \cq{title} and the game parameter structure
+\cq{params} itself must be dynamically allocated by the caller. The
+preset-menu structure will take ownership of it, so the caller must
+not free it.
+
+\S{utils-preset-menu-lookup-by-id} \cw{preset_menu_lookup_by_id()}
+
+\c game_params *preset_menu_lookup_by_id
+\c     (struct preset_menu *menu, int id);
+
+Given a numeric index, searches recursively through a preset menu
+hierarchy to find the corresponding menu entry, and returns a pointer
+to its existing \c{game_params} structure.
+
+This function is intended for front end use (but front ends need not
+use it if they prefer to do things another way). If a front end finds
+it inconvenient to store anything more than a numeric index alongside
+each menu item, then this function provides an easy way for the front
+end to get back the actual game parameters corresponding to a menu
+item that the user has selected.
+
 \H{utils-alloc} Memory allocation
 
 Puzzles has some central wrappers on the standard memory allocation
diff --git a/dominosa.c b/dominosa.c
index dc7c2c7..c86ba19 100644
--- a/dominosa.c
+++ b/dominosa.c
@@ -1709,7 +1709,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Dominosa", "games.dominosa", "dominosa",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/emcc.c b/emcc.c
index 74f17cf..ca033cb 100644
--- a/emcc.c
+++ b/emcc.c
@@ -61,7 +61,8 @@ extern void js_debug(const char *);
 extern void js_error_box(const char *message);
 extern void js_remove_type_dropdown(void);
 extern void js_remove_solve_button(void);
-extern void js_add_preset(const char *name);
+extern void js_add_preset(int menuid, const char *name, int value);
+extern int js_add_preset_submenu(int menuid, const char *name);
 extern int js_get_selected_preset(void);
 extern void js_select_preset(int n);
 extern void js_get_date_64(unsigned *p);
@@ -552,6 +553,21 @@ static game_params **presets;
 static int npresets;
 int have_presets_dropdown;
 
+void populate_js_preset_menu(int menuid, struct preset_menu *menu)
+{
+    int i;
+    for (i = 0; i < menu->n_entries; i++) {
+        struct preset_menu_entry *entry = &menu->entries[i];
+        if (entry->params) {
+            presets[entry->id] = entry->params;
+            js_add_preset(menuid, entry->title, entry->id);
+        } else {
+            int js_submenu = js_add_preset_submenu(menuid, entry->title);
+            populate_js_preset_menu(js_submenu, entry->submenu);
+        }
+    }
+}
+
 void select_appropriate_preset(void)
 {
     if (have_presets_dropdown) {
@@ -787,23 +803,16 @@ int main(int argc, char **argv)
      * Set up the game-type dropdown with presets and/or the Custom
      * option.
      */
-    npresets = midend_num_presets(me);
-    if (npresets == 0) {
-        /*
-         * This puzzle doesn't have selectable game types at all.
-         * Completely remove the drop-down list from the page.
-         */
-        js_remove_type_dropdown();
-        have_presets_dropdown = FALSE;
-    } else {
+    {
+        struct preset_menu *menu = midend_get_presets(me, &npresets);
         presets = snewn(npresets, game_params *);
-        for (i = 0; i < npresets; i++) {
-            char *name;
-            midend_fetch_preset(me, i, &name, &presets[i]);
-            js_add_preset(name);
-        }
+        for (i = 0; i < npresets; i++)
+            presets[i] = NULL;
+
+        populate_js_preset_menu(0, menu);
+
         if (thegame.can_configure)
-            js_add_preset(NULL);   /* the 'Custom' entry in the dropdown */
+            js_add_preset(0, "Custom", -1);
 
         have_presets_dropdown = TRUE;
 
diff --git a/emcclib.js b/emcclib.js
index 1dde2b3..cd8876e 100644
--- a/emcclib.js
+++ b/emcclib.js
@@ -59,28 +59,17 @@ mergeInto(LibraryManager.library, {
     },
 
     /*
-     * void js_add_preset(const char *name);
+     * void js_add_preset(int menuid, const char *name, int value);
      *
-     * Add a preset to the drop-down types menu. The provided text is
-     * the name of the preset. (The corresponding game_params stays on
-     * the C side and never comes out this far; we just pass a numeric
-     * index back to the C code when a selection is made.)
-     *
-     * The special 'Custom' preset is requested by passing NULL to
-     * this function.
-     */
-    js_add_preset: function(ptr) {
-        var name = (ptr == 0 ? "Custom" : Pointer_stringify(ptr));
-        var value = gametypeitems.length;
-
+     * Add a preset to the drop-down types menu, or to a submenu of
+     * it. 'menuid' specifies an index into our array of submenus
+     * where the item might be placed; 'value' specifies the number
+     * that js_get_selected_preset() will return when this item is
+     * clicked.
+     */
+    js_add_preset: function(menuid, ptr, value) {
+        var name = Pointer_stringify(ptr);
         var item = document.createElement("li");
-        if (ptr == 0) {
-            // The option we've just created is the one for inventing
-            // a new custom setup.
-            gametypecustom = item;
-            value = -1;
-        }
-
         item.setAttribute("data-index", value);
         var tick = document.createElement("span");
         tick.appendChild(document.createTextNode("\u2713"));
@@ -88,7 +77,7 @@ mergeInto(LibraryManager.library, {
         tick.style.paddingRight = "0.5em";
         item.appendChild(tick);
         item.appendChild(document.createTextNode(name));
-        gametypelist.appendChild(item);
+        gametypesubmenus[menuid].appendChild(item);
         gametypeitems.push(item);
 
         item.onclick = function(event) {
@@ -100,6 +89,34 @@ mergeInto(LibraryManager.library, {
     },
 
     /*
+     * int js_add_preset_submenu(int menuid, const char *name);
+     *
+     * Add a submenu in the presets menu hierarchy. Returns its index,
+     * for passing as the 'menuid' argument in further calls to
+     * js_add_preset or this function.
+     */
+    js_add_preset_submenu: function(menuid, ptr, value) {
+        var name = Pointer_stringify(ptr);
+        var item = document.createElement("li");
+        // We still create a transparent tick element, even though it
+        // won't ever be selected, to make submenu titles line up
+        // nicely with their neighbours.
+        var tick = document.createElement("span");
+        tick.appendChild(document.createTextNode("\u2713"));
+        tick.style.color = "transparent";
+        tick.style.paddingRight = "0.5em";
+        item.appendChild(tick);
+        item.appendChild(document.createTextNode(name));
+        var submenu = document.createElement("ul");
+        submenu.className = "left";
+        item.appendChild(submenu);
+        gametypesubmenus[menuid].appendChild(item);
+        var toret = gametypesubmenus.length;
+        gametypesubmenus.push(submenu);
+        return toret;
+    },
+
+    /*
      * int js_get_selected_preset(void);
      *
      * Return the index of the currently selected value in the type
diff --git a/emccpre.js b/emccpre.js
index b10bf29..d715858 100644
--- a/emccpre.js
+++ b/emccpre.js
@@ -82,8 +82,9 @@ var dlg_return_sval, dlg_return_ival;
 // The <ul> object implementing the game-type drop-down, and a list of
 // the <li> objects inside it. Used by js_add_preset(),
 // js_get_selected_preset() and js_select_preset().
-var gametypelist = null, gametypeitems = [], gametypecustom = null;
+var gametypelist = null, gametypeitems = [];
 var gametypeselectedindex = null;
+var gametypesubmenus = [];
 
 // The two anchors used to give permalinks to the current puzzle. Used
 // by js_update_permalinks().
@@ -230,6 +231,7 @@ function initPuzzle() {
     };
 
     gametypelist = document.getElementById("gametype");
+    gametypesubmenus.push(gametypelist);
 
     // In IE, the canvas doesn't automatically gain focus on a mouse
     // click, so make sure it does
diff --git a/fifteen.c b/fifteen.c
index 6482714..aee8907 100644
--- a/fifteen.c
+++ b/fifteen.c
@@ -1089,7 +1089,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Fifteen", "games.fifteen", "fifteen",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/filling.c b/filling.c
index 3797e5c..d8d0c8c 100644
--- a/filling.c
+++ b/filling.c
@@ -2111,7 +2111,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Filling", "games.filling", "filling",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/flip.c b/flip.c
index 2249698..c7126fb 100644
--- a/flip.c
+++ b/flip.c
@@ -1313,7 +1313,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Flip", "games.flip", "flip",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/flood.c b/flood.c
index f97de2f..1262be8 100644
--- a/flood.c
+++ b/flood.c
@@ -1336,7 +1336,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Flood", "games.flood", "flood",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/galaxies.c b/galaxies.c
index 53d6fab..f4f75c6 100644
--- a/galaxies.c
+++ b/galaxies.c
@@ -3633,7 +3633,7 @@ static void game_print(drawing *dr, const game_state *state, int sz)
 const struct game thegame = {
     "Galaxies", "games.galaxies", "galaxies",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/gtk.c b/gtk.c
index ab3ad8b..c5e3d1c 100644
--- a/gtk.c
+++ b/gtk.c
@@ -182,7 +182,6 @@ struct frontend {
     char *filesel_name;
 #endif
     GSList *preset_radio;
-    int n_preset_menu_items;
     int preset_threaded;
     GtkWidget *preset_custom;
     GtkWidget *copy_menu_item;
@@ -1884,20 +1883,22 @@ static void changed_preset(frontend *fe)
 	    TRUE);
     } else {
 	GSList *gs = fe->preset_radio;
-	int i = fe->n_preset_menu_items - 1 - n;
-	if (fe->preset_custom)
-	    gs = gs->next;
-	while (i && gs) {
-	    i--;
-	    gs = gs->next;
-	}
-	if (gs) {
-	    gtk_check_menu_item_set_active(GTK_CHECK_MENU_ITEM(gs->data),
-					   TRUE);
-	} else for (gs = fe->preset_radio; gs; gs = gs->next) {
-	    gtk_check_menu_item_set_active(GTK_CHECK_MENU_ITEM(gs->data),
-					   FALSE);
-	}
+        GSList *found = NULL;
+
+        for (gs = fe->preset_radio; gs; gs = gs->next) {
+            struct preset_menu_entry *entry =
+                (struct preset_menu_entry *)g_object_get_data(
+                    G_OBJECT(gs->data), "user-data");
+
+            if (entry && entry->id != n)
+                gtk_check_menu_item_set_active(
+                    GTK_CHECK_MENU_ITEM(gs->data), FALSE);
+            else
+                found = gs;
+        }
+        if (found)
+            gtk_check_menu_item_set_active(
+                GTK_CHECK_MENU_ITEM(found->data), FALSE);
     }
     fe->preset_threaded = FALSE;
 
@@ -2019,14 +2020,15 @@ static void resize_fe(frontend *fe)
 static void menu_preset_event(GtkMenuItem *menuitem, gpointer data)
 {
     frontend *fe = (frontend *)data;
-    game_params *params =
-        (game_params *)g_object_get_data(G_OBJECT(menuitem), "user-data");
+    struct preset_menu_entry *entry =
+        (struct preset_menu_entry *)g_object_get_data(
+            G_OBJECT(menuitem), "user-data");
 
     if (fe->preset_threaded ||
 	(GTK_IS_CHECK_MENU_ITEM(menuitem) &&
 	 !gtk_check_menu_item_get_active(GTK_CHECK_MENU_ITEM(menuitem))))
 	return;
-    midend_set_params(fe->me, params);
+    midend_set_params(fe->me, entry->params);
     midend_new_game(fe->me);
     changed_preset(fe);
     resize_fe(fe);
@@ -2383,6 +2385,36 @@ static void add_menu_separator(GtkContainer *cont)
     gtk_widget_show(menuitem);
 }
 
+static void populate_gtk_preset_menu(frontend *fe, struct preset_menu *menu,
+                                     GtkWidget *gtkmenu)
+{
+    int i;
+
+    for (i = 0; i < menu->n_entries; i++) {
+        struct preset_menu_entry *entry = &menu->entries[i];
+        GtkWidget *menuitem;
+
+        if (entry->params) {
+            menuitem = gtk_radio_menu_item_new_with_label(
+                fe->preset_radio, entry->title);
+            fe->preset_radio = gtk_radio_menu_item_get_group(
+                GTK_RADIO_MENU_ITEM(menuitem));
+            g_object_set_data(G_OBJECT(menuitem), "user-data", entry);
+            g_signal_connect(G_OBJECT(menuitem), "activate",
+                             G_CALLBACK(menu_preset_event), fe);
+        } else {
+            GtkWidget *submenu;
+            menuitem = gtk_menu_item_new_with_label(entry->title);
+            submenu = gtk_menu_new();
+            gtk_menu_item_set_submenu(GTK_MENU_ITEM(menuitem), submenu);
+            populate_gtk_preset_menu(fe, entry->submenu, submenu);
+        }
+
+        gtk_container_add(GTK_CONTAINER(gtkmenu), menuitem);
+        gtk_widget_show(menuitem);
+    }
+}
+
 enum { ARG_EITHER, ARG_SAVE, ARG_ID }; /* for argtype */
 
 static frontend *new_window(char *arg, int argtype, char **error)
@@ -2395,6 +2427,7 @@ static frontend *new_window(char *arg, int argtype, char **error)
     char errbuf[1024];
     extern char *const *const xpm_icons[];
     extern const int n_xpm_icons;
+    struct preset_menu *preset_menu;
 
     fe = snew(frontend);
 #if GTK_CHECK_VERSION(3,20,0)
@@ -2546,11 +2579,11 @@ static frontend *new_window(char *arg, int argtype, char **error)
 
     fe->preset_radio = NULL;
     fe->preset_custom = NULL;
-    fe->n_preset_menu_items = 0;
     fe->preset_threaded = FALSE;
-    if ((n = midend_num_presets(fe->me)) > 0 || thegame.can_configure) {
+
+    preset_menu = midend_get_presets(fe->me, NULL);
+    if (preset_menu->n_entries > 0 || thegame.can_configure) {
         GtkWidget *submenu;
-        int i;
 
         menuitem = gtk_menu_item_new_with_mnemonic("_Type");
         gtk_container_add(GTK_CONTAINER(fe->menubar), menuitem);
@@ -2559,23 +2592,7 @@ static frontend *new_window(char *arg, int argtype, char **error)
         submenu = gtk_menu_new();
         gtk_menu_item_set_submenu(GTK_MENU_ITEM(menuitem), submenu);
 
-        for (i = 0; i < n; i++) {
-            char *name;
-            game_params *params;
-
-            midend_fetch_preset(fe->me, i, &name, &params);
-
-	    menuitem =
-		gtk_radio_menu_item_new_with_label(fe->preset_radio, name);
-	    fe->preset_radio =
-		gtk_radio_menu_item_get_group(GTK_RADIO_MENU_ITEM(menuitem));
-	    fe->n_preset_menu_items++;
-            gtk_container_add(GTK_CONTAINER(submenu), menuitem);
-            g_object_set_data(G_OBJECT(menuitem), "user-data", params);
-            g_signal_connect(G_OBJECT(menuitem), "activate",
-                             G_CALLBACK(menu_preset_event), fe);
-            gtk_widget_show(menuitem);
-        }
+        populate_gtk_preset_menu(fe, preset_menu, submenu);
 
 	if (thegame.can_configure) {
 	    menuitem = fe->preset_custom =
@@ -2826,6 +2843,22 @@ char *fgetline(FILE *fp)
     return ret;
 }
 
+static void list_presets_from_menu(struct preset_menu *menu)
+{
+    int i;
+
+    for (i = 0; i < menu->n_entries; i++) {
+        if (menu->entries[i].params) {
+            char *paramstr = thegame.encode_params(
+                menu->entries[i].params, TRUE);
+            printf("%s %s\n", paramstr, menu->entries[i].title);
+            sfree(paramstr);
+        } else {
+            list_presets_from_menu(menu->entries[i].submenu);
+        }
+    }
+}
+
 int main(int argc, char **argv)
 {
     char *pname = argv[0];
@@ -3229,23 +3262,12 @@ int main(int argc, char **argv)
          * Another specialist mode which causes the puzzle to list the
          * game_params strings for all its preset configurations.
          */
-        int i, npresets;
         midend *me;
+        struct preset_menu *menu;
 
 	me = midend_new(NULL, &thegame, NULL, NULL);
-        npresets = midend_num_presets(me);
-
-        for (i = 0; i < npresets; i++) {
-            game_params *params;
-            char *name, *paramstr;
-
-            midend_fetch_preset(me, i, &name, &params);
-            paramstr = thegame.encode_params(params, TRUE);
-
-            printf("%s %s\n", paramstr, name);
-            sfree(paramstr);
-        }
-
+        menu = midend_get_presets(me, NULL);
+        list_presets_from_menu(menu);
 	midend_free(me);
         return 0;
     } else {
diff --git a/guess.c b/guess.c
index df9b7f6..8f05863 100644
--- a/guess.c
+++ b/guess.c
@@ -1480,7 +1480,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Guess", "games.guess", "guess",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/inertia.c b/inertia.c
index 4cbdd52..c22d2e1 100644
--- a/inertia.c
+++ b/inertia.c
@@ -2213,7 +2213,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Inertia", "games.inertia", "inertia",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/keen.c b/keen.c
index b91e95b..fdaae32 100644
--- a/keen.c
+++ b/keen.c
@@ -2340,7 +2340,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Keen", "games.keen", "keen",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/lightup.c b/lightup.c
index bfc6980..4dd46c8 100644
--- a/lightup.c
+++ b/lightup.c
@@ -2290,7 +2290,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Light Up", "games.lightup", "lightup",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/loopy.c b/loopy.c
index 9cef879..bc6ebb3 100644
--- a/loopy.c
+++ b/loopy.c
@@ -3548,7 +3548,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Loopy", "games.loopy", "loopy",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/magnets.c b/magnets.c
index 4fec131..553ca0d 100644
--- a/magnets.c
+++ b/magnets.c
@@ -2396,7 +2396,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Magnets", "games.magnets", "magnets",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/map.c b/map.c
index f3c4430..f1af38b 100644
--- a/map.c
+++ b/map.c
@@ -3199,7 +3199,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Map", "games.map", "map",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/midend.c b/midend.c
index 190840a..c8250ab 100644
--- a/midend.c
+++ b/midend.c
@@ -30,9 +30,9 @@ struct midend {
     random_state *random;
     const game *ourgame;
 
-    game_params **presets;
-    char **preset_names, **preset_encodings;
-    int npresets, presetsize;
+    struct preset_menu *preset_menu;
+    char **encoded_presets; /* for midend_which_preset to check against */
+    int n_encoded_presets;
 
     /*
      * `desc' and `privdesc' deserve a comment.
@@ -158,10 +158,7 @@ midend *midend_new(frontend *fe, const game *ourgame,
     me->genmode = GOT_NOTHING;
     me->drawstate = NULL;
     me->oldstate = NULL;
-    me->presets = NULL;
-    me->preset_names = NULL;
-    me->preset_encodings = NULL;
-    me->npresets = me->presetsize = 0;
+    me->preset_menu = NULL;
     me->anim_time = me->anim_pos = 0.0F;
     me->flash_time = me->flash_pos = 0.0F;
     me->dir = 0;
@@ -209,10 +206,23 @@ static void midend_free_game(midend *me)
         me->ourgame->free_drawstate(me->drawing, me->drawstate);
 }
 
-void midend_free(midend *me)
+static void midend_free_preset_menu(midend *me, struct preset_menu *menu)
 {
-    int i;
+    if (menu) {
+        int i;
+        for (i = 0; i < menu->n_entries; i++) {
+            sfree(menu->entries[i].title);
+            if (menu->entries[i].params)
+                me->ourgame->free_params(menu->entries[i].params);
+            midend_free_preset_menu(me, menu->entries[i].submenu);
+        }
+        sfree(menu->entries);
+        sfree(menu);
+    }
+}
 
+void midend_free(midend *me)
+{
     midend_free_game(me);
 
     if (me->drawing)
@@ -224,16 +234,7 @@ void midend_free(midend *me)
     sfree(me->seedstr);
     sfree(me->aux_info);
     me->ourgame->free_params(me->params);
-    if (me->npresets) {
-	for (i = 0; i < me->npresets; i++) {
-	    sfree(me->presets[i]);
-	    sfree(me->preset_names[i]);
-	    sfree(me->preset_encodings[i]);
-	}
-	sfree(me->presets);
-	sfree(me->preset_names);
-	sfree(me->preset_encodings);
-    }
+    midend_free_preset_menu(me, me->preset_menu);
     if (me->ui)
         me->ourgame->free_ui(me->ui);
     if (me->curparams)
@@ -927,40 +928,177 @@ float *midend_colours(midend *me, int *ncolours)
     return ret;
 }
 
-int midend_num_presets(midend *me)
+struct preset_menu *preset_menu_new(void)
 {
-    if (!me->npresets) {
-        char *name;
+    struct preset_menu *menu = snew(struct preset_menu);
+    menu->n_entries = 0;
+    menu->entries_size = 0;
+    menu->entries = NULL;
+    return menu;
+}
+
+static struct preset_menu_entry *preset_menu_add(struct preset_menu *menu,
+                                                 char *title)
+{
+    struct preset_menu_entry *toret;
+    if (menu->n_entries >= menu->entries_size) {
+        menu->entries_size = menu->n_entries * 5 / 4 + 10;
+        menu->entries = sresize(menu->entries, menu->entries_size,
+                                struct preset_menu_entry);
+    }
+    toret = &menu->entries[menu->n_entries++];
+    toret->title = title;
+    toret->params = NULL;
+    toret->submenu = NULL;
+    return toret;
+}
+
+struct preset_menu *preset_menu_add_submenu(struct preset_menu *parent,
+                                            char *title)
+{
+    struct preset_menu_entry *entry = preset_menu_add(parent, title);
+    entry->submenu = preset_menu_new();
+    return entry->submenu;
+}
+
+void preset_menu_add_preset(struct preset_menu *parent,
+                            char *title, game_params *params)
+{
+    struct preset_menu_entry *entry = preset_menu_add(parent, title);
+    entry->params = params;
+}
+
+game_params *preset_menu_lookup_by_id(struct preset_menu *menu, int id)
+{
+    int i;
+    game_params *retd;
+
+    for (i = 0; i < menu->n_entries; i++) {
+        if (id == menu->entries[i].id)
+            return menu->entries[i].params;
+        if (menu->entries[i].submenu &&
+            (retd = preset_menu_lookup_by_id(
+                 menu->entries[i].submenu, id)) != NULL)
+            return retd;
+    }
+
+    return NULL;
+}
+
+static char *preset_menu_add_from_user_env(
+    midend *me, struct preset_menu *menu, char *p, int top_level)
+{
+    while (*p) {
+        char *name, *val;
         game_params *preset;
 
-        while (me->ourgame->fetch_preset(me->npresets, &name, &preset)) {
-            if (me->presetsize <= me->npresets) {
-                me->presetsize = me->npresets + 10;
-                me->presets = sresize(me->presets, me->presetsize,
-                                      game_params *);
-                me->preset_names = sresize(me->preset_names, me->presetsize,
-                                           char *);
-                me->preset_encodings = sresize(me->preset_encodings,
-					       me->presetsize, char *);
+        name = p;
+        while (*p && *p != ':') p++;
+        if (*p) *p++ = '\0';
+        val = p;
+        while (*p && *p != ':') p++;
+        if (*p) *p++ = '\0';
+
+        if (!strcmp(val, "#")) {
+            /*
+             * Special case: either open a new submenu with the given
+             * title, or terminate the current submenu.
+             */
+            if (*name) {
+                struct preset_menu *submenu =
+                    preset_menu_add_submenu(menu, dupstr(name));
+                p = preset_menu_add_from_user_env(me, submenu, p, FALSE);
+            } else {
+                /*
+                 * If we get a 'close submenu' indication at the top
+                 * level, there's not much we can do but quietly
+                 * ignore it.
+                 */
+                if (!top_level)
+                    return p;
             }
+            continue;
+        }
 
-            me->presets[me->npresets] = preset;
-            me->preset_names[me->npresets] = name;
-            me->preset_encodings[me->npresets] =
-		me->ourgame->encode_params(preset, TRUE);;
-            me->npresets++;
+        preset = me->ourgame->default_params();
+        me->ourgame->decode_params(preset, val);
+
+        if (me->ourgame->validate_params(preset, TRUE)) {
+            /* Drop this one from the list. */
+            me->ourgame->free_params(preset);
+            continue;
         }
+
+        preset_menu_add_preset(menu, dupstr(name), preset);
+    }
+
+    return p;
+}
+
+static void preset_menu_alloc_ids(midend *me, struct preset_menu *menu)
+{
+    int i;
+
+    for (i = 0; i < menu->n_entries; i++)
+        menu->entries[i].id = me->n_encoded_presets++;
+
+    for (i = 0; i < menu->n_entries; i++)
+        if (menu->entries[i].submenu)
+            preset_menu_alloc_ids(me, menu->entries[i].submenu);
+}
+
+static void preset_menu_encode_params(midend *me, struct preset_menu *menu)
+{
+    int i;
+
+    for (i = 0; i < menu->n_entries; i++) {
+        if (menu->entries[i].params) {
+            me->encoded_presets[menu->entries[i].id] =
+                me->ourgame->encode_params(menu->entries[i].params, TRUE);
+        } else {
+            preset_menu_encode_params(me, menu->entries[i].submenu);
+        }
+    }
+}
+
+struct preset_menu *midend_get_presets(midend *me, int *id_limit)
+{
+    int i;
+
+    if (me->preset_menu)
+        return me->preset_menu;
+
+#if 0
+    /* Expect the game to implement exactly one of the two preset APIs */
+    assert(me->ourgame->fetch_preset || me->ourgame->preset_menu);
+    assert(!(me->ourgame->fetch_preset && me->ourgame->preset_menu));
+#endif
+
+    if (me->ourgame->fetch_preset) {
+        char *name;
+        game_params *preset;
+
+        /* Simple one-level menu */
+        assert(!me->ourgame->preset_menu);
+        me->preset_menu = preset_menu_new();
+        for (i = 0; me->ourgame->fetch_preset(i, &name, &preset); i++)
+            preset_menu_add_preset(me->preset_menu, name, preset);
+
+    } else {
+        /* Hierarchical menu provided by the game backend */
+        me->preset_menu = me->ourgame->preset_menu();
     }
 
     {
         /*
-         * Allow environment-based extensions to the preset list by
-         * defining a variable along the lines of `SOLO_PRESETS=2x3
-         * Advanced:2x3da'. Colon-separated list of items,
-         * alternating between textual titles in the menu and
-         * encoded parameter strings.
+         * Allow user extensions to the preset list by defining an
+         * environment variable <gamename>_PRESETS whose value is a
+         * colon-separated list of items, alternating between textual
+         * titles in the menu and encoded parameter strings. For
+         * example, "SOLO_PRESETS=2x3 Advanced:2x3da" would define
+         * just one additional preset for Solo.
          */
-        char buf[80], *e, *p;
+        char buf[80], *e;
         int j, k;
 
         sprintf(buf, "%s_PRESETS", me->ourgame->name);
@@ -970,57 +1108,27 @@ int midend_num_presets(midend *me)
 	buf[k] = '\0';
 
         if ((e = getenv(buf)) != NULL) {
-            p = e = dupstr(e);
-
-            while (*p) {
-                char *name, *val;
-                game_params *preset;
-
-                name = p;
-                while (*p && *p != ':') p++;
-                if (*p) *p++ = '\0';
-                val = p;
-                while (*p && *p != ':') p++;
-                if (*p) *p++ = '\0';
-
-                preset = me->ourgame->default_params();
-                me->ourgame->decode_params(preset, val);
-
-		if (me->ourgame->validate_params(preset, TRUE)) {
-		    /* Drop this one from the list. */
-		    me->ourgame->free_params(preset);
-		    continue;
-		}
-
-                if (me->presetsize <= me->npresets) {
-                    me->presetsize = me->npresets + 10;
-                    me->presets = sresize(me->presets, me->presetsize,
-                                          game_params *);
-                    me->preset_names = sresize(me->preset_names,
-                                               me->presetsize, char *);
-                    me->preset_encodings = sresize(me->preset_encodings,
-						   me->presetsize, char *);
-                }
-
-                me->presets[me->npresets] = preset;
-                me->preset_names[me->npresets] = dupstr(name);
-                me->preset_encodings[me->npresets] =
-		    me->ourgame->encode_params(preset, TRUE);
-                me->npresets++;
-            }
+            e = dupstr(e);
+            preset_menu_add_from_user_env(me, me->preset_menu, e, TRUE);
             sfree(e);
         }
     }
 
-    return me->npresets;
-}
-
-void midend_fetch_preset(midend *me, int n,
-                         char **name, game_params **params)
-{
-    assert(n >= 0 && n < me->npresets);
-    *name = me->preset_names[n];
-    *params = me->presets[n];
+    /*
+     * Finalise the menu: allocate an integer id to each entry, and
+     * store string encodings of the presets' parameters in
+     * me->encoded_presets.
+     */
+    me->n_encoded_presets = 0;
+    preset_menu_alloc_ids(me, me->preset_menu);
+    me->encoded_presets = snewn(me->n_encoded_presets, char *);
+    for (i = 0; i < me->n_encoded_presets; i++)
+        me->encoded_presets[i] = NULL;
+    preset_menu_encode_params(me, me->preset_menu);
+
+    if (id_limit)
+        *id_limit = me->n_encoded_presets;
+    return me->preset_menu;
 }
 
 int midend_which_preset(midend *me)
@@ -1029,8 +1137,9 @@ int midend_which_preset(midend *me)
     int i, ret;
 
     ret = -1;
-    for (i = 0; i < me->npresets; i++)
-	if (!strcmp(encoding, me->preset_encodings[i])) {
+    for (i = 0; i < me->n_encoded_presets; i++)
+	if (me->encoded_presets[i] &&
+            !strcmp(encoding, me->encoded_presets[i])) {
 	    ret = i;
 	    break;
 	}
diff --git a/mines.c b/mines.c
index da4428c..6a5ce02 100644
--- a/mines.c
+++ b/mines.c
@@ -3142,7 +3142,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Mines", "games.mines", "mines",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/nestedvm.c b/nestedvm.c
index c859526..79b7971 100644
--- a/nestedvm.c
+++ b/nestedvm.c
@@ -382,6 +382,23 @@ int jcallback_about_event()
     return 0;
 }
 
+void preset_menu_populate(struct preset_menu *menu, int menuid)
+{
+    int i;
+
+    for (i = 0; i < menu->n_entries; i++) {
+        struct preset_menu_entry *entry = &menu->entries[i];
+        if (entry->params) {
+            _call_java(5, (int)entry->params, 0, 0);
+            _call_java(1, (int)entry->title, menuid, entry->id);
+        } else {
+            _call_java(5, 0, 0, 0);
+            _call_java(1, (int)entry->title, menuid, entry->id);
+            preset_menu_populate(entry->submenu, entry->id);
+        }
+    }
+}
+
 int main(int argc, char **argv)
 {
     int i, n;
@@ -394,14 +411,12 @@ int main(int argc, char **argv)
 	midend_game_id(_fe->me, argv[1]);   /* ignore failure */
     midend_new_game(_fe->me);
 
-    if ((n = midend_num_presets(_fe->me)) > 0) {
-        int i;
-        for (i = 0; i < n; i++) {
-            char *name;
-            game_params *params;
-            midend_fetch_preset(_fe->me, i, &name, &params);
-	    _call_java(1, (int)name, (int)params, 0);
-        }
+    {
+        struct preset_menu *menu;
+        int nids, topmenu;
+        menu = midend_get_presets(_fe->me, &nids);
+        topmenu = _call_java(1, 0, nids, 0);
+        preset_menu_populate(menu, topmenu);
     }
 
     colours = midend_colours(_fe->me, &n);
diff --git a/net.c b/net.c
index 738ff53..de51f82 100644
--- a/net.c
+++ b/net.c
@@ -3204,7 +3204,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Net", "games.net", "net",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/netslide.c b/netslide.c
index 89b0edf..c56e1ab 100644
--- a/netslide.c
+++ b/netslide.c
@@ -1855,7 +1855,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Netslide", "games.netslide", "netslide",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/nullfe.c b/nullfe.c
index 4c9975b..ad381a1 100644
--- a/nullfe.c
+++ b/nullfe.c
@@ -43,6 +43,11 @@ void print_line_width(drawing *dr, int width) {}
 void print_line_dotted(drawing *dr, int dotted) {}
 void midend_supersede_game_desc(midend *me, char *desc, char *privdesc) {}
 void status_bar(drawing *dr, char *text) {}
+struct preset_menu *preset_menu_new(void) {return NULL;}
+struct preset_menu *preset_menu_add_submenu(struct preset_menu *parent,
+                                            char *title) {return NULL;}
+void preset_menu_add_preset(struct preset_menu *parent,
+                            char *title, game_params *params) {}
 
 void fatal(char *fmt, ...)
 {
diff --git a/nullgame.c b/nullgame.c
index 5e5a073..183b1e3 100644
--- a/nullgame.c
+++ b/nullgame.c
@@ -267,7 +267,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Null Game", NULL, NULL,
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/osx.m b/osx.m
index 4740124..9d74da1 100644
--- a/osx.m
+++ b/osx.m
@@ -426,6 +426,9 @@ struct frontend {
     NSView **cfg_controls;
     int cfg_ncontrols;
     NSTextField *status;
+    struct preset_menu *preset_menu;
+    NSMenuItem **preset_menu_items;
+    int n_preset_menu_items;
 }
 - (id)initWithGame:(const game *)g;
 - (void)dealloc;
@@ -540,6 +543,8 @@ struct frontend {
     int w, h;
 
     ourgame = g;
+    preset_menu = NULL;
+    preset_menu_items = NULL;
 
     fe.window = self;
 
@@ -618,6 +623,7 @@ struct frontend {
 	[fe.colours[i] release];
     }
     sfree(fe.colours);
+    sfree(preset_menu_items);
     midend_free(me);
     [super dealloc];
 }
@@ -847,54 +853,99 @@ struct frontend {
 
 - (void)clearTypeMenu
 {
+    int i;
+
     while ([typemenu numberOfItems] > 1)
 	[typemenu removeItemAtIndex:0];
     [[typemenu itemAtIndex:0] setState:NSOffState];
+
+    for (i = 0; i < n_preset_menu_items; i++)
+        preset_menu_items[i] = NULL;
 }
 
 - (void)updateTypeMenuTick
 {
-    int i, total, n;
+    int i, n;
 
-    total = [typemenu numberOfItems];
     n = midend_which_preset(me);
-    if (n < 0)
-	n = total - 1;		       /* that's always where "Custom" lives */
-    for (i = 0; i < total; i++)
-	[[typemenu itemAtIndex:i] setState:(i == n ? NSOnState : NSOffState)];
+
+    for (i = 0; i < n_preset_menu_items; i++)
+        if (preset_menu_items[i])
+            [preset_menu_items[i] setState:(i == n ? NSOnState : NSOffState)];
+
+    /*
+     * The Custom menu item is always right at the bottom of the
+     * Type menu.
+     */
+    [[typemenu itemAtIndex:[typemenu numberOfItems]-1]
+             setState:(n < 0 ? NSOnState : NSOffState)];
 }
 
-- (void)becomeKeyWindow
+- (void)populateTypeMenu:(NSMenu *)nsmenu from:(struct preset_menu *)menu
 {
-    int n;
+    int i;
+
+    /*
+     * We process the entries in reverse order so that (in the
+     * top-level Type menu at least) we don't disturb the 'Custom'
+     * item which remains fixed even when we change back and forth
+     * between puzzle type windows.
+     */
+    for (i = menu->n_entries; i-- > 0 ;) {
+        struct preset_menu_entry *entry = &menu->entries[i];
+        NSMenuItem *item;
+
+        if (entry->params) {
+            DataMenuItem *ditem;
+            ditem = [[[DataMenuItem alloc]
+                        initWithTitle:[NSString stringWithUTF8String:
+                                                    entry->title]
+                               action:NULL keyEquivalent:@""]
+                       autorelease];
+
+            [ditem setTarget:self];
+            [ditem setAction:@selector(presetGame:)];
+            [ditem setPayload:entry->params];
+
+            preset_menu_items[entry->id] = ditem;
+
+            item = ditem;
+        } else {
+            NSMenu *nssubmenu;
+
+            item = [[[NSMenuItem alloc]
+                        initWithTitle:[NSString stringWithUTF8String:
+                                                    entry->title]
+                               action:NULL keyEquivalent:@""]
+                       autorelease];
+            nssubmenu = newmenu(entry->title);
+            [item setSubmenu:nssubmenu];
+
+            [self populateTypeMenu:nssubmenu from:entry->submenu];
+        }
+
+        [item setEnabled:YES];
+        [nsmenu insertItem:item atIndex:0];
+    }
+}
 
+- (void)becomeKeyWindow
+{
     [self clearTypeMenu];
 
     [super becomeKeyWindow];
 
-    n = midend_num_presets(me);
+    if (!preset_menu) {
+        int i;
+        preset_menu = midend_get_presets(me, &n_preset_menu_items);
+        preset_menu_items = snewn(n_preset_menu_items, NSMenuItem *);
+        for (i = 0; i < n_preset_menu_items; i++)
+            preset_menu_items[i] = NULL;
+    }
 
-    if (n > 0) {
+    if (preset_menu->n_entries > 0) {
 	[typemenu insertItem:[NSMenuItem separatorItem] atIndex:0];
-	while (n--) {
-	    char *name;
-	    game_params *params;
-	    DataMenuItem *item;
-
-	    midend_fetch_preset(me, n, &name, &params);
-
-	    item = [[[DataMenuItem alloc]
-		     initWithTitle:[NSString stringWithUTF8String:name]
-		     action:NULL keyEquivalent:@""]
-		    autorelease];
-
-	    [item setEnabled:YES];
-	    [item setTarget:self];
-	    [item setAction:@selector(presetGame:)];
-	    [item setPayload:params];
-
-	    [typemenu insertItem:item atIndex:0];
-	}
+        [self populateTypeMenu:typemenu from:preset_menu];
     }
 
     [self updateTypeMenuTick];
diff --git a/palisade.c b/palisade.c
index b5fb165..b9d578d 100644
--- a/palisade.c
+++ b/palisade.c
@@ -1347,7 +1347,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Palisade", "games.palisade", "palisade",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/pattern.c b/pattern.c
index 78d6b5e..9a74e55 100644
--- a/pattern.c
+++ b/pattern.c
@@ -1971,7 +1971,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Pattern", "games.pattern", "pattern",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/pearl.c b/pearl.c
index 4e4290e..c6c305f 100644
--- a/pearl.c
+++ b/pearl.c
@@ -2608,7 +2608,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Pearl", "games.pearl", "pearl",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/pegs.c b/pegs.c
index 1902e16..8286851 100644
--- a/pegs.c
+++ b/pegs.c
@@ -1302,7 +1302,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Pegs", "games.pegs", "pegs",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/puzzles.h b/puzzles.h
index 1847d9c..ace6690 100644
--- a/puzzles.h
+++ b/puzzles.h
@@ -154,6 +154,54 @@ struct config_item {
 };
 
 /*
+ * Structure used to communicate the presets menu from midend to
+ * frontend. In principle, it's also used to pass the same information
+ * from game to midend, though games that don't specify a menu
+ * hierarchy (i.e. most of them) will use the simpler fetch_preset()
+ * function to return an unstructured list.
+ *
+ * A tree of these structures always belongs to the midend, and only
+ * the midend should ever need to free it. The front end should treat
+ * them as read-only.
+ */
+struct preset_menu_entry {
+    char *title;
+    /* Exactly one of the next two fields is NULL, depending on
+     * whether this entry is a submenu title or an actual preset */
+    game_params *params;
+    struct preset_menu *submenu;
+    /* Every preset menu entry has a number allocated by the mid-end,
+     * so that midend_which_preset() can return a value that
+     * identifies an entry anywhere in the menu hierarchy. The values
+     * will be allocated reasonably densely from 1 upwards (so it's
+     * reasonable for the front end to use them as array indices if it
+     * needs to store GUI state per menu entry), but no other
+     * guarantee is given about their ordering.
+     *
+     * Entries containing submenus have ids too - not only the actual
+     * presets are numbered. */
+    int id;
+};
+struct preset_menu {
+    int n_entries;             /* number of entries actually in use */
+    int entries_size;          /* space currently allocated in this array */
+    struct preset_menu_entry *entries;
+};
+/* For games which do want to directly return a tree of these, here
+ * are convenience routines (in midend.c) for constructing one. These
+ * assume that 'title' and 'encoded_params' are already dynamically
+ * allocated by the caller; the resulting preset_menu tree takes
+ * ownership of them. */
+struct preset_menu *preset_menu_new(void);
+struct preset_menu *preset_menu_add_submenu(struct preset_menu *parent,
+                                            char *title);
+void preset_menu_add_preset(struct preset_menu *menu,
+                            char *title, game_params *params);
+/* Helper routine front ends can use for one of the ways they might
+ * want to organise their preset menu usage */
+game_params *preset_menu_lookup_by_id(struct preset_menu *menu, int id);
+
+/*
  * Platform routines
  */
 
@@ -242,9 +290,7 @@ void midend_redraw(midend *me);
 float *midend_colours(midend *me, int *ncolours);
 void midend_freeze_timer(midend *me, float tprop);
 void midend_timer(midend *me, float tplus);
-int midend_num_presets(midend *me);
-void midend_fetch_preset(midend *me, int n,
-                         char **name, game_params **params);
+struct preset_menu *midend_get_presets(midend *me, int *id_limit);
 int midend_which_preset(midend *me);
 int midend_wants_statusbar(midend *me);
 enum { CFG_SETTINGS, CFG_SEED, CFG_DESC, CFG_FRONTEND_SPECIFIC };
@@ -514,6 +560,7 @@ struct game {
     const char *winhelp_topic, *htmlhelp_topic;
     game_params *(*default_params)(void);
     int (*fetch_preset)(int i, char **name, game_params **params);
+    struct preset_menu *(*preset_menu)(void);
     void (*decode_params)(game_params *, char const *string);
     char *(*encode_params)(const game_params *, int full);
     void (*free_params)(game_params *params);
diff --git a/range.c b/range.c
index 3f2bdac..588178c 100644
--- a/range.c
+++ b/range.c
@@ -1797,7 +1797,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 struct game const thegame = {
     "Range", "games.range", "range",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/rect.c b/rect.c
index 2f603cb..465e143 100644
--- a/rect.c
+++ b/rect.c
@@ -2962,7 +2962,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Rectangles", "games.rectangles", "rect",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/samegame.c b/samegame.c
index 8e428bb..88edad3 100644
--- a/samegame.c
+++ b/samegame.c
@@ -1643,7 +1643,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Same Game", "games.samegame", "samegame",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/signpost.c b/signpost.c
index 2e2dff2..ca72768 100644
--- a/signpost.c
+++ b/signpost.c
@@ -2228,7 +2228,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Signpost", "games.signpost", "signpost",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/singles.c b/singles.c
index a9b1d9d..5fe054c 100644
--- a/singles.c
+++ b/singles.c
@@ -1814,7 +1814,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Singles", "games.singles", "singles",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/sixteen.c b/sixteen.c
index 06494f5..edc9771 100644
--- a/sixteen.c
+++ b/sixteen.c
@@ -1176,7 +1176,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Sixteen", "games.sixteen", "sixteen",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/slant.c b/slant.c
index 0d3f18c..5f9f4f6 100644
--- a/slant.c
+++ b/slant.c
@@ -2150,7 +2150,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Slant", "games.slant", "slant",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/solo.c b/solo.c
index a8a67e8..0d383c3 100644
--- a/solo.c
+++ b/solo.c
@@ -5543,7 +5543,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Solo", "games.solo", "solo",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/tents.c b/tents.c
index 859b13e..4ffeb7b 100644
--- a/tents.c
+++ b/tents.c
@@ -2611,7 +2611,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Tents", "games.tents", "tents",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/towers.c b/towers.c
index 9525adb..a3a7e55 100644
--- a/towers.c
+++ b/towers.c
@@ -1978,7 +1978,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Towers", "games.towers", "towers",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/tracks.c b/tracks.c
index ca44ce1..43428a1 100644
--- a/tracks.c
+++ b/tracks.c
@@ -2622,7 +2622,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Train Tracks", "games.tracks", "tracks",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/twiddle.c b/twiddle.c
index a1d32cd..6e05f4d 100644
--- a/twiddle.c
+++ b/twiddle.c
@@ -1281,7 +1281,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Twiddle", "games.twiddle", "twiddle",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/undead.c b/undead.c
index ad0ab79..b1f536e 100644
--- a/undead.c
+++ b/undead.c
@@ -2702,7 +2702,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Undead", "games.undead", "undead",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/unequal.c b/unequal.c
index 3664788..a63b7d8 100644
--- a/unequal.c
+++ b/unequal.c
@@ -1993,7 +1993,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Unequal", "games.unequal", "unequal",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/unfinished/group.c b/unfinished/group.c
index bec826e..4a4ad6c 100644
--- a/unfinished/group.c
+++ b/unfinished/group.c
@@ -2067,7 +2067,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Group", NULL, NULL,
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/unfinished/separate.c b/unfinished/separate.c
index 898304a..a7b4fc9 100644
--- a/unfinished/separate.c
+++ b/unfinished/separate.c
@@ -823,7 +823,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Separate", NULL, NULL,
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/unfinished/slide.c b/unfinished/slide.c
index b1aa04b..9d4fce1 100644
--- a/unfinished/slide.c
+++ b/unfinished/slide.c
@@ -2320,7 +2320,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Slide", NULL, NULL,
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/unfinished/sokoban.c b/unfinished/sokoban.c
index b5533c9..2f0af35 100644
--- a/unfinished/sokoban.c
+++ b/unfinished/sokoban.c
@@ -1443,7 +1443,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Sokoban", NULL, NULL,
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/unruly.c b/unruly.c
index 616e5e5..f418efa 100644
--- a/unruly.c
+++ b/unruly.c
@@ -1912,7 +1912,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Unruly", "games.unruly", "unruly",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/untangle.c b/untangle.c
index 49366b1..ac40418 100644
--- a/untangle.c
+++ b/untangle.c
@@ -1455,7 +1455,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Untangle", "games.untangle", "untangle",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,
diff --git a/windows.c b/windows.c
index 9cc66e2..d4b3038 100644
--- a/windows.c
+++ b/windows.c
@@ -195,6 +195,11 @@ struct blitter {
 
 enum { CFG_PRINT = CFG_FRONTEND_SPECIFIC };
 
+struct preset_menuitemref {
+    HMENU which_menu;
+    int item_index;
+};
+
 struct frontend {
     const game *game;
     midend *me;
@@ -213,8 +218,9 @@ struct frontend {
     HMENU gamemenu, typemenu;
     UINT timer;
     DWORD timer_last_tickcount;
-    int npresets;
-    game_params **presets;
+    struct preset_menu *preset_menu;
+    struct preset_menuitemref *preset_menuitems;
+    int n_preset_menuitems;
     struct font *fonts;
     int nfonts, fontsize;
     config_item *cfg;
@@ -244,7 +250,6 @@ void frontend_free(frontend *fe)
     sfree(fe->colours);
     sfree(fe->brushes);
     sfree(fe->pens);
-    sfree(fe->presets);
     sfree(fe->fonts);
 
     sfree(fe);
@@ -1530,12 +1535,12 @@ static frontend *frontend_new(HINSTANCE inst)
 			      NULL, NULL, inst, NULL);
     if (!fe->hwnd) {
         DWORD lerr = GetLastError();
-        printf("no window: 0x%x\n", lerr);
+        printf("no window: 0x%x\n", (unsigned)lerr);
     }
 #endif
 
     fe->gamemenu = NULL;
-    fe->presets = NULL;
+    fe->preset_menu = NULL;
 
     fe->statusbar = NULL;
     fe->bitmap = NULL;
@@ -1658,6 +1663,46 @@ static midend *midend_for_new_game(frontend *fe, const game *cgame,
     return me;
 }
 
+static void populate_preset_menu(frontend *fe,
+                                 struct preset_menu *menu, HMENU winmenu)
+{
+    int i;
+    for (i = 0; i < menu->n_entries; i++) {
+        struct preset_menu_entry *entry = &menu->entries[i];
+        UINT_PTR id_or_sub;
+        UINT flags = MF_ENABLED;
+
+        if (entry->params) {
+            id_or_sub = (UINT_PTR)(IDM_PRESETS + 0x10 * entry->id);
+
+            fe->preset_menuitems[entry->id].which_menu = winmenu;
+            fe->preset_menuitems[entry->id].item_index =
+                GetMenuItemCount(winmenu);
+        } else {
+            HMENU winsubmenu = CreateMenu();
+            id_or_sub = (UINT_PTR)winsubmenu;
+            flags |= MF_POPUP;
+
+            populate_preset_menu(fe, entry->submenu, winsubmenu);
+        }
+
+        /*
+         * FIXME: we ought to go through and do something with ampersands
+         * here.
+         */
+
+#ifndef _WIN32_WCE
+        AppendMenu(winmenu, flags, id_or_sub, entry->title);
+#else
+        {
+            TCHAR wName[255];
+            MultiByteToWideChar(CP_ACP, 0, entry->title, -1, wName, 255);
+            AppendMenu(winmenu, flags, id_or_sub, wName);
+        }
+#endif
+    }
+}
+
 /*
  * Populate a frontend structure with a new midend structure, and
  * create any window furniture that it needs.
@@ -1799,11 +1844,16 @@ static int fe_set_midend(frontend *fe, midend *me)
 	AppendMenu(menu, MF_ENABLED, IDM_SEED, TEXT("Rando&m Seed..."));
 #endif
 
-        if (fe->presets)
-            sfree(fe->presets);
-	if ((fe->npresets = midend_num_presets(fe->me)) > 0 ||
-	    fe->game->can_configure) {
-	    int i;
+        if (!fe->preset_menu) {
+            int i;
+            fe->preset_menu = midend_get_presets(
+                fe->me, &fe->n_preset_menuitems);
+            fe->preset_menuitems = snewn(fe->n_preset_menuitems,
+                                         struct preset_menuitemref);
+            for (i = 0; i < fe->n_preset_menuitems; i++)
+                fe->preset_menuitems[i].which_menu = NULL;
+        }
+	if (fe->preset_menu->n_entries > 0 || fe->game->can_configure) {
 #ifndef _WIN32_WCE
 	    HMENU sub = CreateMenu();
 
@@ -1812,28 +1862,9 @@ static int fe_set_midend(frontend *fe, midend *me)
 	    HMENU sub = SHGetSubMenu(SHFindMenuBar(fe->hwnd), ID_TYPE);
 	    DeleteMenu(sub, 0, MF_BYPOSITION);
 #endif
-	    fe->presets = snewn(fe->npresets, game_params *);
-
-	    for (i = 0; i < fe->npresets; i++) {
-		char *name;
-#ifdef _WIN32_WCE
-		TCHAR wName[255];
-#endif
-
-		midend_fetch_preset(fe->me, i, &name, &fe->presets[i]);
 
-		/*
-		 * FIXME: we ought to go through and do something
-		 * with ampersands here.
-		 */
+            populate_preset_menu(fe, fe->preset_menu, sub);
 
-#ifndef _WIN32_WCE
-		AppendMenu(sub, MF_ENABLED, IDM_PRESETS + 0x10 * i, name);
-#else
-		MultiByteToWideChar (CP_ACP, 0, name, -1, wName, 255);
-		AppendMenu(sub, MF_ENABLED, IDM_PRESETS + 0x10 * i, wName);
-#endif
-	    }
 	    if (fe->game->can_configure) {
 		AppendMenu(sub, MF_ENABLED, IDM_CONFIG, TEXT("&Custom..."));
 	    }
@@ -1841,7 +1872,6 @@ static int fe_set_midend(frontend *fe, midend *me)
 	    fe->typemenu = sub;
 	} else {
 	    fe->typemenu = INVALID_HANDLE_VALUE;
-            fe->presets = NULL;
         }
 
 #ifdef COMBINED
@@ -2893,14 +2923,22 @@ static void update_type_menu_tick(frontend *fe)
     if (fe->typemenu == INVALID_HANDLE_VALUE)
 	return;
 
-    total = GetMenuItemCount(fe->typemenu);
     n = midend_which_preset(fe->me);
-    if (n < 0)
-	n = total - 1;		       /* "Custom" item */
 
-    for (i = 0; i < total; i++) {
-	int flag = (i == n ? MF_CHECKED : MF_UNCHECKED);
-	CheckMenuItem(fe->typemenu, i, MF_BYPOSITION | flag);
+    for (i = 0; i < fe->n_preset_menuitems; i++) {
+        if (fe->preset_menuitems[i].which_menu) {
+            int flag = (i == n ? MF_CHECKED : MF_UNCHECKED);
+            CheckMenuItem(fe->preset_menuitems[i].which_menu,
+                          fe->preset_menuitems[i].item_index,
+                          MF_BYPOSITION | flag);
+        }
+    }
+
+    if (fe->game->can_configure) {
+	int flag = (n < 0 ? MF_CHECKED : MF_UNCHECKED);
+        /* "Custom" menu item is at the bottom of the top-level Type menu */
+        total = GetMenuItemCount(fe->typemenu);
+	CheckMenuItem(fe->typemenu, total - 1, MF_BYPOSITION | flag);
     }
 
     DrawMenuBar(fe->hwnd);
@@ -3146,10 +3184,12 @@ static LRESULT CALLBACK WndProc(HWND hwnd, UINT message,
             } else
 #endif
 	    {
-		int p = ((wParam &~ 0xF) - IDM_PRESETS) / 0x10;
+                game_params *preset = preset_menu_lookup_by_id(
+                    fe->preset_menu,
+                    ((wParam &~ 0xF) - IDM_PRESETS) / 0x10);
 
-		if (p >= 0 && p < fe->npresets) {
-		    midend_set_params(fe->me, fe->presets[p]);
+		if (preset) {
+		    midend_set_params(fe->me, preset);
 		    new_game_type(fe);
 		}
 	    }
@@ -3653,7 +3693,7 @@ void split_into_argv(char *cmdline, int *argc, char ***argv,
 int WINAPI WinMain(HINSTANCE inst, HINSTANCE prev, LPSTR cmdline, int show)
 {
     MSG msg;
-    char *error;
+    char *error = NULL;
     const game *gg;
     frontend *fe;
     midend *me;