Tuesday, March 30, 2010

EversionMod 1.2 bug fixes

I've fixed the gem counting problem for levels before level 8. Also, the HUD is not drawn for level 8; place a 0xDB tile anywhere in the area8.map to force drawing of the HUD for that map. Conversely, place a 0xDA anywhere in a map to hide the HUD for that map. In addition to these tiles, there's also a 0xDC tile which forces the 7-8 gem warp to update according to how many gems the player has collected. This allows the player to collect all the gems on the last level and return to the 7-8 gem warp and eversion. In the original Eversion, you would need to restart the level in order for the 7-8 gem warp to update.

You can't reach these tiles normally, you'll have to turn off "Available tiles only" from the edit menu to get to them, or you can edit "./data/tileLayout.txt" and "./data/tiles.png" and add the 0xDA to 0xDC tiles manually. Closing all the windows in EversionEditor and then opening another window will force the reloading of tileLayout.txt and tiles.png.

EversionMod 1.0

EversionMod 1.2

Friday, March 26, 2010

Obicham -- Color Algorithm

I discovered yesterday that the color selection algorithm I used for the nearest color algorithm didn't quite cover all the possible combination of foregrounds, backgrounds, and blends. The old algorithm code looked something like this:

Let c be the color that is the texel in an image at row y, column x:
Find the nearest two colors in the 16-color VGA palette (note: O(16) time)
Let output be the console character on the screen at row y, column x
Let output's background color be the closest color (most predominant visually)
Let output's foreground color be the next closest color (least predominant visually)
Let output's display character be a blend between 0%, and 50% fill, depending on how close the color is to its nearest color (blank) or to its second-nearest color (50% fill)

And with the new palette containing all available possible characters:

(We build the table before hand)
For fg in 16-color VGA palette:
 For bg in 16-color VGA palette:
  For bl in the available blend amounts:
   Let blend be the bl% mix of color fg onto bg
    If the fg, bg, and blend combination doesn't already exist in the palette then
    Add blend, along with the fg, bg, and blend used, to the palette

(Next, the color selection algorithm)
Let c be the color that is the texel in an image at row y, column x:
Let output be the console character on the screen at row y, column x
Set output to be the fg, bg, and blend combination for the closest color to c in the palette (note: O(310) time)

For small palettes, say the old 16 colors, this algorithm didn't need any optimization. However, now that we have all the possible 310 (!) colors, this algorithm now becomes quite heavy. For an image sized 80 by 60, the total time to convert an image will take O(80x60x310) time, or O(1,488,000) time! So a hunt begins for a data structure that will improve the speed.

I first thought a Voronoi diagram would help sort the data. However, implementing a 3D Voronoi tree builder took me more time than I was willing to spend on it. So I searched elsewhere.

Next, I hypothesized that a Voronoi diagram is the same as a BSP where its branches are a selection of planes, where each unique plane is equidistant to two unique points. Also, it would be faster for me to implement. In a half hour's time, I came up with a rough tree building algorithm:

If there is only one point in P left, then add it to the tree, and return
Find a plane, L, that is equidistant between two points that splits the points as close to half as possible
Repeat for points in P that are in front of the plane L
Repeat for points in P that are behind the plane L

Although there is a small delay building the tree (brute force implementation), the results of this tree are significantly faster, since it takes at most log(310)/log(2) ~8 checks per texel instead of 310! However, my assumption is incorrect:

On the right is the non-BSP color selection algorithm (most correct), and on the left is the BSP color selection algorithm. As you can see there are abnormalities in the BSP color selection algorithm. It became quite clear to me that making a planar cut anywhere in a Voronoi diagram chops off some of the cells! D'oh!

Well, from here I can do two things to spend my weekend:
  1. Build a proper Voronoi structure
    • Either using Fortune's algorithm
    • Or by creating convex meshes from the availble planes built by the original BSP algorithm
  2. Duplicate some of the data in the BSP tree
  3. Play DoTA/League of Legends
  4. Catch up on homework

Hmm ...

Tuesday, March 23, 2010

Obicham -- 3D Rasterizing Demo in a Console Window

Speaking of demos, here's one I recently did. It's a traditional 3D rasterizer ... in a DOS console! Heck yes. The process goes like this: A Rasterizer renders objects in a sort of OpenGL immediate mode fashion onto an Image, a two dimensional array of Colors, and then sends it to a Console which then takes that Image and converts the individual pixels into ascii-characters, and sends the result to the window. A SDL debug window rendered the same image in another window with true color to help debug how the Console was choosing its blend of 16-colors.


Here's the first ever screenshot from Obicham. Its supposed to be a box. As you can see, it is not; it's more like a rhombus on a flat piece of paper that's being rotated. Turns out I was multiplying the matrices in the wrong order.

Here's the second ever screenshot from Obicham, this time, with the matrices multiplied in the right order. This is still supposed to be a box. As you can see, there's some serious WTFs/sec going on. To add insult to injry, the top vertices spun in the opposite direction of the bottom vertices.

Polygon filling and color blending. This took a few tries to get right, but there it is. On the left is the main window, the console window, and on the right, is another SDL window for debugging.

First rotating cube! Having some trouble with the polygon filling, the technique I was using didn't do any bounds-checking, so I aggressively clamped the transformed x and y coordinates of the vertices, which changed the geometry a bit. I also chose a different charset to use for the blending. Looks better, doesn't it?

