Andrew Que Sites list Photos
Projects Contact
Main

Your typical Pseudo-Random Number Generator (PRNG) will generate uniform random numbers—that is, equal odds of any number.  This is often normalized so the random numbers are between 0 and 1.  There are times we do not wish equal odds, but rather some known odds.  One way to do this is through a mapping function that will curve the numbers.  Here is a simple curving function demo:

 

 
 
Curve position: unknown
Coefficient: unknown
Standard deviation: unknown

 

The circle can be moved around to modify the curve and it also depicts odds at that point.  Try dragging it around.  The curve will always pass through the center of the circle by generating a coefficient.  The plot below the main graph is a histogram, showing the distribution of values.  Unless the distribution is uniform (a coefficient of 1) more values will by on one side as opposed to the other.

For example, if the point is at 0.4, 0.3, that means the 40% of all the random numbers will be below 0.3.  Conversely, 70% are above 0.3.  Since this is a one-to-one map transform we can simply plug in a normalized random number to generate a weighted random result.  Since the values are normalized we can scale it up (by multiplying the result by an amplitude constant) and/or offset it (adding a constant).

The function for the mapping is very simple.

y = x c { x ? R | 0 = x = 1 } { c ? R | 0 < c }

This function will map any x value between 0.0 and 1.0 which is the range of normalized PRNG.  The coefficient is any positive real number above zero.  This allows the output to be weighted more toward smaller or larger numbers.  To use the method of applying a fixed-point (as demonstrated by the circle on the plot), the following equation can be used:

c = ln y ln x

Where x and y are the coordinators of the point on the curve.  This will guarantee a coefficient that  passes through the curve.

June 28, 2020

MySQL character encoding problems

My recent articles use UTF-8 character, which apparently are not actually allowed in my database. When I exported the database and imported it on my test server, all those articles failed to display properly. Turns out this is a bit of a nightmare for people, but luckily other people have run across the problem and found a solution.

This article explains the problem I was having. When I first started using MySQL around 2003 I simply used the defaults. Tables were created using latin1 character set, but my website uses UTF-8 and allowed data to be entered as UTF-8. This wasn’t a problem until the data was exported from one database and imported into another.

I do my export/import using mysqldump. The command is as follows:

ssh -C sun-dragon mysqldump -u root --password=******** --all-databases | mysql -u root –password=**********

The fix is to treat the data as UTF-8 and simply update the database to use UTF-8 in place of Latin1. I modified my command to be:

ssh -C sun-dragon mysqldump -u root --password=******** --all-databases --skip-set-charset –default-character-set=latin1 | sed 's/CHARSET=latin1/CHARSET=utf8/' | mysql -u root –password=**********

That did the trick. The imported database now uses UTF-8 for all text and imports the data correctly. I will have to fix my original database, but for now I’m not worried about it. The Sun Dragon is slated to be replaced and the new system will have the correct setup when it imports the database.

June 27, 2020

Game Server—My Path Finding Algorithm vs the Original Trade Wars 2002

Today I will explain the results of my A* search algorithm against the original Trade Wars 2002 algorithm. As explained in previous articles, Trade Wars 2002 uses a directed graph to represent the game field. This graph typically has 1,000 or more nodes connected at random. Traversing the playing field between any two location can be done using the A* search algorithm. I wanted to test my algorithm speed against the original game and wrote a C version that would compile in DOSBox using the Borland C++ compile form 1992.

To test, I needed to slow DOSBox down to a crawl. This would make the search take longer, and the goal was to have it take long enough to measure simply by counting seconds. At a cycle speed of 103 everything was slow enough to take several seconds. I would enter a path into a running version of Trade Wars and type the last digit just as the seconds rolled over. I could then just count seconds until the results of the calculation were printed on the screen. I could do the same thing for my software which had to compute the very same route using the same game file. The results:

