Note that these games only use "45 degrees" ramps. Those 45-degrees slopes don't even need to have lookup tables because y(x+1) = y(x) + 1. It's easy to code such collisions with only addition/subtraction operations.
How they managed to implement the game engine for NES Solstice is much more impressive (given that the NES is tile-based and has one single tile layer). Most people don't realize it, not even those who have played the game, but quite some ingenuity had to be put into it.
The most general attack against MD5 I am aware of is choosen-prefixes collision. Not quite a second preimage attack, but is more powerful than ordinary collision attack.
What I meant with my question was "how is it broken such that it makes it a bad choice in this particular case". As was established earlier, the possibility of deliberate tampering is not the issue here.
A common smaller one is a single CPU instruction, but actually, these instructions are built up by microinstructions, so one could use these as steps too.
Only perhaps the newest consoles. Certainly not the oldest ones. Dividing opcodes into microinstructions is a modern invention. Back then there weren't even pipelines or caches, much less "microinstructions". Each machine opcode took an exact amount of clock cycles to execute, so a clock cycle is the unit of time in older processor (in way, in modern ones too, although it's a bit more complicated).
Voting no because a similar version got rejected for bad game choice.
I think that raises the question of whether that's a valid reason for more or less automatic "no" vote. Just because one of the reasons for a previous run to have been rejected is that the game choice was poor doesn't necessarily mean that all future submissions should automatically be rejected as well. Perhaps a future submission will make the run more entertaining eg. by exploiting bugs or doing something unexpected. (I'm not saying this is such a case.)
Btw, just clear up possible confusion, I would like to point out that the code I posted is not originally mine (although I wasn't sure when I posted it because I couldn't remember). I did figure out the algorithm (or something very similar) all by myself many years ago, and implemented it. However, for this particular implementation I looked up an existing algorithm called midpoint circle algorithm. (You'll probably recognize the variable names in that wikipedia article.) The only thing I did was to modify it slightly so that no repeated pixels would be drawn.
The only thing I can't figure out is why f is set to 1 - radius in particular, but I get the principle.
Note that if you started with a distance of exactly radius, the distance of the next pixel would immediately be too large and hence the y coordinate would be decremented immediately. This would cause all circles to have ugly single pixels poking out of each four main directions. To alleviate this problem the radius is effectively incremented by a half pixel. IIRC correctly the initialization is related to that (it has been so long since I figured out and understood the exact algorithm that I don't remember it precisely right now).
Actually the circle-drawing algorithm given there is not completely optimal because it draws some pixels twice, and uses a needless multiplication by 4 (even though you can optimize it to a left-shift which, in fact, can be slower in some architectures than an integer addition).
I actually once deduced the circle-drawing algorithm all by myself, just for the fun of it.
The basic idea is that you start from one of the points where the circle intersects the main axis (we can assume the circle is centered on the origin, as translating the pixels to their actual location can be trivially done when drawing the pixels), eg. from x=0, y=radius, and then start moving to the right one pixel at a time and keep updating the distance of the new pixel from the origin at each step. If this distance becomes larger than the radius, you decrement y by one (and update the distance variables, of course). While not immediately obvious, it is possible to keep this distance updated using a few integer additions. When you reach the point where x==y, you are done. (You have calculated an eighth of the circle, but the other eighths can be trivially drawn because of symmetry.)
I actually dug up an implementation I once made. It's very optimized in that it never draws the same pixel twice (as is extremely common in implementations you find on the net), and uses only integer additions and subtractions for each pixel, nothing else. (Note that the majority of the code below is the pixel drawing. Each calculated pixel must be duplicated 8 times on each symmetry axis, plus the first and possibly last four pixels have to be drawn separately if we want to avoid duplicated pixels.) Have fun trying to figure out why the algorithm works.
Language: cpp
void drawCircle(int cx, int cy, int radius)
{
int f = 1 - radius;
int ddF_x = 1;
int ddF_y = -2 * radius;
int x = 0;
int y = radius;
drawPixel(cx, cy + radius);
drawPixel(cx, cy - radius);
drawPixel(cx + radius, cy);
drawPixel(cx - radius, cy);
while(true)
{
if(f >= 0)
{
y--;
ddF_y += 2;
f += ddF_y;
}
x++;
ddF_x += 2;
f += ddF_x;
if(x >= y) break;
drawPixel(cx + x, cy + y);
drawPixel(cx - x, cy + y);
drawPixel(cx + x, cy - y);
drawPixel(cx - x, cy - y);
drawPixel(cx + y, cy + x);
drawPixel(cx - y, cy + x);
drawPixel(cx + y, cy - x);
drawPixel(cx - y, cy - x);
}
if(x == y)
{
drawPixel(cx + x, cy + y);
drawPixel(cx - x, cy + y);
drawPixel(cx + x, cy - y);
drawPixel(cx - x, cy - y);
}
}
Btw, I got that in the Linux version of Firefox. I'm also getting the same behavior and error in the MacOS X version, so the problem is not limited to the Linux version or my particular configuration.
Edit: I have Firefox 3.5 on the MacOS X, and Firefox 3.6 on Linux, so it isn't a question of version either.
You really wouldn't want to advance at a rate of one Planck time per step. You would go mad of boredom before you would advance even one billionth of a nanosecond.
For some reason the "watch now using" links are not showing up anymore for me in firefox. They show up ok in konqueror. I haven't changed any settings (javascripts are enabled for tasvideos.org, and it doesn't seem to even try to load them from anywhere else). Apparently the recent player change is the cause for this, but I can't really understand why.
This thought experiment breaks down totally if you take that argument to its logical extreme. You wouldn't be able to manipulate luck because you wouldn't remember what approaches failed. You wouldn't be able to use slowdown, as that would just slow down your brain too. You couldn't disassemble the workings of the world, since a character in a game wouldn't know how to do that. Etc. etc. So the 'real world TAS' would just be living normally! Realistic, but not much fun to think about.
Even if the "TASing" was limited somehow, eg. you could only rewind a few minutes at a time, and could only remember your last attempt but no further (or, alternatively, you could remember only a limited amount of time before you forget), it would still be useful. For example, you could score 3 points in basketball 20 times in a row for an amazing feat (which you could bet on). It could also save your life in dangerous situations.
The function sqrt(r^2 - x^1) gives you a nice half circle. So, if you want to draw a circle at point (x,y) with a radius of r, you could do so using something like:
for (i == x - r + 1; i < x + r; i++)
{
draw_point(y - sqrt(r^2 - (i - x)^2));
draw_point(y + sqrt(r^2 - (i - x)^2));
}
Now, I'm not sure how well you can approximate square roots in 6502, but this should be a lot more useful than sine/cosine stuff.
If you read what I posted, you'll see that it's not necessary to resort to such a heavy-duty function as sqrt in order to draw a circumference of pixels. A few integer additions and subtractions per pixel is enough, using a clever algorithm.
As for a cyclic motion, if it doesn't have to be exactly a sine wave, it can be perfectly well and efficiently approximated with a parabola (in other words, the x2 function) which you mirror and repeat (which, like the circle, can be created with just a few additions and subtractions per point, but the algorithm is even simpler than with the circle drawing).
Besides interpolating values in lookup tables, there are also tons of clever algorithms to calculate circular and other types of spline paths by using additions and subtractions only (or at most a few multiplications per path). These were quite popular in the days when every single clock cycle mattered (modern game programmers have it really easy).
Well, almost. In fact, some of the algorithms are still pertinent even today. For example, OpenGL has no direct support for drawing circles, but it has support for drawing a bunch of individual pixels very efficiently. If you needed to draw tons of circles as fast as possible, even on a modern computer, you could go the lazy way of using sin/cos or the sqrt methods, but that would be needlessly wasteful. In fact, it's possible to draw a circumference of pixels using integer additions and subtractions only (something like 3 or 4 of them per pixel; I don't remember the exact algorithm right now) and a couple of conditionals (per pixel). (If you need to draw a filled circle, it's simply a matter of drawing horizontal lines from edge to edge, which is something that hardware also supports.)
Most opengl circle drawing tutorials you find out there will use the lazy way of drawing lines using sin/cos, but as said, that's the inefficient (and inexact) way of doing it (it's inexact because you are not going to calculate the coordinates of every single pixel with sin/cos, only a few of them). However, as said, it's possible to do this without having to resort to those heavy-duty functions, restricting yourself to a few integer additions/subtractions per pixel, which is really efficient.
(OTOH, nowadays you often would want to draw an antialiased circle, which is quite a lot more complicated than drawing just a circumference of pixels. If the hardware line drawing supports antialiasing, at least you get that for free if you use the sin/cos + line drawing method.)
If someone can make an entertaining non glitched run I'll be very impressed.
Once again, "non-glitched" is far from being easy to define. For example, if you can grab a ladder one frame earlier than normally by doing something special does it constitute a "glitch" or not? If you drop down from a magnet beam and you get immediately full downwards speed because of that (something you don't get when falling from regular platforms) does it constitute a "glitch" or not? (One can argue it's a programming error or oversight.)
You could have a "no major glitches" run, but then you would have to come up with a rather arbitrary list of banned glitches. (A potential problem arising from this is that if a new glitch is discovered during the making of the run, if it should be added to the list or not.)
I don't believe it is, actually. You'd have one hell of a hard time proving that you happened to independently come up with such a similar result, but if you did manage to do so, it would not be infringement. There would be no theft of intellectual property.
However, in the real world, so to speak, it would almost certainly be trademark infringement. And that would shut you down real good.
Trademark infringement? Where did that come from?
Trademarks have nothing to do with copyrights. You don't get automatic trademarks, nor are copyrighted works "trademarked". A trademark is (usually) a brand name that has been officially registered with the proper authority. It's related to the usage of that brand name in a specific context (for example, "Windows" is a trademark owned by Microsoft in the context of computer operating systems, but not eg. in the context of architecture, where someone could perfectly well use the brand name without infringement, as long as it's not confused with the operating system).
In the context of a piece of art, eg. a book, you could trademark a specific name which can be considered a brand (eg. "Star Trek"), but that's distinct from copyright.
By the way, I was not using a modified 'version' of the game. Its the same game. Have you ever been to http://www.fpsbanana.com/ ? Seriously. If I want my tank in Left 4 Dead to look like Venom from Spiderman ( http://www.fpsbanana.com/skins/66757 ), it won't change the gameplay whatsoever.
A game mod isn't exclusively limited to gameplay modifications. Any modification to an existing game is a mod, even if you just change some textures or sounds.
The point is that, as Derakon said, if you use a visibly modded game, that will only raise suspicion for many people. "Hey, he is using a modded game. You can eg. see that this texture is different. This clearly is a fake and cheating." Of course just changing a texture doesn't mean that the run is not genuine and wouldn't work exactly in the same way in the original, unmodified game, but if you give stupid people any reason to raise suspicion on the legitimacy of your run, they will use it.
Even when people know that the run is completely legit, some of them might still prefer seeing it done on the original unmodified game. (Same reason as why eg. skin hacks are basically always rejected at tasvideos.)
Also, I don't know what you are talking about when you said about modified sounds.
The end song was not the original. Maybe you just overdubbed it in the video (rather than modifying the game itself), but it wasn't clear from the video.
I have completed the game Portal by Valve for the PC in under 10 minutes. The speedrun is called Portal Done Pro.
Here is a link to the YouTube video of it:
http://www.youtube.com/watch?v=W1U5RUVENNE
I think it's a bad idea to use a modded version of the game (clearly some textures and sounds were modified). It just raises the suspicion of what else has been modded, perhaps something allowing tricks not normally possible.
