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

Author Topic: Castlevania II (Simon's Quest) - Multilingual enhancement  (Read 417980 times)

BRPXQZME

  • Hero Member
  • *****
  • Posts: 4572
  • じー
    • View Profile
    • The BRPXQZME Network
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #740 on: November 29, 2013, 10:58:19 am »
Attempting to cram the "i" and "j" into the same 8x8 box would be rather inconvenient in this typeface, I believe.
I tried it out. It didn’t look too crammed with the proper adjustments (thinner dots, thinner tail on the j). On the other hand, it accentuates the lowered x-height in those letters too greatly. Oh well, it was worth a shot.

(the t could be a pixel wider; I wouldn’t worry about it, though)

(Hah, I wonder what this would look like in Fraktur!)
Kind of fun to write... an absolute horror to fit into a low-res bitmap :)
we are in a horrible and deadly danger

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #741 on: November 29, 2013, 11:48:11 am »
[Fraktur] Kind of fun to write... an absolute horror to fit into a low-res bitmap :)

Yeah, I don't think I have ever seen a NES game that uses it.

EDIT: Speaking of Dutch having that "ij" occurring very often, Finnish has some rather pale letter pairs that occur fairly often too.


First image: 1× "ji", 1× "li"
Second image: 1× "ii", 1× "lli"
Third image: 5× "ll", 1× "li"
Fourth image: 1× "ij"
Fifth image: 1× "lli"
And this is only the first town.

Here's what they would look like if I created those special glyphs for "lli", "ll", "ij" and "li" (which I did for a test).

In picture #3, I also made the "t" letter one pixel wider as suggested. Now it sticks out... and not in a good way. Now, regarding the combination glyphs:
"li": Too cramped in the first image; distracts. It works in the third image though, because it has the same spacing as the "ll" that comes thereafter.
"ll": Can be confused with "n" in some contexts (for example, "kuolleella" (at the dead) -> "kuolleena" (who is dead at)).
"ij": Way too cramped. And considering that the syllable break goes in between those two letters (si-jait-see)... It is difficult to read.
"lli": This one does not look too bad, but the difference in spacing between the beginning of the word "kristallin" (where "i" is sparse) and the end thereof (that is dense) is rather distracting.

EDIT: By the way, this would be possible to do in the VRAM version (at least for regular dialog & clues). Variable Width Font!


Kerning was not implemented. This one is just a simulation, I did not write it as a ROM. But assuming there'd be enough RAM, the math checks out. This reduced-size dialog box requires 13*4 = 52 VRAM tiles, which is less than the number of tiles currently dedicated for dialog text (~58).
VWF would enable making even more dialog text into the game! Using longer lines and more lines, which could be a boon for some particularly wordy translations. Of course, a translation that takes advantage of such features would only work on VRAM boards; a VROM board would require different translations.

While my patch does support VRAM boards, the primary reason I do not recommend it is because the map feature on the VRAM version looks like crap (and because it does not offer any extra functionality that the VROM version does not).

There is a gimmick that would make it possible to double the number of lines in that VWF dialog box. It however depends on having two dedicated background palettes for text only, which there is not.
« Last Edit: November 29, 2013, 06:36:48 pm by Bisqwit »

Vanya

  • Hero Member
  • *****
  • Posts: 1489
    • View Profile
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #742 on: November 29, 2013, 06:36:00 pm »
Ooh! The first thing I thought of when the discussion started about those letter combinations was VWF. If it's doable and  not too much trouble I say add it in! VWF is always a welcome addition to any game that doesn't have it.

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #743 on: November 29, 2013, 06:40:17 pm »
Ooh! The first thing I thought of when the discussion started about those letter combinations was VWF. If it's doable and  not too much trouble I say add it in! VWF is always a welcome addition to any game that doesn't have it.

Well, it would be nothing short of trouble. I'm just saying it would be doable. With tradeoffs: Shorter dialog box, necessitating scrolling to see all text; require VRAM board (UOROM, SNROM, TNROM or TGROM); no highquality map graphics; and a translation that takes advantage of the VWF features would be incompatible with VROM versions.

About the map:

The map graphics is automatically generated, down to every tile and palette entry, from these two source images below, that have been produced in Gimp. The colors for these images have been manually chosen to guide the ditherer towards a particular outcome.
and
The automatic process first selects the optimal palettes and dithers down the image using sprite overlays; then reduces the number of tiles by merging near-identical tiles in each slice of the picture until it reaches the proper limit for that slice. In the end, it generates the following two pictures; one for VROM (978 tiles in 4 slices), one for VRAM (477 tiles in 2 slices). The dithering algorithm was carefully chosen so that it will not produce disturbing diagonal flashing patterns on NTSC televisions.

