1 2
8 9
Posted: 5/18/2011 6:45 PM
(Edited: 5/20/2011 12:23 AM)
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Currently working on more advanced botting. Most important new finding is addresses FFE0 and FFE1 which signify the current music track playing. This is to (potentially) be used by a bot that implements FatRatKnight's MusicDelay parameter above. Edit: I've updated my walking script to do some more sophisticated guessing and checking. This isn't particularly useful (walking isn't a very difficult thing to do), but it uses a new subfunction that should be very versatile. Basically, if we need to find a specific frame where anything in particular happens, we can test it using the same subfunction. The subfunction is guessandcheck. It takes five arguments: • action-- Some array of controller inputs. For example, if you want to go left, action would be {{left=1},{left=1}} (remember that you have to hold a button for two frames to get a response). • condition-- A passed function* that checks the condition that's desired. In the case of holding left, it should check whether address CCC9 (the horizontal position address) decreases by 1. (In fact, in the current version of my script, it only checks if either of CCC8 or CCC9 changes, regardless of what direction is pressed. It may be a good idea to change this.) Note that condition takes a variable called oldstate that's just a vector of relevant addresses. As our conditions grow more complicated, oldstate will grow larger. Someone could probably come up with a way to clean it up. • framedelay-- How long to wait after action is executed before checking. In the case of stepping left (or right, or up, or down...), the coordinate addresses change on the next frame, so framedelay can be set to 1. I set it equal to 3 in my walking script because I didn't bother to check the actual delay. • lowguess and highguess-- Initial guesses for the first and last frames that should be checked. These guesses are refined. Note that framedelay, lowguess, and highguess have no effect on the script's success as long as they encompass the desired condition. Therefore, they should be set as tight as possible only in the interest of making the script execute more quickly. *Thanks to FatRatKnight, BrandonE, and this site for explaining passed functions to me. The strategy here is very simple and I'll explain it first with an analogy. Suppose you wish to find page 592 in a book. You open up the middle of the book, check if that page is greater than or less than 592, keep the half that encompasses the page you're looking for, open up the middle of that half, and repeat the process. This is more efficient than leafing through the book one page at a time (which is effectively what my old walking script did). The same thing is going on here. It checks the frame in the middle of lowguess and highguess (rounding down). If condition is satisfied, then the earliest frame that can give us the action we want is somewhere between lowguess and the current guess, so highguess is revised to be the current guess. If condition is not satisfied, then lowguess is revised upward to be the current guess, plus one frame. And that's pretty much it. It just executes that loop until lowguess is equal to highguess. For an action like walking, which takes no more than 16 frames, just four iterations of the loop should be necessary to find the optimal frame. What's nice about this subfunction is that it can be used for many purposes other than a walking script. It potentially can be used to automate almost any process. I'm currently considering making an automatic battle fighter. This function should serve as the core of any future bots. Heck, with just a little work, it could be used as a bot for any game (and it would surprise me if no one has come up with something similar already). Edit 2: Noticed a mistake in my bot. If the last guess was unsuccessful, lowguess was bumped up to meet highguess and the loop was broken without executing the correct action. Now it goes back and loads the savestate and executes the proper guess. 
Language: lua
--Finds the earliest frame at which the RAM value at "address" is equal to "condition".
local function guessandcheck(action,condition,framedelay,lowguess,highguess)
	local state2=savestate.create()
	local oldstate={memory.readbyte(0xCCC9),   --x coordinate
			memory.readbyte(0xCCC8),   --y coordinate
			memory.readbyte(0xFFCE),   --cursor x
			memory.readbyte(0xFFCF),   --cursor y
			memory.readbyte(0x994A)}   --battle window
	local foundit=false
	savestate.save(state2)
	while not(foundit) do
		savestate.load(state2)
		guess=math.floor((highguess+lowguess)/2)
		for i=1,guess do
			emu.frameadvance()
		end
		for i=1,#action do
			joypad.set(1,action[i])
			emu.frameadvance()
		end
		for i=1,framedelay do
			emu.frameadvance()
		end
		if condition(oldstate) then
			highguess=guess
		else
			lowguess=guess+1
		end
		foundit = (highguess==lowguess)
	end
	savestate.load(state2)
	for i=1,lowguess do
		emu.frameadvance()
	end
	for i=1,#action do
		joypad.set(1,action[i])
		emu.frameadvance()
	end
	while not(condition(oldstate)) do
		emu.frameadvance()
	end
end


local function tookstep(oldstate)
	if not((memory.readbyte(0xCCC9)==oldstate[1]) and (memory.readbyte(0xCCC8)==oldstate[2])) then
		steptaken=true
	else
		steptaken=false
	end
	return steptaken
end


--Apparently Lua doesn't have a built-in sign function...
local function sign(x)
	if x>0 then      return 1
	elseif x<0>0 then
		for i = 1,n do
			vba.frameadvance()
		end
	end
end


--Walk in a given direction until ready to save.
local function walk(go)
	local speed=memory.readbyte(0xC5B2)
	local framesperstep=16/speed

	for i=1,2 do
		joypad.set(1,go)
		vba.frameadvance()
	end

	for i=1, framesperstep-2 do
		vba.frameadvance()
	end
end

local function makeitso(wpnumstart,wpnumfinish,waypointsx,waypointsy,frame,x,y)
	local wpnum=wpnumstart
	while wpnum<wpnumfinish>0 do
		go = setcourse(waypointsx,waypointsy,wpnum)
		walk(go)
	end
	pauseandsave()
	while vba.framecount()<frame do
		vba.frameadvance()
	end
	reset()
	idleframes(62)
	for i=1,2 do
		joypad.set(1,{A = 1})
		vba.frameadvance()
	end
	idleframes(10)
