! Z-machine Sokoban Constant NumAboutMenuItems 6; [ AboutMenuFunc ix; switch (ix) { 0: return NumAboutMenuItems; 1: return "What is Sokoban"; 2: return "How To Play"; 3: return "Contributors"; 4: return 0; 5: return "About this implementation"; 6: return "Back to previous menu"; } ]; [ About cmd; while (1) { CLS("A Tight Spot -- Z-machine Sokoban", 33, 1); cmd = Menu(AboutMenuFunc, 2, 2, screen_width-3, screen_height-1); switch (cmd) { 1: AboutSokoban(); 2: AboutBasic(); 3: AboutContributors(); 5: AboutThis(); 6: return; } WaitForKey(); } ]; [ AboutContributors; CLS("Contributors", 12); print "First of all, I would like to thank all the authors of levels contained in this release. ^^Also, special thanks go to David Holland, whose comments given to me via his e-mail inspired improvements of many shortcut features in AtS Sokoban engine. ^^The following people provided built-in solutions to this release:^^"; Credits(); "^To have your name included in future releases of this game, please send your best score output to via e-mail."; ]; [ AboutSokoban d; CLS("About Sokoban", 13); print "Sokoban was created in Japan by Hiroyuki Imabayashi of Thinking Rabbit in 1982. Although the rule of the game is very simple, some levels are quite challenging to solve. This unique quality attracted many people from all over the world to the game of Sokoban, and new levels are being invented every day. ^^The game is played in a warehouse and the objective of the game is for you to push all the crates into the destination spaces. The smaller number of moves and/or pushes to reach this objective, the better your solution is. ^^A part of a typical warehouse looks like this:^^"; ! ####### ! #: $@* ! # d = DrawCellHere; font off; d(z_wall);d(z_wall);d(z_wall);d(z_wall);d(z_wall);d(z_wall);d(z_wall); print "...^"; d(z_wall);d(z_spot);d(z_space);d(z_ware);d(z_me);d(z_warespot); new_line; d(z_wall); new_line; font on; print "^The symbols used in a map of a warehouse are:^ "; font off; d(z_me); font on; print ": you^ "; font off; d(z_wall); font on; print ": wall^ "; font off; d(z_spot); font on; print ": destination^ "; font off; d(z_ware); font on; print ": crate^ "; font off; d(z_warespot); font on; print ": crate already on a destination^"; print "^Rules. ^^ - You can move in each of the four compass directions (north, east, west, and south). You cannot move in a diagonal direction such as northeast. ^ - You or a crate can only move to an empty space or an unoccupied destination. You or a crate cannot move into a wall or another crate. ^ - You can, however, push one crate that sits next to you in the direction you are moving, provided if the space behind the crate is an empty space or an unoccupied destination. ^^"; ]; [ AboutBasic; CLS("Basic Commands", 14); "The following key commands are available while solving a level:^ ^m - open menu commands. ^n/e/w/s - move one step in north, east, west or south. ^N/E/W/S - keep moving in that direction while you can. ^u - undo previous move. ^U - undo all moves since the last push. ^r - redo after undo. ^R - redo all moves up to the next push. ^- - go to previous level in the same collection. ^+ - go to next level in the same collection. ^(number) - repeat the next command for specified number of times. ^g - specify a crate and move next to it. ^^After typing 'g', numbers are displayed around crates. Typing a number at the location you would want to go and pressing RETURN will let you move there with the smallest number of steps. ^^Typing '1' '2' 'e' 'N' 2 'u' lets you move east 12 steps, then move north until you hit a wall, and then undo 2 steps, going south by two steps. ^^For people who are used to other implementations of Sokoban, arrow keys and h/j/k/l keys can be used to move around as well. ^^This implementation of Sokoban uses main memory to record solutions you discovered if they are better than the ones that are built into the game, and when you revisit the level, your undo buffer is initialized with that solution. By using `redo' command, you can replay the solution. ^^After you have solved many levels, the memory to hold your solutions will fill up. When this happens, please save your solutions into a file from the menu command. "; ]; [ AboutThis; CLS("About AtS Implementation", 24); GameTitle(); print "^Different copies of this game contain the same set of collections and levels if their Release numbers are the same. The one with a larger serial number contains more built-in solutions contributed by the users. ^^The levels are copyright by individual authors. ^^The author of this implementation, Quim K Holland, can be reached at . ^^This is not the first Sokoban implementation for the Z-machine. Zokoban, released in 1999 by David Jacob (Jake) Wildstrom, was a simple Sokoban implementation without undo that contained 6 levels. Unfortunately, it was impossible to pack many levels with Zokoban's internal representation. This game, A Tight Spot, is an exercise of packing boxes to their destinations for the players, but it is also an exercise of packing thousands of levels compactly in the Z-machine memory. ^^If you are not interested in gory technical details of how that goal was achieved, you may want to stop here and go back to your game. Press N to stop reading; press Y to read gory technical details. [Press Y or N] "; while (1) { switch (GetAKey()) { 'y', 'Y': jump Cont; 'n', 'N': return; } _Bleep(); } .Cont; CLS("About AtS Implementation", 24); print "^Thank you :-). ^^In Zokoban (by David Jacob Wildstrom), each level is represented as an object whose property data consists of 16 bytes. The map for each level is stored in statically initialized memory as a byte array, and one square of the map uses 1 byte (0 for space, 1 for wall, 2 for crate, 3 for the player, 4 for destination, and so on). ^^With this representation, about 4 levels of size 10x20 can fit per 1 kilobyte of Z-machine low memory. Since the low memory is at most 64 kilobytes long (and other global variables must fit there as well), it is impossible to pack thousands of levels using the technique Zokoban uses. ^^The representation used by the AtS Sokoban implementation comes from a realization that the low memory is the most scarce resource in the Z-machine architecture, and a bigger amount of memory is available to store read-only data such as level map and their solutions. ^^The address space of AtS implementation is structured as follows. Addresses of undo_buffer, redo_limit, and board_buffer may be different every time you look at this picture, since what you are looking at is the current state of the game:^^"; font off; @buffer_mode 0; print ".-------------------------------. 00000^"; print "| headers and tables Inform |^"; print "| compiler generates |^"; print "|...............................|^"; print "| 240 global variables |^"; print ".-------------------------------. 0", (Hex) best_score_table, " = best_score_table^"; print "| well played solutions |^"; print ".-------------------------------. 0", (Hex) undo_buffer - BS_HDR_SIZE, " = undo_buffer^"; print "| undo/redo information for the |^"; print "| current level |^"; print "|...............................| 0", (Hex) undo_buffer+ThreeNeed(undo_ptr) - BS_HDR_SIZE, " = redo_limit^"; print "| (undo/redo grow downwards) |^"; print "| |^"; print "|...............................| 0", (Hex) board_buffer, " = board_buffer^"; print "| the current map being played |^"; print ".-------------------------------. 0", (Hex) solved_bitmap, " = solved_bitmap^"; print "| solved bitmap |^"; print ".-------------------------------. 0", (Hex) EndMem(), " = EndMem()^"; print "| tables and the dictionary |^"; print "| Inform compiler generates |^"; print ".===============================. 0", (Hex) 0-->2, " = read only memory.^"; print "| Z-code routines and strings |^"; print ".-------------------------------.^^"; @buffer_mode 1; font on; print "While in play, the program needs to store the current map for the level being played. Since symbols that can appear on a map are limited to 7 kinds (space, wall, destination, crate, crate-on-destination, player, or player-on-destination), one square of the map can be represented with 3 bits (alternatively we could represent only space, wall, and destination with 2 bits and record the location of the player and crates separately, but that is not how AtS is done). A 10x20 level uses 75 bytes of low memory with this scheme. ^^In order to support undo, the past movements of the player needs to be recorded. The movement can only be one of 4 compass directions (north, east, west, or south), one move can be recorded with 2 bits. However, AtS uses an extra bit to record if the move pushed a crate or not; otherwise the entire move history needs to be replayed to undo one move, which is not very practical. A 1000-step undo buffer uses 375 bytes of low memory with this scheme. ^^When the player solves a level with either fewer moves or pushes than the built-in solutions, AtS records these solutions in the best_score_table area. This area records a move with 2 bits, dropping ``did we push?'' information from the normal undo buffer. For each solution, an extra 8 bytes are used to hold the pointer to the next entry in this table (2 bytes), number of moves (2 bytes), number of pushes (2 bytes), and the level ID of the level the solution solves (2 bytes). Taken altogether, 20 1000-step solutions use 5160 bytes of low memory. ^^When the player solves a level even in a suboptimal way, AtS records that fact so that it can display "; style bold; print "(solved)"; style roman; print " on the title area. One bit per level is allocated statically. This release of AtS uses ", ThreeNeed(LS_LevelIdMax(),1), " bytes of low memory to record if each of the ", LS_LevelIdMax(), " distinct levels it contains has been solved. ^^When the player revisits a level that has already been solved with a solution in the best_score_table, the solution is expanded from the 2-bit format in the best_score_table to the 3-bit format of undo/redo buffer. Although the solution recorded in the best_score_table do not have ``did we push?'' information like the normal undo/redo information does, it is not necessary while redoing. ^^The above covers how the low memory is used while a level is in play, but it does not explain how the collections, levels' initial maps, and solutions are stored. They are stored in the high memory (Z-code routines and strings area). The information in this area is not directly accessible from the program with normal @@64load opcode. Z-code routines can only be called, and strings can only be printed. ^^The initial map for levels are stored as Z-machine strings. This string representation is different from the 3-bit per square representation mentioned above, because you cannot put arbitrary byte sequence in a string and expect it to be printed, even when you are printing into an array. Instead, the map is encoded using characters from 'a' to 'z'; this choice of letters lets the Z-machine pack three such characters into two bytes. The average width and height of the levels contained in this release is ", (string) LS_SizeAverageStr(), " squares, and the average length of the Z-machine string to represent these levels is ", (string) LS_BoardEncodedAverageStr(), ". In total, this release uses ", (string) LS_BoardEncodedTotalStr(), " Z-machine string characters to represent maps for ", LS_LevelIdMax(), " levels. ^^When a level is loaded, this string representation is ``printed'' using .print_to_array() to a temporary area, and then decoded into the board_buffer. ^^The only information kept while the above is happening is in either solved_bitmap or best_score_table. The area between solved_bitmap and undo_buffer therefore is used as the temporary area. ^^In order to list the collections and move between the levels contained in a collection, the program needs to be able to say, ``find the string representation of the map for the level L from the collection C''. It cannot use array of strings to implement this, because Array consumes the low memory, use of which we are trying to minimize in order to pack thousands of levels. ^^The solution is to use Z-code routines. The above request is handled by a routine called LevelSet_Data, which takes collection, level, and the address of a callback routine as its arguments. LevelSet_Data is conceptually implemented like this:"; font off; print "^^[ LevelSet_Data collection level cb; ^ if ((collection == 0) && (level == 1)) ^ return cb(19,11,81,~zmruuebibuuebdebu...~,~Author: Thinking Rabbit~); ^ else if ((collection == 0) && (level == 2)) ^ ... ^ ];"; font on; print "^^The callback routine is then called with the width (19), height (11), length of the encoded map (81 bytes), the string, and any per-level information. In addition to the routine that calls print_to_array() on the string and then decodes it into the board_buffer, this function is used to display the copyright information about the level when the user asks ``about this level'' from the menu command. ^^There was another trick necessary for this to work. If the LevelSet_Data routine were implemented as above, the routine would become too big, and the resulting code out of Inform somehow does not work. The author hasn't looked into this deep enough yet, but it seems to generate a jump instruction whose offset wraps around some limit or something like that. Also the above implementation would involve a sequential search which is very inefficient. In the real implementation, this routine is mechanically generated to use binary search (to optimize lookup) and subroutine calls (to limit the size of the routine). If computed jumps were available, it would have been very useful, but the author did not find a way to do it after looking at Z-machine specification for quite some time. ^^The solutions are stored in a similar way by encoding them into Z-machine strings and indexing using similar set of routines. ^^Other notable features in the program that require some low memory are generating the best score reports and the goto command (`g' key). Since these can happen anytime during the play, memory between redo_limit and board_buffer are used as temporary memory as necessary. ^^To generate a best score report for one solution in the best_score_table, the corresponding level's initial map is first loaded just before the board_buffer. Then the solution recorded in the best_score_table is replayed on this temporary board, and the movements are printed to the output stream 2 (game transcript file). After this is done, the solutions in the best_score_table are discarded. ^^To find the shortest path to implement the goto command using a fixed amount of memory, a flood-fill algorithm is employed. First, an area of memory is allocated just before the board_buffer and initialized to all zeros. Starting from the current player's position, each adjacent square that the player can go without pushing any crate is visited, and painted with the number (0 to 3) to record from which direction the square was visited. Then in the next round, squares adjacent to squares visited during the last round are visited and painted in the same way. This continues until no more square can be visited. Squares that were never painted in this procedure are the ones that the player cannot go without pushing any crate. To reach any square that was painted, the program simply needs to retrace the path by following the direction painted on each square, starting from the destination specified by the goto command. This temporary area uses 4 bits per square for the current map; 2 bits are used to record the directions, and the other 2 bits are used to keep track of which squares are being visited during this round, which have already been visited, and which are going to be visited the next round."; ];