News: 11 March 2016 - Forum Rules
Current Moderators - DarkSol, KingMike, MathOnNapkins, Azkadellia, Danke

Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Messages - Disnesquick

Pages: [1] 2
1
Programming / Re: Dumbest Atlas question to date
« on: September 19, 2013, 06:17:16 pm »
I've always hated the dollar sign for hex

2
Programming / Re: Mega Man X3 Sound Effects
« on: August 12, 2013, 01:59:46 pm »
You're only looking at one side of the coin. At some point the 65816 program will send an SPC-700 program into the co-processor. "Co-processor" is the importnat term here because the sound chip on the SNES is a fully functioning processor, which is similar, but not identical, to a 6502. $2140-3 simply map to $f4-f7 inside the SPC700 address space so it could be doing anything. Most likely it has a bunch of SFXs loaded up inside the memory space of the APU and its polling the ports to see if and when it should play a sound.

http://emureview.ztnet.com/developerscorner/SoundCPU/spc.htm is a helpful start.

Best bet is to hit a trace on the SPC itself.

3
Programming / Re: How would you handle SRAM?
« on: July 24, 2013, 10:35:59 am »
With SRAM, you're usually copying a block from RAM into SRAM or vice-versa so keeping it together for one save slot allows you to do a fast/simple copy.

Unless you want to continuously update the SRAM as you play but this seems like begging for trouble...

4
Programming / Re: How would you handle SRAM?
« on: July 24, 2013, 10:22:53 am »
What was the trouble with a 2 byte sum...?

Code: [Select]
LDY #(SIZE-1)
LDA #0
STA BYTE2
CLC
LOOP:
ADC (BASE),Y
BCC SKIP
INC BYTE2
CLC
SKIP:
DEY
BPL LOOP

5
Programming / Re: SNES Assembly: #$ vs # vs $
« on: July 23, 2013, 05:59:09 am »
I had never heard of this strange naming until yesterday. Doing some diggin, it seems to originate from either a confusion with, or simplification of, the old typesetter pound sign "℔". I quite like the name "Octothorp" though for this symbol.
But yea, for all all of us Euro-folk pound is £. What would you guys call this one in your ambiguous-symbol-naming world?

6
1. Yeah it doesn't have much impact on speed in this case. In my C implementation from years back I used a Radix tree to handle the map so this had a much greater impact.
2. It's not particularly tricky. Any existing accepted candidate that is completely contained within the current considered candidate will remove (len(accept) - dictCost) * freq(consider) from the considered benefit. Any existing accepted cadidate that completely contains the considered candidate will remove (len(consider)-dictCost)*freq(accept) from the benefit. You then need a way to count the number of partial overlaps. this can be done in a number of ways and basically will be the single largest speed hog. There are ways to do this very fast if you're using Radix trees though. If a candidate has its benefit adjusted then it is not accept but stuck back in the heap. You can speed this bit up too by using lazy heap structures but its not a huge drain.


7
Gaming Discussion / Re: Your #1 RPG you ever played?
« on: July 22, 2013, 08:53:22 pm »
Top 3 in order. I should point out that all the 16bit classics never made it over here and I only ended up playing them on emulators...

Exile: That game blew my mind back in the BBC micro days. Back in the day, Phoebos seemed endless. The Amiga version was also a fantastic upgrade. AGA sucked though...
LoZ: Another mind-blowing game. I couldn't believe that there was a whole second game in there after beating it the first time around. The SNES one is probably objectively the best LoZ but it didn't have the sheer novelty factor of the original.
Ultima 7: Although I'm a huge fan of 8, I admit that it wasn't terribly good. I also really like worlds of Ultima and Ultima Underworld but it would take a crazed lunatic not to admit that Ultima 7 is the best PCRPG ever made. It's Just That Good.

8
Programming / Re: SNES Assembly: #$ vs # vs $
« on: July 22, 2013, 06:13:07 pm »
Why do all yinz carpetbaggers call the #/hash symbol a "pound"?

9
Yes, you're describing a standard dictionary compression algorithm.

My code looks for all unique strings (currently of unbounded length but in practice there are very few above 15) in a block of text, building length N+1 from the list of strings of length N. As it goes, it counts the number of occurrences and thereby calculates the byte saving per string, were it to be replaced by a dictionary reference.