Same rotating cube! This time, I redid the bounds-checking on the polygon filling, added some back-face culling.


Showing off the different modes the demo offers.

Obicham Demo 2.0 (few more demos, better colors)
Obicham Demo 1.0

Wednesday, March 17, 2010

Video Game in a Week -- Day 4

Well, grim news. I have to put this project on hiatus; this is going to take longer than a week, and I plan to finish it sometime over the summer. Right now, I'm just gonna enjoy my spring break. Here's a semi-playable demo*. At the moment, there's no gameplay elements other than maneuvering; there's no dying, no obstacles, etc. I've tried testing MarbleRun on another computer, and the materials turned up black. Not sure how to fix it, but I'll worry about it later. Another curious thing, when you set the direction of the light towards the south-west corner of the map causes the stencil shadows to go crazy. Also not sure how to fix, but I'm pretty sure it may have to do with ProBoolean not liking the level, i.e. a large chunk of the mesh is removed when I try to combine it with a mesh.

*Heh, if I were to call this a game, I'd be in the same boat as "Big Rigs: Over the Road Racing." Therefore MarbleRun stands as a demo.

Move the mouse to orient the camera
Right mouse button sets the light direction
Space resets the player to the start
The keys W, S, A, and D maneuver the marble FPS style.

Visual C++ 2010 RC1 Runtime Libraries (not included with download)

MarbleRun alpha .3

Tuesday, March 16, 2010

Video Game in a Week -- Day 3

Made some progress today. Setting up Bullet is taking me longer than expected, but at least I'm making some headway. 3dsmax's pro-boolean tool didn't like the tube in the test level, so I had to re-make that part in order to make a few changes to the tube. The results turned out better than I expected. The overall progress of MarbleRun, however, is slower than I expected and I'm worried if I'll be able to meet all the requirements on time... Also had to battle 3dsmax for a while, took me half an hour to figure out that pressing the space bar during "walk-through" mode locks the pitch of the camera! Grawr!



Monday, March 15, 2010

Video Game in a Week -- Day 2

Didn't have much time today to work on Marble Run, had to work today and lots of chores to do. However, of the goals for the day, I accomplished all but the last. I seem to be having trouble obtaining the Ogre wrapper for Bullet. In the meantime, here's how Marble Run is looking:

Here's a 3dsmax rendering of the test level:

Here's what it looks like in game:

Simple directional light with stencil shadows == drool!

I also had a lot of trouble trying to get the materials to show up in Ogre, and it turns out all I was missing was one line of code. Spent more time than I'd like to disclose on getting the materials to show up properly.

Sunday, March 14, 2010

Video Game in a Week -- Day 1

Got the whole week off of school; something about a Spring break epidemic or something. Anyways, about sometime last week I thought it would be a really cool idea if I can get a whole entire game completed in a week. After giving it some thought, I figured it would be a great way to pass the time! The game will be titled "Marble Run," a clone of my favorite marble games, Marble Madness and Hamsterball. I'll be programming in C++, using Ogre3D for rendering, OpenAL for audio, and Bullet for physics. Since I've chosen all open-source multi-platform technologies, I plan to make the source available on release.

Here's the target schedule:
  • Day 1: Basic application setup with Ogre
  • Day 2: Build sample level, integrate Bullet3d
  • Day 3: Gameplay elements and menus
  • Day 4: Asset creation
  • Day 5: Asset creation
  • Day 6: Asset creation, polishing
  • Day 7: Polishing, release

At the closing of the first day, I have accomplished the day's goal with a simple application, Ogre rendering, FPS-style movement and mouse-look:

Saturday, March 13, 2010

Eversion Level Editor 1.3, EversionMod 1.0 Released!

Introducing EversionMod 1.0, which feature modified Eversion scripts that improve the flexibility of the editor. Eversion Level Editor 1.3 now supports EversionMod 1.0's extended tiles. EversionMod includes features such as supporting unlimited number of levels, changing the player starting position, setting the starting eversion per level, support for vertical levels, and support for the death/blood-walls. Eversion Level Editor 1.3 has a new font change, and some new tiles to support the extended tiles that are used in EversionMod. Documentation for Eversion Editor has now moved online, where I can edit it for everyone whenever I find a mistake. :)


Here's a quick demo of the features of EversionMod 1.0 as well as how to install it, and how the extended tiles look inside the editor.

Visual C++ 2010 RC1 runtime libraries (included with download) -> vcredist_x86.exe

Eversion Level Editor 1.3 and EversionMod 1.0
EversionMod 1.2 bugfix

Saturday, March 6, 2010

Eversion Level Editor released!

It's finally here! The level editor you have been waiting for! What are you waiting for? Go download it now!


Demonstrating some capabilities of an older version of the editor. This version uses software rendering GDI, which was incredibly slow. The newer version employs OpenGL, and therefore it's fast(er)! Also, I'm not liking fraps for video recording. It took me all day to get that video onto youtube without any video/audio syncing issues.

Visual C++ 2010 RC1 runtime libraries (included with download) -> vcredist_x86.exe

Eversion Level Editor 1.3 and EversionMod 1.0
Eversion Level Editor 1.0