08 Sep

You Can Stop Programming Now

The above is puls, a 256-byte intro by ?r?ola. It’s basically a raytracer with screen space ambient occlusion (which makes it so much realistic and cooler). While tube — which I think was the best 256-byte intro until now (when design and code are judged together) — also did raytracing of a cylinders, and after that many other intros did similar tracing of more complex surfaces, puls simply crushes all of them with objects that are formed by multiple plane surfaces (e.g. a cube would be a combination of six intersecting planes), a very nice color palette and that delicious ambient occlusion.

Thinking it out in C and sketching it out in asm took about a week, byte crunching took another one… that’s like forty hours of full focus and eighty of playing.

It’s also really, really slow which is the only minus especially because you can’t run 16-bit executables on Windows 7, so you have to use DOSBox to watch it (or, use a boot floppy to run it or something). There’s now a Windows port including a screensaver, see the Pouet.net page for more. A big thank you to nordak5 who was kind enough to upload a video on Youtube.

?r?ola has also included source code with the binary that you can find over here. That said, I’ll be deleting all my own source code since perfection has finally been achieved and there is no need for programmers anymore.

20 Apr

Blog Experiment: Comparing text and SQL

A lot of visitors come from search engines to my page about a little hack I made that acts as a very thin layer between text files and SQLite. Most of the search queries are something akin to “compare text files in SQL“, “SQL text compare” or other SQL and text comparison related searches. So, I’m going to write what I know about the subject.

Comparing text in SQL

Most implementations of SQL can do text comparison in a variety of ways. It is safe to assume any two text strings can be compared with the equal operator and the LIKE operator. The difference between the two basic operators is that the equal operator usually is case-sensitive by default (see below before assuming this is always true) while LIKE is case-insensitive. LIKE also has a nice feature: wildcards. You can check if a string contains a shorter substring.

1   SELECT `name` FROM `table` WHERE `name`='Joe Doe';
2   SELECT `name` FROM `table` WHERE `name` LIKE 'Joe Doe';
3   SELECT `name` FROM `table` WHERE `name`='% Doe';

All the above queries return the rows in which the field `name` (1) is exactly ‘Joe Doe’, not e.g. ‘joe DoE’, (2) the same as (1) but case-insensitive and finally (3) ends with the string ‘% Doe’ (case-insensitive).

As you can see, the percent string acts as a wildcard which can be substituted with any sequence of characters – much like the asterisk (*) when talking about e.g. file paths. The underscore (_) character can be replaced by any one character, this is comparable to what question mark usually does with filenames and paths. The wildcard characters can be different between implementations.

The case-sensitivity can be changed. For example, the equal operator can be case-insensitive if the collation is set to a case-insensitive method. Similarly, the LIKE operator can be set to be-case sensitive. See your SQL implementation manual how to do this.

When it comes to speed, you should always use the equal operator before LIKE. In cases like the below query it is impossible to benefit from an index:

SELECT `name` FROM `table` WHERE `name` LIKE '%Doe%'

Why? Because the substring ‘Doe’ can be anywhere in the compared string. However, most SQL implementations can gain speed from indexes when you have a query something like this:

SELECT `name` FROM `table` WHERE `name` LIKE 'Joe%'

You can think of the speed-up as something similar to trying to find a word in a dictionary. If you have a table of contents, you don’t need to look through every page: quickly flipping pages to a known page (words starting with ‘Joe’) and then finding the word on the page is a lot faster. Again, I’m sure different databases have different limitations.

Advanced comparison

One very nice feature of MySQL is that it has a special kind of comparison built in: regular expressions. The REGEXP operator is used like the LIKE operator but the string after the operator is — a regular expression.

SELECT `name` FROM `table` WHERE `name` REGEXP '^[JM]oe Doe$'

The above example matches names ‘Joe Doe’ and ‘Moe Doe’. Regular expressions of course can be much more complex than that but they are useful when you need just a little bit more functionality than what LIKE can offer.

Fuzzy comparison

Another feature that comes in my mind is PostgreSQL’s pg_trgm module that allows fuzzy text comparison based on trigrams (i.e. word is divided into sets of three letters, ‘car’ would result in trigrams ‘ ca’, ‘car’ and ‘ar ‘ — with the spaces). As far as I remember, it comes with the basic installation so it should be simple to install. Basically, you can then compare strings that are not exactly like each other but within a certain percentage.

