# HG changeset patch
# User John Tsiombikas <nuclear@member.fsf.org>
# Date 1347860459 -10800
# Node ID aa9e28670ae2b34421c67506b390850b6debbb86
# Parent  d52711f2b9a17087a5d95669f5b4721d7a5a3ad0
added sound playback, more to do

diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/Makefile.in
--- a/prototype/Makefile.in	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/Makefile.in	Mon Sep 17 08:40:59 2012 +0300
@@ -1,6 +1,7 @@
 csrc = $(wildcard src/*.c) \
 	   $(wildcard vmath/*.c) \
-	   $(wildcard drawtext/*.c)
+	   $(wildcard drawtext/*.c) \
+	   $(wildcard kdtree/*.c)
 
 ccsrc = $(wildcard src/*.cc) \
 		$(wildcard src/audio/*.cc) \
@@ -12,7 +13,7 @@
 
 warn = -Wall -Wno-format-extra-args -Wno-char-subscripts
 
-inc = -I. -Isrc/audio -Ivmath -Idrawtext `pkg-config --cflags freetype2`
+inc = -I. -Isrc -Ivmath -Idrawtext -Ikdtree `pkg-config --cflags freetype2`
 
 CFLAGS = -pedantic $(warn) $(dbg) $(opt) $(inc)
 CXXFLAGS = $(CFLAGS) $(cxx11_cflags)
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/kdtree/kdtree.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/kdtree/kdtree.c	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,840 @@
+/*
+This file is part of ``kdtree'', a library for working with kd-trees.
+Copyright (C) 2007-2011 John Tsiombikas <nuclear@member.fsf.org>
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+1. Redistributions of source code must retain the above copyright notice, this
+   list of conditions and the following disclaimer.
+2. Redistributions in binary form must reproduce the above copyright notice,
+   this list of conditions and the following disclaimer in the documentation
+   and/or other materials provided with the distribution.
+3. The name of the author may not be used to endorse or promote products
+   derived from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
+WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
+OF SUCH DAMAGE.
+*/
+/* single nearest neighbor search written by Tamas Nepusz <tamas@cs.rhul.ac.uk> */
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include "kdtree.h"
+
+#define USE_LIST_NODE_ALLOCATOR
+#define NO_PTHREADS
+#define I_WANT_THREAD_BUGS
+
+#if defined(WIN32) || defined(__WIN32__)
+#include <malloc.h>
+#endif
+
+#ifdef USE_LIST_NODE_ALLOCATOR
+
+#ifndef NO_PTHREADS
+#include <pthread.h>
+#else
+
+#ifndef I_WANT_THREAD_BUGS
+#error "You are compiling with the fast list node allocator, with pthreads disabled! This WILL break if used from multiple threads."
+#endif	/* I want thread bugs */
+
+#endif	/* pthread support */
+#endif	/* use list node allocator */
+
+struct kdhyperrect {
+	int dim;
+	double *min, *max;              /* minimum/maximum coords */
+};
+
+struct kdnode {
+	double *pos;
+	int dir;
+	void *data;
+
+	struct kdnode *left, *right;	/* negative/positive side */
+};
+
+struct res_node {
+	struct kdnode *item;
+	double dist_sq;
+	struct res_node *next;
+};
+
+struct kdtree {
+	int dim;
+	struct kdnode *root;
+	struct kdhyperrect *rect;
+	void (*destr)(void*);
+};
+
+struct kdres {
+	struct kdtree *tree;
+	struct res_node *rlist, *riter;
+	int size;
+};
+
+#define SQ(x)			((x) * (x))
+
+
+static void clear_rec(struct kdnode *node, void (*destr)(void*));
+static int insert_rec(struct kdnode **node, const double *pos, void *data, int dir, int dim);
+static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq);
+static void clear_results(struct kdres *set);
+
+static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max);
+static void hyperrect_free(struct kdhyperrect *rect);
+static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect);
+static void hyperrect_extend(struct kdhyperrect *rect, const double *pos);
+static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos);
+
+#ifdef USE_LIST_NODE_ALLOCATOR
+static struct res_node *alloc_resnode(void);
+static void free_resnode(struct res_node*);
+#else
+#define alloc_resnode()		malloc(sizeof(struct res_node))
+#define free_resnode(n)		free(n)
+#endif
+
+
+
+struct kdtree *kd_create(int k)
+{
+	struct kdtree *tree;
+
+	if(!(tree = malloc(sizeof *tree))) {
+		return 0;
+	}
+
+	tree->dim = k;
+	tree->root = 0;
+	tree->destr = 0;
+	tree->rect = 0;
+
+	return tree;
+}
+
+void kd_free(struct kdtree *tree)
+{
+	if(tree) {
+		kd_clear(tree);
+		free(tree);
+	}
+}
+
+static void clear_rec(struct kdnode *node, void (*destr)(void*))
+{
+	if(!node) return;
+
+	clear_rec(node->left, destr);
+	clear_rec(node->right, destr);
+	
+	if(destr) {
+		destr(node->data);
+	}
+	free(node->pos);
+	free(node);
+}
+
+void kd_clear(struct kdtree *tree)
+{
+	clear_rec(tree->root, tree->destr);
+	tree->root = 0;
+
+	if (tree->rect) {
+		hyperrect_free(tree->rect);
+		tree->rect = 0;
+	}
+}
+
+void kd_data_destructor(struct kdtree *tree, void (*destr)(void*))
+{
+	tree->destr = destr;
+}
+
+
+static int insert_rec(struct kdnode **nptr, const double *pos, void *data, int dir, int dim)
+{
+	int new_dir;
+	struct kdnode *node;
+
+	if(!*nptr) {
+		if(!(node = malloc(sizeof *node))) {
+			return -1;
+		}
+		if(!(node->pos = malloc(dim * sizeof *node->pos))) {
+			free(node);
+			return -1;
+		}
+		memcpy(node->pos, pos, dim * sizeof *node->pos);
+		node->data = data;
+		node->dir = dir;
+		node->left = node->right = 0;
+		*nptr = node;
+		return 0;
+	}
+
+	node = *nptr;
+	new_dir = (node->dir + 1) % dim;
+	if(pos[node->dir] < node->pos[node->dir]) {
+		return insert_rec(&(*nptr)->left, pos, data, new_dir, dim);
+	}
+	return insert_rec(&(*nptr)->right, pos, data, new_dir, dim);
+}
+
+int kd_insert(struct kdtree *tree, const double *pos, void *data)
+{
+	if (insert_rec(&tree->root, pos, data, 0, tree->dim)) {
+		return -1;
+	}
+
+	if (tree->rect == 0) {
+		tree->rect = hyperrect_create(tree->dim, pos, pos);
+	} else {
+		hyperrect_extend(tree->rect, pos);
+	}
+
+	return 0;
+}
+
+int kd_insertf(struct kdtree *tree, const float *pos, void *data)
+{
+	static double sbuf[16];
+	double *bptr, *buf = 0;
+	int res, dim = tree->dim;
+
+	if(dim > 16) {
+#ifndef NO_ALLOCA
+		if(dim <= 256)
+			bptr = buf = alloca(dim * sizeof *bptr);
+		else
+#endif
+			if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
+				return -1;
+			}
+	} else {
+		bptr = buf = sbuf;
+	}
+
+	while(dim-- > 0) {
+		*bptr++ = *pos++;
+	}
+
+	res = kd_insert(tree, buf, data);
+#ifndef NO_ALLOCA
+	if(tree->dim > 256)
+#else
+	if(tree->dim > 16)
+#endif
+		free(buf);
+	return res;
+}
+
+int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data)
+{
+	double buf[3];
+	buf[0] = x;
+	buf[1] = y;
+	buf[2] = z;
+	return kd_insert(tree, buf, data);
+}
+
+int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data)
+{
+	double buf[3];
+	buf[0] = x;
+	buf[1] = y;
+	buf[2] = z;
+	return kd_insert(tree, buf, data);
+}
+
+static int find_nearest(struct kdnode *node, const double *pos, double range, struct res_node *list, int ordered, int dim)
+{
+	double dist_sq, dx;
+	int i, ret, added_res = 0;
+
+	if(!node) return 0;
+
+	dist_sq = 0;
+	for(i=0; i<dim; i++) {
+		dist_sq += SQ(node->pos[i] - pos[i]);
+	}
+	if(dist_sq <= SQ(range)) {
+		if(rlist_insert(list, node, ordered ? dist_sq : -1.0) == -1) {
+			return -1;
+		}
+		added_res = 1;
+	}
+
+	dx = pos[node->dir] - node->pos[node->dir];
+
+	ret = find_nearest(dx <= 0.0 ? node->left : node->right, pos, range, list, ordered, dim);
+	if(ret >= 0 && fabs(dx) < range) {
+		added_res += ret;
+		ret = find_nearest(dx <= 0.0 ? node->right : node->left, pos, range, list, ordered, dim);
+	}
+	if(ret == -1) {
+		return -1;
+	}
+	added_res += ret;
+
+	return added_res;
+}
+
+#if 0
+static int find_nearest_n(struct kdnode *node, const double *pos, double range, int num, struct rheap *heap, int dim)
+{
+	double dist_sq, dx;
+	int i, ret, added_res = 0;
+
+	if(!node) return 0;
+	
+	/* if the photon is close enough, add it to the result heap */
+	dist_sq = 0;
+	for(i=0; i<dim; i++) {
+		dist_sq += SQ(node->pos[i] - pos[i]);
+	}
+	if(dist_sq <= range_sq) {
+		if(heap->size >= num) {
+			/* get furthest element */
+			struct res_node *maxelem = rheap_get_max(heap);
+
+			/* and check if the new one is closer than that */
+			if(maxelem->dist_sq > dist_sq) {
+				rheap_remove_max(heap);
+
+				if(rheap_insert(heap, node, dist_sq) == -1) {
+					return -1;
+				}
+				added_res = 1;
+
+				range_sq = dist_sq;
+			}
+		} else {
+			if(rheap_insert(heap, node, dist_sq) == -1) {
+				return =1;
+			}
+			added_res = 1;
+		}
+	}
+
+
+	/* find signed distance from the splitting plane */
+	dx = pos[node->dir] - node->pos[node->dir];
+
+	ret = find_nearest_n(dx <= 0.0 ? node->left : node->right, pos, range, num, heap, dim);
+	if(ret >= 0 && fabs(dx) < range) {
+		added_res += ret;
+		ret = find_nearest_n(dx <= 0.0 ? node->right : node->left, pos, range, num, heap, dim);
+	}
+
+}
+#endif
+
+static void kd_nearest_i(struct kdnode *node, const double *pos, struct kdnode **result, double *result_dist_sq, struct kdhyperrect* rect)
+{
+	int dir = node->dir;
+	int i;
+	double dummy, dist_sq;
+	struct kdnode *nearer_subtree, *farther_subtree;
+	double *nearer_hyperrect_coord, *farther_hyperrect_coord;
+
+	/* Decide whether to go left or right in the tree */
+	dummy = pos[dir] - node->pos[dir];
+	if (dummy <= 0) {
+		nearer_subtree = node->left;
+		farther_subtree = node->right;
+		nearer_hyperrect_coord = rect->max + dir;
+		farther_hyperrect_coord = rect->min + dir;
+	} else {
+		nearer_subtree = node->right;
+		farther_subtree = node->left;
+		nearer_hyperrect_coord = rect->min + dir;
+		farther_hyperrect_coord = rect->max + dir;
+	}
+
+	if (nearer_subtree) {
+		/* Slice the hyperrect to get the hyperrect of the nearer subtree */
+		dummy = *nearer_hyperrect_coord;
+		*nearer_hyperrect_coord = node->pos[dir];
+		/* Recurse down into nearer subtree */
+		kd_nearest_i(nearer_subtree, pos, result, result_dist_sq, rect);
+		/* Undo the slice */
+		*nearer_hyperrect_coord = dummy;
+	}
+
+	/* Check the distance of the point at the current node, compare it
+	 * with our best so far */
+	dist_sq = 0;
+	for(i=0; i < rect->dim; i++) {
+		dist_sq += SQ(node->pos[i] - pos[i]);
+	}
+	if (dist_sq < *result_dist_sq) {
+		*result = node;
+		*result_dist_sq = dist_sq;
+	}
+
+	if (farther_subtree) {
+		/* Get the hyperrect of the farther subtree */
+		dummy = *farther_hyperrect_coord;
+		*farther_hyperrect_coord = node->pos[dir];
+		/* Check if we have to recurse down by calculating the closest
+		 * point of the hyperrect and see if it's closer than our
+		 * minimum distance in result_dist_sq. */
+		if (hyperrect_dist_sq(rect, pos) < *result_dist_sq) {
+			/* Recurse down into farther subtree */
+			kd_nearest_i(farther_subtree, pos, result, result_dist_sq, rect);
+		}
+		/* Undo the slice on the hyperrect */
+		*farther_hyperrect_coord = dummy;
+	}
+}
+
+struct kdres *kd_nearest(struct kdtree *kd, const double *pos)
+{
+	struct kdhyperrect *rect;
+	struct kdnode *result;
+	struct kdres *rset;
+	double dist_sq;
+	int i;
+
+	if (!kd) return 0;
+	if (!kd->rect) return 0;
+
+	/* Allocate result set */
+	if(!(rset = malloc(sizeof *rset))) {
+		return 0;
+	}
+	if(!(rset->rlist = alloc_resnode())) {
+		free(rset);
+		return 0;
+	}
+	rset->rlist->next = 0;
+	rset->tree = kd;
+
+	/* Duplicate the bounding hyperrectangle, we will work on the copy */
+	if (!(rect = hyperrect_duplicate(kd->rect))) {
+		kd_res_free(rset);
+		return 0;
+	}
+
+	/* Our first guesstimate is the root node */
+	result = kd->root;
+	dist_sq = 0;
+	for (i = 0; i < kd->dim; i++)
+		dist_sq += SQ(result->pos[i] - pos[i]);
+
+	/* Search for the nearest neighbour recursively */
+	kd_nearest_i(kd->root, pos, &result, &dist_sq, rect);
+
+	/* Free the copy of the hyperrect */
+	hyperrect_free(rect);
+
+	/* Store the result */
+	if (result) {
+		if (rlist_insert(rset->rlist, result, -1.0) == -1) {
+			kd_res_free(rset);
+			return 0;
+		}
+		rset->size = 1;
+		kd_res_rewind(rset);
+		return rset;
+	} else {
+		kd_res_free(rset);
+		return 0;
+	}
+}
+
+struct kdres *kd_nearestf(struct kdtree *tree, const float *pos)
+{
+	static double sbuf[16];
+	double *bptr, *buf = 0;
+	int dim = tree->dim;
+	struct kdres *res;
+
+	if(dim > 16) {
+#ifndef NO_ALLOCA
+		if(dim <= 256)
+			bptr = buf = alloca(dim * sizeof *bptr);
+		else
+#endif
+			if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
+				return 0;
+			}
+	} else {
+		bptr = buf = sbuf;
+	}
+
+	while(dim-- > 0) {
+		*bptr++ = *pos++;
+	}
+
+	res = kd_nearest(tree, buf);
+#ifndef NO_ALLOCA
+	if(tree->dim > 256)
+#else
+	if(tree->dim > 16)
+#endif
+		free(buf);
+	return res;
+}
+
+struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z)
+{
+	double pos[3];
+	pos[0] = x;
+	pos[1] = y;
+	pos[2] = z;
+	return kd_nearest(tree, pos);
+}
+
+struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z)
+{
+	double pos[3];
+	pos[0] = x;
+	pos[1] = y;
+	pos[2] = z;
+	return kd_nearest(tree, pos);
+}
+
+/* ---- nearest N search ---- */
+/*
+static kdres *kd_nearest_n(struct kdtree *kd, const double *pos, int num)
+{
+	int ret;
+	struct kdres *rset;
+
+	if(!(rset = malloc(sizeof *rset))) {
+		return 0;
+	}
+	if(!(rset->rlist = alloc_resnode())) {
+		free(rset);
+		return 0;
+	}
+	rset->rlist->next = 0;
+	rset->tree = kd;
+
+	if((ret = find_nearest_n(kd->root, pos, range, num, rset->rlist, kd->dim)) == -1) {
+		kd_res_free(rset);
+		return 0;
+	}
+	rset->size = ret;
+	kd_res_rewind(rset);
+	return rset;
+}*/
+
+struct kdres *kd_nearest_range(struct kdtree *kd, const double *pos, double range)
+{
+	int ret;
+	struct kdres *rset;
+
+	if(!(rset = malloc(sizeof *rset))) {
+		return 0;
+	}
+	if(!(rset->rlist = alloc_resnode())) {
+		free(rset);
+		return 0;
+	}
+	rset->rlist->next = 0;
+	rset->tree = kd;
+
+	if((ret = find_nearest(kd->root, pos, range, rset->rlist, 0, kd->dim)) == -1) {
+		kd_res_free(rset);
+		return 0;
+	}
+	rset->size = ret;
+	kd_res_rewind(rset);
+	return rset;
+}
+
+struct kdres *kd_nearest_rangef(struct kdtree *kd, const float *pos, float range)
+{
+	static double sbuf[16];
+	double *bptr, *buf = 0;
+	int dim = kd->dim;
+	struct kdres *res;
+
+	if(dim > 16) {
+#ifndef NO_ALLOCA
+		if(dim <= 256)
+			bptr = buf = alloca(dim * sizeof *bptr);
+		else
+#endif
+			if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
+				return 0;
+			}
+	} else {
+		bptr = buf = sbuf;
+	}
+
+	while(dim-- > 0) {
+		*bptr++ = *pos++;
+	}
+
+	res = kd_nearest_range(kd, buf, range);
+#ifndef NO_ALLOCA
+	if(kd->dim > 256)
+#else
+	if(kd->dim > 16)
+#endif
+		free(buf);
+	return res;
+}
+
+struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range)
+{
+	double buf[3];
+	buf[0] = x;
+	buf[1] = y;
+	buf[2] = z;
+	return kd_nearest_range(tree, buf, range);
+}
+
+struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range)
+{
+	double buf[3];
+	buf[0] = x;
+	buf[1] = y;
+	buf[2] = z;
+	return kd_nearest_range(tree, buf, range);
+}
+
+void kd_res_free(struct kdres *rset)
+{
+	clear_results(rset);
+	free_resnode(rset->rlist);
+	free(rset);
+}
+
+int kd_res_size(struct kdres *set)
+{
+	return (set->size);
+}
+
+void kd_res_rewind(struct kdres *rset)
+{
+	rset->riter = rset->rlist->next;
+}
+
+int kd_res_end(struct kdres *rset)
+{
+	return rset->riter == 0;
+}
+
+int kd_res_next(struct kdres *rset)
+{
+	rset->riter = rset->riter->next;
+	return rset->riter != 0;
+}
+
+void *kd_res_item(struct kdres *rset, double *pos)
+{
+	if(rset->riter) {
+		if(pos) {
+			memcpy(pos, rset->riter->item->pos, rset->tree->dim * sizeof *pos);
+		}
+		return rset->riter->item->data;
+	}
+	return 0;
+}
+
+void *kd_res_itemf(struct kdres *rset, float *pos)
+{
+	if(rset->riter) {
+		if(pos) {
+			int i;
+			for(i=0; i<rset->tree->dim; i++) {
+				pos[i] = rset->riter->item->pos[i];
+			}
+		}
+		return rset->riter->item->data;
+	}
+	return 0;
+}
+
+void *kd_res_item3(struct kdres *rset, double *x, double *y, double *z)
+{
+	if(rset->riter) {
+		if(*x) *x = rset->riter->item->pos[0];
+		if(*y) *y = rset->riter->item->pos[1];
+		if(*z) *z = rset->riter->item->pos[2];
+	}
+	return 0;
+}
+
+void *kd_res_item3f(struct kdres *rset, float *x, float *y, float *z)
+{
+	if(rset->riter) {
+		if(*x) *x = rset->riter->item->pos[0];
+		if(*y) *y = rset->riter->item->pos[1];
+		if(*z) *z = rset->riter->item->pos[2];
+	}
+	return 0;
+}
+
+void *kd_res_item_data(struct kdres *set)
+{
+	return kd_res_item(set, 0);
+}
+
+/* ---- hyperrectangle helpers ---- */
+static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max)
+{
+	size_t size = dim * sizeof(double);
+	struct kdhyperrect* rect = 0;
+
+	if (!(rect = malloc(sizeof(struct kdhyperrect)))) {
+		return 0;
+	}
+
+	rect->dim = dim;
+	if (!(rect->min = malloc(size))) {
+		free(rect);
+		return 0;
+	}
+	if (!(rect->max = malloc(size))) {
+		free(rect->min);
+		free(rect);
+		return 0;
+	}
+	memcpy(rect->min, min, size);
+	memcpy(rect->max, max, size);
+
+	return rect;
+}
+
+static void hyperrect_free(struct kdhyperrect *rect)
+{
+	free(rect->min);
+	free(rect->max);
+	free(rect);
+}
+
+static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect)
+{
+	return hyperrect_create(rect->dim, rect->min, rect->max);
+}
+
+static void hyperrect_extend(struct kdhyperrect *rect, const double *pos)
+{
+	int i;
+
+	for (i=0; i < rect->dim; i++) {
+		if (pos[i] < rect->min[i]) {
+			rect->min[i] = pos[i];
+		}
+		if (pos[i] > rect->max[i]) {
+			rect->max[i] = pos[i];
+		}
+	}
+}
+
+static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos)
+{
+	int i;
+	double result = 0;
+
+	for (i=0; i < rect->dim; i++) {
+		if (pos[i] < rect->min[i]) {
+			result += SQ(rect->min[i] - pos[i]);
+		} else if (pos[i] > rect->max[i]) {
+			result += SQ(rect->max[i] - pos[i]);
+		}
+	}
+
+	return result;
+}
+
+/* ---- static helpers ---- */
+
+#ifdef USE_LIST_NODE_ALLOCATOR
+/* special list node allocators. */
+static struct res_node *free_nodes;
+
+#ifndef NO_PTHREADS
+static pthread_mutex_t alloc_mutex = PTHREAD_MUTEX_INITIALIZER;
+#endif
+
+static struct res_node *alloc_resnode(void)
+{
+	struct res_node *node;
+
+#ifndef NO_PTHREADS
+	pthread_mutex_lock(&alloc_mutex);
+#endif
+
+	if(!free_nodes) {
+		node = malloc(sizeof *node);
+	} else {
+		node = free_nodes;
+		free_nodes = free_nodes->next;
+		node->next = 0;
+	}
+
+#ifndef NO_PTHREADS
+	pthread_mutex_unlock(&alloc_mutex);
+#endif
+
+	return node;
+}
+
+static void free_resnode(struct res_node *node)
+{
+#ifndef NO_PTHREADS
+	pthread_mutex_lock(&alloc_mutex);
+#endif
+
+	node->next = free_nodes;
+	free_nodes = node;
+
+#ifndef NO_PTHREADS
+	pthread_mutex_unlock(&alloc_mutex);
+#endif
+}
+#endif	/* list node allocator or not */
+
+
+/* inserts the item. if dist_sq is >= 0, then do an ordered insert */
+/* TODO make the ordering code use heapsort */
+static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq)
+{
+	struct res_node *rnode;
+
+	if(!(rnode = alloc_resnode())) {
+		return -1;
+	}
+	rnode->item = item;
+	rnode->dist_sq = dist_sq;
+
+	if(dist_sq >= 0.0) {
+		while(list->next && list->next->dist_sq < dist_sq) {
+			list = list->next;
+		}
+	}
+	rnode->next = list->next;
+	list->next = rnode;
+	return 0;
+}
+
+static void clear_results(struct kdres *rset)
+{
+	struct res_node *tmp, *node = rset->rlist->next;
+
+	while(node) {
+		tmp = node;
+		node = node->next;
+		free_resnode(tmp);
+	}
+
+	rset->rlist->next = 0;
+}
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/kdtree/kdtree.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/kdtree/kdtree.h	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,129 @@
+/*
+This file is part of ``kdtree'', a library for working with kd-trees.
+Copyright (C) 2007-2011 John Tsiombikas <nuclear@member.fsf.org>
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+1. Redistributions of source code must retain the above copyright notice, this
+   list of conditions and the following disclaimer.
+2. Redistributions in binary form must reproduce the above copyright notice,
+   this list of conditions and the following disclaimer in the documentation
+   and/or other materials provided with the distribution.
+3. The name of the author may not be used to endorse or promote products
+   derived from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
+WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
+OF SUCH DAMAGE.
+*/
+#ifndef _KDTREE_H_
+#define _KDTREE_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct kdtree;
+struct kdres;
+
+
+/* create a kd-tree for "k"-dimensional data */
+struct kdtree *kd_create(int k);
+
+/* free the struct kdtree */
+void kd_free(struct kdtree *tree);
+
+/* remove all the elements from the tree */
+void kd_clear(struct kdtree *tree);
+
+/* if called with non-null 2nd argument, the function provided
+ * will be called on data pointers (see kd_insert) when nodes
+ * are to be removed from the tree.
+ */
+void kd_data_destructor(struct kdtree *tree, void (*destr)(void*));
+
+/* insert a node, specifying its position, and optional data */
+int kd_insert(struct kdtree *tree, const double *pos, void *data);
+int kd_insertf(struct kdtree *tree, const float *pos, void *data);
+int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data);
+int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data);
+
+/* Find the nearest node from a given point.
+ *
+ * This function returns a pointer to a result set with at most one element.
+ */
+struct kdres *kd_nearest(struct kdtree *tree, const double *pos);
+struct kdres *kd_nearestf(struct kdtree *tree, const float *pos);
+struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z);
+struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z);
+
+/* Find the N nearest nodes from a given point.
+ *
+ * This function returns a pointer to a result set, with at most N elements,
+ * which can be manipulated with the kd_res_* functions.
+ * The returned pointer can be null as an indication of an error. Otherwise
+ * a valid result set is always returned which may contain 0 or more elements.
+ * The result set must be deallocated with kd_res_free after use.
+ */
+/*
+struct kdres *kd_nearest_n(struct kdtree *tree, const double *pos, int num);
+struct kdres *kd_nearest_nf(struct kdtree *tree, const float *pos, int num);
+struct kdres *kd_nearest_n3(struct kdtree *tree, double x, double y, double z);
+struct kdres *kd_nearest_n3f(struct kdtree *tree, float x, float y, float z);
+*/
+
+/* Find any nearest nodes from a given point within a range.
+ *
+ * This function returns a pointer to a result set, which can be manipulated
+ * by the kd_res_* functions.
+ * The returned pointer can be null as an indication of an error. Otherwise
+ * a valid result set is always returned which may contain 0 or more elements.
+ * The result set must be deallocated with kd_res_free after use.
+ */
+struct kdres *kd_nearest_range(struct kdtree *tree, const double *pos, double range);
+struct kdres *kd_nearest_rangef(struct kdtree *tree, const float *pos, float range);
+struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range);
+struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range);
+
+/* frees a result set returned by kd_nearest_range() */
+void kd_res_free(struct kdres *set);
+
+/* returns the size of the result set (in elements) */
+int kd_res_size(struct kdres *set);
+
+/* rewinds the result set iterator */
+void kd_res_rewind(struct kdres *set);
+
+/* returns non-zero if the set iterator reached the end after the last element */
+int kd_res_end(struct kdres *set);
+
+/* advances the result set iterator, returns non-zero on success, zero if
+ * there are no more elements in the result set.
+ */
+int kd_res_next(struct kdres *set);
+
+/* returns the data pointer (can be null) of the current result set item
+ * and optionally sets its position to the pointers(s) if not null.
+ */
+void *kd_res_item(struct kdres *set, double *pos);
+void *kd_res_itemf(struct kdres *set, float *pos);
+void *kd_res_item3(struct kdres *set, double *x, double *y, double *z);
+void *kd_res_item3f(struct kdres *set, float *x, float *y, float *z);
+
+/* equivalent to kd_res_item(set, 0) */
+void *kd_res_item_data(struct kdres *set);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif	/* _KDTREE_H_ */
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/audio.cc
--- a/prototype/src/audio/audio.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/audio/audio.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -2,15 +2,6 @@
 #include "openal.h"
 #include "audio.h"
 
