Deacon

01Sep16

I’ve just achieved the rank of “deacon” at CodeAbbey for solving one hundred and five problems.


I recently rebooted development of a project I tried to develop for the Ludum Dare 20 contest held in April 2011, the theme of which was “It’s dangerous to go alone! Take this!”

As the project will require a function for performing line-line collision detection, and as I’m interested in whether it is possible to program that function using the knowledge I’ve gained-, and the abilities I’ve developed-, studying the Introductory Algebra Review (MA004) and Visualizing Algebra (MA006) courses offered by Udacity, I’ve begun an investigation into programming that function.

In this second part of the investigation, I investigate programming a function for performing line-line collision detection when the two lines are finite in length.

★ ★ ★

If a line is imagined to be enclosed in a rectangle where \left( x_{1},y_{1} \right) are the coordinates of a corner of the rectangle and \left( x_{2},y_{2} \right) are the coordinates of the diagonally opposite corner of the rectangle, then w is the width of the rectangle – viz., w=\left| x_{2}-x_{1} \right| – and h is the height of the rectangle – viz., h=\left| y_{2}-y_{1} \right|.

It is possible to determine the horizontal midpoint (s) of a line thusly: s=\frac{x_{2}-x_{1}}{2}+x_{1}s=\frac{x_{2}-x_{1}+2x_{1}}{2}s=\frac{x_{2}+x_{1}}{2}s=\frac{x_{1}+x_{2}}{2}.

Similarly, it is possible to determine the vertical midpoint (t) of a line thusly: t=\frac{y_{2}-y_{1}}{2}+y_{1}t=\frac{y_{2}-y_{1}+2y_{1}}{2}t=\frac{y_{2}+y_{1}}{2}t=\frac{y_{1}+y_{2}}{2}.

★ ★ ★

The following table specifies the algorithm to be used to detect if two lines, which are finite in length, collide.

Horizontal line Vertical line Non-horizontal, non-vertical line
Horizontal line 1. 3. 4.
Vertical line 3. 2. 3.
Non-horizontal, non-vertical line 4. 3. 4. if non-coincident, 5. if coincident or partially coincident

1. In the first part of this investigation, it was stated that two horizontal lines that are infinite in length collide – and are coincident – if y_{A}=y_{B}, otherwise the two lines are parallel; now, with the two lines being constrained to being finite in length, two horizontal lines collide – and are coincident or partially coincident – if y_{A}=y_{B} and if the distance between the horizontal midpoints of the two lines is less than half of the sum of the widths of the two lines – viz., if \left| s_{A}-s_{B} \right|<\frac{w_{A}+w_{B}}{2}.

2. In the first part of this investigation, it was stated that two vertical lines that are infinite in length collide – and are coincident – if x_{A}=x_{B}, otherwise the two lines are parallel; now, with the two lines being constrained to being finite in length, two vertical lines collide – and are coincident or partially coincident – if x_{A}=x_{B} and if the distance between the vertical midpoints of the two lines is less than half of the sum of the heights of the two lines – viz., if \left| t_{A}-t_{B} \right|<\frac{h_{A}+h_{B}}{2}.

An amendment: In the first part of this investigation, it was stated that:

“If A is a horizontal line and B is a vertical line, then the two lines collide, and the coordinates at which the two lines collide are \left( x_{B},y_{A} \right).”

And that:

“If A is neither a horizontal nor a vertical line and B is a vertical line, then the two lines collide, and the coordinates at which the two lines collide are \left( x_{B},m_{A}x_{B}+b_{A} \right).”

As the slope-intercept form equation for a horizontal line takes the form y=mx+by=0x+by=b, the second of the passages quoted above – amended to constrain A from being a vertical line, not from being either a horizontal or a vertical line – obviates the first of the passages quoted above.

3. In the first part of this investigation, it was stated that two lines that are infinite in length collide if the first of the two lines (A) is not a vertical line and if the second of the two lines (B) is a vertical line, and that the coordinates at which the two lines collide (C) are \left( x_{B},m_{A}x_{B}+b_{A} \right); now, with the two lines being constrained to being finite in length, the two lines collide if:

  1. the distance between the x coordinate at which the two lines would collide if they were infinite in length and the horizontal midpoint of the non-vertical line is less than half the width of that line – viz., if \left| x_{\mbox{C}}-s_{A} \right|<\frac{w_{A}}{2};
  2. and the distance between the y coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the non-vertical line is either zero or less than half the height of that line – viz., if \left| y_{\mbox{C}}-t_{A} \right|=0 or \left| y_{\mbox{C}}-t_{A} \right|<\frac{h_{A}}{2};
  3. and the distance between the y coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the vertical line is less than half the height of that line – viz., if \left| y_{\mbox{C}}-t_{B} \right|<\frac{h_{B}}{2}.

4. In the first part of this investigation, it was stated that two lines that are infinite in length collide if the first of the two lines (A) is neither a horizontal nor a vertical line, the second of the two lines (B) is not a vertical line, and the two lines are neither coincident nor parallel, and that the coordinates at which the two lines collide (C) are \left( \frac{b_{B}-b_{A}}{m_{A}-m_{B}},\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}} \right); now, with the two lines being constrained to being finite in length, the two lines collide if:

  1. the distance between the x coordinate at which the two lines would collide if they were infinite in length and the horizontal midpoint of the non-horizontal, non-vertical line is less than half the width of that line – viz., if \left| x_{\mbox{C}}-s_{A} \right|<\frac{w_{A}}{2};
  2. and the distance between the y coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the non-horizontal, non-vertical line is less than half the height of that line – viz., if \left| y_{\mbox{C}}-t_{A} \right|<\frac{h_{A}}{2};
  3. and the distance between the x coordinate at which the two lines would collide if they were infinite in length and the horizontal midpoint of the non-vertical line is less than half the width of that line – viz., if \left| x_{\mbox{C}}-s_{B} \right|<\frac{w_{B}}{2};
  4. and the distance between the y coordinate at which the two lines would collide if they were infinite in length and the vertical midpoint of the non-vertical line is either zero or less than half the height of that line – viz., if \left| y_{\mbox{C}}-t_{B} \right|=0 or \left| y_{\mbox{C}}-t_{B} \right|<\frac{h_{B}}{2}.

5. In the first part of this investigation, it was stated that if two lines that are infinite in length are coincident, then those two lines collide; now, with the two lines being constrained to being finite in length, two coincident or partially coincident lines collide if the distance between the horizontal midpoints of the two lines is less than half of the sum of the widths of the two lines – viz., if \left| s_{A}-s_{B} \right|<\frac{w_{A}+w_{B}}{2}.

#ifndef LEONARDO
#error "This program requires Leonardo IDE to run."
#endif

#include <math.h>
#include <stdlib.h>
#include <syscall.h>
#include "seal_stringToInt_C.h"

/**
View( Out 0 );
ViewOrigin( Out 100, Out 100, 0 );
**/

/**
// y-axis.
Line( Out L, Out X1, Out -100, Out X2, Out 100, 0 )
  For I:InRange( I, 0, 20 )
    Assign L = ( I != 10 )?-2:-1
    Assign X1, X2 = -100 + I * 10;

// x-axis.
Line( Out L, Out -100, Out Y1, Out 100, Out Y2, 0 )
  For I:InRange( I, 0, 20 )
    Assign L = ( I != 10 )?-2:-1
    Assign Y1, Y2 = -100 + I * 10;

LineStyle( -2, Out Dashed, 0 );
LineColor( -2, Out LightGrey, 0 );
LineColor( -1, Out Grey, 0 );
**/

/**
PointSize( _, Out 3, 0 );
PointShape( _, Out Round, 0 );
**/

typedef struct t_Coordinates_struct
{
  double m_x, m_y;
}
t_Coordinates;

typedef enum
{
  k_LINE_TYPE__HORIZONTAL,
  k_LINE_TYPE__VERTICAL,
  k_LINE_TYPE__NON_HORIZONTAL_AND_NON_VERTICAL
}
t_LineType;

typedef struct t_Line_struct
{
  t_Coordinates m_begin, m_end;
  double m_width /* w. */, m_height /* h. */, m_horizontalMidpoint /* s. */, m_verticalMidpoint /* t. */, m_slope /* m. */, m_yIntercept /* b. */;
  t_LineType m_type;
}
t_Line;

