Competes with an existing theory while offering simpler, more convenient (and often incomplete, less explanatory) explanations2
+1
Main proponents are willing to test the theory/claim for validity
-3
Someone directly or indirectly benefits of people accepting it as a truth, as an individual (i.e. someone sells the more books/placebo the more people believe in it)34
+2
Existing knowledge undeniably makes it impossible5
+3
… and the main proponents ignore (and suggest followers to ignore) existing knowledge that clashes with their own ideas6
+4
Has peer-reviewed research and/or credible evidence in case it is completely new idea
Main proponents and experts are from the same field (e.g. evolutionary biologists defending natural selection vs. mathematicians defending creationism)8
-2
People supporting the claim or theory are more interested of defending their position and/or creating more supporters rather than researching the subject9
A lot of sound science goes here, including quantum mechanics, relativity and such but they satisfy the peer-reviewed research requirement ↩
Creationism has tons of this, including using them as an authority rather than a guy who knows about things. And tons of Steves disagree. ↩
The whole climate change hassle fits here, albeit only because while the supporters probably are right, they use their energy to moan about the subject and boosting their egos instead of doing anything. ↩
Here we describe a method for checking collisions between arbitrary objects drawn by the GPU. The objects are not limited to any shape, complexity or orientation. The objects that are checked for collisions can be the same objects that are drawn on the screen. The algorithm is pixel perfect but without further refining is limited to 2D collisions.
Description
The algorithm can be divided in three separate steps:
Determine which objects need testing
Set up the GPU buffers and draw the first object so the stencil buffer is set
Make an occlusion query using the and using the stencil from the previous buffer
If the occlusion query returns any pixels were drawn, the two objects overlap.
Determining objects that need to be tested
Figure 1.
To speed up the algorithm, we need to eliminate object pairs that can’t overlap. This can be done by projecting the object bounding volumes in screen space. Then, we can quickly check which 2D polygons overlap and do further checking. Choosing the shape of the bounding volumes/polygons is not relevant. In this document we will use rectangles for the simplicity.
The example case in figure 1 shows two colliding objects (overlapping bounding rectangles shown red), one near hit (green overlap) and one object with no collisions or bounding rectangle overlap. To determine the collisions (and non-collisions) we need checks for every bounding rectangle (15 checks) and two checks using the GPU1. Without the use of the bounding rectangles, we would need 13 more checks on the GPU.
The bounding rectangles in the example can be generated by finding the maximum and minimum coordinates and using them as the corner points of the rectangle. Since the algorithm finds collisions as seen from the camera, we need first project the object coordinates (or the object bounding volume coordinates) on the screen and find the minima and maxima using those coordinates. Most 3D frameworks provide functions for projecting a 3D point to screen coordinates using the same transformations as seen on screen2.
Drawing objects
Before we start drawing the objects on the graphics buffer, we need to clear the stencil buffer. After that, the GPU should be set to draw only to the stencil buffer, that is we don’t need the color buffer or depth buffer to be updated.
Now, the first object can be drawn. After that, we will draw the second object. Before we start we need to set up the occlusion query to count the drawn pixels. We also need to use the stencil buffer created in the previous step and set the GPU to draw only if the stencil buffer is non-zero. We don’t need to update any buffers at this point.
After the second object is drawn, the pixel count returned by the occlusion query tells how many pixels overlap. For most purposes, we can assume a non-zero value means the two objects collide3.
Figure 2.
Figure 3.
Figure 4.
Consider the above example. Figure 2 shows two objects as seen on screen. Figure 3 shows the stencil derived by drawing only the green (right) object. Figure 4 shows what will be drawn of the red (left) object if we limit the rendering to drawing on the stencil (the occlusion query will tell us six pixels were drawn).
Sprites
For sprite objects that consist of only one quad and an alpha blended texture with transparent area representing the area that cannot collide with anything, the same result can be achieved by setting the alpha testing to discard pixels below a certain tolerance. This will then avoid updating the stencil buffer on the whole area of the quad.
Optimizations
The stencil buffer can be created to contain the collision area of e.g. every enemy currently on the screen and then testing with the player object. This avoids the necessity to test between every object individually, which can be costly since the occlusion query has to finish before the next query can start. If the objects on the screen can be grouped to a handful of categories, such as the player, the enemies, player bullets and so on, multiple objects can be tested simultaneously where it is not important to know exactly which two objects collided (e.g. when deciding whether to kill the player which in a shooter game generally is because the player collides with the background, an enemy bullet or an enemy — all of which would be drawn in the same stencil buffer).
Ideally, the above can be done so that every object group has its own stencil buffer. This then makes it possible to create the stencil and start the queries in their respective buffers, do something useful while they execute and then query for the occlusion query results.
Caveats
Most of all, doing collision detection with occlusion queries is admittedly a curiosity. There are many, many ways to do collisions faster and most likely with less technicalities. Using a simple rectangle (a cube or a sphere in 3D applications) to test collisions between complex objects has been used since the first video games and it still provides acceptable accuracy. Indeed, some games even use an extremely small collision area (e.g. a single pixel) to test collisions with larger objects with great success. Additionally, the algorithm is potentially a bottleneck, especially when triple buffering etc. are used since occlusion queries generally are started after the previous frame is drawn and then read when the next frame is drawn (i.e. it’s asyncronous). This limits either the algorithm accuracy for real time (frame accuracy) or the framerate since we may have to wait for the query to finish for a relatively long time.
A serious consideration is to use the occlusion query algorithm to test between a complex object, e.g. with a large end of level boss with a complex, changing shape and use a simpler geometry based algoritm to test between hundreds of bullets. A hybrid algorithm could even first make an occlusion query to know which objects collide and then use a different algorithm to find out more about the collision.
This is inherently a 2D algorithm. The GPU sees any situations in which two objects overlap as a collision, as seen from the location of the camera. This if fine for side-scrollers et cetera, which also benefit from pixel perfect (fair, predictable) collisions, and other situations in which all the objects to be tested are on the same plane. Multiple depth levels (e.g. foreground objects never collide with background items) improve the situation and so does drawing only the parts of the objects that are between specified depth levels4.
Another possible problem is that the screen resolution may be different between systems, which makes the algorithm have different levels of accuracy. This can be avoided by doing the checks in a fixed resolution. Limiting the collision buffer resolution also improves the algorithm speed in cases the GPU fillrate is a bottleneck.
Finally, some older systems may not support occlusion queries or stencil buffers. As of 2008, this is increasingly rare but should be taken into consideration.
Appendix A. Source code for OpenGL
The following is source code extracted from a proof of a concept/prototype game written in C++ using OpenGL. The source code should be self explanatory.
The following builds the bounding rectangle for a object:
The following can be used to set the rendering mode before drawing the object on the screen, on the stencil buffer or when making the occlusion query (note how we disable most of the rendering when drawing something that will not be visible to the player, also notice how the stencil buffer is cleared if we enable stencil drawing mode — using scissor makes this efficient):
This is from the main loop, it simply goes through all objects in the game. Notice how we first prepare the collision checking for the first object to be tested (i.e. create the stencil as in step 2 of the algorithm).
for (unsigned int a=0;a<m_Objects.size();a++) {
m_Objects[a]->PrepareCollide();
for (unsigned int b=a+1;b<m_Objects.size();b++) {
if (m_Objects[a]->TestCollide(m_Objects[b])) {
// We have a collision
}
}
m_Objects[a]->FinishCollide();
}
Note that DrawObject is the same method as we use to draw the visible object on the screen. The only thing that differs is that the drawing mode is set to stencil or occlusion query. Also worth noting is how we use the rectangle to set the scissor to further reduce the workload.
void GfxObject::PrepareCollide() {
GetGfxManager()->SetScissor(this->GetBoundingRect());
GetGfxManager()->DrawObject(m_GfxId,GetPosition(),GetRotation(),STENCIL);
}
void GfxObject::FinishCollide() {
// We simply reset the scissor
GetGfxManager()->SetScissor();
}
int GfxObject::DrawCollide() {
// We could set the scissor here to even smaller area, the overlapping area
return GetGfxManager()->DrawObject(m_GfxId,GetPosition(),GetRotation(),OCCLUSION);
}
bool GfxObject::TestCollide(Object *obj) {
Rect a=GetBoundingRect();
Rect b=obj->GetBoundingRect();
// No need for further collision testing if the rectangles
// don't overlap
if (!a.TestCollide(b)) return false;
// We have a collision if any pixels were drawn
return obj->DrawCollide() > 0;
}
To speed up the checks done on the GPU, we can set the scissor rectangle to the overlapping area. This helps in cases in which the overlapping area is small compared to the complete area of the object. ↩
It may be useful to consider a larger tolerance for fairness’ sake ↩
E.g. setting the near and far clipping planes to the distance of the second object (assuming it won’t be a problem that the clipping results in objects that have a hole) ↩
Stop luring people on your trite news blogs with misleading titles. Sure, a mysterious or provocative title is a good way to get people interested, but it in worst case makes your blog (and you) look uninformed. Especially, when the first sentence of the news item doesn’t explain the inaccuracies of the main headline.
News should never be speculative and if that is the case, it has to be explicitly stated where the line between fact and fiction goes. Some news are meant to be taken as entertainment but that style of writing should not bleed to potentially important news items. At least I expect to get information from news, even if I just casually pick the interesting sounding ones.
I hereby give away another priceless idea: one-sentence news. That is, you do not need to read the full article after you have read the descriptive, 5-15 word headline. Maybe that’ll cut into the advertising profit for there are less visitors to your site from feed readers etc. but not providing full articles in a feed is yesterday. And if you really only write 20 words per article, well, I guess that could make it profitable if you divide your income by the amount of text you write.
Here’s an example: Popular Science reports “Genetic Material Found on Meteorite“. What went wrong? Take a guess. At the very least I expect to read about scientists finding very discriminating evidence on a meteorite with a blacklight, kinda like how they do it with dead hookers in CSI.
Even the subtitle right below the main title already downplays the sensational title and states “A meteorite in Australia has been found to contain component molecules of DNA”. And if you take the time to read the article, you’ll learn similar molecules that make up DNA are found on a meteorite (I bet a rather large percent of the molecules in your DNA most likely are entirely made on Earth). That’s like reporting there are organic molecules in space (look it up), and not explaining what “organic” actually means. Except in the end, right below the ad banner.
How could that be reported in one sentence and what are the benefits? First, you’ll deliver the exact same amount of information but quicker. “Similar Molecules as in Your DNA Found on a Meteorite”. “The Birth of DNA Molecules Could Have Been Helped by Completely Uninteresting Stuff on Meteorites Billions of Years Ago”. Hell, I don’t care if it’s a haiku. Just make it terse, informative and less stupid.
Probably my most favorite video games are thrustlike games – as in roguelikes begat by Rogue (ADOM, Nethack, Angband, Moria et al.). What I mean with a thrustlike is a game derivative of Asteroids, Lunar Lander, Gravitar and Spacewar that feature a simple physics model, a rotating spaceship and a button for thrust. Hence, “thrustlike” and not “gravitarlike”. Also, mostly because I really like Thrust.
Here are some of the games I consider the best examples of this genre.
Thrust (1986)
What I think Thrust does that makes it so much better than Asteroids and other household names is that it takes the simple rule of motion and inertia, and adds another basic concept, counterforce. In Thrust, you not only maneuver the ship through narrow caves but you also have to lift a heavy load (a “klystron pod”) that swings under the ship. And, in most cases the roles are reversed when the heavy pod transfers its excess kinetic energy to your stationary ship, sending you both spinning towards the nearest wall. However, the whole gameplay doesn’t feel as random as it is with many modern physics based games that often require luck or endless trial and error. You are always in charge of the physics, if you are a good enough pilot.
Thrust on the BBC Micro.
Another thing that I like about Thrust is that the player is easily able to skip a few levels by activating the self-destruct sequence of the planet by shooting the power plant a few too many times. Why I like it is that in a way you feel like you cheated the game (although, you also lost a lot of bonus points). However, without a doubt this was added to make it easier to quickly get to and practice the later levels, it’s a very nice touch it’s built in the game world. It is also possible to get hefty bonus if you manage to both fetch the pod and also destroy the power plant.
Thrust has a reputation for being hard but I can’t really agree with that. The game has a handful of levels and the regular levels are quite easy to finish when you get the hang of it. However, after that the gravity is reversed and the levels loop from the beginning and after a successful completion, the walls turn invisible. And then I guess the game goes reversed-invisible1.
Another proof of the game’s excellence is that it’s probably one of the most ported (officially or not) games, when it comes to radically different platforms. There are equally playable versions for the BBC (also the original version), the C64 (with a rocking Hubbard tune), the 8 and 16-bit Ataris and unofficial ports for Vectrex and Atari VCS2. There also is a C rewrite of the game engine that is open source, which I guess ensures the game can be ported to any semi-modern platform.
There apparently was a sequel, that wasn’t so well received (proving more does not equal better) and I have never seen it.
Gravitar (1982)
Gravitar, on the other hand, does much of the same. Thrust (1986) was obviously very influenced by Gravitar (1982)3, which was probably influenced by Asteroids (1979) and Lunar Lander (1973, 1979). Both Thrust and Gravitar have planets to visit, fuel to be beamed up, enemy bunkers that shoot back and, of course, gravity. But to me, Gravitar doesn’t have as crystallized gameplay as Thrust. Thrust is as solid as, uh, Gravitar’s vectors are, umm, sharp.
Gravitar. The graphics are so sharp you can’t see crap on Youtube videos.
What’s pretty neat in Gravitar is that you can select in which order you play the levels, the levels are simply presented as planets in a solar system and you have to fly the ship avoiding the star that is in the center of the solar system. This also gives another challenge (or a possibility to optimize your gameplay) since the star’s gravity can be exploited to save fuel. Each level also is quite different from the other levels.
Oids (1987)
Oids on the Atari ST.
Another game I really liked was Oids. It combines yet more favorites of mine with Thrust: Choplifter and Space Taxi, both outside the strictest requirements of the thrustlike genre. In Oids, the klystron pods are replaced with little guys (android slaves, or ‘oids) that you have to pick up, first of course having to land the ship carefully, and take up to the mothership. Oids is so loved that the Atari ST emulator Oidemu was made just to run the game, which wouldn’t run on other emulators — and Oidemu subsequently didn’t bother supporting any other games.
The saving the little guys idea is lifted from Choplifter (get it?) in which you use a chopper to demolish prisons and then land nearby and wait for the little men to climb aboard, making multiple runs as the chopper can carry a limited amount of men. The gameplay is much speedier in Oids, you constantly have to dodge incoming bullets and homing missiles and the levels generally are much more open than in Thrust or Gravitar. In all, Oids feels like very natural progression from Thrust.
Maybe one factor that made the game so special was the fact it shipped with a level editor.
Space Taxi (1984)
Hey, taxi!
If we bend the rules what makes a thrustlike, Space Taxi is more than a worthy addition to the genre. Especially so, if you think Lunar Lander fits in the genre — both games have similar controls (thrust up, down and to the sides) and also the common goal of landing quickly yet safely.
There was a nice clone of Space Taxi on the Amiga featuring a caveman flying a stone-age version of a helicopter (think Flintstones). The game was called Ugh! and it was later ported to the PC (it’s great) and C64 (it’s crap).
While Ugh! looks gorgeous and is fun to play, what Space Taxi does infinitely better is that every level in Space Taxi is very different from the other levels, and that is not just the layout that changes (on top of that Ugh! uses the same tiles over and over, however nicely pixeled they might be). The rules of the game are often deviated slightly. For example, one level has a beanstalk that slowly grows leaves on which you can land (and the passengers start appearing on) and others simply have disappearing walls or teleports. I guess that still makes the game quite unique, since even now games rarely have radically different levels.
There also is Space Taxi 2, which is a legit sequel but the tiny voice in my head says it can’t possibly measure up. It’s worth a check, though, as it has the same level designs as the original.
Solar Jetman: Hunt for the Golden Warpship (1990)
Solar Jetman: Hunt for the Golden Warpship is pretty much exactly what Thrust was years earlier but with updated graphics. The only difference is that in each level you have to find a different object, each being a part of the Golden Warpship and various other items which upgrade the ship you pilot around. There’s also a bit of Oids in the game, as it features more shooting and has enemies that follow you around the level.
Solar Jetman: Hunt for the Golden Warpship on the NES.
The game provides welcome variation to NES games and I can see why it wasn’t a success among the younger gamers despite the great graphics (got to love the smooth rotation of the ship). The controls are smooth but as all games of this genre, Solar Jetman can be a handful. Especially, if you are looking for more straight-forward action.
The game is the successor to Lunar Jetman (which shares only half of the name and virtually no gameplay elements, except for the little spaceman that you have to get back to the mothership when your probe is destroyed, see above video) — Solar Jetman was developed by Rare who in fact were called Ultimate Play The Game who developed Lunar Jetman for the Speccy (and loads of other very successful games). Solar Jetman was also going to be released for most of the home computers of the time but the ports were canceled and only the C64 port is available to the public.
“Caveflyers”
In the mid-1990s there was a boom for so called caveflyers (from Finnish “luolalentely”) here in Finland. The caveflyer genre probably owes more to Spacewar as it’s mainly about blowing up the other players. There were dozens of similar games that all featured hotseat multiplayer action (some even had computer controlled), various weapons and levels and most importantly destructible environments.
There had been a lot of similar games by hobbyists before the boom, the single game that started it all probably was Gravity Force on the Amiga. However, I think the flood of cavefliers (in Finland, at least) was triggered by Auts and Turboraketti on the PC. I am very sure different areas had a bit different ideas what was the hottest game but at least to me, Auts was it. After that more and more clones started appearing with constantly improving quality and broadening weapon arsenal. My favorite probably was Kaboom. On the Amiga, there was a bit older similar game called Mayhem (1993) which we played a lot. There’s an abandoned PC conversion that you can find in the linked thread.
This subgenre is still alive and there are many modern caveflyers that have Internet multiplayer features and so on.
3D thrustlikes and other oddities
Virus on the Speccy
There have been various Zarch (1987) on the Acorn Archimedes (ported later in 1998 as Virus for the Amiga, Atari ST, ZX Spectrum and PC) features similar controls for the player ship except that there now are two rotation axes. The gameplay however features minimal interaction with the landscape as there are no caves. Later in 1999, Psygnosis released Lander for the PC that featured closed levels, cargo hauling and teleporting fuel on the lander. So, Lander pretty much is Thrust in 3D.
—
So, were there any games I left out that you think should be here? Do leave a comment. Also, I’d like to thank the people who uploaded gameplay videos of Thrust, Gravitar and Oids to Youtube. I had only a NES emulator with AVI output handy.
This post is a part of a blogging experiment on writing posts based on common search queries from which this site receives traffic. Read the original post for more information on this experiment. See all posts in this series.
In Viewer2, there is a feature that allows fast text searches on huge databases with tens of thousands of filenames (and associated photo captions and other meta data). Here’s how I did it.
The easiest way to find all filenames (the following article talks about filenames but you can use this to search for any text) matching $query (the string we are looking for) can be done a bit like this:
SELECT `filename` FROM `files` WHERE `filename` LIKE '%$query%'
Similarly, you could perform for multi-word searches by adding one test for each word you have extracted from the query string. And, you can very easily extend the syntax to include exclusions. Below is the equivalent SQL query for the query string [kitten -jpg] (filenames with the text ‘kitten’ but not the string ‘jpg’):
SELECT `filename`
FROM `files`
WHERE `filename` LIKE '%kitten%'
AND `filename` NOT LIKE '%jpg%'
The above works well but it can be very, very slow because it has to go through all entries in the table files to find matching rows. Speed can be improved by having queries like LIKE 'word%' but this limits the searches and in the end doesn’t give too much extra speed.
And if you are performing fuzzy searches…
Using a token-based approach
A lot of speed can be gained by splitting the filenames and the searched text into tokens and then performing the search using the tokens. I ended up using the following structure (SQLite syntax):
CREATE TABLE `files` (
`file_id` INTEGER PRIMARY KEY AUTOINCREMENT,
`filename` TEXT
);
CREATE TABLE `tokens` (
`token_id` INTEGER PRIMARY KEY AUTOINCREMENT,
`word` TEXT UNIQUE
);
CREATE TABLE `link_file_token` (
`token_id` INT, -- Foreign key to the table `tokens`
`file_id` INT -- Foreign key to the table `files`
);
The idea is that each word in the filename can be represented with a single index to the `tokens` table. Thus, you can also search by a single integer instead of text comparison. You have to compare text only when generating the tokens (which is extremely helpful if you are using a comparatively expensive comparison).
First, when you insert the a file in the files table, you split the filename into words and link the file and the tokens (which may already exist in the `tokens` table). Later, when you need to perform a search, you do the same but use the generated tokens to search matching links.
The filename ‘Cute kitten picture.jpg‘ can be split in four tokens which results to four links between the token table and the file table. I also split words when the case between characters changes (splits filenames like ‘CuteKittenPicture.jpg‘) but this is up to you. In my implementation the tokens are also case-insensitive.
Searching using tokens
Here is a simple example query that finds matching files using the approach described above:
SELECT `filename`
FROM `files`
JOIN `link_file_token` USING `file_id`
WHERE `token_id` IN (
SELECT `token_id`
FROM `tokens`
WHERE `word` LIKE '%$query%'
)
The subquery first finds all `token_id`‘s that match the query and then the main SELECT finds all filenames that have that `token_id` linked to them. Obviously, this restricts the query to simple OR queries. This is because the text matching is done in one word scope instead of a longer string (using the above filename as an example, a single word can’t match both ‘cat’ and ‘cute’).
Here is how you would do a query like [cat OR dog]:
SELECT `filename`
FROM `files`
JOIN `link_file_token` USING `file_id`
WHERE `token_id` IN (
SELECT `token_id`
FROM `tokens`
WHERE `word` LIKE '%cat%' OR `word` LIKE '%dog%'
)
To perform an AND in the search query you need a query like this:
SELECT `filename`
FROM `files`
JOIN `link_file_token` ON `files`.`file_id` = `link_file_token`.`file_id`
AND `token_id` IN (
SELECT `token_id`
FROM `tokens`
WHERE `word` LIKE '%kitten%'
)
JOIN `link_file_token` ON `files`.`file_id` = `link_file_token`.`file_id`
AND `token_id` IN (
SELECT `token_id`
FROM `tokens`
WHERE `word` LIKE '%cute%'
)
In the above example, using a natural JOIN handles the removal of all rows that only match one of the two searched words. Don’t forget that you can do the same in many ways. For example, you can use INTERSECT (do mind though that if you intersect two result lists of strings, it might be much more resource demanding than intersecting two result lists of integers).
Evaluation order
Keep in mind that if you combine the above AND and OR queries (by adding a OR `word` LIKE… for each OR'd word), it will not work as expected. Boolean algebra states the correct order to evaluate the two operators is AND first and then OR (the relation is similar to multiplication and addition, which may help you remember that). Above, it will work the opposite, the OR is evaluated before the AND.
If you restructure the query so that it, for example, returns indexes to the files table, you can implement correct evaluation order by adding a UNION for each OR term. In effect, you first use the above query to find each pair of terms AND'd and then combine all those queries with UNION.
For the query [cat cute OR dog drooly], the resulting SQL query will look something like this:
SELECT `filename` FROM `files` JOIN ... -- cat AND cute
UNION
SELECT `filename` FROM `files` JOIN ... -- dog AND drooly
Further ideas
To implement a NEAR operator, or when it is important that the searched words are in a certain order (in short strings like filenames it's usually not at all necessary), you could add a field in the file-token links that tell the index of the word in the original string. When you have searched for the results using the above method, you then score the results based on the distance between the tokens.
E.g. if you are looking for [cute kitten], and a result has the text 'Here is a cute dog. It is not a kitten', the indexes for the words 'cute' and 'kitten' will be 4 and 10. Thus, the result should have a worse score than some other piece of text with the exact word order.
Notes
In Viewer2, the exact implementation doesn't use subqueries like described above. Instead, I first generate a longer query that has the needed `token_id`'s and other stuff filled in (a comma separated list of integers in place of the SELECT subquery). You might consider this to gain some more speed but do experiment before you optimize.
Take note that even SQLite has a similar feature called FTS2. In theory, it should provide most if not all of the above. My example is still useful if you need more control over how the text is tokenized and compared (and I think in the case of FTS2 enabling full text searching requires double the storage, if you don't want to store all the text data in the full text search table).
As always, research before you start doing something you think someone probably already did.
Older posts
Probably my most favorite video games are thrustlike games – as in 
Subscribe