Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Link to video
As you can see, from first 'wedge' you can get (0xC5D0400-0xC584500)=0x4BF00 more if you run with speed 0x50500.
You can't get more with this speed.
But you may have 0x50F00 speed, and in that case I guess result will be 0x4BF00+0x50F00-0x50500=0x4C900 - but this is not confirmed.
Also, each one iteration gives 0x4600, this means, you may skip 17 of them!
Sorry, I did update maps yet again. I noticed that places with teal is semitransparent where they should not be, only when I opened it with PaintDotNet. :(
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Link to video
for zips down you need to push direction to the wall, and be as much as close to the wall.
for zips up you need to push direction to the wall, be as muc has close to the wall, and have wall at least 3 blocks, because difference between head-hit-ceil point and floor check point is 32 pixels = 2 blocks exactly, and it's not enough, you need more.
That one in redstar 3 doesn't work because there are exaclty two blocks below.
So, not enough wall in that place.
So, atm I know useful zips from Exonym: Bell castle 3 wall zip, Disco fever 2 tube zip, Dr Dis 1 barrel zip.
Also tried and verified:
1) Disco fever 3 wall zip after 2-nd checkpoint. (right in the middle of the map)
2) Dr Dis 2 wall zip close to head.
Update: Actually in Redstar 3 you can zip into bonus item room and use cannon, then you'll have to break wall from which you jump normaly, and make tricky jump from floor instead.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Final version of maps:
http://www.mediafire.com/file/1q2l3k49eehmtb6/Aero%20the%20Acro-Bat%202%20maps2.zip
Update 1: changed in 50_1, 51_1, 52_1 switch position into "open".
Update 2: fix of update 1.
I don't plan to change them anymore, except if someone find some bug in it.
Ah... Changes: alpha channel, palette fix, priority, height based on floor, left/right flips.
Next, I want to check how actually some of zips works.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
So, after making 157 screenshots and croping 32 sprites, and hardcoding a lot...
I have finished all levels up to performers dungeon (not including).
It's intermediate result.
http://www.mediafire.com/file/phbp9uuv36fvdts/Aero%20the%20Acro-Bat%202%20maps1.zip
here it is.
Two notes:
1) any object position might be slightly off, just because many of them are using ground level which I haven't implemented.
2) any object may have wrong palette, because I've used screenshots.
Update: all maps inside
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Script updated again: https://pastebin.com/mgLLaCnV
I thought assembly has bug, but nope... today I checked it again, and now script is more correct.
There is no longer blue regions, because they has no use.
Green regions: you can jump from below.
Teal: most likely you can't.
But it won't push you down if you don't have increasing height (speed y negative).
All maps without enemies: http://www.mediafire.com/file/djmwhy10kti20lt/Aero%20the%20Acro-Bat%202%20maps.zip
To mark enemies I need to hardcode pics for each one.
Maybe later.
Same thing about "support objects": platforms, checkpoints, switches, etc.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Game mechanics of genesis version is known to me.
But I've never thought about its glitches.
Regarding laps: there are checkpoints on the map.
All you need is to visit them one by one.
Visiting checkpoint is visiting the cell.
So, you only need to have at least once your position inside that cell.
There is counter of checkpoints, you need to find it using RAM search.
Maybe few of first races you can skip by "giving up" after picking all money on the map.
Also you may switch planet/division as soon as you have enough points.
And... changing vehicle is not required. You can finish the game using marauder.
But, of course faster you moving, faster you finish.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
r57shell wrote:
Normaly ceil check does check against two blocks vertically.
So, you have to somehow slip through 16x32 segment.
Hmmm. Looks like it checks again 16x32 only if you have vertical speed UPwards.
If you falling down: it depends on block. On those blocks where you slide down on its own -> looks it does nothing.
On plain solid blocks -> it push from it, or make you stand on corner <- idk logic atm.
Fixed my script, redownload it.
This place: https://i.imgur.com/XhszzNz.gifv
One additional note: if in cell no "ceill" then it won't look for cell below. This is why this zip works!
In theory, you could do same zip without dash if you could cross that corner without that dash. I call it dash by analogy with sonic.
BTW: do you use fractional parts of values? For example, max speed is 0x50000, but if ground increase it by 0x900, then you may have 0x50900 which is 5.03515625 pixels per frame :b, and it will gain 1 pixel after every 28.44(4) frames. (approximately each half of second).
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
After I made script for collisions data, and I became more impressed.
Just random pic of Disco level
I'm impressed by you guys. You found zip when script shows like it's impossible:
This moment in last encode is at 7:10 time.
:O
Script is showing items, spikes, and collisions.
Green ground -> you can jump from below.
Teal ground -> you can't jump from below.
Blue color -> height of "ceil"
Updated script still has same URL: https://pastebin.com/mgLLaCnV
Normaly ceil check does check against two blocks vertically.
So, you have to somehow slip through 16x32 segment.
I'm really curious how it looks with collision overlay.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
I have second my test, I haven't publish it yet.
So, here it is: https://youtu.be/7KGDc8V57RQ (fixed)
Just to make anyone who wants see it to be able to.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Question about difficulty selection for me is more like question about how much technically hard you want your TAS.
For me, it is not much fun to bomb bosses. It's easy.
From other hand, if you have bombs then you have to use them.
Just because your goal is to finish game ASAP.
In "normal" mode you don't need too much coins to have enough magic orbs.
And thus, you don't need to think too much about decision where you need to pick them up.
Easier routing is reducing technically difficulty very much.
I see only one boss that you'll have to fight with sword twice: scorpion.
Also, picking 1p vs 2p seems to me as another kind of difficulty selection.
Just because with 2p you skip many of boss fights.
And with 1p you'll have to boost your sword, and grab coins more carefully.
For me, it looks like there is 4 difficutly: 1p/2p and hard/normal for each.
And, in the end... Anyway you'll have to choose luck/sword hits.
This is tricky. Best option is to try some of them.
Or, you need to make statistic about bosses: I-frames, hp, sword hits required with each level of sword.
And then, plan how many sword levels you need, and which sword-max-hit you select in the first place.
By the way, I was wrong when I was saying that some bosses doesn't take double damage from yellow swing.
In fact, all of them affected by yellow swing.
So, for each boss you need to consider how many double-damage swings you can apply on them.
Update: http://tasvideos.org/Guidelines.html#SelectYourDifficultyWell
Oh, looks like normal should be selected, because:
Faster bossfights on repetitive bosses, especially if their lower health can lead them to be one-cycled, and they are not interesting to fight for longer periods
And all of bosses in this game are boring.
I find it upsetting. And, it's not rules, it's advices.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
ais523 wrote:
For example, if we discover that holding down the Select button on the first frame of the game has no influence on the game's memory, we can prune all the sequences which hold Select on frame 1, as they'll necessarily tie with the equivalent sequence that doesn't use Select.
ais523 wrote:
There are more complex examples of pruning, though. For example, if the memory states differ but the addresses that differ will necessarily be overwritten before they're read (say some memory address holds "buttons held on the previous frame" but it's only used in certain circumstances that don't apply here)
Most of games are using input buttons data as:
1) read current joypad state
2) read from memory previous holded keys
3) compare them to find all new pressed buttons (key Down event)
4) store key down into dedicated variable
5) store current joypad state as "previous holded keys"
So: it's readed & overwritten straightforward.
Also, key down depends on previous frame.
So, character state should also have previous input in it.
Because, it matters.
If everything else is same, but previous input isn't, then it's different state,
because in one of them you can jump on right next frame (for example),
and in other state you have to wait one frame to release jump button, and press it back.
This potentially may lead to 16 "duplicates" of same state in some sense.
Where 16 is all different variants to hold Left Right Jump Action (some).
ais523 wrote:
However, there are algorithms like A* that can be used to produce a good reordering given pretty much any assumption about how the game can act, and are known to find the optimal answer first if the assumption is correct.
I want to dwell on this topic more.
First, few properties of A*:
1) It always finds an optimal path if heuristic is suitable.
2) This optimal path is always first that is reaching goal.
3) It postpond many shorter paths to later moments, and looking among longer paths earlier.
4) One of crucial property of space for A*: point in space never "changes".
To understand idea of A* you may imagine all possible paths to all points in space where we looking for path from start to goal.
All routes from this set is starting in "start" position, but it may end in any point.
Now, imagine you did sort all routes by its cost.
In our case, cost is time.
Then, if you try all routes in this order, you'll end up with eventually stumbing accross lowest cost path to the goal, which is same as shortest in time.
Dijkstra's algorithm is essentially same algorithm but with very optimized method for iterating over paths in such order (by non-decreasing cost).
A* adds following trick.
Imagine that for any point in space p, you know that you need at least h(p) cost (time).
This h is called "heuristic".
Now, recall why we are sorting paths by non-decreasing cost?
We do it because we want to try all paths with lowest cost (time),
then all paths with a bit bigger cost (time), and so on, in exhaustive manner.
All longer paths is some shorter path with additional step.
If we don't reach goal after walking this path, then we need some additional steps to reach the goal.
Thus, for each shorter path we can estimate how many additional steps we need, to reach our goal.
If we make our estimation that it will never be more optimistic than real situation, then h(p) where p is end point of path - is always less than real cost to travel from p to goal.
And cost of path with best addition is always greater than cost(path) + h(p).
Now, because it's always less than real best path, you can reorder paths by cost(path)+ h(p) instead.
This will scan optimistic paths first. But if it doesn't find solution earlier, it will anyway try all possible paths.
Here some comparison: https://www.youtube.com/watch?v=cSxnOm5aceA
2:01 such case where A* try almost all possible paths.
Other case is if you make vertical wall from top to bottom with only one hole in bottom. A* will try many cases.
This was explanation why (1), (2) is true. Also, it shows why and how (3) happen.
(4) is seen on picture itself. It seen that none of dots is filled twice.
For example. when it checks some cell in opposite direction from goal, it doesn't start to recheck all cells towards to the goal.
But in many games you may find advantage in moving backwards for some frames.
So, you have to recheck cell.
This is because cell is not state. State also has enemies and so on.
This means, that A* implementation for game, with following "map" of obstacles:
Here: black - walls, green - "first" chunk of search, and red - "second" chunks of search.
Because space points are changing (enemies, rng, and so on), after each advance in green chunk, you'll redo part of red chunk.
Remember, red part will be fully only at very end, when it'll try best path itself.
(confirmation: https://imgur.com/a/ou3RTVi)
Conclusion: with A* there are three problems:
1) states (points in space) is not consistent, you have to recheck them when you make change in earlier frames.
2) heuristic is not known, and always under suspicion
3) branching factor is big. (variety of inputs)
It's not full list.
Even if you make very good heuristic, these "rechecking" and branching factors will doom your performance.
Regarding other topics:
Good luck with proving that some game has no ACE or zips.
Lag frames: substituting one goal by another is good idea. Also you may change goal from shortest input, to shortest non-zip / non-ACE input ;)
ais523 wrote:
Finally, there's the concept of parallel simulation: you have two gamestates that genuinely are different, but which are similar enough that you can emulate them at the same time rather than having to emulate them separately.
Idk how you would do that. Are you planning to make emu with such feature? :)
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
p4wn3r wrote:
As an example, Deep Blue, that beat Kasparov in chess, was a supercomputer.
Difference between chess and most of games: chess has well defined simple rules.
Warp wrote:
r57shell wrote:
If you try to brute force all orders of grabbing blue spheres - that's 64! approximately 10^89 - not feasable again.
But! Imagine you did that. You did try all orders of grabbing blue spheres...
That's not enough. You also may grab them from four different directions.
This adds 4^64 (approximately 10^38) variants for each.
So, total approximation is 10^127.
And if you try all the possible permutations in the example I gave, it would take at least 77 years to go through. Conclusion: It's impossible to build a comprehensive list of words in a feasible time?
I think you are missing my point.
Your example completely irrelevant.
In SMB / Sonic for example, no such thing as dictionary.
You can finish game in infinite amount of ways.
If you define that list as all inputs with minimum time to finish...
Warp wrote:
The trick is that you don't need to go through all the possible permutations of those 20 letters. When creating permutations, when you have taken two letters, you can check if any words start with them, and if they don't, you can skip all permutations that begin with those two letters. (The same goes of course for permutations of the first three letters, and so on.) This reduces the number of permutations to check to a microscopic fraction of the total.
Then you can't say for any prefix: can you finish game in minimum time or not?
If you would know this, you'll be able to make shortest input movie.
But this is because you know something, which is called "knowledge".
And this case perfectly fits my explanations.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
If you try to reduce game to totally valid model with all effects in game included, you'll end up having same impossible in real life times for search.
Easy example. There is well known blue-spheres bonus in sonic.
There are around 64 blue spheres, which you should grab.
Basically it's kind of "Travelling salesman problem".
If you try to brute force all inputs - not feasable (already discussed).
If you try to brute force all orders of grabbing blue spheres - that's 64! approximately 10^89 - not feasable again.
But! Imagine you did that. You did try all orders of grabbing blue spheres...
That's not enough. You also may grab them from four different directions.
This adds 4^64 (approximately 10^38) variants for each.
So, total approximation is 10^127.
Direction is important because you waste a lot of time for turning.
Okay, lets say we want to reduce options by assumption that having same position & orientation & grabbed spheres = same outcome for same input.
This will damage outcome just because there is speed up timings.
Longer you're in bonus stage, faster you go.
This may be wrong assumption. But it may be used as approximation.
More than that. If you make some wrong proofs that you claim is correct.
Then you may build wall to valid options, and people won't try them, because of authority basis.
He said that it's impossible, then it's impossible.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Warp wrote:
You seem to be arguing something like "you can't call it exhaustive if you don't go through every possible input", when that's not the point.
Yes, but my "support" of this point is different:
Warp wrote:
Depending on the game, there may be combinations of input that cannot lead to an optimal solution, and thus can be skipped.
How do you know?
How do you know that this cannot lead to optimal solution, or other way may lead.
"r57shell wrote:
Most of time, you don't know where may lead this possibility, or may not.
"r57shell wrote:
You may start proving based on code that something is not possible, and step by step simplify simulation of game to make it more predictalbe.
But then you'll have possibility that you've made mistake in your proofs.
So, my point: if you take some assumptions, then it's exhaustive with assumptions.
It's no longer purely exhaustive. And thus, you may miss something.
Possible outcome: "my exhaustive search tells me that it's impossible."
Later someone: "It is possible, I found the way to do it."
Side note: I was saying that you may find optimal solution without exhaustive search, because it may happen that common way of TASing just leads to optimal input for some games.
But presence of short input doesn't prove that all possibilities are exhausted.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Warp wrote:
Just saying that finding a perfect solution doesn't necessarily require trying every possible combination of inputs.
Yes, it's not recessary.
But exhaustive means that you exhausted all other options.
So, there is no shorter input that finish game.
But you can't know that, just because you can't try all of them.
r57shell wrote:
You have to somehow cut possibilities.
To able to cut the search, you need knowledge.
Most of time, you don't know where may lead this possibility, or may not.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
HappyLee wrote:
For example, you want to exhaustive search one extremely difficult movement, which is 100 frames in search length, and you can limit inputs to A B Left Right only (probably because you don't find Up Down Select Start useful in this particular movements). Variants_of_input = 2^4 = 16, and variants to check = 16^100.
Limit to "A B Left Right" - is not truly exhaustive, except if you prove that any other button can't cause any usable effect.
But more than that. 16^100 is not feasable.
Simulation of this count of variants will take more than your life. :D
First, approximate 16^100 = 2.582249878 * 10^120 (aproximately)
And round down > 10^120.
Imagine 10^10 simulations in second on single CPU (unreal for current CPUs), then it is 10^110 seconds.
In year there is 365*24*60*60 = 31536000 seconds.
"Shortend" year by rounding down to 10^7 seconds.
Now for that single unreal CPU you need 10^(110-7) = 10^103 years.
\o/
If you have 10^9 such CPU, it will reduce only by 10^9, so yet again: 10^94.
This is unreal.
Real counts is about 2^64 which is around 10^19.
So after first reduction by CPU it is 10^9.
And after reduction by year it is 10^2.
Then, after reduction by CPU count that is 100, it's feasable.
If computations can be made on GPU which has many CPUs,
then many GPU can break it in months.
HappyLee wrote:
I don't find it feasible using lua script (since it's too slow), but it's totally feasible using MrWint's approach (as we all know he has succeeded in doing it).
For lua it will take kinda same. Lua just adds some time.
For example, in lua it may take ten times longer.
Reason why 100 frames may be feasable, just because using more strong assumptions.
And main such assumption is: no matter how you got particular state of machine (NES), you'll have same results using same inputs afterwards.
This is reducing variants enormously.
But this is yet again making search less exhaustive, because you can't claim that state is same, unless you have all memory and registers state to be same.
And it's very rare to happen. Just because there are: HV counters, scroll positions, enemy positions, and many many other stuff.
So basic approach to assume that state is same if main character has same state.
But even this may lead to problems, because he usually has not only position, but also: velocity, jump/land state, mode (big/short in mario), invtime (I-frames), hit cooldown, and may have many other stuff.
My search that was looking among 90 frames in Donald, is taking 6 seconds.
I used only two buttons: left and right. And state was only speed and position.
Nothing else.
Even though buttons just two: 4^90 is not feasable again.
As I said 2^64 = 4^32 is more real goal.
But it is assumed that you can make simulations extra fast.
HappyLee wrote:
So my question was, could it be achieved without creating a model so it can fit any game?
Mindless - no.
You have to program math model of simplified game behavior.
Thus, you need to reverse engineer it.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Only one truly exhaustive search is: try all possible inputs.
Formula for this, is very easy: variants_to_check = variants_of_input^input_frames
where ^ -> rising in power.
For example, NES has: A B Select Start Up Down Left Right.
It is eight inputs.
All possible variants of this input:
variants_of_input = 2^8 = 256
Because you can press or not, each one independently.
Next accodring to formula above, movie with 67117 input frames will take:
variants_to_check = 256^67117 = 6.9462728 * 10^161633 (approximately)
So, you can say, that it's bigger than 1 with 161633 zeroes after.
You can't check it using all CPU power on the planet during your life.
You'll need then 1 and another few zeroes more centuries.
So, it's not feasable.
You have to somehow cut possibilities.
To able to cut the search, you need knowledge.
Most of time, you don't know where may lead this possibility, or may not.
For example, you may think that something is waste of time, but you just don't know
that waiting somewhere may allow to do some "trick" that will cut some time after.
So, you can't cut possibilities too early, but also you don't know how late you should wait to make sure that this will not help.
I see this "long term" advantages as main obstacle to make TAS, both for human and bot.
You can program some stuff for making decisions: how late/how early...
But this will make possibility that you've missed something.
You can go further. You may start proving based on code that something is not possible, and step by step simplify simulation of game to make it more predictalbe.
But then you'll have possibility that you've made mistake in your proofs.
So, exhaustive search may help only in very local situations, with simplified game simulation, and perform such jobs as subpixel positioning.
It's not really exhaustive. It's exhaustive only in terms of simplified game simulation.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Dacicus wrote:
I ran into the same problem as that guy about only being able to have VGA display in 16 colors.
First, backup your .chd disk.
Switch driver of display in Win98 into Standard VGA using "show all drivers" option dot.
Shutdown windows & mame.
Then, use "-isa1 svga_s3" in command line, to have svga_s3 instead.
Then, in display select "show all drivers" and look for "Number Nine 9FX Vision 330".
Reboot.
Try 256 mode \o/
It works in win95. Only one issue, when you trying to switch to Number Nine 9FX Vision 330 it shows this:
I get rid of this using Number Nine 9FX drivers exe installer.
It installed some buggy driver, that was ugly functional, but switching from that wasn't throwing error.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
MAME can run Diablo in Win95. But not on ET4000.
ET4000 on mame has some issues with driver of ET4000 from Win95.
I was able to run Diablo on svga_s3 (PCI Number Nine 9FX Vision 330 2.03.10)
It has some issues with mame too.
But at least game works fine.
Some glitchy graphics in windows itself persists.
Also, Diablo works fine under PCem with ET4000.
I'm impressed by you guys. You found zip when script shows like it's impossible:
This moment in last encode is at 7:10 time.
:O
Script is showing items, spikes, and collisions.
Green ground -> you can jump from below.
Teal ground -> you can't jump from below.
Blue color -> height of "ceil"
Updated script still has same URL: https://pastebin.com/mgLLaCnV
Normaly ceil check does check against two blocks vertically.
So, you have to somehow slip through 16x32 segment.
I'm really curious how it looks with collision overlay.
Here: black - walls, green - "first" chunk of search, and red - "second" chunks of search.
Because space points are changing (enemies, rng, and so on), after each advance in green chunk, you'll redo part of red chunk.
Remember, red part will be fully only at very end, when it'll try best path itself.
(confirmation: https://imgur.com/a/ou3RTVi)
Conclusion: with A* there are three problems:
1) states (points in space) is not consistent, you have to recheck them when you make change in earlier frames.
2) heuristic is not known, and always under suspicion
3) branching factor is big. (variety of inputs)
It's not full list.
Even if you make very good heuristic, these "rechecking" and branching factors will doom your performance.
Regarding other topics:
Good luck with proving that some game has no ACE or zips.
Lag frames: substituting one goal by another is good idea. Also you may change goal from shortest input, to shortest non-zip / non-ACE input ;)
I get rid of this using Number Nine 9FX drivers exe installer.
It installed some buggy driver, that was ugly functional, but switching from that wasn't throwing error.