View previous topic :: View next topic |
Author |
Message |
Phr34k
Joined: 20 Mar 2006 Posts: 1082 Location: London, Ontario, Canada
|
Posted: Sat Jul 22, 2006 5:19 am Post subject: |
|
|
Well from what I know...the big ass 2gb file on the disc contains all the game data files. You have to use a hex editor that can open a fecking HUGE file...and look for midi file formats. Then extract the data into separate files. This is as much as I know...as my disk was scratched so I couldn't copy the file onto my drive ;_; _________________
|
|
Back to top |
|
|
Riff
Joined: 08 May 2006 Posts: 104 Location: Champaign, IL
|
Posted: Sat Jul 22, 2006 7:51 am Post subject: |
|
|
You can snag my utility for extracting the midi files here. It is a windows console application that will extract the midi files to the same directory from which the program is run. Simply insert your Guitar Hero DVD into your DVD drive, run the application and specify the drive letter for your DVD drive. The midi files will end in .mid. The program takes quite a while to complete because there is no way to find a file entry associated with a given file name without searching through the entire archive.
You're on your own after this _________________
|
|
Back to top |
|
|
Genga
Joined: 19 Apr 2006 Posts: 2474 Location: Glasgow, Scotland
|
|
Back to top |
|
|
fatespeaks
Joined: 25 Mar 2006 Posts: 41 Location: Indianapolis, IN
|
Posted: Mon Jul 24, 2006 2:26 am Post subject: |
|
|
Genga wrote: | these midi files sound well quere :P |
I am sure they do. Probably has 5 unique pitches, maybe 10 if SP are encoded as different notes.
Riff, thanks for the exe. I'll check that out later.
I would still like to know how to parse the data. I think that is very interesting. Can anyone suggest a free Hex editor to use for this. Is there some sort of pattern matching used to locate midi data? While I have worked with midi in the past, I doubt if I would recognise a midi stream in a 2GB data file.
Thanks again,
-Aaron _________________
The guy wouldn’t know majesty if it came up and bit him in the face. |
|
Back to top |
|
|
IEatGlue
Joined: 16 Jul 2006 Posts: 769 Location: Waterford, Michigan
|
Posted: Mon Jul 24, 2006 3:39 am Post subject: |
|
|
i'll try and find you the one i used when i was war driveing and has to crack passwords and decypher stuff that was being sent over the network
it was awesome _________________
|
|
Back to top |
|
|
Genga
Joined: 19 Apr 2006 Posts: 2474 Location: Glasgow, Scotland
|
Posted: Mon Jul 24, 2006 8:29 am Post subject: |
|
|
someone suggested Hex Workshop _________________
ScoreHero's First Ever Mascot! |
|
Back to top |
|
|
adadas
Joined: 27 Jul 2006 Posts: 2
|
Posted: Wed Aug 16, 2006 2:22 am Post subject: |
|
|
I am trying to write a program to calculate the optimal score and sp path. I am working on the following idea:
optimalScore(Song) = computeScore(nextSection) + optimalScore(restOfTheSong);
However, at a given point in the song you have three choices:
1) activate SP and then play the next section
2) whammy during the next section,
3) play the next section without whammying or activating SP
So my program became sth like:
optimalScore(Song) = computeScore(nextSection) + max(optimalScore(restOfTheSong, choice1), optimalScore(restOfTheSong, choice2), optimalScore(restOfTheSong, choice3));
To properly compute the optimal score I also had to treat "section" as the smallest unit possible in a song, i. e., a half of a beat. The problem is that even a ridiculous song like I Love Rock And Roll (Easy) has over 500 halfbeats and calling a function recursively three times for each halfbeat is leading to EXPONENTIALLY long execution times...
I would like to know how you guys managed to write a program without falling into this recursion problem. What ideas did you use?? |
|
Back to top |
|
|
youhas
Joined: 21 Jul 2006 Posts: 3015 Location: Santa Clara, CA
|
Posted: Thu Aug 17, 2006 1:14 am Post subject: |
|
|
I'd been thinking about this a little bit, too.
Assuming that all notes are going to be hit, the only times when you really have to make any decisions are when it comes to star power - when to activate it, and whether to be accruing it via whammying on sustains. Moreover, you can't activate star power when you don't have at least half-bar , and there's no useful action to take while star power is activated and depleting, so the actual number of decision points is (relatively) small.
So given that, I'd hack up a song scoring "emulator" - go half-beat by half-beat, adding points for notes and accruing/depleting star-power accordingly - and brute force my way through the decisions. Make the base case "whammy on star power all the time; always activate star power the moment that I have a half-bar", then grind through every other possible run from there.
True, this has a certain pig-headed inelegance to it. Yes, you'd be iterating through tens of thousands of rock-stupid ideas - testing "saving all your star power and using it on the last three empty beats of the song"... and then following it with "saving all your star power and using it on the last two-and-a-half empty beats of the song". But with a reasonable input format, it should run on the order of minutes at very worst, and it has a certain definitively exhaustive nature that "clever" approaches might miss. (And if "on the order of minutes" proves patently untrue, there are some reasonably easy optimizations to be had: if Option A led you to be at Beat #x with score Y and zero star power, and Option B led you to be at Beat #x with score greater-than-Y and zero star power, don't even consider Option A lead-ins that got you to this point....)
I'd be happy to code something like this up (quick-and-dirty Perl ahoy!); I just lack certain raw data like "how much star power does completing a sequence yield?", "how much star power do you get per whammied beat?", "how many beats does it take to deplete star power?", etc. You know - stuff that is old hat to SP-optimizers and data-miners, but that I've simply been too lazy to actually look into firsthand. |
|
Back to top |
|
|
krimsunmunkeys
Joined: 16 Feb 2006 Posts: 1333 Location: The Hall of the SH Council... watching... (not really)
|
Posted: Thu Aug 17, 2006 1:40 am Post subject: |
|
|
youhas wrote: | I'd be happy to code something like this up (quick-and-dirty Perl ahoy!); I just lack certain raw data like "how much star power does completing a sequence yield?", "how much star power do you get per whammied beat?", "how many beats does it take to deplete star power?", etc. You know - stuff that is old hat to SP-optimizers and data-miners, but that I've simply been too lazy to actually look into firsthand. |
It's all here, in sections IV and V. |
|
Back to top |
|
|
adadas
Joined: 27 Jul 2006 Posts: 2
|
Posted: Thu Aug 17, 2006 5:55 am Post subject: |
|
|
youhas wrote: | the only times when you really have to make any decisions are when it comes to star power - when to activate it, and whether to be accruing it via whammying on sustains. Moreover, you can't activate star power when you don't have at least half-bar , and there's no useful action to take while star power is activated and depleting, so the actual number of decision points is (relatively) small. |
Let's take I Love Rock And Roll (Easy) as an example. Assuming you don't miss a star note and whammy whenever possible, you could accumulate enough SP to use through 30 measures (if I did all the calculations correctly). However, the song has 74 measures. If you are to evaluate which decision to take at every halfbeat, excluding those where SP is depleting, it means you have 704 decision points (44 * 8 * 2). Additionally, if the evaluation is done in a recursive manner, it would require 2^704 (2 to the power of 704) function calls. Not a work to finish in this life!!
youhas wrote: | Make the base case "whammy on star power all the time; always activate star power the moment that I have a half-bar", then grind through every other possible run from there. |
What about those songs where a sequence of star notes is immediately followed by several measures of empty space??
youhas wrote: | there are some reasonably easy optimizations to be had: if Option A led you to be at Beat #x with score Y and zero star power, and Option B led you to be at Beat #x with score greater-than-Y and zero star power, don't even consider Option A lead-ins that got you to this point....) |
This is actually the core of the problem: to evaluate and compare all those options. To effectively calculate the optimal score, you would have to consider EVERY option possible and compare each with all the others in order to decide which yields the best score. This is hardly "reasonably easy".
Last edited by adadas on Thu Aug 17, 2006 7:12 am; edited 2 times in total |
|
Back to top |
|
|
popemobile
Joined: 03 Jun 2006 Posts: 3879
|
Posted: Thu Aug 17, 2006 6:03 am Post subject: |
|
|
I'm pretty sure the optimal score for ILRAR is around 139217 or something, took me about 30 seconds to figure it out |
|
Back to top |
|
|
youhas
Joined: 21 Jul 2006 Posts: 3015 Location: Santa Clara, CA
|
Posted: Thu Aug 17, 2006 8:10 pm Post subject: |
|
|
krimsunmunkeys wrote: | youhas wrote: | I'd be happy to code something like this up (quick-and-dirty Perl ahoy!); I just lack certain raw data like "how much star power does completing a sequence yield?", "how much star power do you get per whammied beat?", "how many beats does it take to deplete star power?", etc. You know - stuff that is old hat to SP-optimizers and data-miners, but that I've simply been too lazy to actually look into firsthand. |
It's all here, in sections IV and V. |
Ah, excellent - knew it was around here someplace that I'd failed to blindly stumble upon yet. Thanks much! |
|
Back to top |
|
|
youhas
Joined: 21 Jul 2006 Posts: 3015 Location: Santa Clara, CA
|
Posted: Thu Aug 17, 2006 8:14 pm Post subject: |
|
|
adadas wrote: | However, the song has 74 measures. If you are to evaluate which decision to take at every halfbeat, excluding those where SP is depleting, it means you have 704 decision points (44 * 8 * 2). Additionally, if the evaluation is done in a recursive manner, it would require 2^704 (2 to the power of 704) function calls. Not a work to finish in this life!! |
Quite true. Which is why I didn't use a recursive manner in the slightest, instead preferring to mindlessly blast my way through every iteration. I'm reasonably sure that this makes determining optimization O(NS), where N is the number of notes in the song and S is the number of potential star power uses, rather than O(2^N) - something along those lines, anyway. I'm pretty sure that there are only a couple thousand possible different combinations for ILRAR/Easy the way I'm envisioning it, though this is just a back-of-the-envelope sort of figure.
adadas wrote: | youhas wrote: | Make the base case "whammy on star power all the time; always activate star power the moment that I have a half-bar", then grind through every other possible run from there. |
What about those songs where a sequence of star notes is immediately followed by several measures of empty space?? |
Oh, sure. That's why I was going to brute force my way though every possible combination. The base case is just an arbitrary "have to start somewhere" point.
Aided by krimsunmunkeys' link, I'll see if I can't do a lame little proof-of-concept with ILRAR/Easy once I'm home from work. And if it turns out that my plan is a hideous screaming failure after all, I will report back here with my head held in shame accordingly. |
|
Back to top |
|
|
youhas
Joined: 21 Jul 2006 Posts: 3015 Location: Santa Clara, CA
|
Posted: Mon Aug 21, 2006 7:09 pm Post subject: |
|
|
Just in case anyone was wondering how this was going: the "find an optimal star path in non-ludicrous time" went quite well.
I named the smallest consideration-worthy interval between two time events to be a "tick" and decided to give "four ticks per beat" on "I Love Rock And Roll" (Easy) a try. By eyeballing the PNG file and painstakingly scrawling out which-event-occurred-when, I created an "events document" for the song for each tick. "At tick 472, the measure changes to 16 ticks/measure, there is a red note comprising the sixth star power grouping, with a starred hold of 43 ticks...." - that sort of thing.
The algorithm used, semi-psuedocode style:
Code: | game_states_to_consider queue has one entry - the initial game state.
completed_game_states queue is empty.
while (entries in the game_states_to_consider queue) {
emulate_game(game_state)
}
sort completed_game_states by score
def emulate_game {
while there are ticks remaining in this emulation {
process the present tick (strike notes, add/decrease star power, etc.)
if (score <= max score in other runs at this tick/star power/activation) {
give up on this run
}
store my score as max score at this tick/star power/activation
if star power can be activated but is not activated {
add to game_states_to_consider this game state where I activate on the next tick
}
advance one tick
}
game over - store in completed_game_states
} |
So to step through things a bit: the initial game run does so on autopilot until tick 212, at which point the second star power has been gotten and the meter is half full. For each tick hereafter in the first run, we'll consider the case where we activated star power right at that tick, from "the moment I got that star power, I used it!" to "I saved it until the very last half-beat of silence". Add all of 'em (~900) to the queue. At the end of this run - where you didn't use star power anywhere - add yourself to the finished runs queue.
Repeat this process for each entry in the queue. For example, when we immediately activated it, we don't get any additional choices until the existing power has run out and we've picked up two more star sequences at tick 380. Explode out the 700+ remaining ticks the same way we did before; lather, rinse, repeat.
Eventually, you'll end up brutally processing your way through every possible star power activation sequence, save for the ones culled by the "give up on this run" detection. Which is a safe culling to make, I think. If I'm at score X at {tick T, S star meter, star power inactive} and you're also at {tick T, S star meter, star power inactive} with score X+C, I might as well give up - just match me note-for-note and activation-for-activation and you will invariably win by C points, no matter what I do. (Without the "give up on this run" branch optimization, I think you end up with something like O(N^S), where N is the number of ticks and S is the number of star power sequences - still too impractical to work with, even with speedy machines.)
But enough theory. Grinding through it with my Ghetto Perl Skillz(tm), ILRAR on Easy, the algorithm considers briefly ~62,000 game states, emulating ~10,000 of them to completion. The path it finds is optimal as far as the emulator is concerned. Which is not quite what the game finds optimal, of course, because my emulator doesn't handle some edge cases correctly. Still, it'd be good enough for top 10 if I played it correctly, and the problem is in my emulator function, not the alorigthm that calls it.
So you probably can get star power optimization in reasonable time - even for hideously complex songs, on the order of hours, if you had the hardware to throw at it. Yay team. (Even with my hokey and inefficient setup, ILRAR/Easy took something less than a minute to chew through.)
Avenues for improvement:
- Rewrite this in a real language; use actual objects instead of "eh, I'll hack this up with another hash".
- Actually read and parse the MIDI files instead of taking PNGs and applying glorified data entry processing mashing them into text files.
- Handle optional whammying. (Right now it assumes that any starred-hold should be whammied non-stop; this is not necessarily the case.)
- Make the emulator more like the game. Increase the tick rate for better granularity. Acknowledge that notes are not single points, but windows during which activation can occur. Don't assume star power is instantaneously available once a star sequence is attained getting you over half a bar. Et cetera and so forth.
- Don't just FIFO the queue entries, but apply some sort of heuristic for handling more promising entries first; this will make the culling comparison more ruthless and cause fewer useless paths to be explored.
I don't know if all of this will scale as readily as I hope - nor how much of this is reinventing wheels that other promising GH code sifters have accomplished - but that's what all I figured out over the last couple of days' free time.
Thoughts? |
|
Back to top |
|
|
HylianHero
Joined: 22 Feb 2006 Posts: 4673 Location: Santa Cruz, CA
|
Posted: Mon Aug 21, 2006 7:54 pm Post subject: |
|
|
...Wow. I wish I was smart enough to piece together that algorithm. [/thought]
Looks pretty good. _________________
|
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Copyright © 2006-2024 ScoreHero, LLC
|
Powered by phpBB
|