Trade Wars 2002 v2 wide beta 7 computed a 9-hop path on a 5000 sector universe in 10 seconds. My implementation took 4 seconds after the 2+ minute load to memory, and 42 seconds if loading data from disk as it searched. I can’t prove Trade Wars isn’t doing disk I/O during its search but I think it is unlikely. Best case I actually expected the search times to be about the same so there is a question as to why my search happens faster. One reason might be if Trade Wars dynamically allocates memory during the search. I use a fixed amount of memory, of which is likely never to be used and thus wasteful, but the fixed memory means I don’t have to ask for it during the calculation.

A second test used 12 hop.  It took Trade Wars 15 seconds after the sectors had been loaded and my search took 8 seconds for memory only.

Seeing the search speeds does answer a question I had about some checks Trade Wars does during game creation. There is a search that takes a fair amount of time looking for inaccessible sectors. I thought they might be doing a complete every-sector to every-other-sector path check. But the speeds at which this runs are for too fast for such an operation and something else must be going on.

This has been a fun experiment and proves to me that I have succeeded in implementing a path finding system for a Trade Wars directed graph style universe. That could be useful if I do end up designing a game that uses a similar playing area.

June 26, 2020

Game Server—Path Finding Mistake

There is an issue with my implementation of the path finding algorithm if I want to do a speed comparison with the original Trade Wars 2002. I implemented a bi-directional search in hopes of finding a solution faster as the problem was being attacked from two directions. However, I discovered that some of my paths did not match what the game actually calculated. This is because a Trade Wars universe isn’t fully two-way—it does contain some one-way connections. This means some routes are faster in reverse. Since my algorithm searches from both directions at once, I have a 50% chance of missing the a shortcut should it exist.

What’s funny about this fact is that when I implemented the Javascript search, I thought about this very fact. However, my implementation for the directed graph always used two-directional link. Thus I never had to worry about one-way links.

The only way around this bug is to not search in both directions. This is less efficient, but the only way not to miss one-way links. It turns out that this is a good exercise anyway. The single direction A* code uses much less memory because it doesn’t need to to have direction associated with the search path. I could entirely remove one search structure, and reduce the other to a simple array of integers. Let’s have a look:

//=============================================================================
// Uses: Find a path between two sectors.
// Date: 2020-06-26
// Author: Andrew Que <www.DrQue.net>
// Notes:
//   Uses a bi-directional A* search.
//   Designed for C99 and Borland C++ 3.1 compilers.
//=============================================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "STDINT.H"
#include "COURSE.H"

typedef enum
{
  REVERSE = -1,
  FORWARD = 1
} Direction;

// Static storage for every possible search path.
static PathNode far searchPaths[ MAX_SECTORS ];

typedef struct
{
  PathNode * path;
  Direction direction;
} TreeNode;

// The tree is a set of what sectors have been searched thus far.
static TreeNode far tree[ MAX_SECTORS ];

// The search FIFO is a list of sectors that need to be searched.
// First-In/First-Out ensures the first path found is the shortest.
typedef struct Search
{
  uint16 sector;
  Direction direction;
} Search;

static Search searchFIFO[ MAX_SECTORS ];
static unsigned searchHead = 0;
static unsigned searchTail = 0;

//-----------------------------------------------------------------------------
// Uses:
//   Add a new sector to be searched to the search FIFO.
// Input:
//   currentPath - Path thus far.
//   sector - New sector to search through.
//   direction - The direction this search is traveling.
//-----------------------------------------------------------------------------
static void queueItem
(
  PathNode * currentPath,
  unsigned sector,
  Direction direction
)
{
  // Add this sector to the new path.
  PathNode * newPath = &searchPaths[ sector ];
  newPath->sector    = sector;
  newPath->link      = currentPath;

  // Add an entry into the search tree about this path.
  tree[ sector ].path      = newPath;
  tree[ sector ].direction = direction;

  // Add sector to search FIFO.
  searchHead += 1;
  searchFIFO[ searchHead ].sector = sector;
  searchFIFO[ searchHead ].direction = direction;
}