-#define CHECK_ERROR \
-    do { \
-        unsigned int err = alGetError(); \
-        if(err != 0) { \
-            fprintf(stderr, "%s:%d: AL error: %#x\n", __FILE__, __LINE__, err); \
-            abort(); \
-        } \
-    } while(0)
-
 static ALCdevice *dev;
 static ALCcontext *ctx;
 
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/audio.h
--- a/prototype/src/audio/audio.h	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/audio/audio.h	Mon Sep 17 08:40:59 2012 +0300
@@ -4,5 +4,4 @@
 bool init_audio();
 void destroy_audio();
 
-
 #endif	/* AUDIO_H_ */
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/auman.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/src/audio/auman.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,68 @@
+#include <algorithm>
+#include <new>
+#include "auman.h"
+
+AudioManager::AudioManager()
+{
+	if(!(sources = kd_create(3))) {
+		fprintf(stderr, "failed to create kd tree\n");
+		throw std::bad_alloc();
+	}
+}
+
+AudioManager::~AudioManager()
+{
+	kd_free(sources);
+}
+
+void AudioManager::clear()
+{
+	kd_clear(sources);
+
+	for(auto s : active_set) {
+		s->stop();
+	}
+	active_set.clear();
+}
+
+void AudioManager::add_source(AudioSource *s)
+{
+	Vector3 pos = s->get_position();
+	if(kd_insert3f(sources, pos.x, pos.y, pos.z, s) == -1) {
+		fprintf(stderr, "AudioManager: failed to add source!\n");
+	}
+}
+
+void AudioManager::active_range(const Vector3 &pos, float range)
+{
+	std::set<AudioSource*> newset;
+
+	// find all the sources in the given range and construct newset.
+	struct kdres *results = kd_nearest_range3f(sources, pos.x, pos.y, pos.z, range);
+	while(!kd_res_end(results)) {
+		newset.insert((AudioSource*)kd_res_item_data(results));
+		kd_res_next(results);
+	}
+	kd_res_free(results);
+
+	/* for each of the currently active sources, if they're not in the
+	 * new set, stop the playback.
+	 */
+	for(auto s : active_set) {
+		if(newset.find(s) == newset.end()) {
+			s->stop();
+		}
+	}
+
+	/* for each of the new active sources not found in the currently active
+	 * set, start the playback.
+	 */
+	for(auto s : newset) {
+		if(active_set.find(s) == active_set.end()) {
+			s->play();
+		}
+	}
+
+	// swap the current with the new, previous current will be destroyed at end of scope
+	std::swap(active_set, newset);
+}
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/auman.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/src/audio/auman.h	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,23 @@
+#ifndef AUMAN_H_
+#define AUMAN_H_
+
+#include <set>
+#include "kdtree.h"
+#include "source.h"
+
+class AudioManager {
+private:
+	struct kdtree *sources;
+	std::set<AudioSource*> active_set;
+
+public:
+	AudioManager();
+	~AudioManager();
+
+	void clear();
+	void add_source(AudioSource *s);
+
+	void active_range(const Vector3 &pos, float range);
+};
+
+#endif	// AUMAN_H_
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/sample.cc
--- a/prototype/src/audio/sample.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/audio/sample.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -5,6 +5,17 @@
 #include "openal.h"
 #include "sample.h"
 