t_Line f_NewLine( const double p_x1, const double p_y1, const double p_x2, const double p_y2 )
{
  t_Line line;
  line.m_begin.m_x = p_x1;
  line.m_begin.m_y = p_y1;
  line.m_end.m_x = p_x2;
  line.m_end.m_y = p_y2;
  line.m_width = fabs( p_x2 - p_x1 );
  line.m_height = fabs( p_y2 - p_y1 );
  line.m_horizontalMidpoint = ( p_x1 + p_x2 ) / 2;
  line.m_verticalMidpoint = ( p_y1 + p_y2 ) / 2;
  {
    const double delta_x = p_x2 - p_x1;
    if( delta_x == 0 )
      line.m_type = k_LINE_TYPE__VERTICAL;
    else
    {
      const double delta_y = p_y2 - p_y1;
      if( delta_y == 0 )
      {
        line.m_slope = 0;
        line.m_yIntercept = p_y1;
        line.m_type = k_LINE_TYPE__HORIZONTAL;
      }
      else
      {
        line.m_slope = delta_y / delta_x;
        line.m_yIntercept = -1 * line.m_slope * p_x1 + p_y1;
        line.m_type = k_LINE_TYPE__NON_HORIZONTAL_AND_NON_VERTICAL;
      }
    }
  }
  return line;
}

typedef enum
{
  k_LINE_LINE_COLLISION_DETECTED__NO = 0,
  k_LINE_LINE_COLLISION_DETECTED__YES,
  k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT
}
t_LineLineCollisionDetected;

typedef struct t_LineLineCollision_struct
{
  t_LineLineCollisionDetected m_detected;
  t_Coordinates m_at;
}
t_LineLineCollision;

// The following function assumes that `p_collision->m_detected == k_LINE_LINE_COLLISION_DETECTED__NO`.
// It would be helpful if Leonardo IDE treated the `inline` qualifier as a no-op if it doesn't support that qualifier…
static /* inline */ bool f_LineLineCollision_Algorithm3( const t_Line * const p_a, const t_Line * const p_b, t_LineLineCollision *p_collision )
{
  if(( p_a->m_type != k_LINE_TYPE__VERTICAL )
    && ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
  {
    p_collision->m_at.m_x = p_b->m_begin.m_x;
    p_collision->m_at.m_y = p_a->m_slope * p_b->m_begin.m_x + p_a->m_yIntercept;

    // i.
    if( !( fabs( p_collision->m_at.m_x - p_a->m_horizontalMidpoint ) < p_a->m_width / 2 ))
      goto l_END_OF_FUNCTION;

    // ii.
    {
      const double d = fabs( p_collision->m_at.m_y - p_a->m_verticalMidpoint );
      if( !(( d == 0 ) || ( d < p_a->m_height / 2 )))
        goto l_END_OF_FUNCTION;
    }

    // iii.
    if( !( fabs( p_collision->m_at.m_y - p_b->m_verticalMidpoint ) < p_b->m_height / 2 ))
      goto l_END_OF_FUNCTION;

    p_collision->m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
    l_END_OF_FUNCTION:return true;
  }
  return false;
}

// The following function assumes that `p_b->m_type != k_LINE_TYPE__VERTICAL`, that the two lines are neither coincident nor parallel, and that `p_collision->m_detected == k_LINE_LINE_COLLISION_DETECTED__NO`.
// Again, it would be helpful if Leonardo IDE treated the `inline` qualifier as a no-op if it doesn't support that qualifier…
static /* inline */ bool f_LineLineCollision_Algorithm4( const t_Line * const p_a, const t_Line * const p_b, t_LineLineCollision *p_collision )
{
  if( p_a->m_type == k_LINE_TYPE__NON_HORIZONTAL_AND_NON_VERTICAL )
  {
    p_collision->m_at.m_x = ( p_b->m_yIntercept - p_a->m_yIntercept ) / ( p_a->m_slope - p_b->m_slope );
    p_collision->m_at.m_y = ( -1 * p_b->m_slope * p_a->m_yIntercept + p_a->m_slope * p_b->m_yIntercept ) / ( p_a->m_slope - p_b->m_slope );

    // i.
    if( !( fabs( p_collision->m_at.m_x - p_a->m_horizontalMidpoint ) < p_a->m_width / 2 ))
      goto l_END_OF_FUNCTION;

    // ii.
    if( !( fabs( p_collision->m_at.m_y - p_a->m_verticalMidpoint ) < p_a->m_height / 2 ))
      goto l_END_OF_FUNCTION;

    // iii.
    if( !( fabs( p_collision->m_at.m_x - p_b->m_horizontalMidpoint ) < p_b->m_width / 2 ))
      goto l_END_OF_FUNCTION;

    // iv.
    {
      const double d = fabs( p_collision->m_at.m_y - p_b->m_verticalMidpoint );
      if( !(( d == 0 ) || ( d < p_b->m_height / 2 )))
        goto l_END_OF_FUNCTION;
    }

    p_collision->m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
    l_END_OF_FUNCTION:return true;
  }
  return false;
}

t_LineLineCollision f_LineLineCollision( const t_Line * const p_a, const t_Line * const p_b )
{
  t_LineLineCollision collision;
  collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__NO;

  // Algorithm 1.
  if(( p_a->m_type == k_LINE_TYPE__HORIZONTAL )
    && ( p_b->m_type == k_LINE_TYPE__HORIZONTAL ))
  {
    if( p_a->m_begin.m_y == p_b->m_begin.m_y )
      if( fabs( p_a->m_horizontalMidpoint - p_b->m_horizontalMidpoint ) < ( p_a->m_width + p_b->m_width ) / 2 )
        collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
    return collision;
  }

  // Algorithm 2.
  if(( p_a->m_type == k_LINE_TYPE__VERTICAL )
    && ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
  {
    if( p_a->m_begin.m_x == p_b->m_begin.m_x )
      if( fabs( p_a->m_verticalMidpoint - p_b->m_verticalMidpoint ) < ( p_a->m_height + p_b->m_height ) / 2 )
        collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
    return collision;
  }

  if( f_LineLineCollision_Algorithm3( p_a, p_b, &collision ))
    return collision;
  if( f_LineLineCollision_Algorithm3( p_b, p_a, &collision ))
    return collision;

  // Algorithm 5.
  if( p_a->m_slope == p_b->m_slope )
  {
    if( p_a->m_yIntercept == p_b->m_yIntercept )
      if( fabs( p_a->m_horizontalMidpoint - p_b->m_horizontalMidpoint ) < ( p_a->m_width + p_b->m_width ) / 2 )
        collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
    return collision;
  }

  if( f_LineLineCollision_Algorithm4( p_a, p_b, &collision ))
    return collision;
  f_LineLineCollision_Algorithm4( p_b, p_a, &collision );
  return collision;
}

FILE *g_file = NULL;

void p_Cleanup( void )
{
  if( g_file != NULL )
    fclose( g_file );
}

char *f_ReadStringFromFile( FILE *p_file, const char p_expectedTerminatorCharacter, char *p_actualTerminatorCharacter, bool *p_endOfFileEncountered )
{
  char c, *s = ( char* )malloc( sizeof( char ));
  size_t s_length = 1;
  *p_endOfFileEncountered = true;
  while( fscanf( p_file, "%c", &c ) != EOF )
  {
    if(( c == '\n' ) || ( c == p_expectedTerminatorCharacter ))
    {
      *p_actualTerminatorCharacter = c;
      *p_endOfFileEncountered = false;
      break;
    }
    s = realloc( s, s_length + 1 );
    s[ s_length - 1 ] = c;
    s_length ++;
  }
  s[ s_length - 1 ] = '\0';
  return s;
}

int f_ReadCoordinateFromFile( FILE *p_file, const char p_expectedTerminatorCharacter, const bool p_endOfFileMayBeEncountered, bool *p_endOfFileEncountered, const char * const p_coordinateLabel, const char p_lineLabel )
{
  char actual_terminator_character, *s = f_ReadStringFromFile( p_file, p_expectedTerminatorCharacter, &actual_terminator_character, p_endOfFileEncountered );
  int coordinate;
  if( *p_endOfFileEncountered && !p_endOfFileMayBeEncountered )
  {
    free( s );
    fprintf( stderr, "Sorry, an error occurred: the end of the test data file was unexpectedly encountered whilst trying to read the %s coordinate of line %c.\n", p_coordinateLabel, p_lineLabel );
    exit( EXIT_FAILURE );
  }
  if( !*p_endOfFileEncountered && ( actual_terminator_character != p_expectedTerminatorCharacter ))
  {
    free( s );
    fprintf( stderr, "Sorry, an error occurred: an end of line was unexpectedly encountered whilst trying to read the %s coordinate of line %c.\n", p_coordinateLabel, p_lineLabel );
    exit( EXIT_FAILURE );
  }
  coordinate = f_seal_StringToInt_C( s );
  if( f_seal_StringToInt_Error_C() != k_seal_STRING_TO_INT_ERROR_C__NONE )
  {
    fprintf( stderr, "Sorry, an error occurred: the string \"%s\" could not be converted into an int/the %s coordinate of line %c.\n", s, p_coordinateLabel, p_lineLabel );
    free( s );
    exit( EXIT_FAILURE );
  }
  free( s );
  if(( coordinate < -10 ) || ( coordinate > 10 ))
  {
    fprintf( stderr, "Sorry, an error occurred: the %s coordinate of line %c is not [ -10, 10 ].\n", p_coordinateLabel, p_lineLabel );
    exit( EXIT_FAILURE );
  }
  return coordinate;
}

t_Line f_ReadLineFromFile( FILE *p_file, bool *p_endOfFileEncountered, const char p_lineLabel )
{
  int x1, y1, x2, y2;
  x1 = f_ReadCoordinateFromFile( p_file, ' ', false, p_endOfFileEncountered, "x1", p_lineLabel );
  y1 = f_ReadCoordinateFromFile( p_file, ' ', false, p_endOfFileEncountered, "y1", p_lineLabel );
  x2 = f_ReadCoordinateFromFile( p_file, ' ', false, p_endOfFileEncountered, "x2", p_lineLabel );
  y2 = f_ReadCoordinateFromFile( p_file, ( p_lineLabel == 'A' )?' ':'\n', p_lineLabel != 'A', p_endOfFileEncountered, "y2", p_lineLabel );
  return f_NewLine( x1, y1, x2, y2 );
}

void main( void )
{
  t_Line A;
  /**
  Point( Out 1, Out X, Out Y, 0 )
    Assign X = A.m_begin.m_x * 10 Y = A.m_begin.m_y * -10;
  Point( Out 1, Out X, Out Y, 0 )
    Assign X = A.m_end.m_x * 10 Y = A.m_end.m_y * -10;
  PointColor( 1, Out Magenta, 0 );
  Line( Out 1, Out X1, Out Y1, Out X2, Out Y2, 0 )
    Assign X1 = A.m_begin.m_x * 10 Y1 = A.m_begin.m_y * -10
    Assign X2 = A.m_end.m_x * 10 Y2 = A.m_end.m_y * -10;
  LineColor( 1, Out Magenta, 0 );
  **/
  bool end_of_file_encountered;
  t_Line B;
  /**
  Point( Out 2, Out X, Out Y, 0 )
    Assign X = B.m_begin.m_x * 10 Y = B.m_begin.m_y * -10;
  Point( Out 2, Out X, Out Y, 0 )
    Assign X = B.m_end.m_x * 10 Y = B.m_end.m_y * -10;
  PointColor( 2, Out Cyan, 0 );
  Line( Out 2, Out X1, Out Y1, Out X2, Out Y2, 0 )
    Assign X1 = B.m_begin.m_x * 10 Y1 = B.m_begin.m_y * -10
    Assign X2 = B.m_end.m_x * 10 Y2 = B.m_end.m_y * -10;
  LineColor( 2, Out Cyan, 0 );
  **/
  t_LineLineCollision collision;
  /**
  Ellipse( Out 3, Out TopLeftX, Out TopLeftY, Out 6, Out 6, 0 )
    Assign TopLeftX = collision.m_at.m_x * 10 - 2
    Assign TopLeftY = collision.m_at.m_y * -10 - 2;
  **/
  bool collision_detected = false;
  /**
  EllipseFrameColor( 3, Out C, 0 )
    Assign C = ( !collision_detected )?Magenta:LightGreen;
  **/
  atexit( p_Cleanup );
  printf( "Please select the test data file.\n" );
  printf( "\n" );
  {
    char file_path[ 1024 ];
    if( GetFileDialog( file_path ) == 0 )
    {
      fprintf( stderr, "Sorry, an error occurred: no test data file was selected.\n" );
      exit( EXIT_FAILURE );
    }
    if(( g_file = fopen( file_path, "r" )) == NULL )
    {
      fprintf( stderr, "Sorry, an error occurred: the selected test data file \"%s\" could not be opened.\n", file_path );
      exit( EXIT_FAILURE );
    }
  }
  do
  {
    A = f_ReadLineFromFile( g_file, &end_of_file_encountered, 'A' );
    B = f_ReadLineFromFile( g_file, &end_of_file_encountered, 'B' );
    collision.m_at.m_x = 0;
    collision.m_at.m_y = 0;
    collision = f_LineLineCollision( &A, &B );
    collision_detected = collision.m_detected != k_LINE_LINE_COLLISION_DETECTED__NO;
    if( !collision.m_detected )
      printf( "No c" );
    else
      printf( "C" );
    printf( "ollision detected" );
    if( collision.m_detected == k_LINE_LINE_COLLISION_DETECTED__YES )
      printf( " at ( %f, %f )", collision.m_at.m_x, collision.m_at.m_y );
    else
      if( collision.m_detected == k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT )
        printf( " – the lines are coincident" );
    printf( ".\n" );
    printf( "\n" );
    printf( "Please press the Return key to %s.", ( !end_of_file_encountered )?"continue":"quit this program" );
    {
      char ignored_char;
      bool ignored_bool;
      free( f_ReadStringFromFile( stdin, '\n', &ignored_char, &ignored_bool ));
    }
    if( !end_of_file_encountered )
      printf( "\n" );
  }
  while( !end_of_file_encountered );
  exit( EXIT_SUCCESS );
}

I recently rebooted development of a project I tried to develop for the Ludum Dare 20 contest held in April 2011, the theme of which was “It’s dangerous to go alone! Take this!”

As the project will require a function for performing line-line collision detection, and as I’m interested in whether it is possible to program that function using the knowledge I’ve gained-, and the abilities I’ve developed-, studying the Introductory Algebra Review (MA004) and Visualizing Algebra (MA006) courses offered by Udacity, I’ve begun an investigation into programming that function.

In this first part of the investigation, I investigate programming a function for performing line-line collision detection when the two lines are infinite in length.

★ ★ ★

The inputs to the function for performing line-line collision detection will be two lines (hereafter A and B), with a line being two pairs of x and y coordinates – viz., \left\{ \left( x_{1},y_{1} \right),\left( x_{2},y_{2} \right) \right\}.

If a line is not a vertical line, it is possible to determine the slope (m) of that line thusly:
m=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}
A horizontal line – viz., a line where y_{1}=y_{2} – has a slope of 0, as m=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}m=\frac{0}{x_{2}-x_{1}}m=0.
A vertical line – viz., a line where x_{1}=x_{2} – has an undefined slope, as m=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}m=\frac{y_{2}-y_{1}}{0}m=undefined.

