Hugi Size Coding Competition

Compo 16: the Hexagon Compo


Welcome to the Hugi Size Coding Compo #16! After the big success of HC15's task, here is another challenge that TAD poses to your brain and talent.

About a year after the Soko Ban compo, it is time for another game -- this time, a cute little puzzle on a 4x8 grid of hexagons. Hexagons? Yep, this is only the first unprecedented challenge in this compo. :-)

Some of the hexagons in the grid are initially colored in blue, green or cyan, and to complete the puzzle they must all be turned black by moving on them a certain number of times (respectively one, two or three). Once a cell turns black, you cannot move to it anymore, so there can be unsolvable positions: to exit the program if you reach one of them (as well as to cover any possible embarrassment when your boss is about to catch you playing this at work) press the Esc key to instantly terminate the program.

The initial tableau is completely customizable through the command line (what task would be good without some command line handling?!?).

History

version 1.02 (Feb 11)
the test suite allows one to set DF and to rely on the final bytes of the PSP (as per general.txt)

version 1.01 (Jan 08)
assuming that a single byte on the command line is >= 4 is explicitly allowed

Step 1 : the command-line

The hexagon grid is a 4 column by 8 row array. The grid is passed to your entry on the command-line as a block of 32 ASCII characters (using '0' to '7').

The following things hold:
- the command line starts at DS:0081 hex
- there can be space character(s) before the grid
- there are 32 ascii characters ('0' to '7') for the grid
- you may assume the command-line ends with a 0D hex byte

You have to skip past leading space character(s): 

   p = 0081 hex
  
   while (byte memory[DS:p] == 32) {
       p = p+1
   }

Then extract the hexagon grid from command-line. Each byte will indicate the color of the hexagon and where the first move will be from. 0 or 4 indicate black hexagons, 1 or 5 mean it is blue, 2 or 6 indicate it is green, 3 or 7 mean it is cyan.

The hexagon whose value is >= 4 is where the cursor is at the beginning. You can assume there is only one such digit. This code assumes that cursorpos holds the cursor position and that hexgrid is a 32-byte array with value 0..3: 

   cursorpos = 0
  
   for (i=0; i<32; i++) {
    c = byte memory[DS:p]
    if ((c & 4)) {
        cursorpos = i;
    }
    p++
    hexgrid[i] = c & 3
   }

Step 2 : Drawing the hexagon grid

The hexagon grid must be drawn in mode 13h (320x200x256 colors).

When viewed as a 4x8 array, the grid must be drawn with every second row being moved to the right:

The distance between two rows is 18 pixels and the distance between two columns is 72 pixels; odd rows are shifted to the right by 36 pixels. The top address hence is calculated like in the following loop: 

   for (cell=0; cell<32; cell++) {
    row = cell / 4
    column = cell & 3
    address = 320 * 18 * row + column * 72
    if (cell & 4) address += 36
    DrawHexCell(cell, address)
   }

For now, let's examine how an hexagon is drawn. Then I'll look at the structure of each cell. A filled hexagon is made of two symmetric parts, one with increasing width and one with decreasing width. In the following pseudo-code, halfHeight is the size of each part and side is the length of the top and bottom scanline: 

   DrawHexagon (address, halfHeight, side, color)
    ofs = halfHeight
    while (ofs < 0) {
      HLine(address + ofs, side, color)
      scroff += 320
      side += 2
      ofs -= 1
    }
    while (ofs <= HalfHeight) {
      HLine(address + ofs, side, color)
      scroff += 320
      side -= 2
      ofs += 1
    }

address will point to the top-left point in the hexagon's bounding box. That is, the least x and the least y touched by DrawHexagon.

How to draw an horizontal line from a given address and with a given side should be clear... to be precise, note that if side is 16 you must draw 16 pixels: the last pixel you touch will hence be address+15, not address+16.

Each colored (i.e. not black) cell has a border. It is also hexagonal, of side 16, and is drawn in color 8 except for the hexagon under the cursor, which has a white border (color 15). Note that unlike other compos real VGA colors are important (not RGB colors). 

   DrawHexCell(cell, address):
    if (cell == cursorpos) {
       color = 15
    } else {
      color = hexgrid[cell] ? 8 : 0;
   }
  
    DrawHexagon (address + 320*2 + 2, 16, 16, color)
    DrawHexagon (address + 320*3 + 3, 15, 16, 0)

320*2 + 2 means that the bounding box is a little inset with respect to the coordinates calculated above. The second call to DrawHexagon draws the inner gap in black.

Now we draw the colored hexagon: 

    color = hexgrid[cell]
    if (color != 0) {
     side = 16 - (2 * color)
     dy = 20 - side
     dx = dy + color
     DrawHexagon (address + 320*dy + dx, side - 2, side, color)
    }

(hmmm.. can u spot an easy optimization above ? ;)

The computations might look weird, but they do look nice...

Step 3 : Check for win