//-----------------------------------------------------------------------------
// Uses:
//   Compute a course between sectors.
// Input:
//   sectors - List of sectors.
//   start - Sector number from which to start.
//   finish - Sector number to finish.
// Output:
//   Linked-list with the path.  `NULL` of there was no path found.
//-----------------------------------------------------------------------------
PathNode const * course( Sectors const * sectors, unsigned start, unsigned finish )
{
  // Place to hold results of search.
  // `null` means there is currently no path.
  PathNode * path = NULL;

  if ( start != finish )
  {
    // Empty search FIFO.
    searchHead = 0;
    searchTail = 0;

    // Clear search tree.
    memset( &tree, 0, sizeof( tree ) );

    // Start search form both directions.
    queueItem( NULL, start, FORWARD );
    queueItem( NULL, finish, REVERSE );

    // Search for a path, or until the search has exhausted all options.
    while ( ( NULL == path )
         && ( searchTail != searchHead ) )
    {
      unsigned sector;
      Direction direction;
      unsigned connectionIndex;
      Interconnects interconnects;

      // Path to search.
      Search const * item = &searchFIFO[ searchTail ];
      searchTail += 1;

      sector    = item->sector;
      direction = item->direction;

      getInterconnects( sectors, interconnects, sector );

      // For all the connections
      for ( connectionIndex = 0; connectionIndex < INTERCONNECTS; connectionIndex += 1 )
      {
        unsigned connection = interconnects[ connectionIndex ];

        if ( ( 0 != connection )
          && ( ! path ) )
        {
          // Is this connection already in the search tree?
          if ( 0 != tree[ connection ].path  )
          {
            TreeNode * branch = &tree[ connection ];
            if ( branch->direction == -direction )
            {
              PathNode * previous;
              PathNode * current;
              PathNode * following;

              // Join two paths together, mindful of which direction we're traversing.
              PathNode * firstSegment;
              PathNode * secondSegment;
              if ( FORWARD == direction )
              {
                firstSegment  = tree[ sector ].path;
                secondSegment = branch->path;
              }
              else
              {
                firstSegment  = branch->path;
                secondSegment = tree[ sector ].path;
              }

              // Reverse first first segment of path.
              previous  = NULL;
              current   = firstSegment;
              following = current;
              while ( current )
              {
                following = following->link;
                current->link = previous;
                previous = current;
                current = following;
              }

              path = previous;

              // Join remaining path.
              firstSegment->link = secondSegment;
            }
          }
          else
            queueItem( tree[ sector ].path, connection, direction );
        }
      }

    }
  }

  return path;
}

//-----------------------------------------------------------------------------
// Uses:
//   Print a course.
// Input:
//   path - Path found through `course` function.
//-----------------------------------------------------------------------------
void printCourse( PathNode const * path )
{
  while ( path )
  {
    char separator = '>';
    if ( ! path->link )
      separator = '\n';

    printf( " %u %c", path->sector, separator );

    path = path->link;
  }
}

June 25, 2020

Game Server—DOS Path Finding

I was curious how my bidirectional A* search I implemented in Javascript performed compared to the original Trade Wars 2002 path calculation. I am running a computer that is at least 100x faster than the computer I started running TW2002, so testing is this is going to require some emulation. DOSBox runs TW2002 just fine, but there would be no way to run Javascript there. So I need a C implementation of the same approach. I actually wanted to do this anyway because in C I believe my implementation will actually be faster.

First I started by making a pure C translation of my Javascript search algorithm. Since I have universe maps from TW2002, it is easiest simply to just use one. The sector records are fairly easy to read and I actually had code from for doing just that from various experiments with the game in years past. Once I had a universe map, I made a translation of the path finder. I made an implementation that simply loaded everything to memory and ran the search. Worked fine with GCC and my Linux console.

The next step would be to make this same code work in the MS-DOS environment. I have a copy of Borland C++ 3.1 I can use to compile my project. There would need to be a couple of changes to my code in order for this to function. My compiler dates from 1992, long before C99 standard I typically conform for C code.

First I would have to move some variable declarations. It is good practice to define local variables as close to their use as possible to limit their scope. However, in C90 standard available at the time one can only declare variables at the start of a section of scope.

Search const * item = &searchFIFO[ searchTail ];
searchTail += 1;