If a line is not a vertical line, it is possible to determine the y-intercept (b) of that line by rearranging the equation for a line in slope-intercept form (y=mx+b) thusly:

  1. y=mx+b
  2. y-b=mx+b-by-b=mx
  3. y-y-b=mx-y-b=mx-y
  4. -1\left( -b \right)=-1\left( mx-y \right)b=-mx+y

If a line is not a vertical line, it is possible to make x the subject of the equation for a line in slope-intercept form by rearranging that equation thusly:

  1. y=mx+b
  2. y-b=mx+b-by-b=mx
  3. \frac{y-b}{m}=\frac{mx}{m}\frac{y-b}{m}=xx=\frac{y-b}{m}

If neither of the two lines is a vertical line, and if at most one of the two lines is a horizontal line, it is possible to arrive at a formula for the x coordinate where the two lines intersect by setting the slope-intercept form equations for the two lines equal to each other and rearranging thusly:

  1. m_{A}x+b_{A}=m_{B}x+b_{B}
  2. m_{A}x+b_{A}-b_{A}=m_{B}x+b_{B}-b_{A}m_{A}x=m_{B}x+b_{B}-b_{A}
  3. m_{A}x-m_{B}x=m_{B}x-m_{B}x+b_{B}-b_{A}m_{A}x-m_{B}x=b_{B}-b_{A}
  4. \left( x \right)\left( m_{A}-m_{B} \right)=b_{B}-b_{A}
  5. \frac{\left( x \right)\left( m_{A}-m_{B} \right)}{\left( m_{A}-m_{B} \right)}=\frac{b_{B}-b_{A}}{\left( m_{A}-m_{B} \right)}x=\frac{b_{B}-b_{A}}{m_{A}-m_{B}}

This formula cannot be used if either or both of the two lines is a vertical line, as either m_{A} or/and m_{B} will be undefined.
Similarly, this formula cannot be used if both of the two lines are horizontal lines, as m_{A}=m_{B}, so m_{A}-m_{B}=0, and so x=\frac{b_{B}-b_{A}}{m_{A}-m_{B}}x=\frac{b_{B}-b_{A}}{0}x=undefined.

