just an update, I've wired up a stub of the bot to snes9x.
The stub successfully creates input, reads Mario Kart's variables, and saves/loads game states to/from arrays.
Now I'm ready to start working out the quadralaterals and the 'meat' of the bot.
Just working out the shortest path for each level won't do much especially if there is CPU interaction.
It would work for time-trials, though :). You could eliminate most of the computations by "hardcoding" the track width, length coordinates. Instead of taking a million years, it would only take about 100 ;).
Or are you just going to be using the bot for short segments? Like bisqbot?
Actually, I'm quite interested to see some of the pseudocode you have. I probably won't understand any of it, but I'm mainly interested in how you managed to interact with SNES9x remotely? Did you call some DLLs? Viewing fmod.dll just gave me a bunch of sound/music functions...
I'm going to use the bot for the whole of the track, from just after accelerate is pressed to get a turbo-start, until it hits the finish line.
I got around the problem of calling snes9x remotely by... not calling it remotely! I've hacked in code to call my bot in the bit where snes9x checks for keyboard input.
Is it going to test every single freaking button combination every single frame until the end of the track recursively to find the combination that yields the fastest time? Or by the whole of the track from the start to the finish line do you mean that you will just be using the bot for the whole track, but splitting the track into segments? Cause I can imagine the first one would take forever...
Well, isn't the bot mostly just figuring out the best way to steer?
Right, which prunes a great amount of recursive calls, as you have a set of coordinates (probably a position, velocity, and time vector too), and a predefined track. You aren't testing randomly, you are testing to fit a situation, which is much easier (it's like a hot/cold thing).
My question still stands. Let's say you sucessfully get the shortest path for a track. What happens if there is CPU intervention in your path?
Won't that cause major problems? And how are you going to manipulate luck so that you get mushrooms, feathers, or stars to take shortcuts?
Well, with CPU intervention the velocity vector will go down so the bot will probably choose a different path.
Manipulating luck to get mushrooms, feathers or stars...I guess you could have the bot check the rom address telling whether or not you have an item and if so what kind, to reject paths that give you anything but a mushroom, feather or star?
Good luck, it sounds like a fun project (about 10,000,000 times harder than the sudoku solver I programmed the other day)
Good luck, it sounds like a fun project (about 10,000,000 times harder than the sudoku solver I programmed the other day)
What a coincidence, I made a sudoku solver a while back (In January).
Catch is, it solves grids of n size n^4 is the size of your puzzle:
For example, n=3 would be the standard 81 cell grid, n=4 would solve a 256 cell grid...
See the details here:
http://inst.eecs.berkeley.edu/~cs61c/sp06/projs/01/doc/index.html
Back on topic. I guess you could program getting stars and going around cpu's on the fly, but it sounds like it would drastically increase the computational time.
Right, I've tested my (very early and crappy) bot out on two corners and a straight connecting them on Mario Circuit 1 on time trial mode... it took about 2 minutes to work out solutions to them, with the input buttons being changed every 10 frames (3 times a second) -- but I know I can get the bot much faster than this, and when I do I'll be able to run it changing the input every frame.
Here's an update on how it works:
It does a depth first search of the possibilities.
In order to not have to search all the possibilities, it searches the most direct ones first -- and uses the first solution it finds that doesn't crash into something or do something else blatantly stupid.
By 'most direct ones first' I mean I first mark all the areas as being left corners or right corners, then (if its in a left corner zone):
it first tries turning left.
its second choice is to hop left
its third choice is to go straight.
Its actually a bit more complicated than this, because I think there's sometimes an advantage in hopping/turning the other way at the end of a corner to straighten out (and there are a few tricks I've thought of too, so the bot won't have to look at so many possibilities), but thats the basic idea.
If it hits another Kart or obstacle or doesn't get the power up it wants it just backtracks and tries the next most direct route.
To manipulate luck to get the power up of choice I may try making it first try pressing on and off the 'use' button while it doesn't have anything to use (I'm not sure if pressing brake in midair does anything or not...) - that way it'll hopefully change the power up it gets without having to comprimise its route.
But I've ran into a problem at the moment; the bot saves a list of 'actions' its tried to a file so I can play it back later (and make a snes9x movie file), but I find it desynchs (what a suprise)... I think this may be being caused by the code in snes9x that saves or loads savestates advances the game state a few frames each time it's called... but that seems very strange.
But I've ran into a problem at the moment; the bot saves a list of 'actions' its tried to a file so I can play it back later (and make a snes9x movie file), but I find it desynchs (what a suprise)... I think this may be being caused by the code in snes9x that saves or loads savestates advances the game state a few frames each time it's called... but that seems very strange.
Does it desynch immediately, or is it successful until a point?
If nothing goes right, there might be a bug in your progam (like the duration between button presses is incorrect). If it works sometimes, then it's probably SNES9x's fault, or a hard to find bug in your program :(.
Actually, it might be beneficial to play time trials with your bot. It would be a better indication if it works or not, as it is less random, and might be faster for your bot to provide the fastest route.
Just some suggestions...
But I've ran into a problem at the moment; the bot saves a list of 'actions' its tried to a file so I can play it back later (and make a snes9x movie file), but I find it desynchs (what a suprise)... I think this may be being caused by the code in snes9x that saves or loads savestates advances the game state a few frames each time it's called... but that seems very strange.
Does it desynch immediately, or is it successful until a point?
If nothing goes right, there might be a bug in your progam (like the duration between button presses is incorrect). If it works sometimes, then it's probably SNES9x's fault, or a hard to find bug in your program :(.
Actually, it might be beneficial to play time trials with your bot. It would be a better indication if it works or not, as it is less random, and might be faster for your bot to provide the fastest route.
Just some suggestions...
yeah, it's probably a problem with my code, but it does seem like snes9x's load/save functions cause a few frames to be skipped.
I'm going to test it out on the time trial maps, but I'd like to do the GP mode when I get it working properly -- because I think that's way more interesting, and probably not that much harder once the bot kinda works.
but I find it desynchs (what a suprise)... I think this may be being caused by the code in snes9x that saves or loads savestates advances the game state a few frames each time it's called... but that seems very strange.
I'm quite sure that is not the problem (somebody would have noticed such a huge bug by now when trying to perform frame-precise maneuvers). It's probably either a bug in your code, or a problem with the version of Snes9x you based your code on. If you didn't use anything from this version then it is likely to desync because previous versions did not save the state of the DSP1 chip in the savestates, and Mario Kart is among the very few games that use that chip.
but I find it desynchs (what a suprise)... I think this may be being caused by the code in snes9x that saves or loads savestates advances the game state a few frames each time it's called... but that seems very strange.
I'm quite sure that is not the problem (somebody would have noticed such a huge bug by now when trying to perform frame-precise maneuvers). It's probably either a bug in your code, or a problem with the version of Snes9x you based your code on. If you didn't use anything from this version then it is likely to desync because previous versions did not save the state of the DSP1 chip in the savestates, and Mario Kart is among the very few games that use that chip.
Heh, by 'strange' I meant 'unlikely' :)
I think I've found what in my code was (at least partly) causing my desynchs -- haven't got round to fixing it yet though.
I'm using DeHackEd's version of snes9x, which I've modified a bit myself. Thanks for letting me know about the DSP1 state thing - that could really screw my run up since my bot saves and loads almost every frame. I'll have to check DeHackEd's version saved it, and if not I'll try doing some diffs and apply them :-S
looks like I don't have the right version of snes9x (no wonder it seemed saving states made it go funny).
Is the source code to 'improvement 9' avaliable anywhere?
Also... I don't understand the snes9x version naming scheme at all
Well my bot's going pretty well, but I've hit an interesting problem:
Immediately after reloading, it appears to go straight through a pipe... but then when I play back the actions my bot did, it hits the pipe.
Now at first I just thought I hadn't properly saved the actions my bot did, but now I think its because for one frame after a reload, the pipes aren't in the right place.
Here are some screenshots I took as evidence:
In the below frame, the bot is about to go off the course... so it reloads:
Then after it reloads, the pipes are in the wrong place!
One frame later, they jump to where they should be:
Since the bot appears to be desyncing by going through a pipe immediately after it reloads, I think this is more than just a visual glitch.
I've made a temporary hack to get around this, but it's not a proper fix and could become a problem later. Really the state should be reloaded exactly as it was when it saves.
Anyone have any idea what could be causing this?
The DSP1 chip?
Make your bot change input every other frame? I dunno how much that would affect the accuracy, but you could try it.
I'm having to do something like that - basically if it hits something, I reload two saves back rather than one (to ensure its at least two frames away from hitting a pipe). This doesn't hurt the accuracy of my bot, but does make it take longer to work out the run.
Incidentally, Mario Kart only checks for left/right input every other frame, but it seems to check for 'hop' input every frame (and if you press hop on frame 0 you can next hop on exactly frame 18).
Currently, changing input every 4 frames, the bot takes overnight to do 5 laps of Mario Circuit 1 on time trial. As soon as I work out how to get my bot to record to smv files I'll post one here :)
in bullet-proof rerecording, aren't movies recorded within the savestates ?
if snes9x isn't bullet-proof, maybe it would be time to add it :)
I'm really eager to see the result of your bot, if it beats the human records by a significant margin.
I never sleep, 'cause sleep is the cousin of death - NAS
in bullet-proof rerecording, aren't movies recorded within the savestates ? if snes9x isn't bullet-proof, maybe it would be time to add it :)
I think so, but working with a very long movie (1.7MB), the save states while recording are typically around 150KB. So I'm not really sure any more... maybe it uses compression?
Huffers wrote:
Currently, changing input every 4 frames, the bot takes overnight to do 5 laps of Mario Circuit 1 on time trial. As soon as I work out how to get my bot to record to smv files I'll post one here :)
Oh nice, what was the time? (I'm too excited to wait for the smv version!)
I think so, but working with a very long movie (1.7MB), the save states while recording are typically around 150KB. So I'm not really sure any more... maybe it uses compression?
Savestates are just dumps of the RAM, they should be the same size for each game no matter what the size of the movie.
I think so, but working with a very long movie (1.7MB), the save states while recording are typically around 150KB. So I'm not really sure any more... maybe it uses compression?
Savestates are just dumps of the RAM, they should be the same size for each game no matter what the size of the movie.
I think they're zipped too, which may change their size a bit.
oh man, more techniques/glitches I didn't know about -- I'm going to have to change my planned routes again :)
Snes9x does have bulletproof recording. (Actually I think it was the first emulator here to have it. Or possibly that was FCEU.)
It sounds like some variable isn't saved in the savestate like it should be, or is somehow loaded improperly. Some games (MMX2) have this problem, others (Zelda alttp) has had it in the past. Someone knowledgeable about the Snes9x source should look into it.
It's not beating the world record time yet, because I didn't know about this 'NBT' trick stuff... and it's going to be tricky figuring out how the NBT stuff really works and how to best do it -- so don't expect a video any time soon :P
And I probably won't have a chance to do any TASing today as I'm going to the zoo and for a meal with a young lady -- but hopefully I'll get rid of her early if I spend the whole date talking about Super Mario Kart :)
Savestates are just dumps of the RAM, they should be the same size for each game no matter what the size of the movie.
No, that couldn't be more wrong. There are many more things that need to be saved in the savestates than the RAM. Including, in this case, the movie.
Truncated wrote:
It sounds like some variable isn't saved in the savestate like it should be
Nitsuja, I'm just curious, how does the save state contain the movie file without being nearly as large as the movie file?
Huffers: even if its not as fast as the WR I'd still be curious what your time was, to compare it to the non-NBT record. And again even if its not as fast as the non-NBT record its still quite an accomplishment considering you automated the whole thing and these records are close to perfect with 12+ years of people working on them.
Then after it reloads, the pipes are in the wrong place!
One frame later, they jump to where they should be:
Since the bot appears to be desyncing by going through a pipe immediately after it reloads, I think this is more than just a visual glitch.
I've made a temporary hack to get around this, but it's not a proper fix and could become a problem later. Really the state should be reloaded exactly as it was when it saves.
Anyone have any idea what could be causing this?
The DSP1 chip?