+
+#define CHECK_ERROR \
+    do { \
+        unsigned int err = alGetError(); \
+        if(err != 0) { \
+            fprintf(stderr, "%s:%d: AL error: %#x\n", __FILE__, __LINE__, err); \
+            abort(); \
+        } \
+    } while(0)
+
+
 AudioSample::AudioSample()
 {
 	albuffer = 0;
@@ -36,7 +47,7 @@
 	printf("loading sample: %s: %ld samples/s, %s (%d chan)\n", fname, vinfo->rate,
 			vinfo->channels == 1 ? "mono" : "stereo", vinfo->channels);
 
-	long num_samples = ov_pcm_total(&vf, -1);
+	long num_samples = ov_pcm_total(&vf, -1) * vinfo->channels;
 	int16_t *samples = new int16_t[num_samples];
 
 	long bufsz = num_samples * sizeof *samples;
@@ -62,6 +73,7 @@
 	}
 
 	alBufferData(bufobj, alfmt, samples, bufsz, vinfo->rate);
+	CHECK_ERROR;
 	if(alGetError()) {
 		fprintf(stderr, "failed to load sample data into OpenAL buffer: %u\n", bufobj);
 		goto err;
@@ -82,3 +94,19 @@
 	}
 	return false;
 }
+
+AudioSample *load_audio_sample(const char *fname)
+{
+	AudioSample *s = new AudioSample;
+
+	if(!s->load(fname)) {
+		delete s;
+		s = 0;
+	}
+	return s;
+}
+
+void destroy_audio_sample(AudioSample *s)
+{
+	delete s;
+}
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/sample.h
--- a/prototype/src/audio/sample.h	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/audio/sample.h	Mon Sep 17 08:40:59 2012 +0300
@@ -1,6 +1,8 @@
 #ifndef SAMPLE_H_
 #define SAMPLE_H_
 
