Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
Both Xkeeper and upthorn are overestimating games.
It would be completely unheard of to move at 4000 units per frame. Generally, programmers don't need that degree of precision. unless you want to measure the radius of a virtual atom, your character's speed will rarely exceed 100, except in games where the speed is generally high, or there are a wide range of speeds. For example racing games or grand theft auto. In GTA, your character's speed would rarely exceed 100 whereas in a vehicle, it may do.
Generally you don't need to measure anything smaller than a millimetre, and a characters speed, divided by 60 or 30 (frames) will generally give <100. your character most likely won't move more than 10cm per frame.
Just bringing up GTA again because I know a little about the workings of San Andreas. Most well programmed games (SA is not nearly like cheetahmen, you've gotta be shitting me). Work on an exponential system, the characteristics of these games is that there is no overflow and that the further away you get from the origin, the less precision you have. Basically If you have a glitch that allows you to travel further away from the map than normally expected, your character will begin to spasm and expand/contract and generally asplode. This is extremely common in games. I have seen this in GTA-SA, SM64, COD4 and countless others. Back to grand theft auto, The precision is six significant figures. 1 unit is approximately 1 metre/yard in GTA-SA, and the map is 6000 units across. Therefore if you are at the edge of the map, and the units are metres, the precision is one centimetre! At a generous 20 cm per frame, your speed is only 20 of the smallest measurable unit, not 4000. Only in 11% of the map is the precision a millimetre, and only a minute 0.00027% of the entire game's standard map is the precision greater than a millimetre, only then will your speed reach over 2000, at that stage, you're right, this is useless, but in the other 99.99972% the map, my theory is surprisingly relevant. GTA-SA was widely acclaimed and has sold over 21 million copies! badly programmed my fucking ass.
Both Xkeeper and upthorn are overestimating games.
It would be completely unheard of to move at 4000 units per frame. Generally, programmers don't need that degree of precision. unless you want to measure the radius of a virtual atom, your character's speed will rarely exceed 100...
In Sonic the Hedgehog, one of the early games for the Sega Genesis, positions have an 8-bit subpixel component. Speeds are 16-bit values in subpixels per frame.
Upshot: In the TAS, Sonic routinely exceeds speeds of 4000, and even 8000.
In Ecco the Dolphin -- perhaps the earliest game that your theory could apply to, positions have 10-bit subpixel components, which means that even one pixel per frame is a speed of more than 1000, and Ecco's speed will frequently exceed 8000 or even 10000 in normal play.
For Super Mario 64, the console's data registers are naturally 64-bits wide, and it'd actually require additional programming effort to avoid using the extra precision...
How fleeting are all human passions compared with the massive continuity of ducks.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
sonic and ecco would both not benefit anyway, no matter how insignificant the gain would be, it doesn't apply to those games. for sm64, the speed is 55 for normal play, but can exceed 60k while bljing
Both Xkeeper and upthorn are overestimating games.
It would be completely unheard of to move at 4000 units per frame. Generally, programmers don't need that degree of precision. unless you want to measure the radius of a virtual atom, your character's speed will rarely exceed 100, except in games where the speed is generally high, or there are a wide range of speeds. For example racing games or grand theft auto. In GTA, your character's speed would rarely exceed 100 whereas in a vehicle, it may do.
... huh.
Samus's speed in Super Metroid is generally around 200,000 of the smallest units per frame. Although the lowest byte is NEVER directly used by speed, but even if you ignored that you'd measure it as around 1000 units per frame (with a maximum of around 4000).
Why would games NOT use that kind of precision when it's easily possible? :/
Work on an exponential system, the characteristics of these games is that there is no overflow and that the further away you get from the origin, the less precision you have. Basically If you have a glitch that allows you to travel further away from the map than normally expected, your character will begin to spasm and expand/contract and generally asplode. This is extremely common in games. I have seen this in GTA-SA, SM64, COD4 and countless others. Back to grand theft auto, The precision is six significant figures.
I'm speechless. I know that even commercial games occasionally get away with horrible programming flaws, but for such an easily avoided flaw to be common? o_O Why would you even use an exponential value for a character's position?
badly programmed my fucking ass.
Common / popular is not mutually exclusive with bad.
kwinse wrote:
Kejardon wrote:
Kriole wrote:
Samus is damaged by a Rinka in the opening.
That's a script action; no damage.
... it just dawned on me I know way too much about SM.
Joined: 1/16/2008
Posts: 358
Location: The Netherlands
Kejardon wrote:
(...)
I'm speechless. I know that even commercial games occasionally get away with horrible programming flaws, but for such an easily avoided flaw to be common? o_O Why would you even use an exponential value for a character's position?
that's a property of float calculations... and integer (exact) numbers usually won't suffice
anyway, in general, I was wondering if the tiny speed increase would weigh out to the increased traveling distance when using such a non-direct route. Or do you think that by abusing the erroneous rounding you'll end up in the exact same locations?
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
Kejardon wrote:
badly programmed my fucking ass.
Common / popular is not mutually exclusive with bad.
yes, but what happens if I want to TAS a popular but badly programmed game? your losing sight of the point.
Also you only need to save 1 unit in some circumstances to save a frame. If you fall just short of your target, you may want to use this to save that frame.
DaTeL237 wrote:
anyway, in general, I was wondering if the tiny speed increase would weigh out to the increased traveling distance when using such a non-direct route. Or do you think that by abusing the erroneous rounding you'll end up in the exact same locations?
there is a definite gain, no matter what your max speed is (in smallest units). For higher speeds, you have to deviate less to gain speed. At relatively low speeds, you can deviate larger amounts, but the distance gained is tiny compared to the speed gain (which also happens to be tiny).
Kejardon wrote:
I'm speechless. I know that even commercial games occasionally get away with horrible programming flaws, but for such an easily avoided flaw to be common? o_O Why would you even use an exponential value for a character's position?
The x,y,and z values are most likely stored in this format: p*2^q. This means that as p has a certain number of bits, as q increases, p loses a degree of precision. They use this format to prevent overflow, but at a cost. This is generally a small cost . Most values stored in the RAM actually benefit from this because at large scales, smaller numbers become insignificant anyway. It's like measuring the width of a football field with plank lengths. It's ridiculous and generally unnecessary to have more than a certain number of significant figures. However, if some values overflow, it becomes fatal to the game's operation. Programmers probably don't nitpick around to find the best type of integer length and format for every value. A "One size fits all" approach would be the most used. If the exponential format proves to be a loss to some values but is generally suited to the rest, it will most likely be used. Anyways, the spasm glitch does not generally occur during normal gameplay. It usually requires the use of a glitch to exceed the game's boundaries. Programmers generally think you will stay within the game boundaries and play like a normal human being. When they programmed sm64 in 1996, they probably weren't thinking emulators would be so prevalent and that a 5:28 completion would be possible.
Games that run on newer hardware and utilize more bits for movement/position are very likely will have rounding errors that are much smaller. The gains from these would, by my guess, be far less than even 1%. If average movement speed is ~4000units/frame, your best change is going to be at best 1 or 2 units (no smaller unit), and that's assuming the game doesn't have higher precision in its movement.
In short: I believe this concept to be completely useless except in either strange circumstances or very badly programmed games.
This is basically what I was saying in my two posts on the first page.
Yes, but as you can see, he doesn't get it.
Game X doesn't follow my theory? Well, game X doesn't count so fuck you.
What I don't get is how it suddenly doesn't apply. Consider that, you know, this is all about movement in two directions. But whatever.
Common / popular is not mutually exclusive with bad.
e.g. Pokémon or basically any other game for which glitchfests are possible, though I must admit that few games make it onto shelves that are as badly programmed as Cheetahmen II or Big Rigs: Over the Road Racing.
(Cheetahmen II didn't actually make it to store shelves.)
Seriously though, I still don't see why this thread has degenerated. It's a very interesting and plausible theory that could use some actual analysis. Couldn't someone boot up Mario64 and give it a try?
yes, but what happens if I want to TAS a popular but badly programmed game? your losing sight of the point.
You have a point but still I'm having a hard time believing this is actually common practice. :/
DaTeL237 wrote:
that's a property of float calculations... and integer (exact) numbers usually won't suffice
Having programmed a good bit myself and understanding various ways to store numbers, this is a really silly statement. Integers are far more appropriate for basically all position variables. I can't think of a case where I'd prefer a float instead.
However, if some values overflow, it becomes fatal to the game's operation. Programmers probably don't nitpick around to find the best type of integer length and format for every value. A "One size fits all" approach would be the most used. If the exponential format proves to be a loss to some values but is generally suited to the rest, it will most likely be used.
That makes sense, I guess. Kinda disappointing though. :/
DaTeL237 wrote:
anyway, in general, I was wondering if the tiny speed increase would weigh out to the increased traveling distance when using such a non-direct route. Or do you think that by abusing the erroneous rounding you'll end up in the exact same locations?
Here's a graphical representation of how this idea might speed up a run:
Overhead view of a (probably 3D) game
Say you start at A and need to get to B. You have to go around a wall first though. Your maximum speed is, say, 15.
Intuitively, the fastest path should be the path that juuust barely clears the wall, passing through point 1. Following that path, your X speed might be 13.9 while your Y speed is 5.8. The game rounds all numbers down though and so you actually only move at 13,5.
Say instead you went to point 2. This angle gives a X-speed of 13.2 and y-speed 7.1, rounding down to 13,7. Like this you could get to the same x-position at the same time but start from a better Y position to reach point B, and possibly reach it in less time.
This can be abused in further detail (you can remove the wall and make line 1 straight, the idea works the same), but the real advantage it can give boils down to how imprecise the position / speed is recorded. If a game is well-programmed you'd be really lucky to get even a single frame from an alternative path. If it's not well-programmed you might be able to save a lot of time.
kwinse wrote:
Kejardon wrote:
Kriole wrote:
Samus is damaged by a Rinka in the opening.
That's a script action; no damage.
... it just dawned on me I know way too much about SM.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
EDIT: this paragraph has been removed due to excessive foul language
The reason this doesn't apply to sonic games is because it has two distinguishable dimensions, the reason it doesn't apply to Ecco is because you don't use an analog joystick, and the reason that it doesn't apply to sm64 is because you can't turn while in midair, which happens to be when you're traveling the fastest. None of these reasons have any proof to say that my theory is bullshit. Next time actually provide an example that actually disproves my theory, and I'll give you a fucking medal.
No hard feelings right?
So, wait, you're basically saying that if a game doesn't have exactly three dimensions, than these rounding errors suddenly don't matter?
Because, think about it;
- Most of the time, Z (height) axis is not controllable in off/on state; and even then, it is not likely to be calculated with any relevance to X or Y outside of possibly initial speed (after all, X/Y is constant motion, Z is usually momentary thrust upwards)
And, uh, as many people have said, the kinds of rounding errors you are looking at would be small to the point of non-optimization.
Also, for whoever mentioned why they would be stored as floating-point: Probably because you can simulate fractional units by simply (operation)ing by 256, e.g. C0FF could be C0 + 0FF/100 units. It's called 'subpixels', and 3D games are likely to use a similar system to make animation less jerky.
As has been countlessly repeated before, it would be overall better to quit looking at this idea until a game is so optimized that it could even be potentially useful, and even then I'm not exactly sure what great games you have in mind as there are almost no N64 runs that allow full control of characters while Z-motion is nonzero.
In short: still an utter waste of time, nothing new here
So, wait, you're basically saying that if a game doesn't have exactly three dimensions, than these rounding errors suddenly don't matter?
Exactly three dimensions? what am I going to have, 2.7 dimensions? As a generalisation, the game will need 3 dimensions. There are probably very few 2D games that will benefit from this rounding error.
As in not 2, you pompous dick.
there are almost no N64 runs that allow full control of characters while Z-motion is nonzero.
you've assumed here that it is a requirement of all 3d games that the fastest method of travel is through the air, this however is not the case. If your fastest method of travel is along the ground then you should be able to turn, easily.
If that's the case, than any 2D game would work as well assuming you have control over both dimensions. Yet you threw that possibility out:
The reason this doesn't apply to sonic games is because it has two distinguishable dimensions
So basically if the fastest travel is along two dimensions, then it's fine, but if it's along two dimensions, then it isn't. Brilliant logic, Jeeves.
And, uh, as many people have said, the kinds of rounding errors you are looking at would be small to the point of non-optimization.
...
As has been countlessly repeated before...
And uh, is many equivalent to 2? because if you count how many "many" is, well...
"Countlessly repeated before". Nice choice of words. It's been repeated about 10 times. By you. I'm also terribly sorry that you can't count to ten.
upthorn wrote:
This is basically what I was saying in my two posts on the first page.
Oh, not just by me. Countless because I don't see actually going and getting an accurate count to be worth the effort, although aparrently you do. You must love wasting times on fruitless things. Oh wait.
Wasted fucking breath, all of it.
If you think it's so useless why don't you just not use it. Now isn't that a radical new thought. Why do you have to repeatedly have to say it's a waste of time? Why can't you let people make up their own minds whether they want to use it?
Because your time could be better spent fixing up other runs that need more major improvements, since you are so clearly such a great TASer as to already be on the micro-micro-optimization scale!
Also, for whoever mentioned why they would be stored as floating-point: Probably because you can simulate fractional units by simply (operation)ing by 256, e.g. C0FF could be C0 + 0FF/100 units. It's called 'subpixels', and 3D games are likely to use a similar system to make animation less jerky.
Games actually use floating point numbers for positions. yeah, it's possible not to, but they do, and it's extremely common. And wow, subpixels? never heard of those? what the hell are subpixels? Of course I've fucking heard of subpixels, that's why I mentioned them in an earlier post and in 3d games we measure things in "units" being the smallest measurable unit. The game cannot possibly have greater precision than "units" because they're the smallest!. As for jerky animation, you could have fairly large units and many people wouldn't notice.
Aparrently I was talking to the wall (mis-remembered a post by somebody else), it wasn't directed at you. Apologies.
As for non-optimisation, I repeat: you only have to save 1 unit in the x or y direction to save a frame, because in some circumstances you fall just short of your target. That would be the major gain of this, being you get there half a frame earlier, but save a whole frame.
And as I've said repeatedly (there, no ambiguous number, don't go shitting your pants over it), there are far more worthwhile optimizations that can be found and taken advantage of instead of spending ten years analyzing a game to determine if you move left while tapping your shoes and balancing an orange on your head will get you there one frame earlier.
But hey, I don't care, I have nothing better to do tonight than argue with you, so fight's on, I guess.
Joined: 1/16/2008
Posts: 358
Location: The Netherlands
Kejardon wrote:
DaTeL237 wrote:
that's a property of float calculations... and integer (exact) numbers usually won't suffice
Having programmed a good bit myself and understanding various ways to store numbers, this is a really silly statement. Integers are far more appropriate for basically all position variables. I can't think of a case where I'd prefer a float instead.
Here's a graphical representation of how this idea might speed up a run:
(img)
Thanks for the graphical example! I'm convinced there's a game where it'll be advantageous now :D
No offense to your programming knowledge (I'm sure it exceeds mine) but look at practically any 3D code sample and you'll see them all using floats (or doubles) for position...
the reason why? Here's a tiny and quick read on it (from a source that defends integer coordinates)
Why do 3D engines generally use floats to represent object position?
Floating point representation can make sense in a rendering engine, where absolutely exact results are not required.
A certain amount of approximation when rendering is normal and has no adverse effects. And the floating range offered by this representation is very convenient given the amount of vector maths involved.
The recommended approach is to maintain agent positions in PathEngine coordinates and then convert to floating point representation whenever this is required to render the agent.
I agree entirely with your source's reasoning. :)
Also, the argument is getting stupid here. The real question is at this point: 'Is there a game this is applicable and significant for?' I can't think of a game that it might be worthwhile for, except maybe Wolfenstein or some other early FPSes, but FPSes are not something I know a lot about. Anyone else?
kwinse wrote:
Kejardon wrote:
Kriole wrote:
Samus is damaged by a Rinka in the opening.
That's a script action; no damage.
... it just dawned on me I know way too much about SM.
that's a property of float calculations... and integer (exact) numbers usually won't suffice
Having programmed a good bit myself and understanding various ways to store numbers, this is a really silly statement. Integers are far more appropriate for basically all position variables. I can't think of a case where I'd prefer a float instead.
That depends on the accuracy and range of the positions you want to use.
Sure, eg. 32-bit integers have a rather large range of possible values. However, if you need to represent the location of something relatively precisely, and your level is very large, it just might be that the 32-bit integer is not enough.
Even if it is enough to pinpoint any location, the integers may fall short when you want to move a location in a rectilinear way towards a given direction, especially if the direction can be defined relatively accurately.
Basically what you are doing here is fixed-point arithmetic. The problem with fixed-point arithmetic is that increasing accuracy decreases range, and vice-versa. If your fixed-point values have a too low accuracy (too few bits reserved for the "decimal part"), you will get large rounding errors, which may become obvious eg. when moving objects around. On the other hand, if you have large accuracy (many bits reserved for the "decimal part"), the minimum-maximum range will suffer.
Also there's only so much you can do with fixed-point arithmetic. Representing very small or very large values is impossible after a certain point. Even if your locations never get even close to these limits, intermediate values in calculations may get very large or very small, and overflow/underflow, screwing up the results.
Floating point arithmetic alleviates this problem by having a dynamic range (with a fixed accuracy). If you use 64-bit floating point values, you will even get a larger range of integer values than you would get with 32-bit integers. And the great thing is that floating point arithmetic is not especially slow because it's hardware-accelerated.
Sounds like you're trying to travel by tesseract, regardless you can do it both ways and either one way will be faster than the other or it would be the same, either way you would go with the faster one. If the question is you are right or you are wrong, it's impossible to prove an absolute negative and until someone proves you right any argument begs the question. If taking a longer path or making a turn will allow you to maintain your pace then do that, if the choice has to be made to take a longer path or make a turn then I suggest you make it because not chosing will definitely be a longer run.
I understand what he's trying to say.
even simpler example.
You wish to move on a 2 dimensional plane, and you move at a certain speed, but can move any direction.
In theory, if you plot every possible direction of straight line movement after 100 seconds, you should make a perfect circle with the endpoints.
However, in reality, due to rounding error, you won't end up with one. You will end up with an imperfect circle.
So in some cases, deviating slightly from a straight will put the rounding error on your side instead of against you, and the rounding error may be enough to overcome the additional length.
To test, we take the corner, and we plot two circles this way, each ending at the corner. we may find that on the free space side of the corner, there's an overlap in the plots, when you actually have them intersecting at the corner. If so, diverting from the most direct path will actually be faster.
Overhead view of a (probably 3D) game
Say you start at A and need to get to B. You have to go around a wall first though. Your maximum speed is, say, 15.
Intuitively, the fastest path should be the path that juuust barely clears the wall, passing through point 1. Following that path, your X speed might be 13.9 while your Y speed is 5.8. The game rounds all numbers down though and so you actually only move at 13,5.
Say instead you went to point 2. This angle gives a X-speed of 13.2 and y-speed 7.1, rounding down to 13,7. Like this you could get to the same x-position at the same time but start from a better Y position to reach point B, and possibly reach it in less time.
This can be abused in further detail (you can remove the wall and make line 1 straight, the idea works the same), but the real advantage it can give boils down to how imprecise the position / speed is recorded. If a game is well-programmed you'd be really lucky to get even a single frame from an alternative path. If it's not well-programmed you might be able to save a lot of time.
