If a game doesn't have randomness at all, and all it cares about is videoframe precision inputs (or inputpoll precision inputs), will it be possible to properly TAS it with no fake time?
Well, making a TAS involves single-stepping, and fast-forwarding, and loading savestates. No game that cares about time at all will do reasonable things under those circumstances, so fake time is a necessity for making a TAS of almost any game.
I suppose there probably are games where you could somewhat reliably play back a TAS using real time (on a sufficiently powerful computer).
cwitty, do you happen to know how exactly libTAS is keeping this consistent no-vsync framerate?
At least in the basic cases, sure. libTAS keeps a current "libTAS time", increments that time whenever the game displays a frame, and reports that time whenever the game asks what time it is.
So if the game displays frames with glXSwapBuffers(), and asks for the time with gettimeofday(), it might make these calls with the given results. (I'm assuming that libTAS time is set to start at 0, and the frame rate is 50Hz, to make the numbers prettier.)
gettimeofday()
-> 0.00
glXSwapBuffers()
gettimeofday()
-> 0.02
glXSwapBuffers()
gettimeofday()
-> 0.04
Which is the same sequence of function calls and results the game would see with vsync on (at 50Hz), or if the game has vsync off and an external tool is limiting the framerate to 50Hz, or if the game has vsync off and just happens to be running on a computer that's exactly fast enough that the game loop runs at 50Hz.
There are a lot of games that are usually played single-player, but also have an optional local co-op mode. Co-op play can be significantly slower (for example, if all characters have to reach the end of the level, and they can't take the same fast route because they would collide with each other), or significantly faster (if multiple characters means you produce much more damage-per-second, or if the characters can take turns tanking hits so you can take a lot more cumulative damage through the level without dying, or if the characters can split up and solve puzzles in different parts of the level simultaneously), or anywhere in between.
I just read through the movie rules and guidelines, and didn't see anything about local co-op, especially in regards to vault eligibility.
My first thought is that speed is king, so only the faster of single-player and multi-player is vault-eligible. (And if the game has drop-in/drop-out co-op, you should make full use of that whenever it's faster.)
But I could also see a case that this choice is similar to a difficulty level choice, and the variant that's more "interesting and entertaining" should be chosen. I think that would usually be multi-player (even when it's a little slower), but maybe single-player would be more interesting and entertaining if the game isn't properly balanced for co-op and having the second player trivializes part of the game. (And if you're going for multi-player on "interesting and entertaining" grounds, maybe drop-out shouldn't be allowed?)
And I can also see a case that if co-op and single-player gameplay are sufficiently different, maybe both could be vault-eligible.
And finally, given that a good co-op run is probably much harder to produce than a good single-player run, maybe a single-player run could be accepted to vault even for games where multi-player would be preferred, but the single-player run could later be obsoleted by a faster multi-player run.
So, what do you think? Are the existing rules adequate (under which I'm guessing "speed is king" would win, and only co-op is vault-eligible for games where co-op is faster), or should a new rule about co-op games be added?
I've written the above in general terms, because I believe you prefer to have general rules rather than individual rulings; but I am interested in a particular game.
I've been considering a TAS of LEGO Batman 2 (for Wii). I've played through the game, and watched both the existing single-player speedruns on speedrun.com; but I've never played it co-op (with anybody competent), I can't find a co-op speedrun, and I haven't started actually TASing. So as a total guess, I think that co-op of this game would be 10% to 30% faster, and that drop-in/drop-out would be slightly faster than a pure 2-player run. (Characters in LEGO games that are under AI control tend to move faster, and occasionally teleport to the main character, compared to characters that are player-controlled.) Also, a co-op run would often have a lot more stuff happening on the screen; but I can't be certain whether that would make the co-op version more entertaining, or if it would just end up being too much stuff on screen and be confusing.
So, if I ever do end up starting this TAS, and I want it to be vault-eligible (because I'm worried not many people will find a >2 hour LEGO game entertaining), should it be single-player, or pure co-op, or whatever is fastest (which I expect to be mostly co-op with occasional drop-out/drop-in segments)?
However, one has to wonder if there nevertheless ought to be a sensible upper limit. If games are being run in an emulated environment, then there's no theoretical upper limit to the refresh rate (even if the host machine can't run it in real-time at that refresh rate, that doesn't matter; to the game it looks like it is, if it's emulated as if it were, even if in actuality it's being emulated at a much lower speed). So what stops a game from being run at a million Hz? Or a billion Hz?
I agree with the idea of an upper limit in theory, but I don't see how to define one in practice. For a game that explicitly supports disabling vsync, I think it should be allowed to run at least as fast as it would on a high-end computer from when the game was released; but defining that as the upper limit is impossible to enforce. (Would we require the TASer to go buy such a computer to run tests? And then the judge also has to buy a computer, to double-check what the TASer says?)
The problem is that libTAS is not an emulator. Our emulators have a model for how many clock cycles it takes to execute a chunk of code, and how many clock cycles are available per frame, and how long various peripherals (like the GPU) take to perform various operations. Even if these models are not completely accurate (for example, I suspect some of our emulators model GPUs as infinitely fast), they are reproducible and thus a suitable basis for rules. In fact, with the sole exception (I think) of DOS emulation with JPC-RR, the emulators don't let you set things like clock rate, so there isn't even a need for a formal rule beyond the list of which emulators are acceptable.
libTAS doesn't have that. It could measure how fast the game loop is on the TASer's computer, but not in a way that's reproducible even from one run of the game to the next on the same computer, and certainly not in a way that's reproducible across different computer models and could be compared to a hypothetical reference computer from a few years ago.
To boil it down, I feel like there are a few desirable principles the rule should follow:
1) Games should not be allowed to run significantly faster than they would on reasonable contemporary hardware.
2) Games should be allowed to run as fast as they would on reasonable contemporary hardware.
3) Rules should be clear and enforceable, with a predictable effect.
And I just don't see any way to satisfy all three principles. I personally prefer principle 2 to principle 1, but I'm glad I'm not responsible for making the final decision :)
We're hacking OS functions to affect the way the game works. Even though some time functions report proper time, allowing the game to be aware of real world time and work at consistent speed gameplay-wise regardless, other time functions are replaced and report false time altogether.
I'm not sure what you're talking about here; libTAS reports "false time" from all time functions (or at least that's the goal), and that's an important part of making the game run reproducibly across different computers.
Also, the whole vsync issue feels like a red herring; from the point of view of a game running under libTAS, successive drawn frames are always exactly 1/fps seconds apart, so as far as the game can tell, vsync is always on (whether it asked for vsync or not). Also, games that support windowed mode need to be able to work with a wide range of frame rates, even with vsync on. (Technically, even games that only support exclusive fullscreen mode should work with a range of refresh rates, because it's not guaranteed that you can change the refresh rate to your desired value. I wouldn't be surprised if some games were buggy and assumed that refresh rate changes always worked, though.)
Finally, a comment on the specific case of Towerfall Ascension. It's my understanding that if you run the game on a high-end computer from 2013 (when the game came out), and go into the game's video settings menu and turn off vsync, it runs at over 1000Hz. Then if a superhuman player played the game on that computer (with a 1000Hz gaming keyboard), they could approximately reproduce keylie's run; to exactly reproduce the run, they would have to slow the game down to exactly 1000Hz.
If all this is correct, then the effect of the 1000Hz frame rate in keylie's run is to slow the game down compared to our hypothetical superhuman player using real hardware. In that case, I think that frame rate should clearly be allowed. And so (going back to the of an overall frame rate limit that is the subject of this thread), whatever general rule TASVideos adopts should be such that keylie's run is allowed.
Some Unity games show a startup window, which breaks libTAS for now. I've looked if there is a way to disable it using a commandline option but it seems it's not possible (there is a commandline option to force that window to show...)
I figured out how to disable the startup window, for at least a couple of Unity games. Find any files named ScreenSelector.so and remove (or rename) them. (More specifically, remove Plugins/x86/ScreenSelector.so if you're on 32-bit, or Plugins/x86_64/ScreenSelector.so if you're on 64-bit.)
As far as I can tell this has no effect on gameplay. Of course, I can't predict whether the judges would allow this for an actual submission; the rules say "No tampering with the files the game is composed of", but that's later qualified with "no ... deleting ... files that affect game-play", so it might be allowed?
With the help of Invariel, we managed to get 2 formulas:
NPCs and your movement make the rng go like this
rand = (rand * 1103515245 + 12345) % 4294967296;
and simply reloading a stage does this:
rand = (rand * 2603963141 + 1051550459) % 4294967296;
I'm guessing the first formula is for using a single random number. If so, then the second formula is for using 7 random numbers.
Another potential source of inspiration or implementation is Mozilla's RR project (rr-project.org). This records a single execution of a Linux program and later plays it back deterministically. (It's intended for debugging. For instance, if you've got an intermittent crashing bug, you can always run your program under rr, and when it crashes play back that execution with a debugger to see what caused the crash.)
It works at the system call level. It supports multiple threads (and even multiple processes), by simulating a single-core machine and deterministically scheduling threads onto that single core.
(I've read about RR, but never actually used it. It looks very cool, though.)
2. Find addresses before, and after a change
Say, if the player's X/Y address is at 02E1E8. After moving to another location, it moves to 02FF48. Note both the addresses down, and keep a small list of address locations for every time it changes.
I haven't tried it, but it seems like in this case you can narrow down the search for the pointer by searching between the two save states with "differs by" 1D60 (that's 02FF48 - 02E1E8). I'd expect that to usually give you only a few results to examine closely, and at least sometimes it would narrow it down to the single correct answer.
The 2496 bytes from address 0x000E9848 to 0x000EA206 (so that's 624 groups of 4 bytes) are used to determine the 624 next random numbers (for example, if the pointer is equal to 54, the 54th group will be used). They are changed each time the pointer come back to 1, and I don't know how the game calculate the new values, however it seems that for 624 given groups, the 624 next groups will always be the same, no matter what you do. Only the initial 624 groups can be manipulated, when you press "new game" in the main menu.
I don't know if you're still looking at this game, but just in case...
Given the state space of 624 4-byte words, I strongly suspect that the game uses the very popular Mersenne Twister PRNG (https://en.wikipedia.org/wiki/Mersenne_Twister).
Is there a method for proving a TAS to be optimal without brute-forcing all input patterns?
Are you asking for a general method that works for all TASes for all existing games? Or for all conceivable games? Or just a particular method that might work for at least one particular game?
I suspect that there is no general method that's fast enough to be practical, but I also suspect that some particular TASes could be proved optimal. (The simpler the game, the easier the proof would probably be; so if I wanted to attempt such a proof, I'd start with Desert Bus.)
Aqfaq wrote:
Is there a universal mathematical relation between an optimal TAS time and the number of alternative input patterns that achieve the same time?
Not sure what you mean by this.
Aqfaq wrote:
Is it possible to complete 1000 NES games with a single input file without dying at all?
Are there even 1000 NES games? Wikipedia claims that there are 826, and judging by the titles in the list, some of those wouldn't even have a concept of dying.
--------------------------------
Also, for people talking about TASing being NP-hard: for a problem to actually be NP-hard, it has to have arbitrarily large instances. So any TAS-related problem that involves TASing existing games that run on existing consoles is unlikely to qualify. (For example, Sokoban is evidently PSPACE-complete (and thus NP-hard); but testing whether a Sokoban map that fits in a 1000x1000 grid has a solution can be done in constant time (albeit a very, very large constant).)
Edit3: the vals always repeat, so it doesn’t seem like they can affect any randomness… :/
The values repeat every 2^25 (that is, 33554432) calls to rng(), and seeds (like the ones you give) that differ by multiples of 2^25 are equivalent (give the same sequence of values). Neither of these facts mean that this isn't where the "randomness" (pseudo-randomness) in the game comes from.
(I don't know anything about Tenchu, or anything relevant about PSX; I'm just looking at the Python code.)
I would suspect that the items you get would be determined by a combination of "val" from the rng(), your rank, and which level you're on; is that still possible, or have your tests ruled that out?
MESHUGGAH: I'm really not interested in running a tournament, although the tools would be available for anybody else to run tournaments if they wanted to. I guess I don't understand what you mean by a "simple project document"... that's what I tried to do with my original post in this thread.
Regarding game choice: Even if some games turn out not to be interesting when played in this fashion, hopefully others will. (And not just fighting games, either... how about Mario Kart?)
The question is whether you can manage to get your enemy's input for a given frame before you decide on your input for that frame.
- Timer starts from X seconds, press your inputs for the actual frame
- After the timer reaches zero, both players sends their input to the other
- Input displays, then go to the next frame
You need to add a lot of complexity to that to make it work across the Internet even if neither player is cheating. Consider a scenario where the clock on player A's computer is 3 minutes fast, the clock on player B's computer is 2 minutes slow, and the round-trip packet time from player A to player B and back is 800 milliseconds. How can you even start the timer at the same time on each computer under these handicaps?
But if one player is cheating the problem goes from annoyingly difficult to impossible. Suppose that somehow both players have synchronized their computer clocks, and have agreed that they should send their next input packets to each other exactly at noon. In the first scenario, the packet transit time is 200ms, so each player sends a packet at noon and receives a packet at noon+200ms. In the second scenario, the actual packet transit time is 50ms, but player B claims that the time is 200ms. Then player A sends a packet at noon, player B gets it at noon+50ms; player B sends a packet at noon+150ms, and player A gets the packet at noon+200ms. Both scenarios look exactly the same to player A, but in the second scenario, player B gets 100 milliseconds for a bot to look at player A's input and decide how to respond.
cwitty wrote:
If two players agree to play a game with some sort of hacked ROM, that's not cheating, that's just playing with a ROM hack. (Who would they be cheating?)
Making a hacked ROM with equal checksum (it's possible), so they can do hacked result of a game (it would be a problem if this project would be a "competitive scene" with championships).
I'm still not understanding the issue. If this "championship" is some sort of tournament, where all that matters is who won and who lost, then the players can control the result of the game just by having one of them deliberately lose. If the game is being judged for some sort of "style points", where the judge actually has to see the run, then this would happen by having the players submit the input file for their match to the judge. If they used a hacked ROM, then the game wouldn't sync when the judge played it back. (I suppose there could be a problem if the players could somehow get the judge to use the hacked ROM? But that would have nothing to do with my system, since the ROMs never touch the server.)
cwitty wrote:
I'm not sure what you mean by "fake matches" or what you're talking about with a second emulator instance.
While playing a match, you could run another emulator in the background, where you put the exactly same inputs you play with your enemy. If you do everything correctly, the online game and your offline (2nd emulator in the background) will sync and you have the opportunity to try various actions before sending your real input to the match. For example, starting a LUA script that uses some basic heuristic algorithms to manage health preserves and maximize damage output.
I was certainly hoping people would do things like this. That's why I said "[You can] ... use whatever methods you wanted to come up with [your input]" in my original posting. (The only difference is that I wasn't going to try to control what the player could do with their emulator, so they could do this in their "main" emulator -- no need for a 2nd emulator in the background.)
cwitty wrote:
I talked in huge detail about how my system would allow game-playing rates of up to 14 frames/day, even if the players couldn't be online at the same time. I agree that this would be a very different experience from playing at something like 1 frame/second, which I never suggested.
Just to make sure: I love your idea and I would even play this thing, but 14 frames/day is REALLY slow. Of course it would be only the "real action" (intros, cutscenes and menu settings would be a bit faster, right?), it's still would be very long matches and they will mostly fail to end due to the lack of motivation after you realize you have no chance to beat the enemy since you made a minor mistake after sending 64 inputs through a week. Sorry if this sounded too harsh, but I think that some seconds is enough to a frame, mostly because you can't try possible outcomes nor "retry" the actual frame.
Well, 14 frames/day is only if the players aren't online at the same time... if they are, then the game can proceed as fast as they want. It would also be possible to allow for an optional timeout if the players wanted it. (But I'd also leave the option to proceed without a time limit. A player might go a week without sending any moves while they search out some new RAM addresses and write a cool new lua script, and that would be OK with the server.)
There would have to be some mechanism for skipping past cutscenes etc. Probably one player would play through the cutscene (controlling both controllers) and submit that input file as a suggestion; then if the other player accepted the suggestion then they would use that input file to be past the cutscene.
I would certainly hope that people WOULD try possible outcomes, which is why I don't like the idea of only allowing seconds per frame. (But like I said, a timeout could be optional, and could certainly be configured for seconds per frame if that's what the players wanted.)
I would gladly help you if you would write down some guidelines regarding the gameplay and the motivation of playing this (online competitive scene, achievements, entertainment, variety). I'm also concerned about the number of players/TASers interested in this type of gameplay experience.
edit: you should do a poll on the forums after you come up with the rules and the system
Well, the motivation would have to be something like "have fun by trying to beat your opponent in a TAS setting". (I hope that it would also result in movies that would be interesting to watch; but if you wanted to do a 2-player playaround or something, these would be the wrong tools.) As far as achievements, tournaments, etc.; those would be interesting, but I wouldn't be interested in trying to set something up.
"... after you come up with ... the system": do you mean an implementation? I would probably try to implement this if people said they were interested, but I'm not going to implement it first just to find out if people are interested -- too much work going to waste if it turns out nobody is interested at all.
If I'm correct, you want to make a "gaming on demand" type of service where the TASers only get the "media" (this means you have no access to the memory, can't do any LUA scripts and I don't even want to think about copyright issues).
No, that's not my idea at all. The server would never have an emulator or any ROMs; the two players would have those. The server would only know how to merge two streams of input to create a single TAS input file.
The disadvantages of gaming on demand is hosting at least one server (money), making a lot of scripts for various emulators to get the most desired settings, restricting TAS features (short note: not everyone has high-speed internet, so it would be a pain to send and recieve HUGE packets at short intervals. that's why I recommend P2P+external program to send only the required inputs which results in VERY small packets).
I would use Google App Engine for the server, which is free (unless you start getting huge numbers of requests/second). Emulator settings would be decided off-line by the two players before starting the match; the server wouldn't even need to know what the settings are. My first post talked about sending inputs to, and receiving inputs from, the server; I guess I didn't explicitly say, but I meant that only the inputs would be sent/received.
At my method, the only disadvantage I can think of is that you can decode your enemies inputs/packets (but you can't alter it, since it won't sync), but it's really not a big deal. At first I thought it would be pleasible to show the enemies input display for frame to make the "gaming" a little bit "educationable", "learnable". Also another security hole would be that 2 gamer could cheat with "unexisting" ROMs, that could be avoided by making a script that replays on a 3rd computer that checks and verifies the results and actions etc.
Well, you have to decode your enemy's input packets in order to get them into your emulator. The question is whether you can manage to get your enemy's input for a given frame before you decide on your input for that frame.
If two players agree to play a game with some sort of hacked ROM, that's not cheating, that's just playing with a ROM hack. (Who would they be cheating?) I was imagining that some of these matches would be submitted to tasvideos (as a new category), at which point the normal rules would apply: only the TAS input file is submitted, so the judges run the input on their own emulator and need their own copy of the ROM in order to see the game. And submitting a ROM hack game but claiming it wasn't a hack would be totally pointless, since the input wouldn't sync for the judges.
The only thing I'm afraid of is: the gaming. Since the games are deterministic, if you win 1 time a game, you just have to send the very same input series/movie file, and you will always win (this is a huge issue especially when you try to abuse this with a friend to make fake matches or just simply running another instance of the emulator that instantly updates as your match so you have a very little time to test some "possible improvements").
Well, you're only controlling the input from one controller. It seems unlikely that many games have a winning input sequence for one player that works regardless of what the other player does. I'm not sure what you mean by "fake matches" or what you're talking about with a second emulator instance.
edit: spellings. and also a side note: gaming on demand would be the same as playing a game at 1 frame / sec. it's another thing than using emulator features that TASes demonstrates and uses to show those godlike movements and experience.
I talked in huge detail about how my system would allow game-playing rates of up to 14 frames/day, even if the players couldn't be online at the same time. I agree that this would be a very different experience from playing at something like 1 frame/second, which I never suggested.
MUGG, Patashu, thanks for the references.
MESHUGGAH, I don't understand the big difference between your idea and mine... your suggestion seems to be a slight refinement.
You have a timeout, I didn't; that could be a configurable option when starting a match. You have some automation in the "external program"; that would be very nice, but isn't essential to my idea and is a lot more work, so I didn't mention it.
The biggest difference seems to be that your programs communicate peer-to-peer, and my idea was to go through a web service. This doesn't actually seem to be a very big difference to me. The peer-to-peer version will probably require one or both players to mess with their firewall, so that argues in favor of the web service.
Also, with the web service, it would be easier to add a feature where other people (with their emulators) could watch a match in progress.
And I totally don't understand this sentence about the web service: "it's only neccessary if you want to restrict TAS features entirely, which is actually the opposite of what TASing really is." How on earth does sending moves to the other player by way of a web service intermediary "restrict TAS features" as compared to sending them directly?
edit: I forgot the main reason for the web service: to prevent cheating. You rely on the players sending each other their input at the same time. I don't see how to keep one player from hacking their "external program" and consistently sending their move a tenth of a second after receiving the other player's move, with a bot that picks a response based on that move. (A cheating player behind a fast internet connection would look just like a non-cheating player behind a slow internet connection.)
As long as both players trust the web service, then they don't have to worry about this form of cheating.
I have an idea for a new form of TAS, where two TASers play a 2-player competitive game (say, a fighting game, or a racing game).
The idea is that the game would be mediated by some sort of web service. Each player would submit their input to the web service, one frame at a time. Once a player has submitted (and committed to) a certain input for frame T, the other player's input for time T-6 would be revealed.
You could take as long as you wanted to submit your input, and use whatever methods you wanted to come up with it. (For instance, you would probably want to guess what the other player will do, and run simulations as to how your strategy will work.) The only thing you can't do is change your input once you've committed to it.
The main reason for the delay in the above description (where you get the other player's input after a 7 frame delay) is that it speeds up the process. For example, if the two players can't manage to be TASing at the same time, and want the maximum information available, then each TASer can provide 14 frames of input per session. (Player A will commit to inputs from T-7 to T+6; then player B will commit to inputs from T to T+13; then player A will commit from T+7 to T+20, etc.) With the minimum possible delay, where you see the other player's input for frame T as soon as you commit to frame T, then each player can only provide 2 frames of input per session.
Does this sound like an interesting idea to anyone else?
Oops, I'm a C++ programmer, it's undefined there. My last one was showing the transformation, poorly. Replace the first == with ->. Even so, I'm utterly surprised the optimization isn't universal, I swear I've seen an article on it before. You had -O3 and stuff?
I had -O3, but not "stuff" :)
$ gcc-3.4 -O3 -S foo.c
Since n%2 means something different than n&1, being able to optimize n%2!=0 would probably require a special case in the optimizer exactly for that expression (at least I can't think of a general-purpose optimization that would help, although I'm not an expert on such things).
Maybe you're thinking of the case where n is unsigned? I expect in that case, n%2 -> n&1 is essentially universal.
(BTW, I'll bet that a lot of C++ compilers always treat n%2 as if it were defined the C way. That's how essentially all hardware will implement a%b; if a%2 gives a different answer than a%b when b happens to be 2, you'll have unhappy users, even if the behavior is allowed by the standard.)
(gcc 4.3.4 is able to optimize "(n%2)!=0" to use the same fast code as "(n&1)!=0", but I prefer not to depend on the compiler being smart enough to implement non-obvious optimizations. I don't know whether other compilers include this optimization or not.)
Non-obvious? Are you kidding? Any compiler worth a grain of salt does that, even old Borland I'm pretty sure.
I did some more testing, and it's certainly not a universal optimization. gcc 3.4 produces an instruction sequence for (n%2)!=0 that is one instruction longer (and presumably is slower) than (n&1)!=0.
Also, you can't say `(-1)%2 is -1` because this is undefined according to the language. It very well could come out 1. That said, because compilers will optimize this to `n&1`, it then becomes trivial to see `n%2` == `n&1` == `n&1`
This was undefined in C89, but C99 (the current official standard for the C programming language) does define it such that (-1)%2 is -1.
I didn't understand the last sentence... was one of your `n&1` at the end supposed to be something else?
Note that n%2 and n&1 don't mean the same thing... (-1)%2 is -1, but (-1)&1 is 1. The code for "int n = ...; return n%2" is much longer/slower than the code for "int n = ...; return n&1". For this reason, I would use n&1 instead of n%2 (or else make sure that n is an unsigned int).
(gcc 4.3.4 is able to optimize "(n%2)!=0" to use the same fast code as "(n&1)!=0", but I prefer not to depend on the compiler being smart enough to implement non-obvious optimizations. I don't know whether other compilers include this optimization or not.)
Functors usually do require templates, and often it is possible to use templates. In this example, it certainly was. Then there is the std::function or whatever it is called. I believe this one can encapsulate a functor so long as you specify the types the functor must have. Which is pretty much the same as the member function pointer, but probably faster.
Functors can be faster than function pointers if the functor is statically known at the call site; in this case, where the functor is not statically known, I don't see how they could be faster than a function pointer. (Functors could be the same speed as a function pointer, which is probably faster than a member function pointer.)
If the algorithm enters an infinite loop and never finds a solution, it is broken. If the algorithm always finds a solution, then it's not broken.
A BFS that ignores history will still find the solution in the presence of loops in the graph (although it may do a lot of extra work). At each level, there is still a finite number of nodes, so it will eventually progress to the level containing the solution.
I've created a new page with useful RAM addresses for Super Mario 64 DS: http://tasvideos.org/SuperMario64DSTricks.html
(If any of you have more information/tricks/etc., please edit the page and add it!)
Is it allowed to use this hacked save data for hard mode runs? Tell me your opinion, please.
If the hacks actually make no difference, then would your completed hard-mode movie work with both the hacked and unhacked save data? If so, then just provide everything: movie to generate unhacked save data, unhacked save data, hacked save data, and hard-mode movie.
Once it's verified that the game plays the same based on both sets of save data, then the encoder could use the hacked save data for the increased entertainment value. I think they probably would, given that some movies use hacked emulators, etc., for the encodes, to increase entertainment.