HTTPS SSH

SugrSonic

SugrSonic is a library for propagating sound on a grid. It is intended for use with roguelike games.

Consider the case where our intrepid hero '@' is around the corner from a monster 'M'.

  ###################
  #  M
  # ######## ########
  # #      # #
  # #      # #
  # #      # #
  # #      # #
  # #      # #
  # #      # #
### ######## #
#         @  #
##############

SugrSonic will tell you whether 'M' can hear any noise that '@' makes, and in which direction it is coming from.

Theory

Sound

In this 2D world, sound is well described by the 2D wave equation

 2     2     2
d u   d u   d u
--- + --- + --- = 0
  2     2     2
dt    dx    dy

where 'u' is the intensity of the sound. If we define a few intermediate terms

u_t = du/dt
u_x = du/dx
u_y = du/dy

then we can express the wave equation as

d(u_t)/dt + d(u_x)/dx + d(u_y)/dy = 0

We construct a staggered grid, where u_t is in the center of the cells and u_x and u_y are on the edges.

Staggered Grid

Then we discretize the wave equation as

(u_t(x,y,t+dt) - u_t(x,y,t-dt)/dt + (u_x(x+dx,y,t) - u_x(x-dx,y,t))/dx
                                  + (u_y(x,y+dy,t) - u_y(x,y-dy,t))/dy = 0

From the definition of the u_t, u_x, and u_y

d(u_x)/dt = d(u_t)/dx
d(u_y)/dt = d(u_t)/dy

which we discretize similarly. We use this to compute u_t, u_x, and u_y at a later time given the current state. Numerical stability limits how large we can set dt in relation to dx. It turns out that dt=dx/2 is a convenient choice. This turns the wave equation into

u_t(x,y,t+dt) = u_t(x,y,t-dt) - (u_x(x+dx,y,t) - u_x(x-dx,y,t)
                                 + u_y(x,y+dy,t) - u_y(x,y-dy,t))/2

u_x(x+dx,y,t+dt) = u_x(x+dx,y,t-dt) + (u_t(x+2*dx,y,t) - u_t(x,y,t))/2
u_y(x,y+dy,t+dt) = u_y(x,y+dy,t-dt) + (u_t(x,y+2*dy,t) - u_t(x,y,t))/2

There is no multiplication, and the only division is by 2. We store u_t, u_x, and u_y as 16 bit integers, allowing us to use bit shifts to divide. It also allows us to store 8 values in a 128 bit SSE2. The end result is that we can compute the new values of u_t, u_x, and u_y using only fast integer bit shifts, adds, and AND's.

Boundary Conditions

At walls, we assume that the the sound reflects perfectly. This is implemented by setting the normal derivative to zero. So if a wave is going right to left, this is equivalent to setting

du/dx = 0

In our case, this is equivalent to setting

u_x = 0

when a grid cell that u_x borders is pure rock.

Sample program

After building, there will be a test program in build/wave. You can run it with a command like

mkdir wave
./build/wave 250 wave/wave

Then you can visualize it with VisIt. After starting up VisIt, open the menu item

File -> Open File

and navigate to the wave/ directory. VisIt will automatically group the files together. Select

wave.visit.* database

Before clicking Ok, from the drop down menu labeled

Open file as type:

select Plaintext. Then click on the button

Set default open options...

and change Data Layout to 2D Array. Click OK and open the file. To get a picture, click the Add button and select Pseudocolor -> var. Click Draw and you should see a blue square. Click the play button and you should see a movie that ends with a picture like this.

Visit

LICENSE

Copyright 2014-2015 Walter Landry

SugrSonic is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. A copy of the license should be included in the file LICENSE.