# Overview

Atlassian Sourcetree is a free Git and Mercurial client for Windows.

Atlassian Sourcetree is a free Git and Mercurial client for Mac.

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

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