Just Another Game Engine / News: Recent posts

After some investigation and a lot of trial and error, I got audio effects working. In case anybody else happens to come upon this problem, here's some info: the stream provided in the SDL mixaudio callback is PCM data in the format chosen when you set up the mixer. I set up SDL_Audio with the AUDIO_S16SYS flag, which means the stream data is signed (S) 16-bit (16) and uses the system byte ordering (SYS), which on Intel is little-endian. I also chose to use two channels (stereo), so the data for each channel are paired up, making for 32 bits per two-channel "sample" (Two channels of 16 bits each).
A PCM sample for my setup looks like this:
[short: left channel amplitude)][short: right channel amplitude]
Each value is a measure of the amplitude of the waveform for that channel at that discrete point in time, ranging from -32767 to 32767 (range of a short- I'm probably off by one or two.) The sampling rate is the number of these samples that gets processed by the sound driver per second, so in my case, since I'm using 44100 hz (CD sample rate), there'll be 44100 of these 32-bit samples to process each second.
To make noise, for instance a sine wave, you have to create a series of these samples reflecting the amplitude of the sine wave at each sample point. For instance, a repeated series of samples like this:
[0][0] [100][100] [0][0] [-100][-100]
gives you a sine wave with a max amplitude of 100/32767 (pretty quiet) and a period of four samples, giving you a tone a little over 11khz. Repeat the four samples ad nauseum (44100 of them per second) and you've got a sustained sine wave.
To mix audio, you can just add the values of samples together and clamp the resulting value to the min and max of the data type (in my case, short.) This could cause some nasty-sounding clipping but it's a simple solution. (Mixing well is a whole other challenge). So to echo, you add the current sample to the sample from X ms ago, and you have a X ms echo.

I've been side-tracked for around a month (!) getting pathfinding working. Today I integrated what I hope to be the final version of the path finder for the Appalachia (tentative title for the scene with "Jed") project. It uses a standard grid-style A* algorithm with a special method for finding adjacent nodes.
When I completed the first version of the path finder, I had a plain A* algorithm that used a grid of 2d integer coordinates, and it worked great as long as the search space involved was small. However, when I made the grid of nodes match the map in pixels, it stopped being feasible, because the number of nodes requiring traversal in a map without obstacles alone scaled linearly with the distance in nodes from start node to goal node. I hadn't planned on it costing so much when I implemented it, but I'd overlooked the cost at each node of finding out if each adjacent node was already in the closed or open node lists (see A* on Wikipedia for an explanation.) Even using a binary index, checking for the existence of a node in a list costs O(log (n)) where n is the number of nodes in each list, which meant the overall runtime would be O(n*log(n)) where n is the distance in nodes from start to goal. This really hurt performance on my netbook, bringing it from about 60 fps to 30. To alleviate the problem, I started using a variable grid-size so I could vary how many nodes the path would search by, for example, treating a group of 3x3 group of nodes as a single node. That meant there were a lot fewer nodes to search. The resolution would vary with the distance from begin to goal to keep the number of search nodes in check while controlling the cost of searching. This didn't work as well as I wanted though because it's possible to find no path at a larger node size when there actually is a valid path available (although it'd require a smaller node size to find.) I tried some variations on the same algorithm, but decided it wouldn't work after all.
While looking for solutions online, I found a tutorial on gamasutra about using a navigation mesh for pathfinding [http://www.gamasutra.com/features/20020405/smith_01.htm], which looked like it'd take more time to implement than I'd like to invest, so I didn't end up using the idea, but the article described a technique of "sectorizing" the nodes in a search space to effectively consolidate nodes without losing the ability to treat the search space as a grid. This seemed like a really useful technique that would work well with existing code, so I prototyped a version called QuadPathFinder that subdivides the search space in a manner similar to the way a quadtree. When looking for the nodes adjacent to a given node, the algorithm quadrisects the search space until it finds a square area without any obstacles and, instead of treating each unit square within as a node, only considers the squares on the inner perimeter of the area, which are all then considered nodes adjacent to the given node. That meant instead of the adjacent nodes of coordinate x,y being (x+1,y) (x,y+1) (x-1,y) and (x,y-1), the adjacent nodes become all the nodes on the inner perimeter of the largest obstacle-free area containing the given node. What that means is we can skip all the intermediary nodes between the given node and its adjacent nodes. So in a square area without obstacles, instead of searching n*n nodes, where n is the width of the area, we only need to search 4*n-4 nodes (the number of nodes that make up the inner perimeter of the square area.) That ends up saving a ton of time when searching large areas without obstacles, as is the case in the Appalachia project. This does require one last step when creating the final path though: while tracing the path from goal node back to the start (after the algorithm's found a valid path), the missing nodes we skipped need to be recreated, since we didn't add them when looking for adjacent nodes. In this step, the QuadPathFinder uses a variation on Bresenham's algorithm to figure out the coordinates of the skipped nodes.
This algorithm seems to be good in places where there are lots of empty spaces, but is probably bad in maze-like maps with small areas that can be traversed. Another important thing to note is that the algorithm doesn't account for the cost of traversal through each node; a node can either be traversed or not, a big difference between it and the standard A* algorithm (but one that doesn't matter for Appalachia.)
Hope this has been interesting and possibly of use to you!

The engine is in decent enough shape for me to promote it to alpha now. The scene isn't done, but most of the work I've been doing (and all that remains for the scene) has been in the scene itself, not in the engine. I've got to get art and sound effects for the scene, finish the win scenario, and make whatever changes are needed, as highlighted by play testers. Took the project to the Chicago Experimental Game Development meetup and got some very helpful criticism.
I'm looking for sound effects, art, and music now. I've used Audiosparx for sound effects in the past, so that's probably where I'll get them this time too. I figure after I get the sprite sheets done (swinging Roger is all that remains,) I can hire an artist to replace my programmer art. For music, I'm thinking of using "Music for Pieces of Wood". That would have to be a purchase made by players though (because I can't license it), and it would require an additional dependency for the MP3 decoder. I'd really like to include it but those two obstacles will probably prevent it from happening. Music may end up being simple .wav flourishes that play at key moments. That's how they did it in "Judith" (freeware) and I think it worked pretty well.
I'll post updates more frequently from now on; I'm starting to wrap up development on this scene and there'll be more to write about as I go into this final stage. This is kind of new to me. I've never hired an artist before or had actual play testing. This should be fun. :)