The upper part of the picture shows the map with sprite overlays; the lower part shows the background graphics only.
Would someone like to contribute a version of the map (the first picture) that requires fewer unique 8x8 tiles to represent, for the VRAM version? It could be artistically completely redesigned as long as all the attractions are in the same spots on the map.
« Last Edit: November 29, 2013, 07:27:55 pm by Bisqwit »

Vanya

  • Hero Member
  • *****
  • Posts: 1489
    • View Profile
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #744 on: November 30, 2013, 06:44:24 pm »
Well, it would be nothing short of trouble. I'm just saying it would be doable. With tradeoffs: Shorter dialog box, necessitating scrolling to see all text; require VRAM board (UOROM, SNROM, TNROM or TGROM); no highquality map graphics; and a translation that takes advantage of the VWF features would be incompatible with VROM versions.

Well... that sort of defeats the purpose of having VWF in the first place doesn't it?

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #745 on: November 30, 2013, 08:46:58 pm »
Well... that sort of defeats the purpose of having VWF in the first place doesn't it?

How do you figure?

BRPXQZME

  • Hero Member
  • *****
  • Posts: 4572
  • じー
    • View Profile
    • The BRPXQZME Network
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #746 on: November 30, 2013, 09:31:28 pm »
Have you considered using a genetic algorithm to find a tileset? I can’t guarantee it’d be the right answer here, but they tend to be pretty good at finding non-intuitive approximations of things. Well, that and soaking up CPU cycles.
we are in a horrible and deadly danger

Vanya

  • Hero Member
  • *****
  • Posts: 1489
    • View Profile
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #747 on: December 01, 2013, 08:00:49 pm »
How do you figure?

Isn't part of the point to have more room for text too? And the gaps aren't that bad really. I dunno. If nothing else it seems like a lot of work for relatively little gain. And you yourself mentioned it could cause problems if any translation is made with VWF in mind.

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #748 on: December 01, 2013, 08:15:02 pm »
Isn't part of the point to have more room for text too? And the gaps aren't that bad really. I dunno. If nothing else it seems like a lot of work for relatively little gain. And you yourself mentioned it could cause problems if any translation is made with VWF in mind.
I think you misread my post and mixed up VRAM & VROM.
VRAM is the version that could support VWF. (And that has crappy map.)
VROM is the one that can not do VWF. Majority of boards that can run Simon's Quest are VROM type. It is the currently recommended type, too.

If the script is changed to take advantage of the liberties possible with VWF, it would only work when VWF is available (i.e. VRAM boards), and not work when VWF is not available (i.e. VROM boards); necessitating either doing away with VROM support, or maintaining two sets of scripts: one that takes advantage of the VWF-granted liberties, and one that does not. In other words, the VRAM version could have beefy script, and the VROM version would either be terminated, or have standard script.
The reason I mentioned this is because some languages may be so wordy that VWF may end up being necessary. The languages that depend on VWF would then not work on VROM boards; they would only work on VRAM boards.

Quote from: BRPXQZME
genetic algorithm to find a tileset [...] and soaking up CPU cycles
The current method indeed requires quite a lot of CPU time. Part of the code:
Code: [Select]
    // Sort the bitmaps in order of commonness
    asort($bitmaps);
    // Find two most similar bitmaps, and merge them
    $bestl = 99999;
    $besta = 0; $bestb = 0;
    foreach($bitmaps as $as=>$a)
      foreach($bitmaps as $bs=>$b)
      {
        //if($as == $bs) continue;
        if($b < $a || $as == $bs) continue;
        $l = &$diffs[$as][$bs];
        if(!isset($l))
          $l = td($as,$bs);
        if($l < $bestl)
          { $besta = $as; $bestb = $bs; $bestl = $l; }
        unset($l);
      }
Code: [Select]
function td($a, $b)
{
  $r = 0;
  for($c=0; $c<64; ++$c)
    if($a[$c] != $b[$c])
      ++$r;
  return $r;
}
I can't think of a genetic algorithm that would work for this purpose. Definitely not one of my strengths.
« Last Edit: December 01, 2013, 10:00:02 pm by Bisqwit »

