Gun Shot Locator Using Sound

Brute Force C code

A Math Puzzle

Soldiers fire an M119 Howitzer It started several years ago, while watching a documentary on World War I. There was a segment on the Brits locating artillery with sound alone.

Then again last year, in a youtube documentary on World War II, there was another segment on the Yanks locating artillery with sound alone.

Neither documentary discussed the math, hence the absolute need for this webpage.

My Starting Assumptions:

"How hard could the math be?" The WW I gear looked simple and was pre-computer.
We are all familiar with counting the seconds between the lightning and the thunder and dividing by 5 to get miles. With a few more observers and some trigonometry, the solution should be simple.
I am "pretty sure" that a 2D world takes at least 3 microphones and that a 3D world takes at least 4 microphones.
You cannot see the opposing forces behind the mountain, so there is no muzzle flash to start the timers and calculate an "absolute distance". The sound will arrive at the closest microphone at "time zero". It will arrive at the other microphones after a delay.

GUN SHOT LOCATOR

MIC COORDINATES
0. A [100,200]
1. B [200,150]
2. C [300,200]

GUN COORDINATES
0. J [120,420]
1. K [210,400]
2. L [280,420]
3. M [220,280]

TEST         Absolute      Zero
DATA         Distance      Time
[ 0, 0] A J  220.9072    0.0000
[ 1, 0] B J  281.6026   60.6953
[ 2, 0] C J  284.2534   63.3462

[ 0, 1] A K  228.2542    8.9371
[ 1, 1] B K  250.1999   30.8828
[ 2, 1] C K  219.3171    0.0000

[ 0, 2] A L  284.2534   63.3462
[ 1, 2] B L  281.6026   60.6953
[ 2, 2] C L  220.9072    0.0000

[ 0, 3] A M  144.2221   31.0850
[ 1, 3] B M  131.5295   18.3924
[ 2, 3] C M  113.1371    0.0000


*******   PROGRAM RUN    *******

                  -- LOCATION --
GUN    ERROR         X         Y
J:    0.0000       120       420
K:    0.0000       210       400
L:    0.0000       280       420
M:    0.0000       220       280

Computing Distance Between Points

The Pythagorean theorem is utilized to calculate the distance between 2 points.

A² + B² = C²

C = SQRT(A² + B²)

In this example, the distance between Gun "J" and Microphone "A" is computed.

          X    Y
     J [120, 420]
   - A [100, 200]
       ----------
   =   [ 20, 220]

Distance = SQRT ( 20*20 + 220*220 )

Distance = SQRT(    400 +   48400 )

Distance = 220.9072

IN C CODE

   dx = mic[i].x - gun[j].x;
   dy = mic[i].y - gun[j].y;         
   absolute[i][j] = sqrt(dx*dx+dy*dy);

Creating Test Data

     ABSOLUTE      TIME
     DISTANCE      ZERO 
---  -------- ---------     
A J  220.9072    0.0000 <- Reaches this microphone first
B J  281.6026   60.6953
C J  284.2534   63.3462

If a shot is fired from gun "J":

The sound will reach Microphone "A" first. This is the system's first contact with the event.
60.6953 ms after reaching Microphone "A", the sound will reach Microphone "B".
63.3462 ms after reaching Microphone "A", the sound will reach Microphone "C".

The Algorithm

The Brute Force Algorithm

goes to every possible location,
calculates the input values the microphones would receive from a gunshot at that location
compares the calculated input with the actual input
if the compare has the least error then saves this possible location
prints out the possible location with the least error.



// ---------------------------------------------------------------------------

struct POINT mic[]=
{
   {"A",100,200},
   {"B",200,150},
   {"C",300,200}
   
};
int miccnt = 3;

struct POINT gun[]=
{
   {"J",120,420},
   {"K",210,400},
   {"L",280,420},
   {"M",220,280},
   
};
int guncnt = 4;


// ---------------------------------------------------------------------------
int dumpmic()
{
   int i;
   
   
   printf("MIC COORDINATES\n");
   
   for(i=0;i<miccnt;i++)
      printf("%d. %s [%3.0f,%3.0f]\n",i,mic[i].name,mic[i].x,mic[i].y);
      
   printf("\n");
   
   return 0;
}

// ---------------------------------------------------------------------------