unsigned sector = item->sector;
Direction direction = item->direction;

for ( unsigned connectionIndex = 0; connectionIndex < INTERCONNECTS; connectionIndex += 1 )
unsigned sector;
Direction direction;
unsigned connectionIndex;
Interconnects interconnects;

Search const * item = &searchFIFO[ searchTail ];
searchTail += 1;

sector = item->sector;
direction = item->direction;

for ( connectionIndex = 0; connectionIndex < INTERCONNECTS; connectionIndex += 1 )

In addition to the variable declaration placement I had to define my own fixed-width types. C99 introduced uintN_t types where N is 8, 16, 32 and 64 for the bit length. These are defined in a system header called stdint.h. That header does not exist in the Borland compiler. Since I still wanted to be able to compile my code with a modern GNU C compiler I simply made a local header file that defines them.

//=============================================================================
// Uses: Standard integers.
// Date: 2020-06-26
// Author: Andrew Que <www.DrQue.net>
// Notes:
//   Designed for C99 and Borland C++ 3.1 compilers.
//   The old Borland compiler did not support fixed-width integers as they
//   did not become standard until 1999.  This is an intermediate file that
//   will use the C99 types if they are available or define the Borland types
//   if not.
//
//                             (C) Copyright 2020
//=============================================================================
#ifndef STDINT_H
#define STDINT_H

// Does this compiler C99 compliant?
#ifdef __STDC_VERSION__
  #if __STDC_VERSION__ >= 199901L
    // Yes, use build-in C99 types.
    #define C99
  #endif
#endif


#ifdef C99
  // If we have the C99 types, use them.
  #include <stdint.h>
  #define MEM
#else
  typedef signed char int8_t;
  typedef unsigned char uint8_t;

  typedef signed short int16_t;
  typedef unsigned short uint16_t;

  typedef signed long int32_t;
  typedef unsigned long uint32_t;

  #define MEM far

#endif

#endif // STDINT_H

The last limitation has to do with MS-DOS and Intel—annoying 640 KB barrier and x86 memory segmentation. Time for a history lesson.

Most old school DOS users can tell you about the 640 KB barrier. MS-DOS started its life as PC-DOS for the original IBM PC in 1981. This machine used an an Intel 8088 CPU, a processor released in 1979. It was an 8-bit external bus version of the 8086 released in 1978. The smaller external bus meant less pins, easier layout and cheaper support chips. From a software standpoint the two processors were identical. The 8086 only had 20 memory address bits which only allowed it to address 1 MiB of RAM as 220 = 1,048,576 (1 MiB). This wasn’t a problem for the IBM PC because it could only be expend to 256 KB of RAM. It was not until the IBM XT in 1983 that the the 640 KB limit first entered the picture. RAM addresses over 640 KiB were marked as reserved for BIOS and memory mapped devices like video memory. MS-DOS was designed with these limitations in place. As memory continued to become cheaper, there was a need to address more. Some of the reserved area above 640 KiB could be RAM known as the upper memory area.

With the advent of the Intel 80286 in 1982 it became possible to address 16 MiB of RAM as it had a 24-bit address bus. This was a problem for an architecture that was designed around 1 MiB of addressable space. To make matters worse one had to be in protected mode in order to access the full range of memory. This mode placed additional restrictions on memory, such as not allowing some memory to run code. The Intel 80386 processor came out in 1985, and like the 286 both processor booted in an 8086 compatible real mode which only allowed access to the first 1 MiB of address space. To do anything above 1 MiB one needed to have the CPU in protected mode. In theory this could provide a flat memory model which is what programmers of today are used to. But with MS-DOS it wasn’t that simple. You could not simply switch your program into protected mode and still call DOS functions. Without DOS reading and writing files is troublesome. Microsoft came up with Extended Memory (XMS) and Expanded Memory (EMS) as a workaround, but from a programming standpoint both sucked. There were other options such as DOS/4GW (used by Doom), but I never had familiarity with it. For the most part, programmers of the DOS era were stuck was being required to make my program run in less than 640 KB.

