Kingdom of the Lyre: Path Generation

Monday, 11th November 2019

In this series, Damian blogs about how the game works.

Having just submitted Kingdom of the Lyre to PROCJAM, I want to make a series of posts about how the game works, so that others can see an example of how to put together an interesting game in Tiny BASIC. I started development with the path generation, so I'll deal with that first. Here's the first subroutine.

    REM --- Determine available paths from an location
    REM --- Get the terrain of a location
    REM --- Inputs:  X - origin location
    REM --- Changes: C - counter
    REM ---          D - short term direction calculation
    REM ---          Y - latitude
    REM ---          Z - random number seed
    REM --- Outputs: E - Exits as a combination of:
    REM ---              1 = east
    REM ---              2 = south
    REM ---              4 = west
    REM ---              8 = north
310 LET Z=4881
    LET C=0
    LET Y=X/80
    LET X=X-80*Y
    IF X-X/2*2=Y-Y/2*2 THEN GOTO 312
    REM --- Process squares independent of their surroundings
311 GOSUB 500
    LET C=C+1
    IF C<=X+80*Y THEN GOTO 311
    IF Y=79 THEN LET R=R-R/8*8
    IF X=0 THEN LET R=R-R/4*4+R/8*8
    IF Y=0 THEN LET R=R-R/2*2+R/4*4
    IF X=79 THEN LET R=R/2*2
    LET E=R
    RETURN
    REM --- Process squares dependent on their surroundings
312 LET E=0
313 GOSUB 500
    IF Y<79 THEN IF C=X+80*(Y+1) THEN LET E=E+8*((R-R/4*4)/2)
    IF X>0 THEN IF C=X-1+80*Y THEN LET E=E+4*(R-R/2*2)
    IF Y>0 THEN IF C=X+80*(Y-1) THEN LET E=E+2*(R/8)
    IF X<79 THEN IF C=X+1+80*Y THEN LET E=E+(R-R/8*8)/4
    LET C=C+1
    IF C<=X+80*(Y+1) THEN IF C<=80*80-1 THEN GOTO 313
    RETURN

Line 990 just the Random Number Generator that you can download from the Subroutine Library, so I won't repeat it here. Another subroutine at line 500 is central to the algorithm, and is reproduced here:

    REM --- Generate a random 3-way junction
    REM --- Changes: Z - random number seed
    REM --- Outputs: R - directional exits for a 3-way junction
    REM ---              07 - west, south, east
    REM ---              11 - north, south, east
    REM ---              13 - north, west, east
    REM ---              14 - north, west, south
500 GOSUB 990
    LET R=Z-Z/4*4
    LET R=15-(R+1+R/2+R/3*3)
    RETURN

The algorithm as a whole works by dividing up the entire NxN map into a chequerboard pattern. Every one of the "black" squares has a random 3-way junction, except the ones at the edge. Here the junctions are clipped to prevent routes leading off the map. The "white" squares in between are subservient, and simply connect the black ones together.

This generates a reasonably open set of paths that might suit a city plan. It's not difficult to find your way through, but there are occasional blockages and dead ends that provide interest. It's not perfect, and it's possible to find sections that are isolated. But Kingdoms of the Lyre has a map of 80x80 locations, and apart from a few isolated edge locations, disconnected parts of the map should be rare.

The routine returns only a single map location, but it counts through all the locations from the south-west corner generating a random number for each one in order to get the value for the current location. My first attempts took a seed from the coordinates and was much quicker, but the poor quality of the random number generator revealed easily-discernible patterns across the map. So I had to resort to this slower method and hope that nobody tries to run this game on an old 8-bit micro. The game should still be reasonably responsive, especially when compiled.

This counting-through-the-map approach is used for other parts of the procedural generation, including terrain generation, which I'll cover in the next blog post.