end

--Boilerplate...
cango=false
j=0
local state1=savestate.create()
movie.rerecordcounting(true)


--Waypoints to be traversed.  Because the player moves orthogonally, they should be staggered so only the x or y coordinate changes with each index *except* when the room changes.
--(Might be possible to take into account the room-- byte CCC7-- but it's a little complicated.)
--                 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
local waypointsx={12,13,13,14,14,15,15,19,19, 7, 7,19}
local waypointsy={11,11,12,12,13,13,14,14, 5, 5,14,14}

--The waypoint number.  Set to the index of the current waypoint or, if the first waypoint has yet to be traversed, just set it equal to 0.
local wpnumstart=1

wpnum=wpnumstart

while wpnum<#waypointsx do
	go=setcourse(waypointsx,waypointsy,wpnum)
	sumcoords=memory.readbyte(0xCCC8)+memory.readbyte(0xCCC9)
	guessandcheck({go,go},tookstep,3,0,16)
	wpnum = incwpnum(waypointsx,waypointsy,wpnum)
end

emu.pause()
Posted: 5/18/2011 9:50 PM
Quote
TheAxeMan
Ambassador, Experienced player (709)
Joined: 7/17/2004
Posts: 985
Location: The FLOATING CASTLE
Great find. Happy scripting! Have you reexamined anything that you thought may have been too tough to manipulate before? It sounds like this just helps give you more ways to manipulate faster but is it possible that it could open any other options?
Posted: 5/19/2011 3:18 AM
(Edited: 5/20/2011 5:34 AM)
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
I can't stand the idea of manual testing, so I am trying to incorporate this into a yet more sophisticated bot. It's intimidating, though. This bot will have to do just about everything. It will need to take note of frames where the music changes, backtrack to just before the music changed, create a savestate, move on, see how well it can manipulate luck, then if it's less than ideal, backtrack to one of those savestates and delay input by one frame at a time. I'd also like it to do some cost-benefit analysis on how many steps to shoot for before saving and resetting. It'll be tough, but if I can get it done, it will "solve" the game and give us nearly ideal input. Expect procrastination for a while. Edit: New useful addresses: C5BD and C5BE. These addresses appear to be zero when outside a text box, but inside dialogue they change to something else. The only caveat is that they also change when you "bump into" an NPC. That shouldn't be an issue, since we shouldn't be colliding with anyone in this run. I'll keep my eyes peeled for similar addresses. Edit 2: New useful address: D3EF. Battle option selection. Very useful for my battle bot. Edit 3: Sorry, D3EF is only for character 1. Here's the full list: Character 1: D3EF Character 2: D3F3 Character 3: D3F7 Character 4: D3FB Additionally, it appears that the subsequent addresses, D3F0, D3F4, D3F8, and D3FC, are the actions' targets. Those may specifically be enemies, with different addresses signifying friendly actions. I'll check it later.
Posted: 5/20/2011 12:27 AM
(Edited: 5/20/2011 10:20 PM)
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Here's a rough draft of my new bot I call "battlebot" (in honor of the show BattleBots that I briefly liked). Note that it uses the guessandcheck function I programmed earlier. As yet, this bot only executes the default commands and doesn't scroll through the text. With just a little bit of work, I can make it much better. Expect forthcoming edits... Edit: Updated version of my bot. This one always selects the second option for each character, though it can be easily modified to select either the first or second option. I had to insert idle frames between each action or it would "desync". With significant work, I can modify it so that any combination of actions can be chosen. I'd eventually like to organize them as a vector like {5,2,1,6}, which would signify that character 1 should execute option 5, character 2 should execute option 2, character 3 should execute option 1, and character 4 should execute option 6. This is nontrivial for a few reasons. First, we may not have four characters (that's simple enough to solve, but not at this hour). Second, I need to convert those options into actual actions. Third, I don't yet know how to optimally navigate the menu; I'll wait for feedback from FatRatKnight on that. In any case, load it up and give it a spin. It should work like a dream. Edit 2: Another new version of my script. This one just takes a vector of four specified actions in the format outlined in my previous edit. These should be input as actionvector near the bottom of the script. Currently, you can only select the default option, scroll down one option, or scroll down two options. In this default version, it always selects the second option. I've tested it and it seems to work fine with any options. (It wasn't able to "finish" the battle any faster with the default options than when selecting the second option. I don't know if that's an indication of success or not.) More thorough testing may come tomorrow. Edit 3: New version. This one works. 
Language: lua
--Finds the earliest frame at which the RAM value at "address" is equal to "condition".
--extra1, extra2, and extra3 are any extra information that needs to be used by the "condition" function.
local function guessandcheck(action,condition,framedelay,lowguess,highguess,extra1,extra2,extra3)
	local state2=savestate.create()
	local oldstate={memory.readbyte(0xCCC9),   --1)  x coordinate
			memory.readbyte(0xCCC8),   --2)  y coordinate
			memory.readbyte(0xFFCE),   --3)  cursor x
			memory.readbyte(0xFFCF),   --4)  cursor y
			memory.readbyte(0x994A),   --5)  battle window changes
			memory.readbyte(0xC424),   --6)  battle window selection offset
			memory.readbyte(0xFF92)}   --7)  selection within battle window
	local foundit=false
	savestate.save(state2)
	while not(foundit) do
		savestate.load(state2)
		guess=math.floor((highguess+lowguess)/2)
		for i=1,guess do
			emu.frameadvance()
		end
		for i=1,#action do
			joypad.set(1,action[i])
			emu.frameadvance()
		end
		for i=1,framedelay do
			emu.frameadvance()
		end
		if condition(oldstate,extra1,extra2,extra3) then
			highguess=guess
		else
			lowguess=guess+1
		end
		foundit = (highguess==lowguess)
	end
	savestate.load(state2)
	for i=1,lowguess do
		emu.frameadvance()
	end
	for i=1,#action do
		joypad.set(1,action[i])
		emu.frameadvance()
	end
	while not(condition(oldstate,extra1,extra2,extra3)) do
		emu.frameadvance()
	end