While most DOS people knew the frustration of the 640 KB barrier, it was mainly just programmers who had to worry about memory segmentation. If 640 KB was a pain, the segmentation problem was worse. For most programming environments it meant that no data set (such as an array) could be larger than 64 KB because of how data is addressed. The 8086 processor was 16-bits, but it had an address space of 20-bits or 1 MB of memory. So they introduced segmentation where memory addresses were addressed using two 16-bit words: a segment and an offset. The segment was offset by 4-bits so that the sum of these two registers produced a 20-bit address. This became a mess for programming languages. One had to use a segment register for the segment of the address, and an offset register for the offset. At the machine-level one could easily work with the offset register. But the segment register required first using some other register as an intermediate. The Intel memory model introduced 6 mode of program design to deal with this. In meant a programmer could choose the trade off between speed and how memory was addressed. The huge mode should allow access to all 640 KiB of RAM, but at the price of slowing down code and making passing around pointers more difficult.

My first problem was that the sector data exceeded 64 KB. I couldn’t get huge mode to work and settled on compact mode. However, I had made my program able to handle very large sector sizes—30,000 sectors—which was only an option in the Gold version of the game. The DOS version only had 1,000 to 5,000 sectors. That was easier to fit. I’m not sure the original game actually held all the sector data in RAM. A 5,000 sector game data file is 626 KiB and wouldn’t leave much RAM for anything else. I actually made two versions of the sector system. One was loaded interconnects fully into memory, and the other loaded off the disk.

Let’s have a look at the code change to the C implementation:

//=============================================================================
// Uses: Find a path between two sectors.
// Date: 2020-06-26
// Author: Andrew Que <www.DrQue.net>
// Notes:
//   Uses a bi-directional A* search.
//   Designed for C99 and Borland C++ 3.1 compilers.
//=============================================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "STDINT.H"
#include "COURSE.H"

typedef enum
{
  REVERSE = -1,
  FORWARD = 1
} Direction;

// Static storage for every possible search path.
static PathNode far searchPaths[ MAX_SECTORS ];

typedef struct
{
  PathNode * path;
  Direction direction;
} TreeNode;

// The tree is a set of what sectors have been searched thus far.
static TreeNode far tree[ MAX_SECTORS ];

// The search FIFO is a list of sectors that need to be searched.
// First-In/First-Out ensures the first path found is the shortest.
typedef struct Search
{
  uint16 sector;
  Direction direction;
} Search;

static Search searchFIFO[ MAX_SECTORS ];
static unsigned searchHead = 0;
static unsigned searchTail = 0;

//-----------------------------------------------------------------------------
// Uses:
//   Add a new sector to be searched to the search FIFO.
// Input:
//   currentPath - Path thus far.
//   sector - New sector to search through.
//   direction - The direction this search is traveling.
//-----------------------------------------------------------------------------
static void queueItem
(
  PathNode * currentPath,
  unsigned sector,
  Direction direction
)
{
  // Add this sector to the new path.
  PathNode * newPath = &searchPaths[ sector ];
  newPath->sector    = sector;
  newPath->link      = currentPath;

  // Add an entry into the search tree about this path.
  tree[ sector ].path      = newPath;
  tree[ sector ].direction = direction;

  // Add sector to search FIFO.
  searchHead += 1;
  searchFIFO[ searchHead ].sector = sector;
  searchFIFO[ searchHead ].direction = direction;
}

