User File #46029021186161583

Upload All User Files

#46029021186161583 - Pictionary RNG DP

pictionary rng.lua
Game: Pictionary ( NES, see all files )
743 downloads
Uploaded 3/26/2018 9:54 PM by warmCabin (see all 30)
Most of this is explained in much more detail within the comments of the lua file, but here's a rundown:
It presses start on a certain frame to examine a word sequence. It reads the phrase from memory (0x0448) and determines how long it takes to type using a simple DP. It can then tell you which sequence of 6 phrases takes the shortest amount of time to type.
Note that it uses your shift+F1 savestate as a starting point...instructions on how to properly set this up are in the comments.

--[[
	I need to learn to read a savestate from a file...
	Currently, slot0 correspond to your shift+F1 savestate.
	It needs to be on frame 479, which is the first frame you can press start after (not) entering your team name.
	To generate this savestate, press start on frames 299, 323, and 463, then wait for frame 479.
]]
local slot0 = savestate.object(1)
local start_frame = 0
local test_frame = 0
local inited = false
local testing = false
local prev = nil
local totalLen = 0
local typeTime = 0
local index = 0
local lagCheck = true
local freeFrame = 0
local lagsChecked = 0
local best = 123456789
local worst = 0

emu.speedmode("turbo") --Doesn't seem to do anything. Try NES -> Emulation Speed -> Turbo in the application.
emu.setrenderplanes(false,false)
--emu.unpause() --seems to either TOGGLE paused state, or do nothing. I'm not really sure...

emu.print("~~~~~~~~~~~~~~~~")
emu.print("Welcome to the Pictionary RNG Checker!")
emu.print("Rendering has been disabled to save on processing time and eyestrain.")
emu.print("Enable turbo mode and mute your sound!")
--emu.print("Unpause the emulator to begin.")
emu.print("~~~~~~~~~~~~~~~~")
emu.print()

local function init()
	
	savestate.load(slot0)
	start_frame = emu.framecount()
	prev = "................"
	totalLen = 0
	typeTime = 0
	index = 0
	testing = false
	lagCheck = false
	lagsChecked = 0
	freeFrame = 0
	inited = true
	
	if test_frame >= 959 then
		emu.pause() --this does nothing??? Is it not valid in a post frame callback????
	end
	
end

--returns the length of this string, ignoring spaces.
--You don't have to type the spaces in Pictionary.
local function spacelessLen(str)
	local ans = 0
	for i=1,#str do
		if str:sub(i,i)~=" " then
			ans = ans + 1
		end
	end
	return ans
end

--reads the word to be guessed from RAM, returned as an ASCII string
--Uses readbyterange, which is actually kind of annoying! Mostly because Lua.
--Also note that Pictionary pads all words to 16 chars, and this function leaves those spaces in.
--All the code here ingores spaces anyway, so there's no point in trimming anything.
local function readWord()
	local word = memory.readbyterange(0x0448, 16)
	local ret  = ""
	for i=1,#word do
		local c = word:sub(i,i):byte() --ith character, as a byte.
		if c == 0x28 then --space
			ret = ret.." "
		elseif c>=0x0A and c<= 0x23 then --it's a letter
			ret = ret..string.char(c-0x0A+65) --convert byte from Pictionary encoding to ASCII, then concatenate
		else
			ret = ret.."." --dot for unknown characters, just like the hex editor
		end
	end
	return ret
end

--remove spaces and prepend an N.
--The cursor always starts at N.
local function preprocess(word)
	local ans = "N"
	for i=1,#word do
		if word:sub(i,i) ~= ' ' then
			ans = ans..word:sub(i,i)
		end
	end
	return ans
end

--ldist and rdist return the distance from one letter to another in the given word,
--for traveling left and right in the alphabet, respectively.
local function ldist(word,i,j)
	i = word:sub(i,i):byte()
	j = word:sub(j,j):byte()
	if j<i then
		return i-j
	else
		return i+32-j
	end
end