I'm guessing I'm about half done with the "scene" I'm working on now. I'm calling it a scene because it's actually only about five minutes of game play. I'm thinking it'll be done by July. I'm trying to lean toward over-estimating the time needed because I'll probably be coming up with other things I want the engine to do and will need time to add. I'm not sure why I'm setting a date because it doesn't really matter, but I guess it'll be neat to look back after I've finished and see how far off my estimate was.
Anyway, I'm planning on just promoting to alpha status after finishing the scene, since I'd guess by then the project will be in a state usable by other developers, for the most part. After it's in alpha, I'll probably start getting it to work on other platforms. My main goal would be 32-bit Windows and Mac (already runs fine on Xandros and, presumably, Linux in general). After that, 64-bit would be nice but that'll probably be quite a bit of work. I've been assuming (abusing may be more appropriate) 32-bit behavior so far and haven't really given much thought at all to 64-bit.
Anyway, that's the state of things.

Since there have been a couple source reads, I guess it would be helpful to anybody downloading to have some info on what this is. This is a 2d game engine using 16-bit color depth exclusively (weird eh) being developed on Linux but which uses SDL in an effort to make it compatible with Win and Mac, although I have yet to actually build it on either. So far there is a functioning system that supports sprite sheets, animations, very basic scene scripting, and programmable visual effects (which is probably the neatest thing about the project. So far there are effects that make surfaces appear translucent, shake around, shimmer, twinkle, and look -kind of- like they're lit by firelight.) Surfaces are arranged in a tree-like scene graph and an attempt is made to draw them efficiently using a microtile scheme. Parallax is achieved using a z coordinate that can be set on surfaces. It has support for custom borders, a crude text box/font system, and wallpapered surfaces. I think that pretty much sums it up for now.
To build, you have to run compileAll.sh and buildAll.sh in the trunk directory because I am a lazy bastard and have not learned how to make a simple automake file. Okay- I'm not lazy, just a little slow. :( Anyone who knows how to use automake would be a very welcome contributor.
Included so far are some bits and pieces from different things I've been using to test, like pieces from a breakout clone that I replaced with a space invaders clone, which I replaced with a forest scene that I plan on actually using as my first completed project.
Adios!