//-----------------------------------------------------------------------------
// Uses:
//   Compute a course between sectors.
// Input:
//   sectors - List of sectors.
//   start - Sector number from which to start.
//   finish - Sector number to finish.
// Output:
//   Linked-list with the path.  `NULL` of there was no path found.
//-----------------------------------------------------------------------------
PathNode const * course( Sectors const * sectors, unsigned start, unsigned finish )
{
  // Place to hold results of search.
  // `null` means there is currently no path.
  PathNode * path = NULL;

  if ( start != finish )
  {
    // Empty search FIFO.
    searchHead = 0;
    searchTail = 0;

    // Clear search tree.
    memset( &tree, 0, sizeof( tree ) );

    // Start search form both directions.
    queueItem( NULL, start, FORWARD );
    queueItem( NULL, finish, REVERSE );

    // Search for a path, or until the search has exhausted all options.
    while ( ( NULL == path )
         && ( searchTail != searchHead ) )
    {
      unsigned sector;
      Direction direction;
      unsigned connectionIndex;
      Interconnects interconnects;

      // Path to search.
      Search const * item = &searchFIFO[ searchTail ];
      searchTail += 1;

      sector    = item->sector;
      direction = item->direction;

      getInterconnects( sectors, interconnects, sector );

      // For all the connections
      for ( connectionIndex = 0; connectionIndex < INTERCONNECTS; connectionIndex += 1 )
      {
        unsigned connection = interconnects[ connectionIndex ];

        if ( ( 0 != connection )
          && ( ! path ) )
        {
          // Is this connection already in the search tree?
          if ( 0 != tree[ connection ].path  )
          {
            TreeNode * branch = &tree[ connection ];
            if ( branch->direction == -direction )
            {
              PathNode * previous;
              PathNode * current;
              PathNode * following;

              // Join two paths together, mindful of which direction we're traversing.
              PathNode * firstSegment;
              PathNode * secondSegment;
              if ( FORWARD == direction )
              {
                firstSegment  = tree[ sector ].path;
                secondSegment = branch->path;
              }
              else
              {
                firstSegment  = branch->path;
                secondSegment = tree[ sector ].path;
              }

              // Reverse first first segment of path.
              previous  = NULL;
              current   = firstSegment;
              following = current;
              while ( current )
              {
                following = following->link;
                current->link = previous;
                previous = current;
                current = following;
              }

              path = previous;

              // Join remaining path.
              firstSegment->link = secondSegment;
            }
          }
          else
            queueItem( tree[ sector ].path, connection, direction );
        }
      }

    }
  }

  return path;
}

//-----------------------------------------------------------------------------
// Uses:
//   Print a course.
// Input:
//   path - Path found through `course` function.
//-----------------------------------------------------------------------------
void printCourse( PathNode const * path )
{
  while ( path )
  {
    char separator = '>';
    if ( ! path->link )
      separator = '\n';

    printf( " %u %c", path->sector, separator );

    path = path->link;
  }
}

June 24, 2020

Game Server—Path Finding

Although I actually wanted to finish the implementation of trading in my mini web-based Trade Wars 2002 lookalike, I got distracted and instead decided to implement the path finding fetcher. It is one of the most complex things in TW2002. Let’s review the Trade Wars playing area.

The Trade Wars universe consists of a set of sectors. Each sector can have a connection to as many as 6 other sectors. Many of these connections are two-ways, but some are one-way meaning you can move into the adjacent sector but not back again. Sectors are identified by numbers, and a typical universe would contain 1000 or more sectors. Version 2 could have 5000 seconds, and the gold version goes all the way to 30000 sectors. With a couple exceptions, all of the connections between sectors in a universe are random. The exceptions are the first 10 sectors which have the same connections to one another regardless of the remaining universe. In the game you are allowed to move to any sector connected to the sector you are in. If you want to move to a sector that isn’t connected, a path would have to be computed.

Having in the past attempted to create games with an arena similar to Trade Wars I am familiar with the problem. The solution comes from the fact that the playing area is a directed graph, and thus paths through it can be calculated using the A* search algorithm. In fact, it is a fairly textbook case.

I decided to use a bidirectional A* search. This allows the search to advance two fronts: one starting at the source, and the other starting at the destination. They will meet in the middle at the shortest path between the two. The bidirectional search is only slightly more complex than unidirectional. We just need to keep track of the direction of the search.

The algorithm consists of a queue of work to be done (sectors to be searched) and a tree of what sectors have already been searched. Each item in the tree and queue contains the path that led to point, and from what direction the search was progressing. The search code is fairly small.