local function rdist(word,i,j)
	i = word:sub(i,i):byte()
	j = word:sub(j,j):byte()
	if i<j then
		return j-i
	else
		return j+32-i
	end
end

--[[
	New & Improved.
	It runs a simple DP to find the fastest possible input sequence.
	I made a few simplifications to make this work; this algorithm assumes the shoes behave as follows:
	  - Accelerate instantly from the start
	  - Take exactly 4 frames between each letter
	  - Take exactly 17 frames to turn around and reach the previous letter, at full speed
	     (a "penalty" of 13 frames)
	  
	With these simplifications, we can easily have a state of N x 2: Which letter we're on and which direction we're travelling.
	
	Here are some nuances this algorithm does not account for:
	  - The shoes can only stop on even letters.
	     Sometimes you have to stop early and tap right for 2 frames to get where you want to go before turning around.
		 This is about 10 frames slower.
	  - You need to slow down to type a double letter.
	     You have a 2-frame window to type each letter, so you have to slow down slightly to get at least a 3-frame window.
		 Letting go of L or R for one frame usually does the trick.
		 
	It's not perfect, but it's extremely close. I think its results are worth considering for a TAS.
]]
local function heuristic2(word)
	
	word = preprocess(word)
	--emu.print("running heuristic2 on "..word)
	local dp = {}
	for i=1,#word do
		dp[i] = {} --[i][0] is left, [i][1] is right
		dp[i][0] = 123456789
		dp[i][1] = 123456789
	end
	dp[1][0] = 0
	dp[1][1] = 0
	
	for i=1,#word-1 do
		dp[i+1][0] = math.min(dp[i+1][0],
					 math.min(dp[i][0]+4*ldist(word,i,i+1),
						      dp[i][1]+4*ldist(word,i,i+1)+13))
		dp[i+1][1] = math.min(dp[i+1][1],
					 math.min(dp[i][1]+4*rdist(word,i,i+1),
						      dp[i][0]+4*rdist(word,i,i+1)+13))
	end
	
	return math.min(dp[#word][0], dp[#word][1])
	
end

local function post_frame()
	
	if not inited then init() end
	
	if emu.framecount() - start_frame == test_frame then
		emu.print("Testing frame "..emu.framecount().."...")
		testing = true
		joypad.set(1,{start=true})
		return
	end
	
	if not testing then return end
	
	--I determine wait time based on how many lags have started and ended.
	--By the time we reach 5, the board has reappeared after "not even guessing."
	--I do this to account for the frame rule.
	if freeFrame==0 and not lagCheck and emu.lagged() then
		lagCheck = true
		lagsChecked = lagsChecked + 1
	end
	
	if freeFrame==0 and lagCheck and not emu.lagged() then
		lagCheck = false
		if lagsChecked == 5 then
			--emu.print("Escaped lag at frame "..emu.framecount())
			freeFrame = emu.framecount()
		end
	end
	
	--mash the FUCK out of the start button!
	--Lets us skip minigames and give up on guesses.
	if emu.framecount() % 2 == 0 then
		joypad.set(1,{start=true})
	end
	
	local word = readWord() --read word every frame, then do stuff if it changed.
	
	if word ~= prev then
		local h = heuristic2(word) --FIXME: take frame rules into account. round up to nearest multiple of 128?
		typeTime = typeTime + h
		emu.print(string.format("%s\t(%d)",word,h))
		totalLen = totalLen + spacelessLen(word)
		index = index + 1
		if index==6 then --TODO: make 6 into a parameter, to find more words for RTA runners
			test_frame = test_frame + 1
			inited = false
			local waitTime = freeFrame-1182 --1182 is when the board reappears on a frame 479 test
			local total = waitTime + typeTime
			emu.print(totalLen.." characters")
			emu.print(typeTime.." frames to type + "..waitTime.." frames of waiting = "..total)
			if total < best then
				emu.print("!!BEST SO FAR!!")
				best = total
			elseif total > worst then
				emu.print("...WORST SO FAR...")
				worst = total
			end
			emu.print("________________________")
		end
	end
	
	prev = word
	
end
emu.registerafter(post_frame)