BRPXQZME

  • Hero Member
  • *****
  • Posts: 4572
  • じー
    • View Profile
    • The BRPXQZME Network
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #749 on: December 02, 2013, 12:36:36 am »
Hm, you could certainly make some adjustments to this algorithm as-is (e.g. prioritize black over green/yellow/brown details, use something more sophisticated than pixel-per-pixel equality for image similarity, synthesize a new tile that tries to fill in for the tiles to eliminate...). I was trying to think how this might be improved into a more effective greedy search, but while it seems like it should be possible, I couldn’t come up with anything that wasn’t basically the same as this.

For a genetic algorithm, I would (at least the first time trying this) make each individual a tile set, the fitness function a similarity measure (such as the histogram method described here) for the closest image you can construct out of that tile set, and the mutation... well, that would be tough part, since it depends on representation. Assuming any pixel can be any color, you can always represent tilesets as a large vector of floating-point numbers and round them to get the color values.

If it sounds like I have no idea how well this would work or how fast it would run, or even if it’s a reasonable choice given what else is out there, it’s because I don’t :)

To my knowledge, this has never been done before for exactly the task of constructing an image out of tiles, but it has done a pretty good job on comparable graphics tasks before (e.g. finding wavelet- or fractal-based approximations of images). Maybe I should ask my AI professor what he’d use, but GAs and related topics are kind of his strong point....

This is not super hard, but it’s not trivial, either. The good news is that expected runtime is fairly predictable. Most of the time by far will be spent in the fitness evaluation, and from there you can get a pretty good estimate of how long a run will take (population size * generations * average fitness evaluation time). With a GA it is crucial to tune parameters such as crossover/mutation probability to get as close to the best possible as possible; if you’re feeling frisky, you can always use a GA to find decent parameters for a different GA. Also, the “one-fifth rule” is a decent rule of thumb for autotuning mutation variance.

The main reason I’m not setting this all up for you myself is because I need a bit more experience handling graphics programmatically before attempting this, and I’m not going to get that experience during the last week of classes + finals. I’d be glad to help you out if you’re interested in doing this yourself, though.

EDIT:
I asked said professor, and his hunches were about the same. One thing I didn’t mention that decision trees might be helpful somehow; I couldn’t think of a way to make it possible, though.

One possible adjustment I have thought up (that is a lot simpler!) is that you may wish to experiment with the standard of choosing which tiles to eliminate. Rather than finding the two most similar tiles out of the tile set, you might want to try some other evaluation of how “useful” a given tile is (maybe something involving the tile’s entropy and frequency of occurrence?). Bonus: finding the similar tile to merge it into becomes O(n).

Lurching back into the realms of the not-so-sane methods, I don’t know exactly what you do to “merge” tiles, but it might be feasible to graphically merge them on them some level (plain old blending? moving pixels around?) and try reevaluating their placement on the final image.

I have also entertained the notion in my head that it might be fruitful to attempt some sort of greedy search on pixels in a tile set (akin to the min-conflicts algorithm) that gets re-evaluated at each step instead of on tiles in the tile set (not sure whether you have them stay in fixed positions here, though that would make sense for what you already have). I suspect it would get caught in local optima quite a bit, though.
« Last Edit: December 06, 2013, 09:46:26 am by BRPXQZME »
we are in a horrible and deadly danger

Chpexo

  • Hero Member
  • *****
  • Posts: 731
    • View Profile
.
« Reply #750 on: December 18, 2013, 12:21:29 am »
.
« Last Edit: January 01, 2016, 10:25:27 am by Chpexo »

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #751 on: December 18, 2013, 09:00:24 am »
Thanks, but help with implementing VWF is not what I think I need at this point. I have done it before.

But if someone could replace this map -- http://bisqwit.iki.fi/cv2fin/dev/cv2map2_thu.png -- with something that is closer to tile-based graphics, with at most ~400 distinct tiles, that would help the CHR-RAM version a great deal.

Vanya

  • Hero Member
  • *****
  • Posts: 1489
    • View Profile
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #752 on: December 18, 2013, 04:42:26 pm »
I'll give it a shot.