SELECT `name` FROM `table` WHERE similarity('Joe Doe',`name`)>0.5

The above would match all names that are relatively similar (more than 50 percent) to ‘Joe Doe’. For example, ‘John Doe’ would most likely match.

And yet again, MySQL and other DB’s could have the same feature. And I intentionally left out the phonetic (“sounds like”) comparison features that are very often built-in (AFAIK MySQL and PHP should have those included by default). This article knows MySQL’s “sounds like” operator is quite logically SOUNDS LIKE.

Text files and SQL

A lot of search queries are looking for something that combines text files and SQL. As far as I know, there is no SQL engine that writes and reads raw text files as the tables (other than my hack mentioned in the first paragraph).

However, at least what I have tooled with the idea, it can be quite useful. Bundle that with the fuzzy and regexp comparison from the bigger databases and it’s a killer idea right there.

Dumping tables into text files

Most databases come with a tool that can dump (or export) the database tables into SQL statements that can then be used on another table to duplicate the structure and the data. It is quite safe to say most bigger databases have their own command line tools that can do this, a visual database tool such as phpMyAdmin for MySQL and of course numerous desktop applications for that.

I use SQLyog for MySQL tinkering. In SQLyog it is as simple as selecting the table (or database) and then clicking DB/Table > Export as SQL Statements and soon you have a text file (or XML file or…). And doing it backwards is as simple as copypasting the text file contents and running the statements.

Checking if two tables are identical

Here’s a method for comparing two tables for identical data is to inner join both tables (returns only matching rows) and checking if the number of rows is equal to the total number of rows in a table. The idea is that we use every field to be checked as a foreign key to the other table.

SELECT COUNT(*)/(SELECT COUNT(*) FROM `myFriends`) as `equality` 
  FROM `myFriends` as a, `yourFriends` as b
  WHERE a.`name`=b.`name` AND a.`phoneNumber`=b.`phoneNumber`

Column `equality` in the query result is a percentage of how many matching lines there are compared to the total row count. The above won’t care about the order of the rows which may or may not be useful (unless you include something like an auto incrementing key in the comparison).

There, another almost useful page added to the Internets. I hope the above will be helpful at least to some random visitors.

24 Mar

Show Me Yours and I’ll Show You Mine

The level editor for your games, that is. My personal experience of making games is that the behind the scenes tools such as level editors are at least half the work. If you’re lucky, you can use existing tools for creating the data but I guess that is very specific to a genre.

I have found that developing an editor is not only convenient but also allows you to polish the game mechanics a lot better than doing that purely in code. I guess many game developers think level editors and such are only for bigger projects where the programmer is not the guy who makes the levels. It is possible and manageable to create games by hardcoding the level data and object behavior but as mentioned, a proper editor is so much better.

Of course, if you have been smart, you will be able to share the code between the game and the editor. And if you are a bit smarter, you can build the editor inside the game so you have a perfect testing environment for the levels — as long as using dynamic level data is possible in your engine. An extremely good example is the Cube Engine which allows multi-player level editing while playing.

Anyway, the original point of this post is that it can be very hard to imagine what’s a good editor like. Doubly so, if your game idea is different from the average game. I figured it could be helpful for some indie game devs if I show some of my level editors. I hope this inspires people to tell about their development environment.

Below is the level editor for my forthcoming Pac-Man clone. I couldn’t use any tile-based map editors, which probably would have been more than sufficient for a tile-based game. Mine uses linked nodes that can be moved freely in 2D space.

The level editor does most of the work: the game only gets a crunched copy of the level data with precalculated splines and so on. Stuff like that makes it possible to keep the level rendering code intact while the editor gets more features. Originally, the editor and the game just did straight lines. When I added the splines to the editor, the game still got a list of straight lines and used the old code.

The game and the editor are both made using SDL and OpenGL. Using SDL means you have to reinvent the wheel a bit when it comes to GUI stuff but it is manageable. If you can figure out how to implement dragging with the mouse (SDL only provided events for mouse clicks, releases and motion), you are able to create a GUI that will be good enough for your project.

This is a level editor for an untitled shmup project of mine. All the attack wave movement is defined by Catmull-Rom splines (unless the object is of special type, e.g. a homing missile).