+#include "dataset.h"
+
 class AudioSample {
 private:
 	unsigned int albuffer;
@@ -12,6 +14,13 @@
 	~AudioSample();
 
 	bool load(const char *fname);
+
+	friend class AudioSource;
 };
 
+typedef DataSet<AudioSample*> SampleSet;
+
+AudioSample *load_audio_sample(const char *fname);
+void destroy_audio_sample(AudioSample *s);
+
 #endif	// SAMPLE_H_
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/source.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/src/audio/source.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,73 @@
+#include "openal.h"
+#include "source.h"
+
+AudioSource::AudioSource()
+{
+	sample = 0;
+
+	alGenSources(1, &alsrc);
+	alSourcei(alsrc, AL_LOOPING, AL_TRUE);
+}
+
+AudioSource::~AudioSource()
+{
+	if(alsrc) {
+		if(is_playing()) {
+			stop();
+		}
+		alDeleteSources(1, &alsrc);
+	}
+}
+
+void AudioSource::set_sample(const AudioSample *sample)
+{
+	stop();
+
+	if(sample) {
+		if(!sample->albuffer) {
+			fprintf(stderr, "%s: trying to attach null buffer!\n", __FUNCTION__);
+			return;
+		}
+		alSourcei(alsrc, AL_BUFFER, sample->albuffer);
+	}
+	this->sample = sample;
+}
+
+const AudioSample *AudioSource::get_sample() const
+{
+	return sample;
+}
+
+void AudioSource::set_position(const Vector3 &pos, bool viewspace)
+{
+	alSourcei(alsrc, AL_SOURCE_RELATIVE, viewspace ? AL_TRUE : AL_FALSE);
+	alSource3f(alsrc, AL_POSITION, pos.x, pos.y, pos.z);
+}
+
+Vector3 AudioSource::get_position() const
+{
+	float pos[3];
+	alGetSourcefv(alsrc, AL_POSITION, pos);
+	return Vector3(pos[0], pos[1], pos[2]);
+}
+
+bool AudioSource::is_playing() const
+{
+	int state;
+	alGetSourcei(alsrc, AL_SOURCE_STATE, &state);
+	return state == AL_PLAYING;
+}
+
+void AudioSource::play()
+{
+	if(sample) {
+		alSourcePlay(alsrc);
+	}
+}
+
+void AudioSource::stop()
+{
+	if(sample) {
+		alSourceStop(alsrc);
+	}
+}
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/audio/source.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/src/audio/source.h	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,27 @@
+#ifndef SOURCE_H_
+#define SOURCE_H_
+
+#include "vmath/vmath.h"
+#include "sample.h"
+
+class AudioSource {
+private:
+	unsigned int alsrc;
+	const AudioSample *sample;
+
+public:
+	AudioSource();
+	~AudioSource();
+
+	void set_sample(const AudioSample *sample);
+	const AudioSample *get_sample() const;
+
+	void set_position(const Vector3 &pos, bool viewspace = false);
+	Vector3 get_position() const;
+
+	bool is_playing() const;
+	void play();
+	void stop();
+};
+
+#endif	// SOURCE_H_
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/camera.cc
--- a/prototype/src/camera.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/camera.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -132,6 +132,10 @@
 	inval_cache();
 }
 
