Very nice. That's definately a much better way to conduct the search. Instead of keeping a heap of all the nodes which need to be visited, you're keeping track of only the path used to get there. Although it needs to rebuild the entire tree every time the depth is increased, it only requires a constant amount of memory to do so, instead of exponential. It also doesn't keep track of which states it's already visited either (not paths, but states), so it ends up looking at a lot more nodes than necessary, but then again, that would require a lot of memory to do. I'm actually quite glad you posted this... I'll be able to optimize some of my other solvers because of it as well :)
In alphabetical order by system:
NES Batman by Jecy
One of my favorite games when I was a youngster. Seeing it played so well brings a tear to the eye.
NES Gauntlet by FODA
Another game I spent years playing. I didn't even realize it had an end!
NES Metroid any% by Zoizite
This is officially the first game I ever did a speedrun of, at about the age of 10. I was pretty boastful of my 20 minutes too.
NES Rygar warpful by Walker Boh
I also owned this game, but I gave up on it because it was too hard.
NES Snake Rattle'n Roll by Nitsuja
The mobility in this game is unreal. This game is a lot harder than he makes it look, especially the under water levels.
SNES Donkey Kong Country 101% by Arnethegreat
Diddy can fly? Omgwtfh4x0rz!111!!eleven!
SNES Mega Man X & X2 by DeHackEd
I've never played either of these, but this video is absolutely amazing. Perhaps it will inspire similar runs?
SNES Super Metriod 100% by JXQ
What can I say? I'm a huge Metriod fan, and this still remains the best of the series imho. JXQ's run does it the justice it deserves.
Genesis Sonic 3 & Knuckles by SprintGod
The very embodiment of fast paced, SprintGod utilizes both unintended and unexpected routes to make this game even faster. Don't blink!
N64 Super Mario 64 by Spezzafer
I'll quote myself after the first time I watched it: "That's the most amazing thing I've ever seen in my life."
nobody is going to go behind your back and complete the run before you.
...but even if someone were to, the better (primarily faster, and more entertaining) of the two runs would be the one that was published. That's why, as adelikat stated, it is important to take your time, and to produce the best run you are capable of producing.
Certainly :)
SlidePuzzle.javaPuzzleState.java
So, after a little experimentation, I found that my A* search had the same problem as xebra's... for a completely random puzzle (as small as 4x4), java would run out of heap space long before it found the (optimal) solution. The only reason why I was able to find the solution for the 6x6, is because it wasn't mixed up too badly. Although more heap space can be allocated by adding -Xmx256M (for 256Mb) option to java.exe, it really doesn't solve the problem, so I added a little pruning.
I'm using a completely different heuristic for pruning, however. That being the minimum average distance for the remaining incorrect pieces. The logic behind it is pretty intuitive; if a puzzle state has two incorrect pieces, each an average of three tiles away, it is far less likely to lead to an optimal solution than a state which has six incorrect pieces each one tile away from where they belong. I use this as an example, becuse using the other heuristic, they would both be weighted equally (assuming a path of equal length to get there).
Overall, it seems to work pretty well. The 6x6 puzzle Zurreco provided can be solved with a pruning beam as small as 100. Although a random puzzle, like the 4x4 in the code, took a beam of 5000 to find the optimal solution of 62. To turn on pruning, uncomment line 48 in SlidePuzzle.java, and the beam size can be adjusted by changing the BEAM value on line 25. All in all, this was a fun problem to work on, considering that I really like these puzzles. I've actually made my own applet, which can be found on my site. Cheers :)
Looks great. I do have one question though. In your fight with Great Tiger, you save two star punches from the first time you knock him down, and then uppercut him twice in a row as soon as he gets up. My question is, couldn't you have done the same thing in the first Piston Honda fight? I could be wrong, of course, but it seemed to work on him once... why not twice?
After running an A* search, I found a path of 50, which by definition of the algorithm is optimal. I know you said you don't need it anymore, but I figured I'd post it anyway :)
down down right up left left down left up right up left down right down left left up up up right down down left up right right down right down left up left down right up up up right down right up left up up left left down left up
I had some time after work, so I decided to implement this quick. I was able to find two solutions, both of length 54. The directive 'up' means to slide a tile upwards into the blank spot, and other directives are defined similarly.
Solution 1:
down down right up left left left down right up right down left up left down left up up up right down down left up right right up right down right up left up up left left down left down down right right down left down right up up left up left up up
Solution 2:
down left left down right up right down right up left down left up left down left up up up right down down left up right right up right down right up left up up left left down left down down right right down left down right up up left up left up up
In case you'd like the code for other puzzles, it can be found in the following locations:
SlidePuzzle.javaPuzzleState.java
It should work for any size puzzle (even non-squares), you just need to define the initial array value in the SlidePuzzle class. If you want to adjust the beam size, you can do so by changing the parameter sent to the weed method. Both of these solutions were found with a beam size of 1000, but I also tried 10000 which didn't find any better ones, so they are probably optimal. Good luck :)
It seems like your best bet may be to use a beam search of some sort. I've done this for other puzzles with varying success. The idea is to use an iterative search, but after the queue has reached a certain size, 1000 for example, weed out bad paths so that there is once again only 1000. It doesn't guarentee an optimal solution, but it's nice that in that it has linear complexity, instead of exponential. A simple heuristic could probably be something along these lines:
For each tile in the puzzle, calculate how far it is from its proper location (that is, how many shifts it would take to move it there). The sum of these could be used to compare various paths. A value of zero would be a solved state, and larger values would be further from a solution, and thus would be weeded out. If there are multiple optimal paths, you could then decide which would be the fastest to execute (if there is in fact a difference in input time).
There may be better heuristic functions, but this one seems pretty intuitive and would be easy to implement. I could probably crunch a small app out in about an hour or so if you'd like.
I took the time to watch the previous movie before watching this submission. Getting the 'weapon' upgrade right at the beginning sped things up immensely. This is particularly apparent in the boss battles (number 4 especially!), but also throughout the game, when attacking was unavoidable. The point total screens were also a lot faster; good find. As mentioned before, the input stops a bit early, so my yes vote should be applied to the alternative movie file you posted, and not the actual submission. Great work :)
You get a different ending in DuckTales if you can perform the (impossible) task finishing the game with no money.
Speculation: In earlier implementations of the prototype, it most likely was possible to lose all of your cash, necessitating the alternate ending. Later, the game was changed so that this was no longer possible, and the ending was forgotten about. When the text translators received the code from the outsourcers, translating engrish to english, they most likely had no idea which code was actually used, and just translated everything.
As for the as many coins as possible run, I tend to agree with Blublu. This is a side scroller, with no backtracking. By looking at the maps, it should be immediately apparent which route needs to be taken in each level to obtain the maximum number of coins. Unless, of course, glitches could be used to obtain coins that normally wouldn't be possible... but it seems like the occurance of this would be rare, if at all existant.
A zero coin run might be a little more interesting, because there are a few coins along the way which aren't normally avoidable. There are most likely several different solutions to each situation, but for the most part, it would be a clone of the normal run, only slower in those places.
/me blinks
You don't need my input to know this, but that was absolutely amazing. I was afraid to blink... I didn't want to miss anything :) What more can I say? Yes!
I've posted a new WIP, in the same place as usual. Progress is now completed through the Safari Zone, and somehow (I really don't know how), I still seem to be picking up time. I'm now 17,778 frames ahead, which means I picked up almost a minute in this section, although it's nearly identical to my Mew run. Besides the 750 frames I saved from not catching Snorlax, the only other things I can think of are that Mew has a long battle cry (which he does every time he comes out), and Mega Punch has a slow animation (the same one Hydro Pump has). But a full minute? At any rate, I'm not complaining. It looks like a 1:41 might be possible afterall :)
I had to change the route a little bit. Gyarados didn't have a high enough special to do Celedon Gym before the Poké Tower (which means I've lost 4 Ice Beams, because they weren't auto-healed in the tower). But it turned out to be for the best; I found that by biking from the gym to Snorlax, I saved around 45 frames over flying and then cycling. If I had done the gym first, flying and then cycling would have been my only option. I'm not too concerned about losing the Ice Beams though. Surf has 5 more PP than Psychic did, and in general, has the same use as Ice beam (barring a few plant pokémon), so it shouldn't be a problem.
The next update probably won't be for while. I haven't planned the attacks out yet, and I'll need to do a lot of experimentation before I determine the best order of Fuschia/Saffron/Cinnibar.
I also voted no. Aiming for pure speed through this game, it seems that a multi-player run could be a lot faster than a single player, especially considering that there are multiple paths through certain areas. However, I don't think four players is necessary. Considering how the game lags, two players would probably be optimal; you'd be able to traverse multiple paths, and have the minimum amount of increased lag. And, as adelikat mentioned, a lot of times you treat the four players as two groups of two... in these parts you are essentially doing a two player run, just with a lot more lag.
When the game isn't lagging, it does seem to be fast paced, which would make it interesting to watch. Although the idea of a four person run is very appealing, unfortunately the game lags to much to make it feasible. But even if the game didn't lag so much, I'm not at all convinced that a four player run would be any faster than a two player run; it doesn't seem like there's ever more than two paths to take.
Unfortunately, Gyarados doesn't learn Bite at level 20, because he already knows it. The same was true for Mew with Mega Punch.
I guess you could hurry and replace it with TMs just before you can learn Bite again!
I don't think that would be useful. Of course it could be tried out if it didn't mean so much trouble.
It's a good idea in theory... but it won't work because he's already level 21 when I get Thunderbolt. The other option is of course Bubblebeam, but this would mean charging Nugget Bridge without Bubblebeam, and then not having Bite again until S.S. Anne. Although it would generate more attacks, it would most certainly be a slower option (and I have enough attacks as it is anyway, so the fastest route is just to continue on as I am d=(^^,)z).
EDIT:
Looks like I've made a mistake. I had banked upon being able to use Bite on the first Cubone in Rock Tunnel... but I need a Bubblebeam. I could just use Hydro Pump here, but I'd be losing the full 55 frames. The best place to use it that I can I identify is Gary's Pidgeotto on S.S. Anne, at the cost of only about 10 frames. Not too much backtracking, so that looks like what I'll be doing.
EDIT2:
I've updated the WIP file. It's 19 frames slower than the previous, but I'll be saving 55 frames later because of it. Hopefully I won't have to redo anything else.
Wait, doesn't every Pokemon game have an option to turn off battle animations? It flips itself back on for 'final' battles in some of the games though, frame counting will be important there.
I have animations turned off, but there seems to be several different 'no animation' animations, some slower than others. Hydro Pump seems to have a slow one.
Yesterday was a national holiday, so I had a few hours at my disposal. The updated WIP, with progress through Vermillion. I waited until after I teleported back to Cerulean so that I could get an accurate comparison. Amazingly, I'm currently 14,526 frames (just over four minutes) ahead of the published run. I really hadn't expected everything to be a OHKO. Before you get too excited, keep in mind that this is a trade-off; I'll be losing a lot of time near the end. But it looks as though the gains will outweigh the losses by a good margin.
Couple quick things. I have a lot of attacks on hand, and typically no matter which one I use, I can get a OHKO for everything. So I've done my best to minimize the number of critical hits needed, and also to avoid switching between attacks as much as possible. This basically means using the same attack for every pokémon a trainer has (notable exceptions are Gary and Lt. Surge). I also avoid using Hydro Pump, although it could have saved critical hits. The reason being is that the animation for it is slow, about 55 frames slower than the other attacks (you'll notice the opponent flashes for a pretty long period of time). It's almost always faster to crit a Bite or Bubblebeam than to use Hydro Pump.
The most difficult part about this section is attack planning. I have 75 attacks for 72 opponents. It's pretty tight, but I think I've got it figured out. The key is to make sure that an attack is completely depleted before replacing it. If I made a mistake in planning (I sure hope I didn't), I may have to do part (or all) of this section over again, but otherwise this will be included in the final run.
FractalFusion wrote:
I was going to mention that Gyarados relearns Bite at level 20, so you can replace Bite if it's low on PP.
By the way, are there any Ethers that are worth getting?
Unfortunately, Gyarados doesn't learn Bite at level 20, because he already knows it. The same was true for Mew with Mega Punch.
There is an ether directly on the main path (just before Bill's). I didn't pick it up though, because I don't think I need it.
The current WIP, as promised. If you've seen my other runs, this is nothing too impressive, although it may be interesting to watch exactly how the Gyarados is obtained (very similar to Mew, but different setting). At the last point when I could get a valid comparison (the last trainer before Mt. Moon), I was 922 frames ahead of the published run. I won't really be able to compare again until after I finish with Bill's, but by then, I hope to have increased this mark by several thousand.
LagDotCom wrote:
What TMs are you feeding to Gyarados when he is caught? As mentioned Dragon Rage is a bit low on PPs.
Immediately when he is caught? None. He starts with a full set of moves. If you mean TMs throughout the course of the game, probably something like this:
primorial#soup wrote:
Start:
Bite, Dragon Rage, Leer, Hydro Pump
-Bubblebeam replaces Leer. No brainer.
-Thunderbolt replaces Dragon Rage. Against pokémon level < 20, Dragon Rage will typically be a OHKO. But at this point in the game, it's outlived its usefulness.
-Ice Beam replaces Bubblebeam. Also not much to think about. Just about everything Bubblebeam would have been effective against, Ice Beam is as well.
-Surf replaces Hydro Pump. This would be happening directly before Blaine. It's a shame to see it go, but I see it as a necessity.
-Strength replaces Bite. This is certainly questionable. A strong normal attack is needed to fight Sabrina, and I don't think Bite would cut it. There are certainly a lot of other options, but this one is particularly appealing, because it saves having to teach Strength to Charmander.
I'm still debating the order of Fuschia/Saffron/Cinnibar. I'd like to still have Hydro Pump while doing Koga, but I don't want to have to teach Strength without teaching Surf. My thought is that Bite may not be powerful enough to take out all the Drowzees in one hit if I choose to do Fuschia first. I'm thinking that perhaps I could do the Saffron office building first, then Koga, learn Surf and Strength, then Blaine, then Sabrina. I'll most likely have to do a lot of experimenting to see what is best.
Just wondering, but was Dragon Rage able to OHKO most of the Pokemon around Nugget Bridge and beyond? How about rival battle?
At levels 12-16, most Pokemon would be close to 40HP.
Or maybe I'm missing something.
This is exactly where the saved time from early battles (as mentioned above) is coming from. That, and having Hydro Pump. I went through my previous run with a memory viewer, and it turns out that almost all of the pokémon up through Vermillion have 40 HP or less. Dragon Rage only has 10 PP however, so I'll need to use Bite as often as possible. I'm also going to change things up a bit by doing the gym immediately as I enter Cerulean, which will give me Bubblebeam before I even enter Nugget Bridge. I'm fairly confident that I can get away with only healing once in Cerulean (and not again until Indigo Plateau), directly after the gym battle, considering that I have four useful attacks at this point, instead of only two. This will counter the time use to heal before Mt. Moon (necessary for Gyarados glitching).
Or use the minus world glitch in 1-2 and warp to world 5.
1st goes 1-1 to 4-2 >warp> 8-1 to 8-4
2nd goes 1-1 to 1-2 >warp> 5-1 to 8-4
I was unaware of this glitch. Very cool. I completely second this suggestion if it turns out that 1-3 to 4-2 happens to take the same amount of time as 5-1 to 7-4 (you could probably watch the full run to get a good idea).
I've made a few discoveries that eliminate the need to catch an Abra (at least in a run that doesn't use Mew). First discovery: Escape Rope can be used from Bill's house. Even if you have an Abra, it's still faster, because you don't have to walk outside, and the item menu is faster than the pokémon menu (I really should have done this in my Mew run). Second discovery: Escape rope (or Dig) can be used to return from Vermillion. Although it can't be used from inside the gym, it can be used from inside the pokémon fan club building (where you get the Bike Voucher). It's hard to say exactly how much time not catching an Abra would save (Cut needs to be used a second time, but there is less backtracking), but I would estimate in the neighborhood of 1500 to 2000 frames; not a small chunk by any standards.
This brings me back to thinking about a Gyarados run. Although my Mew run isn't perfect (30-45 seconds could potentially be saved by rolling better stats, and by using Metronome in a few places), I think a Gyarados run could be even faster. I did a test run (without TAS) and found that the Elite Four wasn't as big of a problem as I had thought. The STAB on Surf makes up for the his lower level pretty well. The amount of time saved from earlier battles easily offsets the few extra attacks needed here. Also, Snorlax doesn't need to be caught either making this a three pokémon run (which is the theoretical minimum, if you don't allow backtracking through Diglett Cave to glitch a Mew slave). I'll be posting a WIP soon (probably after Cerulean gym).
watched, it looks good. Improvement over the current run so yes vote.
Though I don't know exactly what you did to gain the 13 seconds, could you explain?
Comparing this run with the previous, it seems there are a few small improvements (where the first hole is made, for example), but the big improvement seems to be the 'walk on air' glitch, which saves time in not having to use the blob to make a bridge (used three times throughout the run). Great discovery, a definite yes vote.
Besides the two routes Inzult suggested, I think this one would be interesting as well:
only 4: 1144445555666677778888
only 7: 1111222233334477778888
It's a bit longer than the other two, but all of the levels in the game would be played at least once, which might make it more interesting to watch. The only downfall is that both levels 7 and 8 would be done twice and at the same time, instead of just level 8. It seems like there might be a lot of places that could be done in two (or more) entirely different ways without losing any time, however. Being able to see these both in tandem could be very entertaining to watch.
Compiles fine without modification in vs6.0 under win2k. Is there any reason why it prints out 11 zeros before the digits of pi? This is an awesome program for its size, nice work :)
I find this movie to be a good compliment to the existing movie by Genisto. One aims for fastest completion, the other for style. But truthfully, I think the fact that it warps directly to level 23 is one of its saving points; were it to warp through all 30 levels one by one, I think it would be pretty boring. The first time I viewed it, I had the same concerns as MattyXB; namely that sometimes many bricks were destroyed before finding the warp. But considering what you have said (that only certain bricks can contain power-ups), it seems to be very well done. Voting yes.