BRPXQZME

  • Hero Member
  • *****
  • Posts: 4572
  • じー
    • View Profile
    • The BRPXQZME Network
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #753 on: December 29, 2013, 12:29:35 am »
I’ve resized the edges to coincide with 8x8 tile boundaries more closely. Things shouldn’t be moved more than a few pixels, only a little detail is lost, and I hope this buys enough tiles before I start trying anything algorithmic.
we are in a horrible and deadly danger

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #754 on: December 29, 2013, 08:51:17 am »
I’ve resized the edges to coincide with 8x8 tile boundaries more closely. Things shouldn’t be moved more than a few pixels, only a little detail is lost, and I hope this buys enough tiles before I start trying anything algorithmic.

Just the edges of the image? I have actually done that. The image is shifted 50 pixels down and 2 pixels right before processing. It is not nearly enough.
What would help is if all the mountains in the picture were aligned in a 8x8 grid and used identical tiles; forests had a repeating 16x16 pattern, etc.
« Last Edit: December 29, 2013, 08:58:07 am by Bisqwit »

BRPXQZME

  • Hero Member
  • *****
  • Posts: 4572
  • じー
    • View Profile
    • The BRPXQZME Network
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #755 on: December 29, 2013, 03:41:06 pm »
Perhaps my changes have been too subtle.

In the original image, the edges have not been shored up to quite the extent I have done here—if you check the results with a grid, you’ll see that a lot of tiles are used for part-border, part-map portions of the image along the left, right, and bottom. It certainly looks more natural, but it’s a waste with the limited tile budget. The edges in this one stay very carefully inside 8x8 tiles, and shouldn’t bleed over into the contents of the map too much (I did leave a stray pixel in the upper left by mistake), which are now inside an 8x8-aligned grid.

I’m sure this won’t solve anything (certainly not to the extent that homogenizing or eliminating the borders would do), but I’m a programmer, too... gotta profile before optimizing further :woot!:
« Last Edit: December 29, 2013, 04:32:01 pm by BRPXQZME »
we are in a horrible and deadly danger

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #756 on: December 29, 2013, 04:32:05 pm »
Perhaps my changes have been too subtle.

In the original image, the edges have not been shored up to quite the extent I have done here—if you check the results with a grid, you’ll see that a lot of tiles are used for part-border, part-map portions of the image along the left, right, and bottom. It certainly looks more natural, but it’s a waste with the limited tile budget. The edges in this one stay very carefully inside 8x8 tiles, and shouldn’t bleed over into the contents of the map too much, which are now inside an 8x8-aligned grid.

Fair enough.
CHR-RAM-version map. Left: Before change. Right: After change.

In the rightside picture, I undid the hardcoded +2 offset both horizontally and vertically, and used the picture you provided.

M-Tee

  • Hero Member
  • *****
  • Posts: 595
  • One pixel at a time…
    • View Profile
    • M-Tee Retro Graphics
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #757 on: December 29, 2013, 09:16:35 pm »
Is the full set of palettes available for this screen ) 4 bground and 4 sprite? Also, are you cool with a map that is done in solid tones instead of with dithers?

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #758 on: December 29, 2013, 10:48:40 pm »
Is the full set of palettes available for this screen ) 4 bground and 4 sprite? Also, are you cool with a map that is done in solid tones instead of with dithers?

Please do not do any dithering, palettes or posterization. My program will do that. It will choose the best palettes to represent the source image and does dithering (lighter dithering for the CHR-RAM version). I just need a source RGB image to work on; one that lends itself to tile'ization better than what we have now. The current picture is fine for the CHR-ROM version because we can do bank-switching several times in the middle of the frame, but because this kind of option is not available for CHR-RAM, it has to do with fewer distinct tiles and this is where it becomes important that the image lends itself to being formed from tiles.
« Last Edit: December 29, 2013, 11:18:47 pm by Bisqwit »

BRPXQZME

  • Hero Member
  • *****
  • Posts: 4572
  • じー
    • View Profile
    • The BRPXQZME Network
Re: Castlevania II (Simon's Quest) - Multilingual enhancement
« Reply #759 on: December 30, 2013, 01:46:37 am »
Thanks for showing what would happen; unfortunately, that’s the one easy edit there is. While some of the detail has come back in, it’d take at least a couple dozen more usable tiles to get passable results (though some of those blobs of nothing can just be replaced with a different tile). This certainly wouldn’t be quick, if it’s even doable. But I’m still doing a little bit to see if I can’t pre-prime a different process entirely... (not one discussed in the wall-o-text above).

Spoiler:
If you look hard enough, you’ll eventually find the handful of mountains and trees that look a little suspicious. Or just overlay it with the previous sample. That works too.
we are in a horrible and deadly danger