+const Vector3 &FpsCamera::get_position() const
+{
+	return pos;
+}
 
 
 FlyCamera::FlyCamera()
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/camera.h
--- a/prototype/src/camera.h	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/camera.h	Mon Sep 17 08:40:59 2012 +0300
@@ -56,6 +56,8 @@
 
 public:
 	void input_move(float x, float y, float z);
+
+	const Vector3 &get_position() const;
 };
 
 class FlyCamera : public Camera {
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/dataset.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/src/dataset.h	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,68 @@
+#ifndef DATASET_H_
+#define DATASET_H_
+
+#include <string.h>
+#include <string>
+#include <map>
+#include <functional>
+#include "datapath.h"
+
+template <typename T>
+class DataSet {
+private:
+	mutable std::map<std::string, T> data;
+
+	std::function<T(const char*)> load;
+	std::function<void(T)> destroy;
+
+public:
+	DataSet(std::function<T(const char*)> load_func, std::function<void(T)> destr_func);
+	~DataSet();
+
+	T get(const char *name) const;
+};
+
+template <typename T>
+DataSet<T>::DataSet(std::function<T(const char*)> load_func, std::function<void(T)> destr_func)
+{
+	load = load_func;
+	destroy = destr_func;
+}
+
+template <typename T>
+DataSet<T>::~DataSet()
+{
+	if(destroy) {
+		for(auto it : data) {
+			destroy(it.second);
+		}
+	}
+}
+
+template <typename T>
+T DataSet<T>::get(const char *name) const
+{
+	auto iter = data.find(name);
+	if(iter != data.end()) {
+		return iter->second;
+	}
+
+	const char *path, *slash;
+	if((slash = strrchr(name, '/'))) {
+		path = slash + 1;
+	} else {
+		path = name;
+	}
+	if(!(path = datafile_path(path))) {
+		fprintf(stderr, "can't find data file: %s\n", name);
+		return 0;
+	}
+
+	T res = load(path);
+	if(res) {
+		data[name] = res;
+	}
+	return res;
+}
+
+#endif	// DATASET_H_
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/level.cc
--- a/prototype/src/level.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/level.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -107,6 +107,14 @@
 	return Vector3(posx, 0, posy);
 }
 