Then the dictionary is built: A heap is used to order the strings by their byte saving. First, each string is checked to see if it overlaps with an existing (accepted) string. if so, then the savings must be recalculated and the string is pushed back to the heap, otherwise it is accepted. Code makes sure that a string is never  checked twice against an already-seen accepted word.

The saving of this approach is that you don't rebuild the hash every word.

The code doesn't handle encoding but once you have the dictionary, that is completely trivial using a rolling hash or some-such. Yes, once encoded it will be completely equivalent to your (and all other) dictionary implementations.

I tightened the code up a bit more:

Code: [Select]
import heapq


def stripUnique(stripDict):
newDict = {}
for key, val in stripDict.items():
if val[0] > 1:
newDict[key] = val
return newDict

def countOverlap(posList1, len1, posList2, len2):
count1 = 0
count2 = 0
iter1 = iter(posList1)
iter2 = iter(posList2)
len1 -= 1
len2 -= 1
try:
l1 = next(iter1)
l2 = next(iter2)
r1 = l1+len1
r2 = l2+len2

if l2 < l1:
while r2 < l1:
l2 = next(iter2)
r2 = l2 + len2
if l1 > l2:
count2+=1
l1 = next(iter1)
r1 = l1 + len1
while True:
while r1 < l2:
l1 = next(iter1)
r1 = l1 + len1
if l2 > l1:
count1+=1
l2 = next(iter2)
r2 = l2 + len2
while r2 < l1:
l2 = next(iter2)
r2 = l2 + len2
if l1 > l2:
count2+=1
l1 = next(iter1)
r1 = l1 + len1
except StopIteration:
pass
return count1,count2

#text blocks within text should be null terminated!
# "block1\0block2\0endofblocks\0"
def dictionaryScan(text, dictCost=1, dictionarySize=128, recursive = True):
if text[len(text)-1] != "\0":
text = text + "\0"
buildDict = [None]*(dictCost+1)
priority = []
totalBenefit=0
textLen = len(text)
#Initialize the dictionary
nextDict = {}
for char,pos in zip(text,range(textLen)):
if not char in nextDict:
nextDict[char] = (0,[])
count,curList = nextDict[char]
curList.append(pos)
nextDict[char] = count+1,curList


curDict = stripUnique(nextDict)
curLength = 1
fullDict = {}
while curDict != {}:
print(curLength, len(curDict))
curLength += 1
nextDict = {}
for count, posList in curDict.values():
for pos in posList:
nextPos = pos + curLength
if text[nextPos-1]=="\0":
break
newStr = text[pos:nextPos]
if not newStr in nextDict:
nextDict[newStr] = count, curList = (0,[])
else:
count, curList = nextDict[newStr]
curList.append(pos)
nextDict[newStr] = count+1, curList

curDict = stripUnique(nextDict)
if curLength <= dictCost:
continue
buildDict.append(curDict)

for testStr, val in curDict.items():
benefit = (val[0]-1)*(curLength-dictCost)
heapq.heappush(priority, (-benefit, val[0], 0, testStr))
outputList = []
foundCount = 0
touched = {}

while len(outputList) < dictionarySize and priority != []:
benefit, count, overlapCount, candidate = heapq.heappop(priority)

# Check whether an fragment overlaps with a found candidate
candLen = len(candidate)
candList = buildDict[candLen][candidate][1]
benefitChange = 0
for foundCount, found in outputList[overlapCount:]:
foundLen = len(found)
foundList = buildDict[foundLen][found][1]
flag = 0
if candidate in found:
if recursive:
benefitChange += (foundCount - 1) * (len(candidate)-dictCost)
else:
benefitChange += foundCount * (len(candidate)-dictCost)
elif found in candidate:
if recursive:
benefitChange += (count - 1) * (len(found)-dictCost)
else:
benefitChange += count * (len(found)-dictCost)
else:
for i in range(1,candLen):
frag = candidate[:i]
fragLen = len(frag)
if frag == found[-fragLen:]:
flag = 1
break
for i in range(1,candLen):
frag = candidate[-i:]
fragLen = len(frag)
if frag == found[:i]:
flag = 1
break
if flag == 1:
c1, c2 = countOverlap(foundList, foundLen, candList, candLen)
benefitChange += c1*(len(candidate)-dictCost)
benefitChange += c2*(len(found)-dictCost)