If neither of the two lines is a vertical line, and if at most one of the two lines is a horizontal line, it is possible to arrive at a formula for the y coordinate where the two lines intersect by setting the slope-intercept form equations for the two lines – rearranged to make x the subject of those equations – equal to each other and rearranging thusly:

  1. \frac{y-b_{A}}{m_{A}}=\frac{y-b_{B}}{m_{B}}
  2. \left( m_{A} \right)\left( m_{B} \right)\left( \frac{y-b_{A}}{m_{A}} \right)=\left( m_{A} \right)\left( m_{B} \right)\left( \frac{y-b_{B}}{m_{B}} \right)\left( m_{B} \right)\left( y-b_{A} \right)=\left( m_{A} \right)\left( y-b_{B} \right)
  3. \left( m_{B} \right)\left( y-b_{A} \right)=\left( m_{A} \right)\left( y-b_{B} \right)m_{B}y-m_{B}b_{A}=m_{A}y-m_{A}b_{B}
  4. m_{B}y-m_{B}b_{A}+m_{A}b_{B}=m_{A}y-m_{A}b_{B}+m_{A}b_{B}m_{B}y-m_{B}b_{A}+m_{A}b_{B}=m_{A}y
  5. m_{B}y-m_{B}y-m_{B}b_{A}+m_{A}b_{B}=m_{A}y-m_{B}y-m_{B}b_{A}+m_{A}b_{B}=m_{A}y-m_{B}y
  6. -m_{B}b_{A}+m_{A}b_{B}=\left( y \right)\left( m_{A}-m_{B} \right)
  7. \frac{-m_{B}b_{A}+m_{A}b_{B}}{\left( m_{A}-m_{B} \right)}=\frac{\left( y \right)\left( m_{A}-m_{B} \right)}{\left( m_{A}-m_{B} \right)}\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}}=yy=\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}}

This formula cannot be used if either or both of the two lines is a vertical line, as either m_{A} or/and m_{B} will be undefined.
Similarly, this formula cannot be used if both of the two lines are horizontal lines, as m_{A}=m_{B}, so m_{A}-m_{B}=0, and so y=\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}}y=\frac{-m_{B}b_{A}+m_{A}b_{B}}{0}y=undefined.

★ ★ ★

If both of the two lines are horizontal lines, then the two lines collide – and are coincident – if y_{A}=y_{B}, otherwise the two lines are parallel.

If both of the two lines are vertical lines, then the two lines collide – and are coincident – if x_{A}=x_{B}, otherwise the two lines are parallel.

If A is a horizontal line and B is a vertical line, then the two lines collide, and the coordinates at which the two lines collide are \left( x_{B},y_{A} \right).

If A is a vertical line and B is neither a horizontal nor a vertical line, then the two lines collide, and the coordinates at which the two lines collide are \left( x_{A},m_{B}x_{A}+b_{B} \right).

If neither of the two lines is a vertical line, at most one of the two lines is a horizontal line, and the two lines are neither coincident nor parallel, then the two lines collide, and the coordinates at which the two lines collide are \left( \frac{b_{B}-b_{A}}{m_{A}-m_{B}},\frac{-m_{B}b_{A}+m_{A}b_{B}}{m_{A}-m_{B}} \right).

If the two lines are coincident, then the two lines collide.

#ifndef LEONARDO
#error "This program requires Leonardo IDE to run."
#endif

#include "seal_stringToInt_C.h"

/**
View( Out 0 );
ViewOrigin( Out 100, Out 100, 0 );

// y-axis.
Line( Out L, Out X1, Out -100, Out X2, Out 100, 0 )
  For I:InRange( I, 0, 20 )
    Assign L = ( I != 10 )?-2:-1
    Assign X1, X2 = -100 + I * 10;

// x-axis.
Line( Out L, Out -100, Out Y1, Out 100, Out Y2, 0 )
  For I:InRange( I, 0, 20 )
    Assign L = ( I != 10 )?-2:-1
    Assign Y1, Y2 = -100 + I * 10;

LineColor( -1, Out Grey, 0 );
LineColor( -2, Out LightGrey, 0 );
LineStyle( -2, Out Dashed, 0 );

PointShape( _, Out Round, 0 );
PointSize( _, Out 3, 0 );
**/

typedef struct t_Coordinates_struct
{
  double m_x, m_y;
}
t_Coordinates;

typedef enum
{
  k_LINE_TYPE__STANDARD,
  k_LINE_TYPE__HORIZONTAL,
  k_LINE_TYPE__VERTICAL
}
t_LineType;

typedef struct t_Line_struct
{
  t_Coordinates m_begin, m_end;
  double m_slope /* m. */, m_yIntercept /* b. */;
  t_LineType m_type;
}
t_Line;

void p_DetermineSlopeAndTypeOfLine( t_Line *p )
{
  const double delta_x = p->m_end.m_x - p->m_begin.m_x;
  if( delta_x == 0 )
    p->m_type = k_LINE_TYPE__VERTICAL;
  else
  {
    const double delta_y = p->m_end.m_y - p->m_begin.m_y;
    if( delta_y == 0 )
    {
      p->m_slope = 0;
      p->m_type = k_LINE_TYPE__HORIZONTAL;
    }
    else
    {
      p->m_slope = delta_y / delta_x;
      p->m_type = k_LINE_TYPE__STANDARD;
    }
  }
}

void p_DetermineYInterceptOfLine( t_Line *p )
{
  p->m_yIntercept = -1 * p->m_slope * p->m_begin.m_x + p->m_begin.m_y;
}

