There is a delay in the keyboard movement in order to make it possible to change Peter's facing (look into another direction) without actually walking.
When Peter is looking to the left and you press right, Peter will turn right immediately, but you need to _hold_ the button for more than 1 frame in order to walk to that direction.
In mouse movement, there's no need for those delays.
This is necessary when turning towards a box without moving it (so that you can kick it instead).
However, if there's no box at the direction where you turn the delay doesn't really make sense. It could be removed without it affecting gameplay (that is, only have a delay when turning towards a box).
OTOH removing the delay now would make many if not most of the records for longer levels obsolete, ruining many hours of hard work.
By the way, isn't it interesting how much competition can reduce the time of a level like this? The current record is already more than one minute faster than your original record...
I wonder how many of the other levels could be equivalently reduced...
Towards the end of 5-1, when you have 5 boxes left, you leave the three boxes on the lower right to be and go directly to handle the two other boxes. I have the feeling that you should get a somewhat faster path if you go to the three boxes first and move them closer to the goal before taking the two boxes to the goal. However, for this I think that you have to get the box at the top right closer to the goal before you can do this (else it will be on the way).
Also, from the three boxes in the lower right you push the lowest one in such way that when it is the only one left you have to make a rather large walk around in order to get to it. I think that it would be beneficial to push it at least one step up (from the location you leave it currently) so that you can walk directly to it.
A game should have the best possible controls and not make crappy^H^H^H^H^H^H difficult controls part of the challenge.
It's not so much a question of good/bad controls but more a question of behaviour. An interruptible kick might be seen by some as a good thing in very long levels because you might have already played 5 minutes of the level and then you accidentally press the kick button when you shouldn't, risking to ruin the entire run. However, since you can interrupt it by moving then you just do so and lose just some tenths of a second instead of having to start all over again.
But of course uninterruptible kicks will make it trivial to not to waste time after the kick has been done, cutting a great deal of time in most runs.
However, where should this aiding stop? Next someone will suggest that the 1-frame delay when turning with the keyboard should be removed (except when turning towards a box), thus making keyboard navigation almost as fast as mouse navigation, thus making it a whole lot easier to get top times.
However, mouse navigation, especially in long levels, requires tons of practice and skill. Once again, what do we want? A show of skill or a show of (easy) speed? Is this a challenge about who finds the fastest path, or a challenge about who finds the fastest path and is able to perform it with the uttermost skill?
Of course I have to admit that it feels a bit exasperating that someone could just look at your path, practice a bit with the mouse and beat your time by some tenths of a second... But skill is skill.
Ok, worked a bit on it and beat your record by 6 frames with a sloppy as hell performance.
I'm still not happy, so you'll have to do better... ;)
(My route is still not perfect. I will have to perfect the moving combinations of those last blocks. I also have some mistakes costing precious tenths of seconds, summing up probably to several seconds...)
By the way, about the discussed (un)interruptible kicks and mouse paths:
IMO mouse paths should remain interruptible. In fact, I have used this exact feature to my advantage in some runs. In longer levels it's very difficult to constantly use the mouse, so for some levels where there's a point to which you need to go dozens of times I simply but the mouse cursor there and place the mouse so that I can press its left button with my thumb. This way every time I need to go to that point I just press the mouse button with my thumb, regardless of where peter is at that point. This is a rather easy way of saving extra tenths of seconds in long levels.
However, sometimes I need to go towards that point only partially. In other words, I press the mouse button to make peter walk towards that point but then at the point I need to deviate I just press the cursors. This is actually handy. If, however, mouse movement could not be interrupted with the keyboard, I could no longer do this.
As for the kicks, it's a question of skill. If kicks are uninterruptible then one big element of skill is removed from the game, making it a lot easier to make fast times. Do we want to just show off how fast a level can be completed, or do we want to compete on who has the most skill in completing a level as fast as possible? After all, this is not tool-assisted speedrunning, but a genuine show of skill.
There's one great thing about this site: It's not stuffed with tons of blinking flashy ad banners like most other sites (which makes them a real pain to surf). It would be a pitty if this site was degraded to the same level as all those other sites.
Edit: Actually, I have no idea if this only affects this level. I just mentioned the level number because it's the last level and maybe nobody has beaten it before...
And that's what makes this game so cool! There are so many glitches that can be used to save time that it is.. awesome! ;)
However, if you actually try playing the game and try finding the glitches (especially without knowing them), they are extremely hard to find and to abuse. I think most of the glitches can only be performed with tool-assistance, and even then they are probably rather elaborated.
Then what you were describing wasn't actually a compression technique, like I read it as, but a pre-process technique that was relying on zLib to do the actual heavy-weight compression.
Technically speaking, you may be right. I think that what I was doing before giving the data to zlib to compress is called a filter in compression techniques.
A filter does not actually reduce the size of the data (in some cases it may even increase it), but it modifies it so that it will compress better, and that's exactly what I was doing.
(As a curiosity, filtering is the reason why a PNG will often be smaller than taking the raw image and compressing with an archiver program.)
Anyways, that's just semantics. The end result is what's important. :P
It would be convenient if when traversing a completely unobstructed rectangle he would minimize the number of turns, and make the straight approach to the target square in the target direction be as long as possible.
I assume this would only have aesthetic meaning because, as far as I know, turns do not have the 1-frame penalty when using the mouse...
The middle mouse button can be used for "kicking", but apparently it also invokes a "<load link from clipboard and load that page>" feature in Mozilla, effectively unloading the game.
The windows version of mozilla does not have this feature and there the middle button kick works just ok. (Aargh, windows-only features??? ;) )
First, and this is the simple trick, merge all the tiles that move the same amount into a single 'macro tile' when there are more than a certain amount of them. Considering that a bit-mask of the entire screen on NES (256x240) would only be 30 bytes (16x15 blocks, 240 bits, 8 bits to the byte) and the vast majority of the screen IS going to move in lock-step, this is very likely to reduce the space needed for matching block-moves dramatically.
That might or might not reduce the video size, depending on how exactly zlib does its work. Zlib will, naturally, already compress sets of identical motion vectors in some way. I'm actually not completely convinced that even if the result is smaller that the reduction would be so dramatical (it could be, of course).
You have to also take into account that your 30-byte bitmask will often be a rather random set of values, making compression harder.
My guess is: More compression, probably. Dramatically more compression, unlikely.
Second, also simple, don't try to keep things aligned on the byte-order. For example, if you only need (-16,15) range, don't use 8 bits. Use 5 bits.
Again, the benefit of this depends a lot on how it affects the values to be compressed and how zlib works. If zlib works on a byte-by-byte or a 2-bytes-by-2-bytes basis, storing values between byte boundaries might actually do more harm than good (depending on how "random" the resulting bytes will be, of course). Of course only practical testing will show.
When I tested my compression idea, the single element which BY FAR most affected compression was, naturally, that the diff frames are mostly full of zeros. Other little optimizations (such as creating special frames which do not store as much information or choosing motion vectors so that there would be more repetition) only improved the compression slightly.
I don't think that eg. reducing somehow the amount of motion vectors will have a big impact on the compression ratio (although even a 1% better compression is always welcome, of course).
Third, and this would be simple but processor-intensive (what compression isn't?), try all possible alignments of the grid on the new screen. Don't lock them to the boundaries of the screen, so to speak. This would allow better 'locking' with two-axis-scrolling games, and moderately improve the lockdown on single-axis-scrolling games.
This might have some impact, and another thing which might have some impact is to extend the macroblock search (partially) outside the image boundaries (which I did not do). It might increase the amount of zeros in the frame diff info which can markedly increase compression.
The bitmasks can be trivially encoded with run-length compression run through some type of Huffman compression as a trivial solution, which could also work quite well with the limited-selection 'unvectored pixel' values on highly-limited-palette systems like the NES games since such a technique would cause a LOT of chaotically-random sequential pixels that might not compress well because their localized relevance was dramatically reduced, so Huffman's advantage (localized differences aren't any harder to compress than distant differences) might give it an edge over more modern LZ-based compression.
Huffman encoding is actually part (in fact, I think it's the major compression algorithm) of zlib. By default zlib makes first a dictionary search and then it compresses the result using huffman-encoding. So it's probably already doing what you describe above (about compressing the pixels with huffman).
Actually I felt a bit bad about looking at your route and then copying it and beating your time by just a few tenths of a second... But I just had to try, I couldn't resist. Sorry. :)
I'll have to try that change you suggest to see if I can beat my own time.
I have a rather acceptable skill for understanding spoken English, but in that clip they are talking very unclearly plus the extreme compression makes it even harder to understand. So I didn't get even 10% of what they were saying. (I am referring to the walker video clip; Conan's speech was quite clear.)
Is there a website where I can learn more about this optimized for at-most-256-color tile-based scrolling videos codec?
Explaining my idea exactly? Probably not (unless someone has come up with the same idea and made such page, which isn't completely impossible, actually). I used well-known motion video compression techniques, though. Here's a short description:
My main idea was to use motion vectors to describe the motion of square-shaped areas of the picture. This is exactly the same thing as the MPEG-1 motion vectors idea (as far as I know). It works like this:
Divide the image into square-shaped blocks. The optimal size for the blocks depends on a few factors (the smaller the blocks the more optimal motion vectors you will find, but the more vectors there will be, taking up space, of course; and the other way around). By trying different sizes I found out that 16x16 pixel blocks are the most optimal for NES videos (I also tried 8x8 and 4x4 but they gave bigger results).
Now, in frame N, for each block search from previous frames (ie. frame N-1, N-2, etc) a 16x16 area of the image which most resembles the contents of the block in this frame. The block being searched in previous frames can be located anywhere in the frame (not just at block boundaries). In other words, the search should be started from every pixel of the previous frame. Naturally the more frames you search the slower the encoding will become. I designed my video format so that it would support searching from at most the N-16 frame (ie. I reserved 4 bits for this information). In practice I only searched at most from the N-8 frame because of speed/compression ratio.
The comparison function as another thing to optimize. Often you will find an exact match (ie. a block which is identical to the current block) but not always. In this case you should find a block which is as similar as possible. Since I supported only paletted 256-color images in my video I ended up with a quite simple function being more or less optimal: A function which counts how many of the pixels are different in the two squares being compared.
To speed up the searching you can limit how far from the location of the current block (in image coordinates) the search is done. Since games usually don't scroll too much at a time (eg. scrolling a half screen at a time is extremely rare) you can limit the search to a certain amount of pixels away from the current block. I used 32 pixels as this limit (in other words it searches inside an area of 65x65 pixels around the current block). My format supports motion vectors between (-128,-128) and (127,127) (ie. I reserved two bytes per motion vector).
There are tricks to speed up the searching: I started the search from the same location as the current block and then in a spiraling order around it since it's most probable that an identical block will be found in earlier frames very close to the location of the current block (naturally if you find an identical block there's no need to continue searching). Also, as you search, you naturally keep count of the best match found so far. A radical speedup is achieved with the simplest trick: When comparing blocks if the current sum of differing pixels becomes larger than the current best, stop comparing. (It's actually a very simple idea but it didn't occur to me at first...)
Once you find the motion vectors for all the blocks in the current frame, write them to the result. Now, since the frame which can be reconstructed from these motion vectors will usually not be identical to the original frame, of course, we will now have to write a differential frame. That is, reconstruct the current frame using the motion vectors (ie. for each motion vector copy the block it refers to and reconstruct a frame in this way) and then calculate the difference of the actual current frame and the reconstructed one. Since the differences will be minimal, most of the diff frame will be full of zeros (which compress very well). Write this diff info to the result.
Now, compression has to be used for the result, of course. I used zlib for this. Unlike many other C libraries, zlib is surprisingly easy to use, especially for writing compressed files: You simply use "gz" versions of the regular C file handing functions (ie. gzopen(), gzwrite(), etc) and that's it, you get a compressed file.
The main idea in this is, naturally, that since the diff frames are usually just mostly full of zeros they compress extremely well, and this is indeed the case.
I used some other minor tweaks to increase compression as well:
- I used different types of frames. For example, if the diff info is completely full of zeros it's rather useless to store all those zeros, thus I just store a special frame type which has only motion vectors but not diff info. And likewise, if all the motion vectors are zeros it's useless to store them. If both are full of zeros, then it's not necessary to store the frame at all. I also made "one-color frames" which are used if the original frame is just filled with one color (in which case it's enough to simply store that color).
- When searching for motion vectors I tested first the same motion vector as in the previous block. In scrolling videos this often gives an identical block right away, speeding up the encoding, plus it makes more of the motion vectors identical, enhancing the compression ratio.
I actually made simple player program for unix (uses GTK) to play the videos in order to check that they are bugless. If anyone is interested I could make a packet and include the three example videos.
It is, after all, a 10 minute movie crammed into 64kb. What they're doing is unreal...
People are way too accustomed to bloatware, thanks to the big software developers.
Those developers don't care about optimizations. Heck, most of them don't want to optimize. They want and in fact need to get results fast and they don't care if it takes 100 times more memory and disk space. Memory is cheap, disk space is cheap, why would they want or need to optimize the size of their software?
This has caused people to grow into the belief that all programs are big by necessity. A program which draws pretty graphics on screen has to be big, a 3D engine has to be big, graphics take a lot of space, there's no other way. Then when someone shows them that it's not the only way, they get amazed. They can't understand how it is possible.
Which reminds me of one thing:
As far as I know, many of the categories awarded to the movies are done so more or less automatically just because the author claims in his submission that the movie belongs to that category. That is, the one who publishes the submission usually makes no effort to check the validity of the categories. In other words, categories are awarded way too loosely, lessening their usefulness.
With some categories this isn't a problem, of course. For example, most of the genre categories are probably ok and there's little to check there.
However, some categories are awarded, in my opinion, too easily to any movie which the author claims it to belong to. One example of this is the "manipulates luck" category.
That is one category which I think should have a much tighter definition. If the definition is too loose then practically all movies where (pseudo)random things happen belong to that category. This would include the majority of movies.
I think that this category should mean that luck manipulation is such an important and drastic thing that without it the movie would be twice longer or whatever. Luck manipulation should also be clear to the viewer, especially if we assume the viewer has played the game. The castlevania 2 movie is a great example of this: Each monster kill gives a heart, even though in regular play this happens a lot more rarely. If one has played the game one immediately sees that luck is being strongly manipulated and that it is saving huge amounts of time (because collecting a certain number of hearts is mandatory).
If the "luck manipulation" in a video means that the position of a monster is manipulated so that the run will be 0.1 seconds faster, in my opinion it's not enough to deserve the category. The luck manipulation should be very obvious and save huge amounts of time.
Another category which should be deserved and not granted too loosely is "abuses programming errors". There are probably other similar categories as well.
I wonder if it would be a good idea for someone to go through the movies and their author descriptions and revise whether the awarded categories are really fit. I think this should be done before a search capability is added to the site or else category search would be much less useful. (If I'm searching for "manipulates luck" videos I expect to find clear examples of this, not videos which save 0.1 seconds by "manipulating luck".)
A friend of mine lives in a building where there's a shared internet connection. The great thing about it is that it's completely unlimited to everyone, meaning that if nobody else in the same building is using it you get its full capacity.
I have seen him downloading more than 5 megabytes/s with bittorrent.
I once experimented with lossless video compression optimized for at-most-256-color tile-based scrolling videos. Here are some results (no sound, just picture information):
First 1109 frames of the SMB3 video: 263320 bytes.
First 5492 frames of the Snake Rattle&Roll video: 2248127 bytes.
First 8646 frames of the Vicedoom video: 3079616 bytes.
While the results were promising, they were only a bit smaller than DivX-encoded versions of the same frames with acceptable quality. I decided that it (at least my idea) was not worth the efforts: While you would get lossless video, it would require people to download and install an obscure codec, while at a comparable file size and acceptable quality it would be enough to have the far more popular DivX codec installed.
Moreover, with the introduction of H264, which has even a better quality/size ratio than DivX, the idea became even more obsolete.
Doom is an example of a game where many tracks are taken from somewhere: http://www.doomworld.com/linguica/doomcovers/
Again, the Doom versions suck and the original ones rule IMHO.
The E1M1 music and the Metallica song don't sound any alike. Perhaps that guy is hallucinating?
Sounds like regular speedrunning to me. Perhaps this is the wrong site for that.
I think that movie submission only accept record files, not video files.
Pros that come to mind when using matroska are for example: Less overhead than AVIs (ie. smaller file size), possibility to use wider range of Audio/Video codecs than those handled by AVI (Ogg Vorbis, AAC), possibility to add chapters to files (could be cool for longer RPG-runs) and embedding of subtitles (which could be used for comments etc.).
The videos published so far do not use any of those advantages. The videos don't need those advantages. What's the point?
By the way, how much is your "smaller file size"? Some hundreds of bytes? Some... oooooh... kilobytes perhaps?!? I'm reaaaallllly impressed.