int dumpgun()
{
   int j;
    
   // GUN COORDINATES
   
   printf("GUN COORDINATES\n");
   for(j=0;j<guncnt;j++)
      printf("%d. %s [%3.0f,%3.0f]\n",j,gun[j].name,gun[j].x,gun[j].y);
   printf("\n");
 
   return 0; 
}

// ---------------------------------------------------------------------------
// CREATE TEST DATA FROM GUN AND MIC LOCATIONS

int createtestdata()
{ 
   int i,j;
   double dx,dy;     
   double lowest;
         
   printf("TEST         Absolute      Zero\n");
   printf("DATA         Distance      Time\n");
   
   for(j=0;j<guncnt;j++)
   {
      lowest=1000000;
      for(i=0;i<miccnt;i++)
      {      
         // CALCULATE ABSOLUTE DISTANCE BETWEEN MIC AND GUN
         
         dx = mic[i].x - gun[j].x;
         dy = mic[i].y - gun[j].y;         
         absolute[i][j] = sqrt(dx*dx+dy*dy);
         
         // FIND CLOSEST DISTANCE
         
         if (absolute[i][j] < lowest)
            lowest = absolute[i][j];         
      }
      
      // SUBTRACT CLOSEST DISTANCE FROM ALL DISTANCES
      
      for(i=0;i<miccnt;i++)
      { 
         zero[i][j] = absolute[i][j] - lowest;         
         printf("[%2d,%2d] %s %s %9.4f %9.4f\n",i,j,mic[i].name,gun[j].name,absolute[i][j],zero[i][j]);
      }
      printf("\n");
   }
   printf("\n");
 
   return 0;
}


// ---------------------------------------------------------------------------
// SOLVE

int brute(int j)
{
   int i,x,y;
   double dx,dy;
   
   double bruteabs[MAXMIC];
   double brutezero[MAXMIC];
   
   double lowest;
   double error,errormin;
   int bestx,besty;
      
   // INSIST UPON EXPLICIT CONVERSION FROM INTEGER TO DOUBLE
   
   double doublex,doubley;  
   
   
   // INITIALIZE BEST ANSWER VARIABLES
   
   errormin = 1000000.0;
   bestx=-1;
   besty=-1;
   
   // SCAN ENTIRE SEARCH SPACE IN 1 UNIT INCREMENTS
   
   for(x=0;x<400;x++)
   {
      doublex = x;
      
      for(y=0;y<500;y++)
      {
         doubley = y;
         
         // USED TO FIND CLOSEST MIC
         
         lowest = 1000000.0; 
         
         for(i=0;i<miccnt;i++)
         {
            // ABSOLUTE DISTANCE FROM EVENT AT THIS X,Y TO EACH MIC
            
            dx = mic[i].x - doublex;
            dy = mic[i].y - doubley;            
            bruteabs[i] = sqrt(dx*dx+dy*dy); 

            // KEEP TRACK OF CLOSEST DISTANCE
            
            if (bruteabs[i] < lowest)
               lowest = bruteabs[i];         
         }  
         
         // CONVERT "ABSOLUTE DISTANCE" TO "ZERO TIME"
         
         for(i=0;i<miccnt;i++)
            brutezero[i] = bruteabs[i] - lowest;
         
         
         // COMPARE GENERATED WITH ACTUAL
         // ACCUMULATE TOTAL ABSOLUTE ERROR FROM ALL MICS
         
         error = 0;         
         for(i=0;i<miccnt;i++)
            error += fabs( zero[i][j] - brutezero[i] );
         
         // SAVE THIS X,Y AS BEST IF IT HAS THE LEAST ERROR
         
         if (error < errormin)
         {
            errormin = error;
            bestx = x;
            besty = y;
         }                
      }
   }
   
   // PRINT BEST ANSWER
   
   printf("%s: %9.4f %9d %9d",gun[j].name,errormin,bestx,besty);
   
   if (bestx == -1)
      printf(" FUBAR");
      
   printf("\n");
   return 0;
}


// ---------------------------------------------------------------------------

int main()
{
   int j;
   
   printf("GUN SHOT LOCATOR\n");
   dumpmic();
   dumpgun();
   createtestdata();
   
   
   // RUN BRUTE FORCE LOCATOR
    
   printf("*******   PROGRAM RUN    *******\n\n");
   printf("                  -- LOCATION --\n");
   printf("GUN    ERROR         X         Y\n");
   
   for(j=0;j<guncnt;j++)
     brute(j);   
     
   printf("\n");
   
   return 0;
   
}