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.