end


local function tookstep(oldstate)
	if not((memory.readbyte(0xCCC9)==oldstate[1]) and (memory.readbyte(0xCCC8)==oldstate[2])) then
		steptaken=true
	else
		steptaken=false
	end
	return steptaken
end


--Should be incorporated as a special case into selectedcorrect
local function selecteddefault(oldstate)
	if not(memory.readbyte(0x994A)==oldstate[5]) then
		selected=true
	else
		selected=false
	end
	return selected
end


--Checks if the cursor was moved down the proper number of slots before the selection was made.
--extra1 should be set to the character in question, extra2 should be the default actions, extra 3 should be 

the number of slots to scroll down.
local function selectedcorrect(oldstate,character,defaultaction,scrolllength)
	local defaultselection=defaultaction[character]
	if memory.readbyte(0xD3EB + 4*character)==(defaultselection+scrolllength) then
		selected=true
	else
		selected=false
	end
	return selected
end


local function idleframes(n)
	for i = 1,n do
			vba.frameadvance()
	end
end


--Finds the slot of the first usable action by any character.
local function firstusable(character)
	local foundit=false
	i=0
	while not(foundit) do
		ability=memory.readbyte(0xCC0F + 2*i + 0x1F*(character-1))
		uses=memory.readbyte(0xCC0F + 2*i + 0x1F*(character-1) + 1)
		if (uses<100) or (ability==0x13) or (ability==0x17) then
			foundit=true
		else
			i=i+1
		end
	end
	return i
end


local function loadactions(numalive)
	local action={}
	for i = 1,4 do
		action[i]=firstusable(i)
	end
	return action
end


local function autofight(scroll,actionvector,targetvector)
	defaultactions=loadactions()
	print(defaultactions)
	difference={}
	for i=1,#defaultactions do
		difference[i]=actionvector[i]-defaultactions[i]
	end

	guessandcheck(scroll[1],selecteddefault,6,0,16)
	for i=1,#actionvector do
		guessandcheck(scroll[difference[i]+1],selectedcorrect,8,0,16,i,defaultactions,difference[i])
		idleframes(2)

		--The following line should be updated to allow for selecting arbitrary targets (based on 

targetvector, which is unused).  Doing so would obsolete selectdefault.
		guessandcheck(scroll[1],selecteddefault,6,0,16)
	end
end


scroll={{{A=1},{A=1}},                                              --don't scroll
	{{down=1},{down=1,A=1},{A=1}},                              --scroll down 1
	{{down=1},{down=1,right=1},{down=1,right=1},{A=1},{A=1}}}   --scroll down 2
actionvector={6,2,2,6}
targetvector={}  --Unused, as yet.  Should specify which enemy to target.

autofight(scroll,actionvector,targetvector)


vba.pause()
Posted: 5/20/2011 3:39 AM
Quote
FatRatKnight
Editor, Skilled player (1202)
Joined: 9/27/2008
Posts: 1085
TheAxeMan wrote:
Have you reexamined anything that you thought may have been too tough to manipulate before? It sounds like this just helps give you more ways to manipulate faster but is it possible that it could open any other options?
Nothing was "too tough" to manipulate before. But this lets us get what we did manipulate possibly in fewer frames, as this opens up other ways of tweaking the RNG. However, this doesn't actually open up new RNG options. If it did, I would get the stoning version of GAZE in a hurry, don't bother with POWER, skip the stone book, and turn SEI-RYU into instant art. We're currently investigating a new route possibility through World I. Out of curiosity, I decided to equip the KING sword to see how much faster we slay the single SKELETON. It beat the previous time by quite a significant amount, as we go through NO attack animations thanks to the CRITICAL HIT!! that shows up. So now we're looking to see if a route change for an earlier sword is worth it. Old route: Tower -> Bandit Cave -> TELEPOR -> Castle Armor -> TELEPOR -> Castle Sword -> TELEPOR -> Castle Shield -> Town -> TELEPOR and climb Tower New route: Tower -> Castle Sword -> TELEPOR -> Castle Shield -> Bandit Cave -> TELEPOR -> Castle Armor -> TELEPOR -> Town -> TELEPOR and climb Tower The new route, along with an earlier powerful weapon, will also save exactly one step. The early KING sword we get will let us bypass attack animations thanks to that CRITICAL HIT!! it does to so many things. So far, I figured out how to beat KINGSWRD while manipulating TELEPOR off of him. Only problem is that we have to do it somewhat messy, fighting an extra battle early for more Mana, and one of our fodder dies much earlier thanks to the difficult RNG. We'll see what this means as we work out this new route.
Posted: 5/20/2011 4:10 AM
Quote
TheAxeMan
Ambassador, Experienced player (709)
Joined: 7/17/2004
Posts: 985
Location: The FLOATING CASTLE
That route sounds pretty badass to me. Good luck.
Posted: 5/30/2011 7:27 AM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Been working on new scripts. Most useful one so far is a script that will increment a "bin" vector to eventually run through all the possibilities. Special thanks to Nitrodon for helping me make sense of the algorithm. Here it is in a quickly testable format: 
Language: lua
local function sum(vector,low,high)
	if not(low) then
		low=1
	end
	if not(high) then
		high=#vector
	end
	local total=0
	for i=low,high do
		total=total+vector[i]
	end
	return total