//-----------------------------------------------------------------------------
// Uses: Course finder.
// Date: 2020-06-19
// Author: Andrew Que (http://www.DrQue.net)
// Notes:
//   Search is a bidirectional A* algorithm.  Should be fairly fast.
//
//                          (C) 2020 by Andrew Que
//-----------------------------------------------------------------------------

"use strict"

define(
[
],
function
(
)
{
  // Value to denote a path's starting point.
  // Can be any value that is not a valid sector number.
  const START_OF_PATH = 0

  // Way to denote forward from reverse.
  // Values don't matter as long as they are different.
  const FORWARD = 1
  const REVERSE = -1

  // Add a new sector to be searched to the search FIFO and mark what
  // sector led to the new sector.
  function queueItem( coverage, searchFIFO, parent, sector, direction )
  {
    // Add an entry into the search coverage about this path.
    coverage[ sector ] =
    {
      // This is the sector that led to this one.  0 means the start of
      // the path.
      parent : parent,

      direction: direction
    }

    // Add sector to search FIFO.
    searchFIFO.push( { sector: sector, direction: direction } )
  }

  // Make a path by following the parent it back to the starting point.
  function getPath( sector, coverage )
  {
    const path = []
    while ( START_OF_PATH != sector )
    {
      path.push( sector )
      sector = coverage[ sector ].parent
    }

    return path
  }

  return function course( sectors, start, finish, avoids=[] )
  {
    // Place to hold results of search.
    // `null` means there is currently no path.
    var path = null
    var complexity = 0

    if ( ( ! ( start in sectors ) )
      || ( ! ( finish in sectors ) ) )
    {
      console.log( "Invalid course request", start, "to", finish )
    }
    else
    if ( start != finish )
    {
      // The coverage is a set of what sectors have been searched thus far.
      const coverage = {}

      // The search FIFO is a list of sectors that need to be searched.
      // First-In/First-Out ensures the first path found is the shortest.
      const searchFIFO = []

      // Start search form both directions.
      queueItem( coverage, searchFIFO, START_OF_PATH, start, FORWARD )
      queueItem( coverage, searchFIFO, START_OF_PATH, finish, REVERSE )

      // Search for a path, or until the search has exhausted all options.
      while ( ( null == path )
           && ( searchFIFO.length > 0 ) )
      {
        // Path to search.
        const item = searchFIFO.shift()
        const sector = item.sector
        const direction = item.direction

        complexity += 1

        // For all the connections...
        for ( var connection of sectors[ sector ].connections )
        {
          if ( connection in coverage )
          {
            // Is the connection coming from the opposite direction?
            // If so, we have a complete path.
            if ( coverage[ connection ].direction != direction )
            {
              // Get paths from both directions.
              const thisPath  = getPath( sector, coverage )
              const otherPath = getPath( connection, coverage )

              // Construct a complete path using the two path.
              // Which is the start depends on the direction we found the other
              // path.  The forward path must be reversed (coverage always
              // points to parent), but this is correct when traversing from
              // the opposite direction.
              if ( FORWARD == direction )
                path = thisPath.reverse().concat( otherPath )
              else
                path = otherPath.reverse().concat( thisPath )
            }

            // If the connection direction is the same, this means we have
            // already searched the connection in this direction.

          }
          else
            // If we are not avoiding this sector, add it to items to be searched.
            if ( ! avoids.includes( connection ) )
              queueItem( coverage, searchFIFO, sector, connection, direction )
        }

      }
    }
    else
      // If the beginning and end are the same, the path is the just the
      // single sector.
      // While not useful, this is a legitimate case.
      path = [ start ]

    return path
  }

})

The difficult part of this explanation is that I don’t have a good way to demonstrate the the algorithm in action. Something I will have to consider for a future article.

   Biked into work today for the first time since March as I am starting a new project and needed to go on-site to review the hardware.  On the way home I biked on State Street for the first time since the George Floyd protests.  The street is has a lot of boarded up windows and spray painted tags, but the messages everywhere seem to stand in solidarity with the protesters.

June 21, 2020

Game Server—Blinking in Terminal Emulation