if benefitChange > 0 and benefit+benefitChange < 0:
heapq.heappush(priority, (benefit+benefitChange, count, len(outputList), candidate))
elif benefitChange == 0:
outputList.append((count,candidate))
print(str(len(outputList))+": '''"+candidate+"''' saves "+str(-benefit))
totalBenefit -=benefit
print("Total savings of %d"%totalBenefit)
return outputList

What my code (and yours too) can't handle is when a dictionary entry overlaps with itself: E.g. dictionary compression of the string "hello hello bello  bello mellow yellow fellow" would give false heuristics on the byte saving per entry.

10
As before, hashes are your friends.

Quite a rough implementation here and (because I hate Java) its in python but hopefully it will give you some pointers:

Code: [Select]
import heapq


def stripUnique(stripDict):
newDict = {}
for key, val in stripDict.items():
if val[0] > 1:
newDict[key] = val
return newDict

def countOverlap(posList1, len1, posList2, len2):
count = 0
iter1 = iter(posList1)
iter2 = iter(posList2)
len1 -= 1
len2 -= 1
try:
l1 = next(iter1)
l2 = next(iter2)
r1 = l1+len1
r2 = l2+len2
while True:
while r1 < l2:
l1 = next(iter1)
r1 = l1 + len1
while r2 < l1:
l2 = next(iter2)
r2 = l2 + len2
if l2 > l1 and l2 <= r1:
count+=r1-l2+1
l2 = next(iter2)
r2 = l2 + len2
if l1 > l2 and l1 <= r2:
count+=r2-l1+1
l1 = next(iter1)
r1 = l1 + len1
except StopIteration:
pass
return count

#text blocks within text should be null terminated!
# "block1\0block2\0endofblocks\0"
def dictionaryScan(text, dictCost=1, dictionarySize=128, recursive = True):
if text[len(text)-1] != "\0":
text = text + "\0"
buildDict = [None]*(dictCost+1)
priority = []
totalBenefit=0
textLen = len(text)
#Initialize the dictionary
nextDict = {}
for char,pos in zip(text,range(textLen)):
if not char in nextDict:
nextDict[char] = (0,[])
count,curList = nextDict[char]
curList.append(pos)
nextDict[char] = count+1,curList


curDict = stripUnique(nextDict)
curLength = 1
fullDict = {}
while curDict != {}:
print(curLength, len(curDict))
curLength += 1
nextDict = {}
for count, posList in curDict.values():
for pos in posList:
nextPos = pos + curLength
if text[nextPos-1]=="\0":
break
newStr = text[pos:nextPos]
if not newStr in nextDict:
nextDict[newStr] = count, curList = (0,[])
else:
count, curList = nextDict[newStr]
curList.append(pos)
nextDict[newStr] = count+1, curList

curDict = stripUnique(nextDict)
if curLength <= dictCost:
continue
buildDict.append(curDict)

for testStr, val in curDict.items():
benefit = (val[0]-1)*(curLength-dictCost)
heapq.heappush(priority, (-benefit, val[0], 0, testStr))
outputList = []
foundCount = 0
touched = {}

while len(outputList) < dictionarySize and priority != []:
benefit, count, overlapCount, candidate = heapq.heappop(priority)
if benefit >= 0:
continue
# Check whether an fragment overlaps with a found candidate
candLen = len(candidate)
candList = buildDict[candLen][candidate][1]
benefitChange = 0
for foundCount, found in outputList[overlapCount:]:
foundLen = len(found)
foundList = buildDict[foundLen][found][1]
flag = 0
if candidate in found:
if recursive:
benefitChange += count * (len(candidate)-dictCost)
else:
benefitChange += count * len(candidate)
elif found in candidate:
if recursive:
benefitChange += count * (len(found)-dictCost)
else:
benefitChange += count * len(found)
else:
for i in range(1,candLen):
frag = candidate[:i]
fragLen = len(frag)
if frag == found[-fragLen:]:
flag = 1
frag = candidate[-i:]
fragLen = len(frag)
if frag == found[:i]:
flag = 1
if flag == 1:
benefitChange += countOverlap(foundList, foundLen, candList, candLen)

