# 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.

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.