Adding blinking to the terminal emulator was another task at marking the emulation complete.  CGA monitors had a built-in method for colored text.  This was done through using two bytes per character.  One contained the character to be display, and the other the color.  The color was broken into two 4-bit values, one for the foreground (text) color, and one for the background.  There were 8 colors: black , blue , green , cyan , red , purple , brown , and gray .  For foreground colors, there were bright versions of this set: dark gray , light blue , light green , light cyan , light red , light purple , yellow , and white .   For background colors, the upper 8 colors denoted that the foreground text blinked.  Programs such as DOSBox don't actually use the exact colors, opting for slightly brighter versions of each color.  I'm not sure why, but I use the pure representation.  The only thing I didn't have yet was the blinking.

HTML remove the blink element a long time ago.  However, HTML5 added the animate style which can produce the same thing.  This CSS produces a blink pretty close to the original terminal.

      .blink
      {
        animation: blinker 0.5s step-start infinite;
      }

      @keyframes blinker
      {
        50%
        {
          opacity: 0;
        }
      }

Here is some terminal output:

Enter your choice [T] ? T
<Port>
 
Docking...
 
Commerce report for Regulus Primus: Sun, Jun 28, 1:44:42 PM, 2048
 
-=-=-        Docking Log        -=-=-
No current ship docking log on file.
 
Items     Status  Trading % of max OnBoard
-----     ------  ------- -------- -------
Fuel Ore   Selling   2820    100%      20
Organics    Buying   1300    100      0
Equipment   Buying   2950    100      0
 

Now one of the other tricks that color ASCII art did was use a flashing block with a background color to do animation.

   
   FedSpacePoliceHQ
   
       
      ·    ·    
     · ·  · ·  
       ·    ·   
      · ·  · ·   
      ·    ·    
          /                \       
   

To accomplish this task required some fancy regular expressions and a lot of trial and error, but I have the results I want now.

The ASCII artwork in this article comes from Trade Wars 2002 v2 wide beta 7 by Gary Martin.

June 20, 2020

Game Server—Terminal Emulation

While I have plenty of work to do, I got side tracked on my terminal emulation.  BBSes often used ANSI escape codes to enhance text with color and create ANSII art.  The escape codes allowed colors to be added, and with the use block and line characters some artwork could be made.  IBM compatible PCs used code page 437 which isn't really an option for web browsers.  In order to produce the ANSII art from TW2002, I would need to be able to emulate the characters of code page 437.  I found a translation table on the Wikipedia page that translated the ASCII characters to UTF-8.  This allows me make a program that could convert the ANSII screens from TW into HTML.  The results are pretty effective.

  ·   ·   · ·  ·         ·    · .                 
      ·    · ·    ·   ·              ·          
   ·    · ·    ·   ·      ·    . ·   ·               
             ·  ·                    
 ·      ··   ·  ·       . ·   ·   ·                
  ·   ·        ·  ·  ·       ·      ·            
    .  ·  ·    ·    · . ·    ·  ·    · ·                 
 ·    ·    ··          ·   · ·   ·  .    · ·     ·   
    .   ·           ·  ··  ·   ·     ·    · ·     ·    · ·  ·        
 ·     ·     ·   · .       ·             ·    · · 
   
  
    
    .         ·  ·        · ·               ·    
   ·     ·        ·  ·   ·  ·    · ·           ·     ·       
  . ·   · ·    · ·    . ·        . ·        ·   . ·      
  ·· ·      · . ·    ·  ·              
 . ·    ·    ·  ·   . ·    ·     
   ·.    ·  .      ·   ·  ·   ·    
   ·   .   ·  ·         ·    ·    
    ·    ·. ·     . ·     ·      ·  ·    
  ·   . ·   ·    ·  ·   ·   ·   ·   . ·   ·    ·        · · 
   ·    ·   ·   . ·    ·         ·    ·  ·       .  · ·    ·     ·   
                                                                                
                                                                                

My biggest issue is the spacing between characters.  Adjusting line height helped but it isn't perfect.  There are still a lot of lines in the result mainly caused by background colors and characters not aligning.  However, the results are close.