if benefitChange > 0:
heapq.heappush(priority, (benefit+benefitChange, count, len(outputList), candidate))
else:
outputList.append((count,candidate))
print(str(len(outputList))+": '''"+candidate+"''' saves "+str(-benefit))
totalBenefit -=benefit
print("Total savings of %d"%totalBenefit)
return outputList

It builds a dictionary for "Bleak House" (2Mb of text ) in three minutes on my machine. I haven't had chance to compare your code to compare though but there are numerous ways to speed up the above algorithm (centred around how it handles pushing candidates on the "this candidate overlaps an accepted dictionary entry" heap)

11
Quite a small point but you seem to be using a quadratic-time algorithm for LZ-variant encoding. Rather than searching through all possible sliding windows, it's faster to create a map that binds two-byte values to their location. At each position you can then check the map on the current two-byte value and get a list of all window seeds then extend them. You can cull the list as values fall off the end of the sliding window.

12
News Submissions / Re: Translations: Energy Breaker English V1.00
« on: November 29, 2012, 09:11:03 am »
The game is actually pretty easy IMHO. If you're having toruble in fights then the best bet is to play tactically and hit them from behind. Mummies cast poison drop on you, which, after two hits, will reduce your damage down to 1. Focus on mummies first before they have a chance to get you with their stat-dropping evil.

13
Ever consider just writing your code directly to the rom via a hex editor?  Works for me.

Never, ever do this.

You will end up screwing your future self HARD.

14
News Submissions / Re: Translations: Energy Breaker English V1.00
« on: October 09, 2012, 07:10:25 am »
Found  your hidden text, nice retrospective.

 ;D

I'm glad our little egg didn't go unseen!

15
Programming / Re: What causes this in games?
« on: October 08, 2012, 12:08:44 pm »
Yup, these missing lines make a bit more sense. I guess the FF stuff is just them making completely sure that the scroll registers went off-screen to show blank space for those scanlines. Or possibly something weird

Code: [Select]

6F 00 00      112 "normal" lines
0C 04 00      12-pixel high character line
0C 08 00      12-pixel high character line
0C 0C 00      12-pixel high character line
0C 10 00      12-pixel high character line
10 60 FF      16 WTF lines
0C 04 00      12-pixel high character line
0C 08 00      12-pixel high character line
10 38 FF      16 WTF lines
10 28 FF      16 WTF lines
00            Finish HDMA

16
News Submissions / Re: Translations: Energy Breaker English V1.00
« on: October 08, 2012, 12:02:50 pm »
I thought I had fixed that left conversation menu thing :(

I am gearing up for a final 1.1 release in about a month's time (given this project and delays that probably means 2022), taking care of all the reported bugs that are still in there. After the major stuff was done I didn't want to keep overloading RHDN staff with new releases every night, and I really needed a break from EB hacking.

I am in complete agreement that the game is too easy. I would like to take a stab at a hardtype version. For the moment I can only suggest going through the game without any scrolls. I guarantee that you will not have an easy time.

17
News Submissions / Re: Translations: Energy Breaker English V1.00
« on: October 01, 2012, 05:27:08 am »
There seems to be an issue with using the Reincarnation when its in the item box. I've never had issues with using it outside of one though.

Some people report that this disappears when you've started a new game with 1.02 but I haven't tested that yet.

You don't need to hold onto Grimoires once they have been looked at and should sell them for some filthy lucre.

18
News Submissions / Re: Translations: Energy Breaker English V1.00
« on: September 27, 2012, 04:58:07 pm »


AWESOME!!!!!!


but yeah, this is fixed in 1.02

19
News Submissions / Re: Translations: Energy Breaker English V1.00
« on: September 27, 2012, 12:10:56 pm »


Irony is that I just fixed this last night having found it myself  :thumbsup:
I think all the "critical" bugs are now dead. I'll be rolling all of these non-critical bugs into a 1.1 release in a couple of weeks. I think the RHDN staff are getting tired of my daily bug-fixes.

20
News Submissions / Re: Translations: Energy Breaker English V1.00
« on: September 25, 2012, 07:42:39 pm »
1.01 is released. This corrects all known issues including the Lenardo memory glitch. It should be regarded as a critical update so download it ASAP. Don't continue on with older patches as you may get your IRL memory scrambled.

Pages: [1] 2