sharmaeklavya2 / packing-game Goto Github PK

Slider/Text box both should work.

Maybe using double-click, but would that work for mobile users?

It will be useful to be able to import/export the progress of the game, i.e. which items are packed at what places in the bins. This can be used to save a game and resume later. We can do this by serializing to CSV or JSON.

We should also allow exporting to SVG/TikZ/PNG, because this game is a good way to create packing diagrams. This would be especially helpful if we allow a user to easily choose the input instance. (See #15 for a related issue.)

Will look good on smaller devices etc. More importantly, should help with #7.

Currently we have just 4 levels. The first one is very simple and is good for showing how the game works. The others are challenging and enjoyable.

We need more levels. They should be challenging, but not have too many items. Ideally, their solution should employ a 'cool trick'.

The game allows specifying input parameters using querystrings. Document that in the readme.

Examples:
https://sharmaeklavya2.github.io/packing-game/?srctype=gen&src=bp1&n=40&xLen=30&yLen=30
https://sharmaeklavya2.github.io/packing-game/?srctype=url&src=levels/bp/1.json

Let the user view the optimum/approximate solution with the movements to the bin or knapsack are shown using some animation.
A brute force optimum algorithm should be enough when there are smaller number of items. When there are a large number of items a switch to an approximate solution can be made.
This can be done in two ways:

1. An animated version can be shown after a person finishes solving
2. An animated version can run in parallel with the human solver.

(This is going to take considerable amount of time)

Currently the game starts with a level generated by bp1. We have more levels and generators, but the user may not know that there's more to explore or which levels to try out first. We should make changes to the UI to fix this.

One option is to add a 'story mode', where users are presented a curated list of levels one-by-one.

Another option is to add a 'feature tour' or tutorial, which highlights features like levels/generators, algorithms, zoom, save, edit.

If you press the 'unpack' button, items would be unpacked from the bins and arranged back in the inventory. This also appends an action to the action history, so that you can use undo/redo buttons.

However, we don't want to append 'unpack' to history when the bins are already empty. This will also signal the users that pressing the button didn't cause anything.

We can maybe also disable the unpack button if the bins are already empty and the items are already well-arranged in the inventory.

We'll need a place to add buttons like "I give up; Show me the solution", "put the items back", "load a new game", "show me the instructions", etc. We can probably have a navbar at the top for this.

For the "load a new game" option, we can have a dropdown/pop-up that allows the user to choose from a preset game (see the levels directory) or specify parameters for the random instance generator.

This issue is important, since almost all functionality that requires user interaction needs a place for the elements/buttons.

List of UI elements needed in toolbar/sidebar/popup:

• Load new game.
• Give up; show solution.
• Put items back in inventory.

Probably the only thing we need to do is to add CSS rules in @media (prefers-color-scheme: dark).

Pressing Ctrl+z or Cmd+z should undo the last move. We should also have a button for it so that mobile users can undo too. We should also have a redo button to undo the undo.

We can do this by recording a list of moves, where each move is the triplet (item, from_pos, to_pos). Alternatively,
for each item, we can store the list of positions, and store a list of items that were moved.

The game can be easily extended to 2D knapsack.

Currently we can only move one item at a time. Moving multiple items at once can be really useful, like if we want to move a large group of items from one bin to another.

There are 2 things to be done here:

1. Make a function that takes multiple items are arguments and the target position and moves those items to that position. This can be exposed in the developer console.
2. Implement a UI for the above function. If the user clicks outside an item and drags the pointer, we should show a selection rectangle, and the items lying inside it should get selected. Later when these items are moved, they should move together. If some other item is moved, the selection should deactivate.

I think this will require major changes to the code, i.e. instead of having one active item, we'll now have multiple active items, and we'll have to handle more states.

If loading a level fails, there is no visual indication to the user. This is especially problematic for URL-based levels on a flaky internet connection.

Currently, we have algorithms nfdh, ffdh-nf and ffdh-ff and their mirror images. These do well, but usually don't give the optimal solution. Since we usually have only a small number of items, we can work with brute-force-ish algorithms.

Issues with the current random instance generator (bp1):

• Many 1-by-1 items are present, which make the game easy.
• opt(I) is usually ceil(area(I)).

Ideally we would like small number of items that are hard to pack optimally. Maybe tweaking some parameters of bp1 would improve it, but I doubt it. bp1 was written to be easy to implement, and I didn't do any research on how to generate hard inputs.

Currently, long packing algorithms like opt-guill-ks block the main thread, which makes the UI unusable. We should have a way of running it in a non-blocking way and allow the user to cancel the algorithm.

Maybe we can wrap these algorithms in a web worker.

Another alternative is to convert these algorithms to generators, and add yield statements at appropriate points. This allows us to pause and resume them. The drawback is that it can be tricky to add yield statements appropriately. If yields are too far apart in time, then we will continue to face main-thread-blocking, and if they are too close together, then the packing algorithm's performance may get degraded.

Levels are loaded from and saved as JSON files. Document the JSON format, and give examples. This will help people create their own levels.

This would be useful for creating packing diagrams.

We should let the user choose whether to include the inventory or not, and which bins to include.

Currently, we use ceil(area) as a lower bound on the minimum number of bins. It's easy to come up with inputs where ceil(area) is far from optimal (but I don't know how true this is for 'interesting' inputs). We need something better.

These lower-bounds should either be very efficiently computable, or we should have a mechanism where a user can choose to compute them on-demand-only.

It's not possible to reproducibly try out level-generators that use randomization, because we don't use a seed in the random number generator.