This is simple: just check if all 32 bytes in the hexgrid = 0. 
   win = 1
  
   for (cell=0; cell<32; cell++) {
    if (hexgrid[cell] !=0 {
       win = 0
    }
   }
   
   If win, set text mode and exit

(Note: Steps 2 and 3 can be inverted. The test suite checks that the display is correct just before step 4, that you don't ask for a key when the tableau is empty, and that mode 3 is restored only when there is a win condition or Esc is pressed).

Step 4 : Check movement keys

Movement on a hexagon based grid is slightly more complex than on a normal square based one. Let's take another look at the tableau:

As you can see each hexagon has six neighbours. The movement must be broken down into odd and even rows to help explain things:

That is, 

                           even row              odd row
	dir   key	 delta  dx  dy         delta  dx  dy
	NW    7           -5    -1  -1          -4    -1   0
	N     8           -8     0  -2          -8     0  -2
	NE    9           -4    -1   0          -3    +1  -1
	SE    3           +4    +1   0          +5    +1  +1
	S     2           +8    +2   0          +8    +2   0
	SW    1           +3    -1  +1          +4    +1   0

Non-numeric keys need not be assigned precise meanings, but invalid numeric keys ([0456]) simply must *not* move the cursor. 

    if (key == Esc)
      goto step 6
  
    xpos = cursorpos mod 4
    ypos = cursorpos / 4

I'll assume that you have stored the data in the table above into four arrays: oddDX, oddDY, evenDX, evenDY 

    if (ypos & 1) {
      xpos += oddDX[key]
      ypos += oddDY[key]
    } else {
      xpos += evenDX[key]
      ypos += evenDY[key]
    }

Check that we are still in bounds and that we're moving to a valid hexagon: 

    if (ypos < 0) --> bad_move
    if (ypos > 7) -->  bad_move
    if (xpos < 0) -->  bad_move
    if (xpos > 3) -->  bad_move
  
    newpos = xpos + ypos * 4
    if (hexgrid[newpos] == 0) --> bad_move

If we came here, the move is good: 

    hexgrid[newpos] -= 1
    cursorpos = newpos

And if the move is not good?!? Well, do nothing and go read another key.

Of course, after each move you must go back to step 2.

That's all

Well, now it's up to you... for now, we can only hope you have fun coding this puzzle!

Now, here is some extra information you might like:

Test suite

TAD, Ruud and Bonz even provided you with a nice test-suite program. This masterpiece of MS-DOS hooking and hacking even includes a useful debug-option which allows you to view any graphical errors between their ENTRY.COM program and the built-in reference puzzle game.

You can run the test suite calling "test.bat", which feeds a few pre-cooked key sequences into your program. If you want full power, however, you must run the HEX_DBUG.COM program manually: 

        hex_dbug [-d] ENTRY-FILE [ < INPUT-FILE ]

For example, 

        hex_dbug  -D  ENTRY.COM <KEYS1

If the keys are all eaten or if you don't specify an input redirection, the program will read from the keyboard (called "interactive playing mode").

Unless you use the "-D" switch, the program will silently record mistakes in your entry without telling you when they occur (the errorlevel will report them -- that is how the test suite uses HEX_DBUG.COM). But if you use said switch, errors in the visualization will immediately bring you into debug mode; and since it is human to change your mind, even without the "-D" switch, and even without errors in your entry's display, you can enter debug mode by pressing [F1] in interactive playing mode.

The debug-mode displays a zoom-window together with an area indicated by the cursor. You can move this cursor around with either the mouse, or the normal [CURSOR] keys. You can also use the [TAB] key to cycle between the ENTRY.COM screen and the built-in reference screen.

Here is a short key reference: 

        [UP]            - move up    1 pixel
        [DOWN]          - move down     ""
        [LEFT]          - move left     ""
        [RIGHT]         - move right    ""        [SHIFT+UP]      - move up    8 pixels
        [SHIFT+DOWN]    - move down     ""
        [SHIFT+LEFT]    - move left     ""
        [SHIFT+RIGHT]   - move right    ""        [TAB]           - switches between the reference and
                          ENTRY.COM screens.        [N]             - find the next pixel-error
                          (the cursor will be moved over it).        [SPACE]         - run until the next game-loop error.        [ESC]           - turn OFF debug-mode and run as normal.                [F1]            - toggle help/zoom window mode        [F10]           - exit debug mode and fake [ESC] key press
                          (in fact, exit to DOS)

Credits for the HEX_DBUG.COM program mostly go to TAD. Ruud adapted the program to HC #10, and that's where Bonz started to write the current HEX_DBUG.COM. Bonz also wrote the test suite proper.

Some more mumbo jumbo

Besides the rules described in this document, you must comply with the general rules that apply to all Hugi size coding competitions. These are described in the file GENERAL.TXT.

If you are unsure about some detail, then just post a question to the Hugi compo mailing list at Yahoo! Groups (hugi-compo@yahoogroups.com). Please monitor it, because it is often discussed there whether some things that are valid or not (and what works or does not work on Adok's machine which is the official test bed).

Please note that passing the test suite does not guarantee that your entry has followed all the rules. It's quite possible that loop holes exist. Check the Hugi Size Coding Competion's website and/or the Yahoo! Groups mailing list for updated test suites.

Anyway, for this reason a period of public judgment occurs after the entry submission deadline, during which you and others determine penalties for rule violations.

Schedule

Here is the compo's timeline: 
   ASAP :-)                   Compo starts
   Mar 04, 2002 11:59 pm CET  Deadline for entry submission
   Mar 05, 2002               Entries and beta results released
                              Start of Public Judgment
   Mar 11, 2002 11:59 pm CET  End of Public Judgment
   Mar 12, 2002               Final results released

Submission

The address you submit your entry to is:

So... Good luck! (even though luck has nothing to do with it)

TAD & Bonz

Back to the main page