+void Level::get_cell_coords_at(const Vector3 &pos, int *xptr, int *yptr) const
+{
+	float posx = pos.x + cell_size * (float)xsz / 2.0f;
+	float posy = pos.z + cell_size * (float)ysz / 2.0f;
+	*xptr = (int)round(posx / cell_size);
+	*yptr = (int)round(posy / cell_size);
+}
+
 unsigned int Level::get_cell_dirmask(int x, int y) const
 {
 	unsigned int dmask = TILE_ALL;
@@ -229,6 +237,16 @@
 }
 
 
+AudioSample *Level::get_sample(int x, int y, int which) const
+{
+	const GridCell *cell = get_cell(x, y);
+	if(!cell) {
+		return 0;
+	}
+	return cell->get_sample(which);
+}
+
+
 GridCell::GridCell(Tile *tile)
 {
 	if(tile) {
@@ -285,3 +303,14 @@
 		psys_draw(ps);
 	}
 }
+
+AudioSample *GridCell::get_sample(int which) const
+{
+	for(auto tile : tiles) {
+		AudioSample *s = tile->get_sample(which);
+		if(s) {
+			return s;
+		}
+	}
+	return 0;
+}
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/level.h
--- a/prototype/src/level.h	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/level.h	Mon Sep 17 08:40:59 2012 +0300
@@ -4,9 +4,9 @@
 #include <vector>
 #include "vmath/vmath.h"
 #include "psys/psys.h"
+#include "tile.h"
 
 class GridCell;
-class Tile;
 
 class Level {
 private:
@@ -30,6 +30,7 @@
 
 	const GridCell *get_cell(int x, int y) const;
 	Vector3 get_cell_pos(int x, int y) const;
+	void get_cell_coords_at(const Vector3 &pos, int *xptr, int *yptr) const;
 	unsigned int get_cell_dirmask(int x, int y) const;
 
 	void update(unsigned long msec, float dt);
@@ -37,6 +38,8 @@
 	void draw() const;
 	void draw_lights() const;
 	void draw_post() const;
+
+	AudioSample *get_sample(int x, int y, int which) const;
 };
 
 class GridCell {
@@ -57,6 +60,8 @@
 	void draw(unsigned int draw_mask) const;
 	void draw_lights(unsigned int draw_mask) const;
 	void draw_post(unsigned int draw_mask) const;
+
+	AudioSample *get_sample(int which) const;
 };
 
 #endif	// LEVEL_H_
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/main.cc
--- a/prototype/src/main.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/main.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -5,7 +5,7 @@
 #include "opengl.h"
 #include "psys/psys.h"
 #include "level.h"