#define M_ASSIGN_ARGUMENT_TO_COORDINATE( p_line, p_coordinates /* `begin` or `end`. */, p_coordinate /* `x` or `y`. */ ) \
  p_line .m_ ## p_coordinates .m_ ## p_coordinate = f_seal_StringToInt_C( argv[ i ] );                                   \
  if(( f_seal_StringToInt_Error_C() != k_seal_STRING_TO_INT_ERROR_C__NONE )                                              \
    || ( p_line .m_ ## p_coordinates .m_ ## p_coordinate < -10 )                                                         \
    || ( p_line .m_ ## p_coordinates .m_ ## p_coordinate > 10 ))                                                         \
  {                                                                                                                      \
    error_occurred = true;                                                                                               \
    goto l_ERROR_OCCURRED;                                                                                               \
  }                                                                                                                      \
  i ++;

void p_PrintLine( const char * const p_lineName, const t_Line * const p_line )
{
  printf( "%s: { ( %d, %d ), ( %d, %d ) }", p_lineName, ( int )p_line->m_begin.m_x, ( int )p_line->m_begin.m_y, ( int )p_line->m_end.m_x, ( int )p_line->m_end.m_y );
  if( p_line->m_type != k_LINE_TYPE__STANDARD )
    printf( " (%sal)", ( p_line->m_type == k_LINE_TYPE__HORIZONTAL )?"Horizont":"Vertic" );
  printf( "\n" );
  printf( "   m = " );
  if( p_line->m_type != k_LINE_TYPE__VERTICAL )
    printf( "%f", p_line->m_slope );
  else
    printf( "Undefined" );
  printf( "\n" );
  printf( "   b = " );
  if( p_line->m_type != k_LINE_TYPE__VERTICAL )
    printf( "%f", p_line->m_yIntercept );
  else
    printf( "Undefined" );
  printf( "\n" );
}

typedef enum
{
  k_LINE_LINE_COLLISION_DETECTED__NO = 0,
  k_LINE_LINE_COLLISION_DETECTED__YES,
  k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT
}
t_LineLineCollisionDetected;

typedef struct t_LineLineCollision_struct
{
  t_LineLineCollisionDetected m_detected;
  t_Coordinates m_at;
}
t_LineLineCollision;

t_LineLineCollision f_LineLineCollision( const t_Line * const p_a, const t_Line * const p_b )
{
  t_LineLineCollision collision;
  collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__NO;
  if(( p_a->m_type == k_LINE_TYPE__VERTICAL )
    && ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
  {
    if( p_a->m_begin.m_x == p_b->m_begin.m_x )
      collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
    return collision;
  }
  if(( p_a->m_type == k_LINE_TYPE__HORIZONTAL )
    && ( p_b->m_type == k_LINE_TYPE__HORIZONTAL ))
  {
    if( p_a->m_begin.m_y == p_b->m_begin.m_y )
      collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
    return collision;
  }
  if(( p_a->m_type == k_LINE_TYPE__HORIZONTAL )
    && ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
  {
    collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
    collision.m_at.m_x = p_b->m_begin.m_x;
    collision.m_at.m_y = p_a->m_begin.m_y;
    return collision;
  }
  if(( p_a->m_type == k_LINE_TYPE__VERTICAL )
    && ( p_b->m_type == k_LINE_TYPE__HORIZONTAL ))
  {
    collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
    collision.m_at.m_x = p_a->m_begin.m_x;
    collision.m_at.m_y = p_b->m_begin.m_y;
    return collision;
  }
  if(( p_a->m_type == k_LINE_TYPE__STANDARD )
    && ( p_b->m_type == k_LINE_TYPE__VERTICAL ))
  {
    collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
    collision.m_at.m_x = p_b->m_begin.m_x;
    collision.m_at.m_y = p_a->m_slope * p_b->m_begin.m_x + p_a->m_yIntercept;
    return collision;
  }
  if(( p_a->m_type == k_LINE_TYPE__VERTICAL )
    && ( p_b->m_type == k_LINE_TYPE__STANDARD ))
  {
    collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
    collision.m_at.m_x = p_a->m_begin.m_x;
    collision.m_at.m_y = p_b->m_slope * p_a->m_begin.m_x + p_b->m_yIntercept;
    return collision;
  }
  if( p_a->m_slope == p_b->m_slope )
  {
    if( p_a->m_yIntercept == p_b->m_yIntercept )
      collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT;
    return collision;
  }
  collision.m_detected = k_LINE_LINE_COLLISION_DETECTED__YES;
  collision.m_at.m_x = ( p_b->m_yIntercept - p_a->m_yIntercept ) / ( p_a->m_slope - p_b->m_slope );
  collision.m_at.m_y = ( -1 * p_b->m_slope * p_a->m_yIntercept + p_a->m_slope * p_b->m_yIntercept ) / ( p_a->m_slope - p_b->m_slope );
  return collision;
}

int main( const int argc, const char * const argv[] )
{
  bool error_occurred = false;
  if( argc != 8 )
    error_occurred = true;
  else
  {
    t_Line A, B;
    int i = 0;
    t_LineLineCollision collision;
    M_ASSIGN_ARGUMENT_TO_COORDINATE( A, begin, x )
    M_ASSIGN_ARGUMENT_TO_COORDINATE( A, begin, y )
    M_ASSIGN_ARGUMENT_TO_COORDINATE( A, end, x )
    M_ASSIGN_ARGUMENT_TO_COORDINATE( A, end, y )
    /**
    Point( Out 1, Out X, Out Y, 0 )
      Assign X = A.m_begin.m_x * 10 Y = A.m_begin.m_y * -10;
    Point( Out 1, Out X, Out Y, 0 )
      Assign X = A.m_end.m_x * 10 Y = A.m_end.m_y * -10;
    PointColor( 1, Out Magenta, 0 );
    Line( Out 1, Out X1, Out Y1, Out X2, Out Y2, 0 )
      Assign X1 = A.m_begin.m_x * 10 Y1 = A.m_begin.m_y * -10
      Assign X2 = A.m_end.m_x * 10 Y2 = A.m_end.m_y * -10;
    LineColor( 1, Out Magenta, 0 );
    **/
    p_DetermineSlopeAndTypeOfLine( &A );
    if( A.m_type != k_LINE_TYPE__VERTICAL )
      p_DetermineYInterceptOfLine( &A );
    p_PrintLine( "A", &A );

    M_ASSIGN_ARGUMENT_TO_COORDINATE( B, begin, x )
    M_ASSIGN_ARGUMENT_TO_COORDINATE( B, begin, y )
    M_ASSIGN_ARGUMENT_TO_COORDINATE( B, end, x )
    M_ASSIGN_ARGUMENT_TO_COORDINATE( B, end, y )
    #undef M_ASSIGN_ARGUMENT_TO_COORDINATE
    /**
    Point( Out 2, Out X, Out Y, 0 )
      Assign X = B.m_begin.m_x * 10 Y = B.m_begin.m_y * -10;
    Point( Out 2, Out X, Out Y, 0 )
      Assign X = B.m_end.m_x * 10 Y = B.m_end.m_y * -10;
    PointColor( 2, Out Cyan, 0 );
    Line( Out 2, Out X1, Out Y1, Out X2, Out Y2, 0 )
      Assign X1 = B.m_begin.m_x * 10 Y1 = B.m_begin.m_y * -10
      Assign X2 = B.m_end.m_x * 10 Y2 = B.m_end.m_y * -10;
    LineColor( 2, Out Cyan, 0 );
    **/
    p_DetermineSlopeAndTypeOfLine( &B );
    if( B.m_type != k_LINE_TYPE__VERTICAL )
      p_DetermineYInterceptOfLine( &B );
    p_PrintLine( "B", &B );

    collision = f_LineLineCollision( &A, &B );
    if( !collision.m_detected )
      printf( "No c" );
    else
      printf( "C" );
    printf( "ollision detected" );
    if( collision.m_detected == k_LINE_LINE_COLLISION_DETECTED__YES )
    {
      printf( " at ( %f, %f )", collision.m_at.m_x, collision.m_at.m_y );
      /**
      Ellipse( Out 0, Out TopLeftX, Out TopLeftY, Out 6, Out 6, 0 )
        Assign TopLeftX = collision.m_at.m_x * 10 - 2
        Assign TopLeftY = collision.m_at.m_y * -10 - 2;
      EllipseFrameColor( 0, Out LightGreen, 0 );
      **/
    }
    else
      if( collision.m_detected == k_LINE_LINE_COLLISION_DETECTED__YES__COINCIDENT )
        printf( " – the lines are coincident" );
    printf( ".\n" );

    l_ERROR_OCCURRED:;
  }
  if( error_occurred )
    printf( "Sorry, an error occurred: this program expects to have passed to it eight integer ([ -10, 10 ]) arguments.\n" );
  while( true ); // The lines declared in this function are no longer drawn after this function terminates😦
}

Fanatic

29Jun16

I’ve just achieved the rank of “fanatic” at CodeAbbey for solving eighty-five problems.


[…]

The Advent Programming Contest, being organized by the IEEE Student Branch Klagenfurt[,] will provide a new problem every day from December 1st to December 24th. You can submit solutions any day until the contest ends on December 26[th]. You can choose to use C, C++, C#, Java, Perl, Python 2.x or Python 3.x as programming language.

[…]

Until a solution is correct you can submit your program as often as you want (but please don’t spam our server).

[…]

The event is open to everyone.

[…]

If you want to participate, please register at http://mooshak.nes.aau.at/ (Registration is also possible after 1st December)[.]

– Wilfried Elmenreich

Source: Advent Programming Contest 2015 [Self-Organizing Networked Systems, 30th November 2015]


Interrogating a Sony PlayStation 2 DualShock 2 controller; I've yet to figure out why SDL2 reports that the DualShock 2 has five axes (although my PlayStation-to-USB adapter might be to blame), I've yet to figure out a solution – which doesn't involve a ⅓ axis dead zone – to the problem of the thumbsticks on the DualShock 2 not always returning all the way to the origin when they're released, and I last touched a DualShock 2 a long, long time ago so I'd forgotten that the D-pad is disabled in analogue mode :/

Interrogating a Sony PlayStation 2 DualShock 2 controller; I’ve yet to figure out why SDL2 reports that the DualShock 2 has five axes (although my PlayStation-to-USB adapter might be to blame), I’ve yet to figure out a solution – which doesn’t involve a ⅓ axis dead zone – to the problem of the thumbsticks on the DualShock 2 not always returning all the way to the origin when they’re released, and I last touched a DualShock 2 a long, long time ago so I’d forgotten that the D-pad is disabled in analogue mode:/

I recently rebooted development of a project I tried to develop for the Ludum Dare 20 contest held in April 2011, the theme of which was “It’s dangerous to go alone! Take this!”

As the project will require a controller with an analogue stick to play I’ve begun to develop a utility to interrogate the capabilities of various controllers – and as I feel that the SDL2 documentation is lacking with regards to the joystick support offered by that library I’m posting here the source code to the third version of that utility, for the benefit both of myself and of others.

SDL2 joystick interrogator.mm:

#include <SDL2/SDL.h>
#include "seal_intToString.h"
#include "seal_stringConcatenation.h"
#include "seal_stringQueue.h"
#include "seal_tree.h"
#include "seal_tileBackground.h"

void p_StringToTileBackground( const char * const p_string, seal_TileBackground *p_tileBackground )
{
  const size_t transparent_sub_texture = 10 /* '0'..'9' */ + 26 /* 'A'..'Z' */ + 5 /* '+', '-', '.', '(', ')' */;
  p_tileBackground->p_SetAllSubTextures( transparent_sub_texture );
  size_t i = 0;
  int x = 0, y = p_tileBackground->f_Height() - 1;
  for( ; i < strlen( p_string ); i ++, x ++ )
  {
    const char character = p_string[ i ];
    size_t sub_texture = transparent_sub_texture;
    if(( character >= '0' ) && ( character <= '9' ))
      sub_texture = character - '0';
    else
      if(( character >= 'a' ) && ( character <= 'z' ))
        sub_texture = character - 'a' + 10;
      else
        if(( character >= 'A' ) && ( character <= 'Z' ))
          sub_texture = character - 'A' + 10;
        else
          switch( character )
          {
            case '+': sub_texture = 36; break;
            case '-': sub_texture = 37; break;
            case '.': sub_texture = 38; break;
            case '(': sub_texture = 39; break;
            case ')': sub_texture = 40;
          }
    if( character == '\n' )
    {
      x = -1;
      y --;
    }
    else
      p_tileBackground->p_SetSubTexture( x, y, sub_texture );
  }
}

static seal_Texture *g_font;
static seal_TileBackground *g_number_of_joysticks_background;

void p_UpdateNumberOfJoysticksBackground( void )
{
  const int number_of_joysticks = SDL_NumJoysticks();
  char *number_of_joysticks_string = f_seal_IntToString( number_of_joysticks, false );
  char *message = f_seal_ConcatenateStrings(( number_of_joysticks == 0 )?( char* )"No":number_of_joysticks_string, " joystick", ( number_of_joysticks == 1 )?"":"s", " detected.", NULL );
  free( number_of_joysticks_string );
  p_StringToTileBackground( message, g_number_of_joysticks_background );
  free( message );
}

typedef struct t_JoystickTreeNode_struct
{
  SDL_JoystickID m_instanceId;
  bool m_open;
  SDL_Joystick *m_joystick;

  seal_TileBackground *m_nameBackground;

  int m_numberOfButtons;
  bool *m_buttonPressed;
  seal_TileBackground *m_buttonsPressedBackground;

  int m_numberOfAxes;
  Sint16 *m_axis;
  seal_TileBackground *m_axesBackground;
}
t_JoystickTreeNode;

class JoystickTree : public seal_Tree<t_JoystickTreeNode*, SDL_JoystickID>
{
  private:
    t_JoystickTreeNode *m_mostRecentlyAdded;

  public:
    JoystickTree( void )
    {
      m_mostRecentlyAdded = NULL;
    }

    void p_Open( const Sint32 p )
    {
      SDL_Joystick *joystick = SDL_JoystickOpen( p );
      const SDL_JoystickID instanceId = SDL_JoystickInstanceID( joystick );
      t_JoystickTreeNode *n = f_Get( instanceId );
      if( n == NULL )
      {
        n = ( t_JoystickTreeNode* )malloc( sizeof( t_JoystickTreeNode ));
        p_Set( n );
      }
      n->m_instanceId = instanceId;
      n->m_open = true;
      n->m_joystick = joystick;

      const char * const name = ( SDL_JoystickName( joystick ) != NULL )?SDL_JoystickName( joystick ):"NULL";
      n->m_nameBackground = new seal_TileBackground( g_font, strlen( name ), 1 );
      p_StringToTileBackground( name, n->m_nameBackground );

      n->m_numberOfButtons = SDL_JoystickNumButtons( joystick );
      n->m_buttonPressed = ( bool* )malloc( sizeof( bool ) * n->m_numberOfButtons );
      int i = 0;
      for( ; i < n->m_numberOfButtons; i ++ )
        n->m_buttonPressed[ i ] = SDL_JoystickGetButton( joystick, i );
      n->m_buttonsPressedBackground = new seal_TileBackground( g_font, 13, n->m_numberOfButtons + 1 );
      p_UpdateButtonsPressedBackground( n );

      n->m_numberOfAxes = SDL_JoystickNumAxes( joystick );
      n->m_axis = ( Sint16* )malloc( sizeof( Sint16 ) * n->m_numberOfAxes );
      for( i = 0; i < n->m_numberOfAxes; i ++ )
        n->m_axis[ i ] = SDL_JoystickGetAxis( joystick, i );
      n->m_axesBackground = new seal_TileBackground( g_font, 13, n->m_numberOfAxes + 1 );
      n->m_axesBackground->p_SetBottomLeftX( n->m_buttonsPressedBackground->f_Right());
      p_UpdateAxesBackground( n );

      n->m_nameBackground->p_SetBottomLeftY( n->m_buttonsPressedBackground->f_Top());

      m_mostRecentlyAdded = n;
    }

    void p_Close( const Sint32 p )
    {
      t_JoystickTreeNode *n = f_Get( p );
      if(( n != NULL ) && ( n->m_open ))
        p_Delete( n );
    }

    void p_PressButton( const SDL_JoystickID p_instanceId, const Uint8 p_button )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceId );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_buttonPressed[ p_button ] = true;
        p_UpdateButtonsPressedBackground( n );
      }
    }

    void p_ReleaseButton( const SDL_JoystickID p_instanceId, const Uint8 p_button )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceId );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_buttonPressed[ p_button ] = false;
        p_UpdateButtonsPressedBackground( n );
      }
    }

    void p_MoveAxis( const SDL_JoystickID p_instanceID, const Uint8 p_axis, const Sint16 p_value )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceID );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_axis[ p_axis ] = p_value;
        p_UpdateAxesBackground( n );
      }
    }

    void p_Render( void )
    {
      if(( m_mostRecentlyAdded != NULL ) && ( m_mostRecentlyAdded->m_open ))
      {
        m_mostRecentlyAdded->m_nameBackground->p_Render();
        m_mostRecentlyAdded->m_buttonsPressedBackground->p_Render();
        m_mostRecentlyAdded->m_axesBackground->p_Render();
      }
    }

  private:
    t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( t_JoystickTreeNode *p_old, t_JoystickTreeNode *p_new )
    {
      if( p_new->m_instanceId < p_old->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_new->m_instanceId > p_old->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
    }

    t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( t_JoystickTreeNode *p_content, SDL_JoystickID p_identifier )
    {
      if( p_identifier < p_content->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_identifier > p_content->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
    }

    t_JoystickTreeNode *f_IsNotInTree( SDL_JoystickID p )
    {
      return NULL;
    }

    void p_Delete( t_JoystickTreeNode *p )
    {
      if( p->m_open )
      {
        p->m_open = false;
        SDL_JoystickClose( p->m_joystick );
        delete p->m_nameBackground;
        free( p->m_buttonPressed );
        delete p->m_buttonsPressedBackground;
        free( p->m_axis );
        delete p->m_axesBackground;
      }
    }

    void p_UpdateButtonsPressedBackground( t_JoystickTreeNode *p )
    {
      seal_StringQueue sQ;
      if( p->m_numberOfButtons == 0 )
        sQ.p_Push(( char* )"No buttons" );
      else
      {
        sQ.p_Push(( char* )"Buttons (" );
        char *number_of_buttons = f_seal_IntToString( p->m_numberOfButtons, false );
        sQ.p_Push( number_of_buttons );
        free( number_of_buttons );
        sQ.p_Push(( char* )")\n" );
      }
      int i = 0;
      for( ; i < p->m_numberOfButtons; i ++ )
      {
        if(( p->m_numberOfButtons >= 100 ) && ( i < 100 ))
          sQ.p_Push(( char* )" " );
        if(( p->m_numberOfButtons >= 10 ) && ( i < 10 ))
          sQ.p_Push(( char* )" " );
        char *i_string = f_seal_IntToString( i, false );
        sQ.p_Push( i_string );
        free( i_string );
        sQ.p_Push(( char* )" .. " );
        sQ.p_Push(( char* )(( !p->m_buttonPressed[ i ] )?"Up":"Down" ));
        if( i + 1 < p->m_numberOfButtons )
          sQ.p_Push(( char* )"\n" );
      }
      char *s = sQ.f_String();
      p_StringToTileBackground( s, p->m_buttonsPressedBackground );
      free( s );
    }

    void p_UpdateAxesBackground( t_JoystickTreeNode *p )
    {
      seal_StringQueue sQ;
      if( p->m_numberOfAxes == 0 )
        sQ.p_Push(( char* )"No axes" );
      else
      {
        sQ.p_Push(( char* )"Axes (" );
        char *number_of_axes = f_seal_IntToString( p->m_numberOfAxes, false );
        sQ.p_Push( number_of_axes );
        free( number_of_axes );
        sQ.p_Push(( char* )")\n" );
      }
      int i = 0;
      for( ; i < p->m_numberOfAxes; i ++ )
      {
        char *i_string = f_seal_IntToString( i, false );
        sQ.p_Push( i_string );
        free( i_string );
        sQ.p_Push(( char* )" .. " );
        char *axis = f_seal_IntToString( p->m_axis[ i ], true );
        sQ.p_Push( axis );
        free( axis );
        if( i + 1 < p->m_numberOfAxes )
          sQ.p_Push(( char* )"\n" );
      }
      char *s = sQ.f_String();
      p_StringToTileBackground( s, p->m_axesBackground );
      free( s );
    }
};

int main( const int argc, const char * const argv[] )
{
  const int W = 494, H = 304;

  SDL_Init( SDL_INIT_VIDEO | SDL_INIT_JOYSTICK );
  SDL_Window *window = SDL_CreateWindow( "SDL2 joystick interrogator", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W, H, SDL_WINDOW_OPENGL );
  SDL_GLContext context = SDL_GL_CreateContext( window );

  glMatrixMode( GL_PROJECTION );
  glLoadIdentity();
  glOrtho( 0, W, 0, H, -1, 1 );
  glMatrixMode( GL_MODELVIEW );
  glClearColor( 0.5, 0.5, 0.5, 1.0 );
  glEnable( GL_TEXTURE_2D );
  glEnableClientState( GL_VERTEX_ARRAY );
  glEnableClientState( GL_TEXTURE_COORD_ARRAY );

  g_font = new seal_Texture( "font.png", 19, 19 );
  g_number_of_joysticks_background = new seal_TileBackground( g_font, 23, 1 );
  g_number_of_joysticks_background->p_SetBottomLeftY( H - 19 );
  JoystickTree *joysticks = new JoystickTree();

  p_UpdateNumberOfJoysticksBackground();

  bool quit = false;
  do
  {
    SDL_Event event;
    while( SDL_PollEvent( &event ))
      switch( event.type )
      {
        case SDL_QUIT:
          quit = true;
          break;
        case SDL_JOYDEVICEADDED:
          p_UpdateNumberOfJoysticksBackground();
          joysticks->p_Open( event.jdevice.which );
          break;
        case SDL_JOYDEVICEREMOVED:
          p_UpdateNumberOfJoysticksBackground();
          joysticks->p_Close( event.jdevice.which );
          break;
        case SDL_JOYBUTTONDOWN:
          joysticks->p_PressButton( event.jbutton.which, event.jbutton.button );
          break;
        case SDL_JOYBUTTONUP:
          joysticks->p_ReleaseButton( event.jbutton.which, event.jbutton.button );
          break;
        case SDL_JOYAXISMOTION:
          joysticks->p_MoveAxis( event.jaxis.which, event.jaxis.axis, event.jaxis.value );
      }
    glClear( GL_COLOR_BUFFER_BIT );
    g_number_of_joysticks_background->p_Render();
    joysticks->p_Render();
    SDL_GL_SwapWindow( window );
  }
  while( !quit );

  delete joysticks;
  delete g_number_of_joysticks_background;
  delete g_font;

  SDL_GL_DeleteContext( context );
  SDL_DestroyWindow( window );
  SDL_Quit();
  return 0;
}

font.png:

font


Priest

11Sep15

I’ve just achieved the rank of “priest” at CodeAbbey for solving sixty-five problems.


Ludum Dare 33

22Aug15

Ludum Dare 33 has begun; the theme is “You are the Monster”.


Interrogating a Sony PlayStation 2 DualShock 2 controller.

Interrogating a Sony PlayStation 2 DualShock 2 controller.

I recently rebooted development of a project I tried to develop for the Ludum Dare 20 contest held in April 2011, the theme of which was “It’s dangerous to go alone! Take this!”

As the project will require a controller with an analogue stick to play I’ve begun to develop a utility to interrogate the capabilities of various controllers – and as I feel that the SDL2 documentation is lacking with regards to the joystick support offered by that library I’m posting here the source code to the second version of that utility, for the benefit both of myself and of others.

SDL2 joystick interrogator.mm:

#include <SDL2/SDL.h>
#include "seal_intToString.h"
#include "seal_stringConcatenation.h"
#include "seal_stringQueue.h"
#include "seal_tree.h"
#include "seal_tileBackground.h"

void p_StringToTileBackground( const char * const p_string, seal_TileBackground *p_tileBackground )
{
  const size_t transparent_sub_texture = 10 /* '0'..'9' */ + 26 /* 'A'..'Z' */ + 3 /* '.', '(', ')' */;
  p_tileBackground->p_SetAllSubTextures( transparent_sub_texture );
  size_t i = 0;
  int x = 0, y = p_tileBackground->f_Height() - 1;
  for( ; i < strlen( p_string ); i ++, x ++ )
  {
    const char character = p_string[ i ];
    size_t sub_texture = transparent_sub_texture;
    if(( character >= '0' ) && ( character <= '9' ))
      sub_texture = character - '0';
    else
      if(( character >= 'a' ) && ( character <= 'z' ))
        sub_texture = character - 'a' + 10;
      else
        if(( character >= 'A' ) && ( character <= 'Z' ))
          sub_texture = character - 'A' + 10;
        else
          if( character == '.' )
            sub_texture = 36;
          else
            if( character == '(' )
              sub_texture = 37;
            else
              if( character == ')' )
                sub_texture = 38;
    if( character == '\n' )
    {
      x = -1;
      y --;
    }
    else
      p_tileBackground->p_SetSubTexture( x, y, sub_texture );
  }
}

static seal_Texture *g_font;
static seal_TileBackground *g_number_of_joysticks_background;

void p_UpdateNumberOfJoysticksBackground( void )
{
  const int number_of_joysticks = SDL_NumJoysticks();
  char *number_of_joysticks_string = f_seal_IntToString( number_of_joysticks, false );
  char *message = f_seal_ConcatenateStrings(( number_of_joysticks == 0 )?( char* )"No":number_of_joysticks_string, " joystick", ( number_of_joysticks == 1 )?"":"s", " detected.", NULL );
  free( number_of_joysticks_string );
  p_StringToTileBackground( message, g_number_of_joysticks_background );
  free( message );
}

typedef struct t_JoystickTreeNode_struct
{
  SDL_JoystickID m_instanceId;
  bool m_open;
  SDL_Joystick *m_joystick;
  int m_numberOfButtons;
  bool *m_buttonPressed;
  seal_TileBackground *m_buttonsPressedBackground;
}
t_JoystickTreeNode;

class JoystickTree : public seal_Tree<t_JoystickTreeNode*, SDL_JoystickID>
{
  private:
    t_JoystickTreeNode *m_mostRecentlyAdded;

  public:
    JoystickTree( void )
    {
      m_mostRecentlyAdded = NULL;
    }

    void p_Open( const Sint32 p )
    {
      SDL_Joystick *joystick = SDL_JoystickOpen( p );
      const SDL_JoystickID instanceId = SDL_JoystickInstanceID( joystick );
      t_JoystickTreeNode *n = f_Get( instanceId );
      if( n == NULL )
      {
        n = ( t_JoystickTreeNode* )malloc( sizeof( t_JoystickTreeNode ));
        p_Set( n );
      }
      n->m_instanceId = instanceId;
      n->m_open = true;
      n->m_joystick = joystick;
      n->m_numberOfButtons = SDL_JoystickNumButtons( joystick );
      n->m_buttonPressed = ( bool* )malloc( sizeof( bool ) * n->m_numberOfButtons );
      int i = 0;
      for( ; i < n->m_numberOfButtons; i ++ )
        n->m_buttonPressed[ i ] = SDL_JoystickGetButton( joystick, i );
      n->m_buttonsPressedBackground = new seal_TileBackground( g_font, 13, n->m_numberOfButtons + 1 );
      p_UpdateButtonsPressedBackground( n );
      m_mostRecentlyAdded = n;
    }

    void p_Close( const Sint32 p )
    {
      t_JoystickTreeNode *n = f_Get( p );
      if(( n != NULL ) && ( n->m_open ))
        p_Delete( n );
    }

    void p_PressButton( const SDL_JoystickID p_instanceId, const Uint8 p_button )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceId );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_buttonPressed[ p_button ] = true;
        p_UpdateButtonsPressedBackground( n );
      }
    }

    void p_ReleaseButton( const SDL_JoystickID p_instanceId, const Uint8 p_button )
    {
      t_JoystickTreeNode *n = f_Get( p_instanceId );
      if(( n != NULL ) && ( n->m_open ))
      {
        n->m_buttonPressed[ p_button ] = false;
        p_UpdateButtonsPressedBackground( n );
      }
    }

    void p_Render( void )
    {
      if(( m_mostRecentlyAdded != NULL ) && ( m_mostRecentlyAdded->m_open ))
        m_mostRecentlyAdded->m_buttonsPressedBackground->p_Render();
    }

  private:
    t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( t_JoystickTreeNode *p_old, t_JoystickTreeNode *p_new )
    {
      if( p_new->m_instanceId < p_old->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_new->m_instanceId > p_old->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
    }

    t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( t_JoystickTreeNode *p_content, SDL_JoystickID p_identifier )
    {
      if( p_identifier < p_content->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__LEFT;
      if( p_identifier > p_content->m_instanceId )
        return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
      return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
    }

    t_JoystickTreeNode *f_IsNotInTree( SDL_JoystickID p )
    {
      return NULL;
    }

    void p_Delete( t_JoystickTreeNode *p )
    {
      if( p->m_open )
      {
        p->m_open = false;
        SDL_JoystickClose( p->m_joystick );
        free( p->m_buttonPressed );
        delete p->m_buttonsPressedBackground;
      }
    }

    void p_UpdateButtonsPressedBackground( t_JoystickTreeNode *p )
    {
      seal_StringQueue sQ;
      if( p->m_numberOfButtons == 0 )
        sQ.p_Push(( char* )"No buttons" );
      else
      {
        sQ.p_Push(( char* )"Buttons (" );
        char *number_of_buttons = f_seal_IntToString( p->m_numberOfButtons, false );
        sQ.p_Push( number_of_buttons );
        free( number_of_buttons );
        sQ.p_Push(( char* )")\n" );
      }
      int i = 0;
      for( ; i < p->m_numberOfButtons; i ++ )
      {
        if(( p->m_numberOfButtons >= 100 ) && ( i < 100 ))
          sQ.p_Push(( char* )" " );
        if(( p->m_numberOfButtons >= 10 ) && ( i < 10 ))
          sQ.p_Push(( char* )" " );
        char *i_string = f_seal_IntToString( i, false );
        sQ.p_Push( i_string );
        free( i_string );
        sQ.p_Push(( char* )" .. " );
        sQ.p_Push(( char* )(( !p->m_buttonPressed[ i ] )?"Up":"Down" ));
        if( i + 1 < p->m_numberOfButtons )
          sQ.p_Push(( char* )"\n" );
      }
      char *s = sQ.f_String();
      p_StringToTileBackground( s, p->m_buttonsPressedBackground );
      free( s );
    }
};

int main( const int argc, const char * const argv[] )
{
  const int W = 437, H = 285;

  SDL_Init( SDL_INIT_VIDEO | SDL_INIT_JOYSTICK );
  SDL_Window *window = SDL_CreateWindow( "SDL2 joystick interrogator", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W, H, SDL_WINDOW_OPENGL );
  SDL_GLContext context = SDL_GL_CreateContext( window );

  glMatrixMode( GL_PROJECTION );
  glLoadIdentity();
  glOrtho( 0, W, 0, H, -1, 1 );
  glMatrixMode( GL_MODELVIEW );
  glClearColor( 0.5, 0.5, 0.5, 1.0 );
  glEnable( GL_TEXTURE_2D );
  glEnableClientState( GL_VERTEX_ARRAY );
  glEnableClientState( GL_TEXTURE_COORD_ARRAY );

  g_font = new seal_Texture( "font.png", 19, 19 );
  g_number_of_joysticks_background = new seal_TileBackground( g_font, 23, 1 );
  g_number_of_joysticks_background->p_SetBottomLeftY( H - 19 );
  JoystickTree *joysticks = new JoystickTree();

  p_UpdateNumberOfJoysticksBackground();

  bool quit = false;
  do
  {
    SDL_Event event;
    while( SDL_PollEvent( &event ))
      switch( event.type )
      {
        case SDL_QUIT:
          quit = true;
          break;
        case SDL_JOYDEVICEADDED:
          p_UpdateNumberOfJoysticksBackground();
          joysticks->p_Open( event.jdevice.which );
          break;
        case SDL_JOYDEVICEREMOVED:
          p_UpdateNumberOfJoysticksBackground();
          joysticks->p_Close( event.jdevice.which );
          break;
        case SDL_JOYBUTTONDOWN:
          joysticks->p_PressButton( event.jbutton.which, event.jbutton.button );
          break;
        case SDL_JOYBUTTONUP:
          joysticks->p_ReleaseButton( event.jbutton.which, event.jbutton.button );
      }
    glClear( GL_COLOR_BUFFER_BIT );
    g_number_of_joysticks_background->p_Render();
    joysticks->p_Render();
    SDL_GL_SwapWindow( window );
  }
  while( !quit );

  delete joysticks;
  delete g_number_of_joysticks_background;
  delete g_font;

  SDL_GL_DeleteContext( context );
  SDL_DestroyWindow( window );
  SDL_Quit();
  return 0;
}

font.png:

font.png


SDL2 joystick interrogator animation

I recently rebooted development of a project I tried to develop for the Ludum Dare 20 contest held in April 2011, the theme of which was “It’s dangerous to go alone! Take this!”

As the project will require a controller with an analogue stick to play I’ve begun to develop a utility to interrogate the capabilities of various controllers – and as I feel that the SDL2 documentation is lacking with regards to the joystick support offered by that library I’m posting here the source code to the first version of that utility, for the benefit both of myself and of others.

SDL2 joystick interrogator.mm:

#include <SDL2/SDL.h>
#include "seal_intToString.h"
#include "seal_stringConcatenation.h"
#include "seal_tileBackground.h"

void p_StringToTileBackground( const char * const p_string, seal_TileBackground *p_tileBackground )
{
  const size_t transparent_sub_texture = 10 /* '0'..'9' */ + 26 /* 'A'..'Z' */ + 1 /* '.' */;
  p_tileBackground->p_SetAllSubTextures( transparent_sub_texture );
  size_t i = 0;
  for( ; i < strlen( p_string ); i ++ )
  {
    const char character = p_string[ i ];
    size_t sub_texture = transparent_sub_texture;
    if(( character >= '0' ) && ( character <= '9' ))
      sub_texture = character - '0';
    else
      if(( character >= 'a' ) && ( character <= 'z' ))
        sub_texture = character - 'a' + 10;
      else
        if(( character >= 'A' ) && ( character <= 'Z' ))
          sub_texture = character - 'A' + 10;
        else
          if( character == '.' )
            sub_texture = 36;
    p_tileBackground->p_SetSubTexture( i, 0, sub_texture );
  }
}

static seal_TileBackground *g_number_of_joysticks_background;

void p_UpdateNumberOfJoysticksBackground( void )
{
  const int number_of_joysticks = SDL_NumJoysticks();
  char *number_of_joysticks_string = f_seal_IntToString( number_of_joysticks, false );
  char *message = f_seal_ConcatenateStrings(( number_of_joysticks == 0 )?( char* )"No":number_of_joysticks_string, " joystick", ( number_of_joysticks == 1 )?"":"s", " detected.", NULL );
  free( number_of_joysticks_string );
  p_StringToTileBackground( message, g_number_of_joysticks_background );
  free( message );
}

int main( const int argc, const char * const argv[] )
{
  const int W = 437, H = 19;

  SDL_Init( SDL_INIT_VIDEO | SDL_INIT_JOYSTICK );
  SDL_Window *window = SDL_CreateWindow( "SDL2 joystick interrogator", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W, H, SDL_WINDOW_OPENGL );
  SDL_GLContext context = SDL_GL_CreateContext( window );

  glMatrixMode( GL_PROJECTION );
  glLoadIdentity();
  glOrtho( 0, W, 0, H, -1, 1 );
  glMatrixMode( GL_MODELVIEW );
  glEnable( GL_TEXTURE_2D );
  glEnableClientState( GL_VERTEX_ARRAY );
  glEnableClientState( GL_TEXTURE_COORD_ARRAY );

  seal_Texture *font = new seal_Texture( "font.png", 19, 19 );
  g_number_of_joysticks_background = new seal_TileBackground( font, 23, 1 );

  p_UpdateNumberOfJoysticksBackground();

  bool quit = false;
  do
  {
    SDL_Event event;
    while( SDL_PollEvent( &event ))
      switch( event.type )
      {
        case SDL_QUIT:
          quit = true;
          break;
        case SDL_JOYDEVICEADDED:
        case SDL_JOYDEVICEREMOVED:
          p_UpdateNumberOfJoysticksBackground();
      }
    glClear( GL_COLOR_BUFFER_BIT );
    g_number_of_joysticks_background->p_Render();
    SDL_GL_SwapWindow( window );
  }
  while( !quit );

  delete g_number_of_joysticks_background;
  delete font;

  SDL_GL_DeleteContext( context );
  SDL_DestroyWindow( window );
  SDL_Quit();
  return 0;
}

font.png:

font.png