The editor imports all the object classes thus it is trivial to display the graphic for an object. The editor then exports the level data as C++ code by subclassing the level class and automatically writing code for events like “spawn object type Enemy when camera enters this node”.

The editor allows the user to “rewind” and “play” the level while editing. When F5 is pressed, the camera starts following the camera movement spline from the currently selected node and enemies move along their own paths. This is only an approximation since no AI code is available in the editor. That means you can only see spline based movement. It nonetheless makes it much nicer to plan attack waves.

The intermediate game level data for both editors is stored as an XML document. Most game data is representable as a tree, so XML is a natural choice for it. As recommended in an earlier post, xmlParser is an excellent choice for a quick way to save your level data. Do not fear XML because of how clunky it can be from the perspective of a programmer — the mentioned library pretty much removes most of the friction. And, you can always write an XML to converter afterwards.

Condensing, here’s what I have learned:

  • Writing an editor can be a lot of work but you can make it fun and it will pay off in the end
  • Use existing frameworks
    • for displaying the game data in the editor
    • for saving the editor data
  • If at all possible, allow gameplay inside the editor

So, what do your editors look like? What have you learned about game development and how editors can make it more fun?

21 Mar

A Tiny XML Parser

While looking for a convenient way for storing some level data for a game I’m working on (more of that later), I came across this small C++ XML parser. Originally, I wanted to stay away from XML or other formats as they are overkill for the simple game format. However, this parser is both small (the Xerces parser is over 50 megabytes!) and easy to use.

In case you can’t find a download link on the project page: you have to email the author to receive the library (the page promises a direct download link in a few weeks). I think that’s actually quite nice, considering people who write free software rarely get the praise and attention they deserve.

24 Feb

Google Chart API is pretty cool

I just stumbled upon the Google Chart API and I couldn’t resist playing with it (statistics being a fetish of mine). A few moments later, I came up with some PHP code that uses my stats plugin for WordPress to fetch page views and generates an URL for the Google API (see below for the attached source code).

The main idea behind Google Chart is that the chart is an image and all data for the chart is in the URL. That includes the chart title, size and the data sets. Personally, I think this is a brilliant idea. You can embed the charts anywhere you can use images and best of all, you don’t need to have data anywhere else but in the URL (you don’t even need to duplicate the generated image in your own webspace).
You can also pretty much generate charts by hand if needed.

On the other hand, when using dynamic data fetched from a database, it is a relatively small task to encode the data into the format Google Chart uses. They even provide a Javascript snippet for that (obviously, you might want to do that server-side – see below). Or, you can simply use floating point numbers if you don’t mind long URLs (and I’m not even sure you can always use very long URLs).

For example, below there’s a graph generated from daily visits to this site:

And here is the URL used to get that graph (lines split for convenience):


The above URL has quite Google-like short parameter names but that’s obviously because of technical limitations. The chd parameter is where the data set for the graph is: s:NQGHJsimple encoding : encoded data.

One interesting aspect arises because of the encoding: you need to fit your data set to use the granularity the encoding has. E.g. when using simple encoding and encoding a data set of 0, 4.7 and 244, you have to normalize and remap the data so the data goes from 0 (character A) to 61 (character 9), not from 0 to 244. That may sound horribly inaccurate but remember, nobody measures the charts with a ruler – they look at the numbers for accurate data. And there are more accurate encodings.

I like how the charts look slick. A lot of existing libraries and APIs for similar stuff tend to have less aesthetic appeal. Anti-aliasing does not better stats make but it certainly looks more professional. The API also has nice features such as adding arrows and red X’es on a graph (think an arrow with the caption “stock market crash” – after which the graph plummets), the always useful Venn diagrams (see right) and other usual stuff you’d need.

Anyway, my original point was that Chart is a cool API, is probably easier to use and faster to install than gnuplot or other chart drawing software, is compatible with any browser able to display images and it’s free for everyone to use (the limit is something like 50 thousand views per user per day – and I guess their policy says nothing against caching the charts on your own site). Check it out.

P.S. This is quite obvious but… I predict that in the future, Google will use the accumulated charts for some kind of statistics search. The charts contain text (label, title) so a Google search result might include relevantly labeled graphs. Which is an interesting scenario, considering the Internet is full of lies, kooks and gullible users.