-#include "texman.h"
+#include "texture.h"
 #include "camera.h"
 #include "datapath.h"
 #include "tileset.h"
@@ -14,7 +14,8 @@
 #include "cmdcon.h"
 #include "cfg.h"
 #include "timer.h"
-#include "audio.h"
+#include "audio/audio.h"
+#include "audio/source.h"
 
 bool init(int xsz, int ysz);
 void cleanup();
@@ -43,6 +44,8 @@
 
 static bool show_con;
 
+static AudioSource *move_sound;
+
 int main(int argc, char **argv)
 {
 	glutInit(&argc, argv);
@@ -91,8 +94,17 @@
 
 	add_data_path(".");
 	add_data_path("data");
+	add_data_path("data/audio");
 	add_data_path("sdr");
 
+	if(cfg.sound && !init_audio()) {
+		fprintf(stderr, "failed to initialize audio, continuing silently\n");
+		cfg.sound = false;
+	}
+	if(cfg.sound) {
+		move_sound = new AudioSource;
+	}
+
 	rend = new DeferredRenderer();
 	if(!cfg.use_deferred || !rend->init(xsz, ysz)) {
 		printf("falling back to crappy renderer...\n");
@@ -126,17 +138,13 @@
 
 	cam.input_move(0, 0.5, 0);
 
-	if(cfg.sound && !init_audio()) {
-		fprintf(stderr, "failed to initialize audio, continuing silently\n");
-		cfg.sound = false;
-	}
-
 	return true;
 }
 
 void cleanup()
 {
 	if(cfg.sound) {
+		delete move_sound;
 		destroy_audio();
 	}
 
@@ -238,17 +246,22 @@
 	float dx = 0, dy = 0;
 
 	// handle key input
+	bool did_move = false;
 	if(keystate['w'] || keystate['W']) {
 		dy -= offs;
+		did_move = true;
 	}
 	if(keystate['s'] || keystate['S']) {
 		dy += offs;
+		did_move = true;
 	}
 	if(keystate['d'] || keystate['D']) {
 		dx += offs;
+		did_move = true;
 	}
 	if(keystate['a'] || keystate['A']) {
 		dx -= offs;
+		did_move = true;
 	}
 
 	cam.input_move(dx, 0, dy);
@@ -256,6 +269,24 @@
 	tileset->update_tiles(msec);
 	level->update(msec, dt);
 
+	// play the walking sound if we're walking
+	int cellx, celly;
+	level->get_cell_coords_at(cam.get_position(), &cellx, &celly);
+
+	const AudioSample *move_sample;
+	if(did_move && (move_sample = level->get_sample(cellx, celly, TILE_SAMPLE_WALK))) {
+		if(move_sample != move_sound->get_sample()) {
+			move_sound->stop();
+			move_sound->set_sample(move_sample);
+			move_sound->play();
+		}
+	} else {
+		if(move_sound->get_sample()) {
+			move_sound->stop();
+			move_sound->set_sample(0);
+		}
+	}
+
 	last_upd = msec;
 }
 
@@ -287,6 +318,27 @@
 		stereo_shift_pressed = true;
 		break;
 
+	case 'p':
+		{
+			Vector3 pos = cam.get_position();
+			int cell_x, cell_y;
+			level->get_cell_coords_at(pos, &cell_x, &cell_y);
+			printf("Current position: [%.2f %.2f %.2f]  cell: [%d %d]\n", pos.x, pos.y, pos.z,
+					cell_x, cell_y);
+		}
+		break;
+
+	case 'P':
+		{
+			Vector3 pos = cam.get_position();
+			int cell_x, cell_y;
+			level->get_cell_coords_at(pos, &cell_x, &cell_y);
+			AudioSample *sample = level->get_sample(cell_x, cell_y, TILE_SAMPLE_WALK);
+			printf("walk sample: %p\n", (void*)sample);
+		}
+		break;
+
+
 	case '\n':
 	case '\r':
 		{
@@ -375,5 +427,5 @@
 unsigned int load_psys_tex(const char *fname, void *cls)
 {
 	TextureSet *texset = tileset->get_textures();
-	return texset->get_texture(fname);
+	return texset->get(fname);
 }
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/material.cc
--- a/prototype/src/material.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/material.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -48,7 +48,7 @@
 		for(int j=0; j<2; j++) {
 			aiString tex_name;
 			if(asstypes[i][j] > 0 && aiGetMaterialString(assmat, AI_MATKEY_TEXTURE(asstypes[i][j], 0), &tex_name) == 0) {
-				tex[i] = texset->get_texture(tex_name.data);
+				tex[i] = texset->get(tex_name.data);
 				break;
 			} else {
 				tex[i] = 0;
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/material.h
--- a/prototype/src/material.h	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/material.h	Mon Sep 17 08:40:59 2012 +0300
@@ -2,7 +2,7 @@
 #define MATERIAL_H_
 
 #include "color.h"
-#include "texman.h"
+#include "texture.h"
 
 enum {
 	TEXTYPE_DIFFUSE,
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/texman.cc
--- a/prototype/src/texman.cc	Sun Sep 16 08:16:50 2012 +0300
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,75 +0,0 @@
-#include <string.h>
-#include "opengl.h"
-#include "imago2.h"
-#include "texman.h"
-#include "datapath.h"
-
-unsigned int load_texture(const char *fname);
-
-TextureSet::~TextureSet()
-{
-	for(auto iter : textures) {
-		glDeleteTextures(1, &iter.second);
-	}
-}
-
-unsigned int TextureSet::get_texture(const char *fname) const
-{
-	auto iter = textures.find(fname);
-	if(iter != textures.end()) {
-		return iter->second;
-	}
-
-	const char *path, *slash;
-	if((slash = strrchr(fname, '/'))) {
-		path = slash + 1;
-	} else {
-		path = fname;
-	}
-	if(!(path = datafile_path(path))) {
-		fprintf(stderr, "can't find texture: %s\n", fname);
-		return 0;
-	}
-
-	printf("loading texture: %s\n", path);
-	unsigned int tex = load_texture(path);
-	if(tex) {
-		textures[fname] = tex;
-	} else {
-		fprintf(stderr, "failed to load texture: %s\n", path);
-	}
-	return tex;
-}
-
-unsigned int load_texture(const char *fname)
-{
-	struct img_pixmap img;
-
-	img_init(&img);
-	if(img_load(&img, fname) == -1) {
-		img_destroy(&img);
-		return 0;
-	}
-
-	unsigned int intfmt = img_glintfmt(&img);
-	unsigned int fmt = img_glfmt(&img);
-	unsigned int type = img_gltype(&img);
-
-	unsigned int tex;
-	glGenTextures(1, &tex);
-	glBindTexture(GL_TEXTURE_2D, tex);
-	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_LINEAR);
-	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
-	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
-	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
-
-	if(GLEW_SGIS_generate_mipmap) {
-		glTexParameteri(GL_TEXTURE_2D, GL_GENERATE_MIPMAP_SGIS, GL_TRUE);
-		glTexImage2D(GL_TEXTURE_2D, 0, intfmt, img.width, img.height, 0, fmt, type, img.pixels);
-	} else {
-		gluBuild2DMipmaps(GL_TEXTURE_2D, intfmt, img.width, img.height, fmt, type, img.pixels);
-	}
-
-	img_destroy(&img);
-	return tex;
-}
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/texman.h
--- a/prototype/src/texman.h	Sun Sep 16 08:16:50 2012 +0300
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,17 +0,0 @@
-#ifndef TEXMAN_H_
-#define TEXMAN_H_
-
-#include <string>
-#include <map>
-
-class TextureSet {
-private:
-	mutable std::map<std::string, unsigned int> textures;
-
-public:
-	~TextureSet();
-
-	unsigned int get_texture(const char *fname) const;
-};
-
-#endif	// TEXMAN_H_
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/texture.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/src/texture.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,41 @@
+#include "opengl.h"
+#include "imago2.h"
+#include "texture.h"
+
+unsigned int load_texture(const char *fname)
+{
+	struct img_pixmap img;
+
+	img_init(&img);
+	if(img_load(&img, fname) == -1) {
+		img_destroy(&img);
+		return 0;
+	}
+
+	unsigned int intfmt = img_glintfmt(&img);
+	unsigned int fmt = img_glfmt(&img);
+	unsigned int type = img_gltype(&img);
+
+	unsigned int tex;
+	glGenTextures(1, &tex);
+	glBindTexture(GL_TEXTURE_2D, tex);
+	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_LINEAR);
+	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
+	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
+	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
+
+	if(GLEW_SGIS_generate_mipmap) {
+		glTexParameteri(GL_TEXTURE_2D, GL_GENERATE_MIPMAP_SGIS, GL_TRUE);
+		glTexImage2D(GL_TEXTURE_2D, 0, intfmt, img.width, img.height, 0, fmt, type, img.pixels);
+	} else {
+		gluBuild2DMipmaps(GL_TEXTURE_2D, intfmt, img.width, img.height, fmt, type, img.pixels);
+	}
+
+	img_destroy(&img);
+	return tex;
+}
+
+void destroy_texture(unsigned int tex)
+{
+	glDeleteTextures(1, &tex);
+}
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/texture.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prototype/src/texture.h	Mon Sep 17 08:40:59 2012 +0300
@@ -0,0 +1,11 @@
+#ifndef TEXTURE_H_
+#define TEXTURE_H_
+
+#include "dataset.h"
+
+typedef DataSet<unsigned int> TextureSet;
+
+unsigned int load_texture(const char *fname);
+void destroy_texture(unsigned int tex);
+
+#endif	// TEXTURE_H_
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/tile.cc
--- a/prototype/src/tile.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/tile.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -21,6 +21,8 @@
 {
 	tset = tileset;
 	last_upd = LONG_MIN;
+
+	memset(samples, 0, sizeof samples);
 }
 
 Tile::~Tile()
@@ -39,6 +41,14 @@
 	}
 }
 
+AudioSample *Tile::get_sample(int sidx) const
+{
+	if(sidx >= 0 && sidx < MAX_TILE_SAMPLES) {
+		return samples[sidx];
+	}
+	return 0;
+}
+
 const struct psys_attributes * const *Tile::get_unique_psys() const
 {
 	return &psattr[0];
@@ -85,6 +95,11 @@
 	printf("loaded tile %s: %d meshes, %d lights\n", saved_fname, (int)meshes.size(), (int)lights.size());
 
 	aiReleaseImport(scn);
+
+	// XXX get the default audio samples for now
+	SampleSet *sampleset = tset->get_samples();
+	samples[TILE_SAMPLE_WALK] = sampleset->get("walk_stone.ogg");
+	samples[TILE_SAMPLE_RUN] = sampleset->get("run_stone.ogg");
 	return true;
 }
 
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/tile.h
--- a/prototype/src/tile.h	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/tile.h	Mon Sep 17 08:40:59 2012 +0300
@@ -7,6 +7,7 @@
 #include <psys/psys.h>
 #include "mesh.h"
 #include "light.h"
+#include "audio/sample.h"
 
 enum {
 	TILE_NORTH	= 1,
@@ -16,12 +17,21 @@
 	TILE_ALL	= 0xffff
 };
 
+enum {
+	TILE_SAMPLE_WALK,
+	TILE_SAMPLE_RUN,
+
+	MAX_TILE_SAMPLES
+};
+
 class TileSet;
 
 class Tile {
 private:
 	TileSet *tset;
 
+	AudioSample *samples[MAX_TILE_SAMPLES];
+
 	std::vector<Mesh*> meshes;
 	std::vector<unsigned int> mesh_side, light_side, psys_side;
 	std::vector<Light*> lights;
@@ -38,6 +48,8 @@
 	Tile(TileSet *tileset = 0);
 	~Tile();
 
+	AudioSample *get_sample(int sidx) const;
+
 	const struct psys_attributes * const *get_unique_psys() const;
 	int get_unique_psys_count() const;
 
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/tileset.cc
--- a/prototype/src/tileset.cc	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/tileset.cc	Mon Sep 17 08:40:59 2012 +0300
@@ -6,6 +6,11 @@
 
 static TileSet *active_tileset;
 
+TileSet::TileSet()
+	: texset(load_texture, destroy_texture),
+	  sampleset(load_audio_sample, destroy_audio_sample)
+{
+}
 
 TileSet::~TileSet()
 {
@@ -66,6 +71,16 @@
 	return &texset;
 }
 
+SampleSet *TileSet::get_samples()
+{
+	return &sampleset;
+}
+
+const SampleSet *TileSet::get_samples() const
+{
+	return &sampleset;
+}
+
 Tile *TileSet::get_tile(const char *name) const
 {
 	auto res = tiles.find(name);
diff -r d52711f2b9a1 -r aa9e28670ae2 prototype/src/tileset.h
--- a/prototype/src/tileset.h	Sun Sep 16 08:16:50 2012 +0300
+++ b/prototype/src/tileset.h	Mon Sep 17 08:40:59 2012 +0300
@@ -4,15 +4,18 @@
 #include <string>
 #include <map>
 #include "tile.h"
-#include "texman.h"
+#include "texture.h"
+#include "audio/sample.h"
 
 class TileSet {
 private:
 	std::map<std::string, Tile*> tiles;
 
 	TextureSet texset;
+	SampleSet sampleset;
 
 public:
+	TileSet();
 	~TileSet();
 
 	bool load(const char *fname);
@@ -20,6 +23,9 @@
 	TextureSet *get_textures();
 	const TextureSet *get_textures() const;
 
+	SampleSet *get_samples();
+	const SampleSet *get_samples() const;
+
 	Tile *get_tile(const char *name) const;
 
 	void update_tiles(unsigned long msec);