end


local function incbins(vector)
	local i=1
	local total=sum(vector)
	while (vector[i]==0 and not(vector[#vector]==total)) do
		i=i+1
	end
	if vector[#vector]==total then
		vector={}
	elseif not(vector[i]==0) then
		vector[i+1]=vector[i+1]+1
		vector[i]=0
		vector[1]=total-sum(vector,2)
	end
	return vector
end


local vector={5,0,0,0,0}
while #vector>0 do
	print(vector)
	vector=incbins(vector)
	emu.frameadvance()
end

emu.pause()
Give that a run and I'll explain it. Did you run it? Good. Given any vector of "bins", this script will increment it to the next permutation, eventually running through all possible permutations. Suppose the music changes three times in a segment and we wish to test all of the possible ways to manipulate luck that involve delaying input for three frames total. Then our initial bin vector will be {3, 0, 0} which signifies to delay input by three frames at the first change in the music, zero frames at the second change in the music, and zero frames again at the third change in the music. By repeatedly plugging this vector into the incbins function, all possible permutations will be exhausted. These should be {3, 0, 0}, {2, 1, 0}, {1, 2, 0}, {0, 3, 0}, {2, 0, 1}, {1, 1, 1}, {0, 2, 1}, {1, 0, 2}, {0, 1, 2}, {0, 0, 3} (you can check these by replacing the vector={5, 0, 0, 0, 0} line in my script). This script should be extremely useful to us. I've also been working on my "ultimate bot", which should essentially solve the game for us. As yet, I only have a very rough draft that does not run, but it helps simply to have the format down. Here it is: Edit: After a hard night's work, I've got the basic structure of the bot functional. You may run this script at power on to suboptimally run the game through naming the first character. Once I write the musicmanip function, we should be nearly ready to test it through the first reset. I think the real test will be running the bot through several segments to compare it with the input of our existing run. If we override some parameters (not sure exactly how...) we should be able to reproduce the existing run exactly. If the two don't match, we can compare their inputs and see where it went wrong. Progress is accelerating. If the bot executes in any reasonable amount of time (say, less than an hour for one segment), we should be able to solve this game (for our given route). There's still a whole lot of work to do, but I now feel like the end is within sight. Edit 2: New version, with the main (only?) addition being the musicmanip function. (Thanks to BrandonE for help debugging it.) Looking through what remains, the hardest parts will be the walk function (which will also save and reset for us) and my battlebot function, which still isn't finished because it doesn't scroll through the battle narration. After those are written, it should just be a matter of writing some specialized functions and cleaning the whole thing up. 
Language: lua
local function sum(vector,low,high)
	if not(low) then
		low=1
	end
	if not(high) then
		high=#vector
	end
	local total=0
	for i=low,high do
		total=total+vector[i]
	end
	return total
end


local function incbins(vector)
	local i=1
	local total=sum(vector)
	while (vector[i]==0 and not(vector[#vector]==total)) do
		i=i+1
	end
	if vector[#vector]==total then
		vector={}
	elseif not(vector[i]==0) then
		vector[i+1]=vector[i+1]+1
		vector[i]=0
		vector[1]=total-sum(vector,2)
	end
	return vector
end


--condition is a table that takes the form {fn=condition function, adr={relevant addresses}, extra 1, extra 2, etc...}
--If executeaction is true, it executes the actions specified, if false, it merely advances frames up to lowguess.  Useful in conjunction with musicmanip.
local function guessandcheck(action,condition,framedelay,lowguess,highguess,executeaction)
	local state2=savestate.create()
	local oldstate={}
	for i=1,#condition["adr"] do
		oldstate[i]=memory.readbyte(condition["adr"][i])
	end
	local foundit=false
	savestate.save(state2)
	while not(foundit) do
		savestate.load(state2)
		guess=math.floor((highguess+lowguess)/2)
		for i=1,guess do
			emu.frameadvance()
		end
		for i=1,#action do
			joypad.set(1,action[i])
			emu.frameadvance()
		end
		for i=1,framedelay do
			emu.frameadvance()
		end
		if condition["fn"](unpack(oldstate),unpack(condition)) then
			highguess=guess
		else
			lowguess=guess+1
		end
		foundit = (highguess==lowguess)
	end
	savestate.load(state2)
	for i=1,lowguess do
		emu.frameadvance()
	end
	if executeaction then
		for i=1,#action do
			joypad.set(1,action[i])
			emu.frameadvance()
		end
	end
	--while not(condition["fn"](oldstate,unpack(condition))) do
	--	emu.frameadvance()
	--end
end


local function idleframes(n)
	for i = 1,n do
		vba.frameadvance()
	end
end


local function holdA(n)
	for i=1,n do
		joypad.set(1, {A=1})
		vba.frameadvance()
	end
end


local function gamestarted(startedflag)
	if not(memory.readbyte(0x9822)==startedflag) then   --0x9822 may not be the best byte to use.  Check others.
		return true
	else
		return false
	end
end


local function mutantfselected()
	if (memory.readbyte(0x8000)==3 and memory.readbyte(0x803E)==128) then		--Check if these are the addresses you really want
		return true
	else
		return false
	end
end


local function selectmutantf()
	action={{down=1},{down=1, right=1},{down=1,right=1,A=1},{down=1,A=1}}
	condition={fn=mutantfselected,adr={}}
	guessandcheck(action,condition,10,0,40,true)
end


local function namedR()
	if (memory.readbyte(0xFF93)==16 and memory.readbyte(0xFF92)==8) then
		return true
	else
		return false
	end
end


local function namechar1()
	action={{right=1},{right=1, down=1},{right=1, down=1},{up=1, right=1},{up=1, right=1},{right=1, down=1},{right=1, down=1},{right=1, A=1},{right=1, A=1}}
	condition={fn=namedR,adr={}}
	guessandcheck(action,condition,10,0,40,true)
end

local function musicmanip(backgroundaction,delayedaction,framesdelay)
	local action={{}}
	local buttons={"A","B","select","start","down","up","left","right"}
	for i=#backgroundaction+1,#delayedaction+framesdelay do
		backgroundaction[i]={}
	end
	for i = 1,(framesdelay+#delayedaction) do
		action[i]={}
		if i<framesdelay then
			for j=1,#buttons do
				action[i][buttons[j]]=backgroundaction[i][buttons[j]]
			end
		else
			for j=1,#buttons do
				action[i][buttons[j]]=backgroundaction[i][buttons[j]] or delayedaction[i-framesdelay][buttons[j]]
			end
		end
		joypad.set(1,action[i])
		emu.frameadvance()
	end
end

--anticipatebattle(waypointsx,waypointsy,waypoint,encounterrates)

--Create an updated guessandcheck function that supports background actions

--Change framesdelay to be a two-level table later on, based on the segment
framesdelay = {0,0,0,0,0,0,0,0}

pressA={{A=1},{A=1}}
pressB={{B=1},{B=1}}
pressselect={{select=1},{select=1}}
pressstart={{start=1},{start=1}}
pressdown={{down=1},{down=1}}
pressup={{up=1},{up=1}}
pressleft={{left=1},{left=1}}
pressright={{right=1},{right=1}}

local segment={}
segment[1]={	{fn=idleframes,60},
			{fn=guessandcheck,pressA,{fn=gamestarted, adr={0x9822}},10,0,20,true},				--guess and check when to start the game
			{fn=idleframes,5},
			{fn=holdA,320},
			{fn=selectmutantf},
			{fn=namechar1},					--cursor should end on the letter R
			{fn=idleframes,5},				--change to guessandcheck function with pressstart and executaction=false
			{fn=musicmanip,{{}},pressstart,framesdelay[1]},
			{fn=walk,1},					--walk to guild
			{fn=guessandcheck,...},				--guess and check when to press A to enter the guild
			{fn=guessandcheck,...},				--guess and check when to press down to select the second character slot
			{fn=guessandcheck,...},				--guess and check when to press A to select OK
			{fn=selectmutantf},
			{fn=namechar2},
			{fn=guessandcheck,...},				--select third character slot
			{fn=guessandcheck,...},				--press A
			{fn=selectmutantf},
			{fn=namechar3},
			{fn=guessandcheck,...},				--press up to select fourth character slot
			{fn=guessandcheck,...},				--press A
			{fn=namechar4},
			{fn=guessandcheck,...},				--press B
			{fn=walk,2},					--walk out of town
			{fn=walk,3}}					--the walk script should be modified to save and reset as it nears the encounter


for i=1,#segment do
	for j=1,#segment[i] do
		segment[i][j]["fn"](unpack(segment[i][j]))
	end
end


--should be able to overwrite frame constraints

--(reset)
--save state
--perform actions optimally until just before change of music
--use default action until appropriate frame, then use delayed action (possible overlap to consider)
--repeat previous two steps until "near" reset point (quantify "near")
--pause, save, and reset, much like luckman2 script (also check near misses for holding B)
--when a hit is found, add up total frames "wasted" and number of steps wasted, calculating the likelihood of an additional reset needed due to steps wasted, record these values to file
--set new frame contraint equal to best result so far plus one
--load state
--repeat previous seven steps until frame constraint is reached

--pseudocode (actions) to start the game
--------------------------------------
--press A
--hold A
--select and name character (luck manipulation?)
--walk to guild
--press A
--select and name supporting cast, leave guild menu
--leave town, enter field (luck manipulation?)
--(shuffle party?)
--walk as far as possible, reset

--press A to load game (luck manipulation?)
--walk until battle (luck manipulation?)
--fight
--defeat enemy (luck manipulation?)
--finish battle (luck manipulation?)
--walk until need to reset
Okay, most of that is notes and garbage. The important part is the segment[1] vector, which outlines every action we will take in the first segment of the game. This vector also establishes the syntax I'd like to follow. All that really remains is writing the appropriate functions, then running the code. I'll then incorporate the frame delays for luck manipulation and find an appropriate way to output the results (I was thinking I'd save them to file). Most of the code has already been written (little functions like namechar1 should take no more than three or four lines), so I think we're deceptively close to the testing phase. Polishing the script, however, will take quite a bit of time.
Posted: 6/4/2011 7:59 AM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Edit 3: Mapping complete! I have 190 maps in a .txt file that's 762 KB as well as a .tbl file that's 6.4 MB. Now I need to figure out what to do with them. --------------------- I made a mapper! Huge thanks to Acmlm and Ilari for pointing me in the right direction and even going so far as to find the map data in the RAM. This is a very simple version of the mapper-- its output is graphical (even though it's a .txt file), whereas the finished version will save the map as a table. I also plan on having it automatically detect room switches. With the game maps, I should be able to predict when we will fight our next battle. That should complete the walking script (with a little bit of work). Edit: New version of the mapper. You'll notice a "while not(beenthere[47])" statement. Room 47 corresponds to the Creator's plateau at the top of the tower. I ran my script with a different room number (corresponding to castle shield) and it worked fine. I tried running the updated version and got as far as the MACHINE in the power plant before being hit by a beam and killed. I've had problems like this before-- despite my "infinite health" cheat, it still decides to kill me. Because I didn't reach the Creator, no data was saved. Bummer. Next time, I'll use save states. (Also, in case anyone else wishes to use this script, some NPCs insist on getting in your way. You can shift them north by using VBA's built-in cheat functions and changing the corresponding addresses. Some other cheats are also necessary.) Note the "dofile("savetable.lua")" line at the top. That's a script I pilfered from this site. Seems to do the trick, but it's too early to say for sure (I haven't used its "load" function yet). Edit 2: I disabled the cheats and ran the script again with FatRatKnight's old run. The good news is that it worked fine, as you can see from this pastebin link with most of the maps. (I had to remove about 30 of the 140-or-so maps to get it under the 500 KB file size limit.) See how many of them you can identify! http://pastebin.com/SmLm8NP0 The bad news is that I still need to run it again, completing the game. The most glaring omission off the top of my head is the Northeast Town in World 2, which FatRatKnight didn't visit (it was before we re-evaluated the route). If anyone wants to run this script, tear through the game (while visiting as many rooms as possible), and send the resulting files to me, I'd be much obliged. If not, my project for tomorrow is pretty clear. 
Language: lua
dofile("savetable.lua")
local map={{{}}}
local mapfile = io.open("map.txt","w+")
local beenthere={}

for i=0,255 do
	beenthere[i]=false
end

for room=0,255 do
	map[room]={{}}
	for i=0,61 do
		map[room][i]={}
	end
end

while not(beenthere[47]) do
	--Change all RNGs
	for i=0,0x7F do
		memory.writebyte(0xC300+i, 0xBE)
	end

	--Super characte*r
	memory.writeword(0xCC06, 60000)
	memory.writeword(0xCC08, 60000)
	memory.writebyte(0xCC0B, 240)
	memory.writebyte(0xCC0C, 240)
	memory.writebyte(0xCC0D, 240)
	memory.writebyte(0xCC0E, 240)

	local currroom=memory.readbyte(0xCCC7)

	if not(beenthere[currroom]) then

		for frames=1,30 do
			emu.frameadvance()
		end

		map[currroom]={{}}
		for i=0,61 do
			map[currroom][i]={}
			for j=0,63 do
				map[currroom][i][j]=memory.readbyte(0xD000+64*i+j)
			end
		end
		beenthere[currroom]=true
	end


	emu.frameadvance()
end

for room=0,255 do
	--draw maps to text file
	local charcounter=65
	local isused={}
	if #map[room][1]>0 then
		for i=0,61 do
			for j=0,63 do
				tile=map[room][i][j]
				if isused[tile] then
					tilechar=isused[tile]
				else
					isused[tile]=string.char(charcounter)
					tilechar=isused[tile]
					charcounter=charcounter+1
				end
				mapfile:write(tilechar)
			end
			mapfile:write("\n")
		end
		mapfile:write("\n\n\n\n\n")
	end
end

--flush files
mapfile:flush()
assert( table.save( map, "map.tbl" ) == 1 )
savetable.lua: 
Language: lua
--[[
   Save Table to File/Stringtable
   Load Table from File/Stringtable
   v 0.94
   
   Lua 5.1 compatible
   
   Userdata and indices of these are not saved
   Functions are saved via string.dump, so make sure it has no upvalues
   References are saved
   ----------------------------------------------------
   table.save( table [, filename] )
   
   Saves a table so it can be called via the table.load function again
   table must a object of type 'table'
   filename is optional, and may be a string representing a filename or 

true/1
   
   table.save( table )
      on success: returns a string representing the table (stringtable)
      (uses a string as buffer, ideal for smaller tables)
   table.save( table, true or 1 )
      on success: returns a string representing the table (stringtable)
      (uses io.tmpfile() as buffer, ideal for bigger tables)
   table.save( table, "filename" )
      on success: returns 1
      (saves the table to file "filename")
   on failure: returns as second argument an error msg
   ----------------------------------------------------
   table.load( filename or stringtable )
   
   Loads a table that has been saved via the table.save function
   
   on success: returns a previously saved table
   on failure: returns as second argument an error msg
   ----------------------------------------------------
   
   chillcode, http://lua-users.org/wiki/SaveTableToFile
   Licensed under the same terms as Lua itself.
]]--
do
   -- declare local variables
   --// exportstring( string )
   --// returns a "Lua" portable version of the string
   local function exportstring( s )
      s = string.format( "%q",s )
      -- to replace
      s = string.gsub( s,"\\\n","\\n" )
      s = string.gsub( s,"\r","\\r" )
      s = string.gsub( s,string.char(26),"\"..string.char(26)..\"" )
      return s
   end
--// The Save Function
function table.save(  tbl,filename )
   local charS,charE = "   ","\n"
   local file,err
   -- create a pseudo file that writes to a string and return the 

string
   if not filename then
      file =  { write = function( self,newstr ) self.str = 

self.str..newstr end, str = "" }
      charS,charE = "",""
   -- write table to tmpfile
   elseif filename == true or filename == 1 then
      charS,charE,file = "","",io.tmpfile()
   -- write table to file
   -- use io.open here rather than io.output, since in windows when 

clicking on a file opened with io.output will create an error
   else
      file,err = io.open( filename, "w" )
      if err then return _,err end
   end
   -- initiate variables for save procedure
   local tables,lookup = { tbl },{ [tbl] = 1 }
   file:write( "return {"..charE )
   for idx,t in ipairs( tables ) do
      if filename and filename ~= true and filename ~= 1 then
         file:write( "-- Table: {"..idx.."}"..charE )
      end
      file:write( "{"..charE )
      local thandled = {}
      for i,v in ipairs( t ) do
         thandled[i] = true
         -- escape functions and userdata
         if type( v ) ~= "userdata" then
            -- only handle value
            if type( v ) == "table" then
               if not lookup[v] then
                  table.insert( tables, v )
                  lookup[v] = #tables
               end
               file:write( charS.."{"..lookup[v].."},"..charE )
            elseif type( v ) == "function" then
               file:write( charS.."loadstring("..exportstring

(string.dump( v )).."),"..charE )
            else
               local value =  ( type( v ) == "string" and exportstring( 

v ) ) or tostring( v )
               file:write(  charS..value..","..charE )
            end
         end
      end
      for i,v in pairs( t ) do
         -- escape functions and userdata
         if (not thandled[i]) and type( v ) ~= "userdata" then
            -- handle index
            if type( i ) == "table" then
               if not lookup[i] then
                  table.insert( tables,i )
                  lookup[i] = #tables
               end
               file:write( charS.."[{"..lookup[i].."}]=" )
            else
               local index = ( type( i ) == "string" and 

"["..exportstring( i ).."]" ) or string.format( "[%d]",i )
               file:write( charS..index.."=" )
            end
            -- handle value
            if type( v ) == "table" then
               if not lookup[v] then
                  table.insert( tables,v )
                  lookup[v] = #tables
               end
               file:write( "{"..lookup[v].."},"..charE )
            elseif type( v ) == "function" then
               file:write( "loadstring("..exportstring(string.dump( v 

)).."),"..charE )
            else
               local value =  ( type( v ) == "string" and exportstring( 

v ) ) or tostring( v )
               file:write( value..","..charE )
            end
         end
      end
      file:write( "},"..charE )
   end
   file:write( "}" )
   -- Return Values
   -- return stringtable from string
   if not filename then
      -- set marker for stringtable
      return file.str.."--|"
   -- return stringttable from file
   elseif filename == true or filename == 1 then
      file:seek ( "set" )
      -- no need to close file, it gets closed and removed 

automatically
      -- set marker for stringtable
      return file:read( "*a" ).."--|"
   -- close file and return 1
   else
      file:close()
      return 1
   end
end

--// The Load Function
function table.load( sfile )
   -- catch marker for stringtable
   if string.sub( sfile,-3,-1 ) == "--|" then
      tables,err = loadstring( sfile )
   else
      tables,err = loadfile( sfile )
   end
   if err then return _,err
   end
   tables = tables()
   for idx = 1,#tables do
      local tolinkv,tolinki = {},{}
      for i,v in pairs( tables[idx] ) do
         if type( v ) == "table" and tables[v[1]] then
            table.insert( tolinkv,{ i,tables[v[1]] } )
         end
         if type( i ) == "table" and tables[i[1]] then
            table.insert( tolinki,{ i,tables[i[1]] } )
         end
      end
      -- link values, first due to possible changes of indices
      for _,v in ipairs( tolinkv ) do
         tables[idx][v[1]] = v[2]
      end
      -- link indices
      for _,v in ipairs( tolinki ) do
         tables[idx][v[2]],tables[idx][v[1]] =  tables[idx][v[1]],nil
      end
   end
   return tables[1]
end
-- close do
end
Posted: 4/25/2017 7:18 AM
Quote
ruadath
Active player (261)
Joined: 12/13/2016
Posts: 352
Dang, how did you guys put so much work into a project and then not finish it off? In the meantime... improvements to the glitched category! Link to video
Posted: 4/26/2017 3:26 AM
Quote
FatRatKnight
Editor, Skilled player (1202)
Joined: 9/27/2008
Posts: 1085
ruadath wrote:
Dang, how did you guys put so much work into a project and then not finish it off?
I can put a lot of effort into analysis, taking apart a game most thoroughly, and can get all the way to something like 99% completion, then suddenly fall off and never come back to it again. I've left other unfinished projects, but I'm always happy if someone picks up the pieces and finishes what was started. I'm not sure how I can push myself back into finishing this. I can probably give support, but I can not lead this anymore, for some odd psychological reason I don't fully understand.
Posted: 12/28/2017 2:00 PM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Mothrayas suggested that I post this here. Originally, it was posted to this thread. There's basically no new information, but it's a nice little summary of how the RNG works.
Dwedit wrote:
Game Boy doesn't have an RNG, everything is software, and it would be odd for something to only appear on SGB or GBC.
I'm looking through my old notes, taking screenshots, and trying to disentangle the results of some trace logs. It's all very time consuming and I'd like to put up a very thorough document, as per Alyosha's request, but I think it's most important that I write down a quick summary while I know I still have the attention I need to devote to this:
  • The spell in question in Final Fantasy Legend is a version of GAZE that carries the stone effect. This is extremely important because there are some enemies and bosses (SEI-RYU in particular) that are immune to instant-death but not immune to stone. Having the GAZE spell means we can insta-kill him and other enemies, saving a lot of time. The reason I'm mentioning all this is to emphasize that this is not some abstract hypothetical: I intend to show that using SGB or GBC could potentially allow us access to an important spell that would save a good number of seconds in the run.
  • The RNG table is universal and begins at address CB00 and ends at CBFF (256 values). These values are fixed. I had a trace log at some point that pinpointed exactly how it was written-- I probably should reproduce that investigation. For the sake of the rest of this post, I'll assume that there is absolutely nothing we can do to manipulate the values in the table (I'm fairly certain that's the case).
  • There is a list of RNG pointers beginning at address C300 and ending at C37F. These pointers reference indices in the RNG table, generating random numbers for various purposes in the game. There are (no more than) 128 randomized functions, including potion effectiveness, random encounters, NPC movement frequency, NPC movement direction, etc. Basically, everything that's randomized in the game corresponds to a pointer somewhere in the C300-C37F range. Whenever a random number is needed, the value at CBxx is looked up where xx is the value of the corresponding pointer, then the pointer is incremented, modulo 256. This means if I roll a random number 256 times, the values will begin to repeat.
  • These pointers are all initialized upon startup or soft reset. I'll get into the actual mechanics of that later, but for now, I'll point out that the pointers start off "close" to each other and "creep upwards". For example, C300 might have the value 2A and all pointers up to C306 might also be 2A. The value might then increase such that pointers C307 through C30C are 2B and C30D is 2C. This "creeping" is extremely consistent and we have a nice mathematical formula to describe it. Effectively, the only thing that varies upon a soft reset is the exact starting point. Later on, I'll explain how this creeping arises and how it's potentially affected by the GBC or SGB modes. Much of this write-up assumes we're working with the vanilla GB platform, which we did throughout most or all of our investigations of the game.
  • The pointer that decides what mutant bonus is obtained is at C30B and the pointer that decides what spell the mutant learns (among other things) is at C34B. Based on the formula I just mentioned and the fact that these pointers are exactly 64 spaces away in memory, we've shown that C30B and C34B are "locked" to one another such that C34B will always be nine greater than C30B. Back in the day, FatRatKnight confirmed this experimentally. Crucially, this means that we can't manipulate mutant bonus type and learned spell independent of one another and we are limited to 256 initial states.
  • None of these 256 initial states correspond to learning GAZE (stone) at any time. We can't learn it initially and when we learn other abilities, we get locked into other periodic RNG patterns that consistently miss the magic values we need to learn the GAZE spell. I believe FatRatKnight investigated this long ago, but I've tried to confirm it by simulating RNG pointer patterns in Excel. Unfortunately, I'm getting some results that are inconsistent with what I'm seeing in the game, so my spreadsheet needs some refinement. I'm writing this up now in case I lose motivation and am unable to properly simulate RNG rolls.
  • Now's where it gets interesting. We know that the values of the pointers "creep upwards", but I haven't yet said why they do. Perhaps they are set in such a way that we actually can manipulate them such that C30B and C34B are not locked at values 9 apart from one another, giving us another degree of freedom with which to manipulate luck. To investigate this, we need to run a trace and determine how the RNG pointers are initialized. As it turns out, the code is pretty dang simple: upon startup, the value of address FF04 is loaded into C300, and then a loop counter increments and loads FF04 into C301. This continues 80 times total until the RNG pointers up to C37F are all set.
  • Now we need to know what FF04 is and why it increments. After reading a few articles online, I've learned that FF04 is the "divider register". It's basically a timer that runs independently of the rest of the game and increases at a fixed rate. Based on the short and consistent length of the loop that initializes the RNG pointers FF04 will always increment at such a rate that when C34B is initialized, FF04 will always be 9 greater than its value when it was used to initialize C30B.
  • BUT! The rate of this timer is dependent on the platform! Take a look at this page. With the SGB, the divider runs about 2.4 percent faster and it can even be run at double speed under the GBC. Dwedit, correct me if I'm wrong, but I believe this effectively acts as a "hardware RNG", although due to a tragic coincidence, it produces some not very random values when used to initialize the software RNG.
  • And to close out this post, I'll say that most of this is untested on my part. I know, I know, I should just sit down and force the SGB or GBC core, but I've done enough research for one night. Also, I just rebooted the game in the SGB core and I can't even find the damn RNG pointers in RAM watch. It's possible (or even likely) that although FF04 runs fast on the SGB, so too does the CPU by the exact same amount. Only differences in the relative clock speeds-- not absolute differences-- should free up the possibility to manipulate C30B and C34B independently of one another.
Whew! Good night, everyone!
Posted: 12/29/2017 12:57 AM
Quote
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3824)
Joined: 11/30/2014
Posts: 2832
Location: US
GBA TASer of 2023 Homebrew TAS of 2023 Gameboy TASer of 2022 NES TASer of 2015
Interesting. I looked over things quickly, and I don't think there is much room for manipulation here. SGB deosn't change the relative time between CPU and timer, so I don't think that will help. As mentioned by Dwedit, double speed mode requires the game to turn it on. I looked at where this is happening. It takes exactly 2304 (256 * 9) cycles between the time FF04 is read between those two addresses, and interrupts are not enabled at that time. So there really doesn't seem to be anything that would allow difference to be something other then 9. Too bad, that would have been cool.
Posted: 12/29/2017 4:11 AM
Quote
Bobo_the_King
Player (80)
Joined: 8/5/2007
Posts: 865
Alyosha wrote:
Interesting. I looked over things quickly, and I don't think there is much room for manipulation here. SGB deosn't change the relative time between CPU and timer, so I don't think that will help. As mentioned by Dwedit, double speed mode requires the game to turn it on. I looked at where this is happening. It takes exactly 2304 (256 * 9) cycles between the time FF04 is read between those two addresses, and interrupts are not enabled at that time. So there really doesn't seem to be anything that would allow difference to be something other then 9. Too bad, that would have been cool.
Yeah, this makes me wonder exactly how consistent the timing of these chips is. Is FF04 on a separate clock entirely? If there is some clock drift, there will be a small probability of deviating from the 256*9 cycles. In any case, I figure that with the millions of copies of this game and the number of times it's been booted up or reset, it's almost assured that some kid somewhere managed to learn GAZE through either the above-mentioned clock drift or some other hardware error. It's funny for me to think about how lucky they must have been without even realizing it. After all, Mutants are a pretty bad choice of character in unassisted runs of the game. Heh, they may have even learned GAZE and then immediately lost it due to ability shuffling or overwriting that spell slot.
1 2
8 9