Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Align a screenshot to a background

This thread is locked; no one can reply to it. rss feed Print
Align a screenshot to a background
Dario ff
Member #10,065
August 2008
avatar

Maybe you guys can help me wrap my head around this, probably in a way that doesn't kill the CPU every frame. ;)

Say we have a picture of the world map, let's call it Background Map:
{"name":"603082","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/e\/bea3341c2502b6ab6debea19e0c85c1d.png","w":800,"h":300,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/e\/bea3341c2502b6ab6debea19e0c85c1d"}603082

And we have a screenshot of the game:
603085

The screenshot needs to be aligned to the corresponding Background Map, with a 100% pixel precision. I'm currently able to obtain the coordinates of the camera, but it still doesn't map very well. Here's an example result:
{"name":"603084","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/b\/3beba7f86931453a25a8416916b6ac5d.png","w":800,"h":300,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/b\/3beba7f86931453a25a8416916b6ac5d"}603084

The thing is, these alignment problems never go beyond 10-20 pixels or the like. I don't have any control over this, all I need to do is find a way to align the image back to where it should be. So the marked red area means what I would use to search for the possible correct position.

The end result should be something like this, mapping the screenshot to the correct coordinate.
{"name":"603083","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/e\/4e35266b9712bbcd211361f405f12eb5.png","w":800,"h":300,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/e\/4e35266b9712bbcd211361f405f12eb5"}603083

What I can't wrap my head around so far is how could I try to align this? Keep in mind the screenshot's contents could obviously be different from the world map(in this case, there's the Mario sprite there).

I thought about searching from the outer edges and comparing in the search area, but I'm not really sure if that would work for every area. :-[ At least I can reduce the search area drastically by using the camera values. Got any smart ideas on how to do this?

I should clarify that performance isn't very critical, but it shouldn't take 2 seconds to do it. :P

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Matthew Leverton
Supreme Loser
January 1999
avatar

Edge detection is simple to do:

#SelectExpand
1#include <allegro5/allegro.h> 2#include <allegro5/allegro_image.h> 3#include <string.h> 4 5int main() 6{ 7 ALLEGRO_BITMAP *bg, *fg; 8 ALLEGRO_DISPLAY *display; 9 ALLEGRO_LOCKED_REGION *bg_lock, *fg_lock; 10 uint32_t *bg_data, *fg_data; 11 int bg_h, bg_w, bg_x, bg_y; 12 int fg_h, fg_w, fg_y; 13 14 int m_x = -1, m_y = -1; 15 16 al_init(); 17 al_init_image_addon(); 18 19 display = al_create_display(800, 300); 20 21 bg = al_load_bitmap("bg.png"); 22 bg_h = al_get_bitmap_height(bg); 23 bg_w = al_get_bitmap_width(bg); 24 25 fg = al_load_bitmap("fg.png"); 26 fg_h = al_get_bitmap_height(fg); 27 fg_w = al_get_bitmap_width(fg); 28 29 bg_lock = al_lock_bitmap(bg, ALLEGRO_PIXEL_FORMAT_ARGB_8888, ALLEGRO_LOCK_READONLY); 30 fg_lock = al_lock_bitmap(fg, ALLEGRO_PIXEL_FORMAT_ARGB_8888, ALLEGRO_LOCK_READONLY); 31 32 bg_data = bg_lock->data; 33 34 for (bg_y = 0; bg_y <= bg_h - fg_h; bg_y++) 35 { 36 for (bg_x = 0; bg_x <= bg_w - fg_w; bg_x++) 37 { 38 fg_data = fg_lock->data; 39 40 // test top edge 41 if (memcmp(&bg_data[bg_x], fg_data, fg_w)) 42 continue; 43 44 // test bottom edge 45 if (memcmp( 46 (uint8_t*)&bg_data[bg_x] + bg_lock->pitch * (fg_h - 1), 47 (uint8_t*)fg_data + fg_lock->pitch * (fg_h - 1), 48 fg_w)) continue; 49 50 // test left edge 51 for (fg_y = 1; fg_y < fg_h - 1; ++fg_y) 52 { 53 uint32_t *bg_p = (uint32_t *) ((uint8_t*)&bg_data[bg_x] + bg_lock->pitch * fg_y); 54 uint32_t *fg_p = (uint32_t *) ((uint8_t*)fg_data + fg_lock->pitch * fg_y); 55 56 if (*bg_p != *fg_p) break; 57 } 58 if (fg_y < fg_h - 1) continue; 59 60 // test right edge 61 for (fg_y = 1; fg_y < fg_h - 1; ++fg_y) 62 { 63 uint32_t *bg_p = (uint32_t *) ((uint8_t*)&bg_data[bg_x + fg_w - 1] + bg_lock->pitch * fg_y); 64 uint32_t *fg_p = (uint32_t *) ((uint8_t*)&fg_data[fg_w - 1] + fg_lock->pitch * fg_y); 65 66 if (*bg_p != *fg_p) break; 67 } 68 if (fg_y < fg_h - 1) continue; 69 70 71 72 m_x = bg_x; 73 m_y = bg_y; 74 } 75 76 bg_data = (uint32_t*) (((uint8_t*)bg_data) + bg_lock->pitch); 77 } 78 79 al_unlock_bitmap(bg); 80 al_unlock_bitmap(fg); 81 82 if (m_x != -1) 83 { 84 al_draw_bitmap(bg, 0, 0, 0); 85 al_draw_bitmap(fg, m_x, m_y, 0); 86 al_flip_display(); 87 al_rest(5); 88 } 89 90 return 0; 91}

This requires an exact match, down to the RGB values for every edge pixel. Works in this case and is fast enough. To make this more flexible you could replace the direct comparisons with a fuzzy match and allow for x% of failures.

The final match is shown in this case. You could break ties based on strength of match.

I think the above code could be adapted to do a complete square match if you bailed out as soon as there were enough failures (as opposed to always calculating the entire match for every pixel location). Obviously if you were to do a more intelligent approach where you only focused on probable areas based on a general color / pattern match, you could speed things up.

If you always know within 20 pixels or so of where it should go, then I'd just rate each of those 20 locations based on a complete analysis and pick the best.

Dario ff
Member #10,065
August 2008
avatar

Thanks for the answer. I have a more clear idea now.

Still, it seems I need to account for something else now I didn't notice before. The output screenshot from the emulator doesn't have the exact same colors as in the ripped map I got from vgmaps.com. And there isn't a noticeable pattern in the RGB differences for each pixel sadly(like in, -2 in each RGB channel). So I guess I'll have to make direct comparisons per pixel and search if it's in the same range. The differences aren't bigger than 7 in a color channel from what I've noticed.

Your solution did look sexy though. ;)

So I guess I'll start searching from the edges, to the inside. But instead of doing a full square check, I could skip several rows/columns to make it faster, like this:
{"name":"603089","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/4\/8487596f5b85214bbf93803f95af707b.png","w":256,"h":224,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/4\/8487596f5b85214bbf93803f95af707b"}603089

Like you said, I'll need to do a fuzzy check, since it's very likely something else will be in the edge of the screen, like an enemy or an animated object. Probably leave just the best 10 comparisons, and do more precise checks from there, until only 1 of them is the "best".

The user would be able to set the precision of this in a GUI, including a full square check. It's just so it doesn't take an insane amount of time.

  • Just a question, would it be much faster if I stored the RGB values of the pixels I want to compare(the background search area, and the screenshot) in an array of my own, instead of requesting them with al_get_pixel in every check? I'll be using MEMORY_BITMAPs if it helps, since I'm dealing with very large images for the world map.

EDIT: Or I suppose reading the data from the lock like you showed me is enough? I don't know if I should get out the rgb values for doing the check, or is there some other way to detect if the values are similar?

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Matthew Leverton
Supreme Loser
January 1999
avatar

For speed, you should lock the bitmaps as I was doing.

You can get the RGB values by using the uint32_t cast, and doing normal shift operations to get at the values.

Regarding the fuzzy match, I would simply do something like a sum of squared errors for each pixel that you test. Keep track of the best one, and use that. If you know there's a match, then it should always give you the best result.

So something like:

best_sse = infinity
foreach pixel:
  sse += (R1 - R2)^2 + (G1 - G2)^2 + (B1 - B2)^2
  if (sse > best_sse) goto next

best_sse = sse

next:
  move to next spot on the map, restart test

So basically, as soon as the SSE is larger than the best known one, stop testing that area, and move on to the next. I'm guessing that this is adequate for what you need. Using HSV instead of RGB might give better results, but I'd start simple and see how it goes.

Dario ff
Member #10,065
August 2008
avatar

Woot! This seems to be working.

For the sake of knowing what I was writing, I didn't do any optimizations by reading the data directly using the locks. It's not really fast, but I can put more precision using the search_skip int. The current precision is 5, so it'll search in rects like my image above separated by 5 pixels between each other.

#SelectExpand
1#include <allegro5/allegro.h> 2#include <allegro5/allegro_image.h> 3#include <allegro5/allegro_primitives.h> 4#include <string.h> 5 6 7int main() 8{ 9 ALLEGRO_BITMAP *bg, *fg; 10 ALLEGRO_DISPLAY *display; 11 ALLEGRO_LOCKED_REGION *bg_lock, *fg_lock; 12 uint32_t *bg_data, *fg_data; 13 int bg_h, bg_w, bg_x, bg_y; 14 int fg_h, fg_w, fg_x, fg_y; 15 16 int m_x = -1, m_y = -1; 17 18 al_init(); 19 al_init_image_addon(); 20 al_init_primitives_addon(); 21 22 display = al_create_display(800, 600); 23 24 al_set_new_bitmap_flags(ALLEGRO_MEMORY_BITMAP); 25 bg = al_load_bitmap("bg.png"); 26 bg_h = al_get_bitmap_height(bg); 27 bg_w = al_get_bitmap_width(bg); 28 29 fg = al_load_bitmap("fg.png"); 30 fg_h = al_get_bitmap_height(fg); 31 fg_w = al_get_bitmap_width(fg); 32 33 bg_lock = al_lock_bitmap(bg, ALLEGRO_PIXEL_FORMAT_ARGB_8888, ALLEGRO_LOCK_READONLY); 34 fg_lock = al_lock_bitmap(fg, ALLEGRO_PIXEL_FORMAT_ARGB_8888, ALLEGRO_LOCK_READONLY); 35 36 bg_data = (uint32_t *)bg_lock->data; 37 38 int search_skip=5; 39 int search_step=0; 40 41 float best_sse = 999999999; 42 43 44 for (bg_y = 0; bg_y <= bg_h - fg_h; bg_y++) 45 { 46 for (bg_x = 0; bg_x <= bg_w - fg_w; bg_x++) 47 { 48 float sse=0; 49 50 for (search_step=0; ((fg_w/2) > (search_skip*search_step)) && ((fg_h/2) > (search_skip*search_step)); search_step++) 51 { 52 int rx, ry, rfx, rfy, ra; 53 ra = search_skip*search_step; 54 rx = ra+bg_x; 55 ry = ra+bg_y; 56 rfx = rx + (fg_w-(ra*2)); 57 rfy = ry + (fg_h-(ra*2)); 58 59 // Test Top of the rect 60 fg_y = ry; 61 for (fg_x=rx; fg_x<=rfx; fg_x++) 62 { 63 unsigned char R1, G1, B1, R2, G2, B2; 64 ALLEGRO_COLOR c=al_get_pixel(bg, fg_x, fg_y); 65 al_unmap_rgb(c, &R2, &G2, &B2); 66 67 c=al_get_pixel(fg, fg_x-rx+ra, fg_y-ry+ra); 68 al_unmap_rgb(c, &R1, &G1, &B1); 69 70 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 71 } 72 73 // Test Bottom of the rect 74 fg_y = rfx; 75 for (fg_x=rx; fg_x<=rfx; fg_x++) 76 { 77 unsigned char R1, G1, B1, R2, G2, B2; 78 ALLEGRO_COLOR c=al_get_pixel(bg, fg_x, fg_y); 79 al_unmap_rgb(c, &R2, &G2, &B2); 80 81 c=al_get_pixel(fg, fg_x-rx+ra, fg_y-ry+ra); 82 al_unmap_rgb(c, &R1, &G1, &B1); 83 84 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 85 } 86 87 // Test Left of the rect 88 fg_x = rx; 89 for (fg_y=ry; fg_y<=rfy; fg_y++) 90 { 91 unsigned char R1, G1, B1, R2, G2, B2; 92 ALLEGRO_COLOR c=al_get_pixel(bg, fg_x, fg_y); 93 al_unmap_rgb(c, &R2, &G2, &B2); 94 95 c=al_get_pixel(fg, fg_x-rx+ra, fg_y-ry+ra); 96 al_unmap_rgb(c, &R1, &G1, &B1); 97 98 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 99 } 100 101 // Test Right of the rect 102 fg_x = rfx; 103 for (fg_y=ry; fg_y<=rfy; fg_y++) 104 { 105 unsigned char R1, G1, B1, R2, G2, B2; 106 ALLEGRO_COLOR c=al_get_pixel(bg, fg_x, fg_y); 107 al_unmap_rgb(c, &R2, &G2, &B2); 108 109 c=al_get_pixel(fg, fg_x-rx+ra, fg_y-ry+ra); 110 al_unmap_rgb(c, &R1, &G1, &B1); 111 112 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 113 } 114 } 115 116 if (best_sse > sse) 117 { 118 best_sse = sse; 119 m_x = bg_x; m_y = bg_y; 120 } 121 } 122 } 123 124 125 al_unlock_bitmap(bg); 126 al_unlock_bitmap(fg); 127 al_draw_bitmap(bg, 0, 0, 0); 128 al_draw_bitmap(fg, m_x, m_y, 0); 129 130 al_flip_display(); 131 al_rest(4); 132 133 return 0; 134}

And these are the images I used. In the end result, it mapped with a 100% pixel precision, even if the colors are different! :D

The background bitmap(it's a section of the world map, which is near the camera values).
{"name":"603090","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/0\/9007984332707dccd0e454871af45243.png","w":300,"h":260,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/0\/9007984332707dccd0e454871af45243"}603090

And the screenshot picture:
{"name":"603091","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/9\/3986d4616e9aa63022c489ffb112b45e.png","w":256,"h":224,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/9\/3986d4616e9aa63022c489ffb112b45e"}603091

So now off to optimizing it I guess...

EDIT: Here's my optimized version:

#SelectExpand
1#include <allegro5/allegro.h> 2#include <allegro5/allegro_image.h> 3#include <allegro5/allegro_primitives.h> 4#include <string.h> 5#include <stdio.h> 6 7 8int main() 9{ 10 ALLEGRO_BITMAP *bg, *fg; 11 ALLEGRO_DISPLAY *display; 12 ALLEGRO_LOCKED_REGION *bg_lock, *fg_lock; 13 uint32_t *bg_data, *fg_data; 14 int bg_h, bg_w, bg_x, bg_y; 15 int fg_h, fg_w, fg_x, fg_y; 16 17 int m_x = -1, m_y = -1; 18 19 al_init(); 20 al_init_image_addon(); 21 al_init_primitives_addon(); 22 23 display = al_create_display(800, 600); 24 25 al_set_new_bitmap_flags(ALLEGRO_MEMORY_BITMAP); 26 bg = al_load_bitmap("bg.png"); 27 bg_h = al_get_bitmap_height(bg); 28 bg_w = al_get_bitmap_width(bg); 29 30 fg = al_load_bitmap("fg.png"); 31 fg_h = al_get_bitmap_height(fg); 32 fg_w = al_get_bitmap_width(fg); 33 34 bg_lock = al_lock_bitmap(bg, ALLEGRO_PIXEL_FORMAT_ARGB_8888, ALLEGRO_LOCK_READONLY); 35 fg_lock = al_lock_bitmap(fg, ALLEGRO_PIXEL_FORMAT_ARGB_8888, ALLEGRO_LOCK_READONLY); 36 37 bg_data = (uint32_t *)bg_lock->data; 38 fg_data = (uint32_t *)fg_lock->data; 39 40 int search_skip=20; 41 int search_step=0; 42 43 float best_sse = 999999999; 44 45 for (bg_y = 0; bg_y <= bg_h - fg_h; bg_y++) 46 { 47 for (bg_x = 0; bg_x <= bg_w - fg_w; bg_x++) 48 { 49 float sse=0; 50 51 for (search_step=0; ((fg_w/2) > (search_skip*search_step)) && ((fg_h/2) > (search_skip*search_step)); search_step++) 52 { 53 int rx, ry, rfx, rfy, ra; 54 uint32_t *bg_p; 55 uint32_t *fg_p; 56 unsigned char R1, G1, B1, R2, G2, B2; 57 ra = search_skip*search_step; 58 rx = ra+bg_x; 59 ry = ra+bg_y; 60 rfx = rx + (fg_w-(ra*2)); 61 rfy = ry + (fg_h-(ra*2)); 62 63 // Test Top of the rect 64 fg_y = ry; 65 for (fg_x=rx; fg_x<=rfx; fg_x++) 66 { 67 fg_p = (uint32_t *) ((uint8_t*)&fg_data[fg_x-rx+ra] + fg_lock->pitch * (fg_y-ry+ra)); 68 R1 = (*fg_p & 0x00FF0000) >> 16; 69 G1 = (*fg_p & 0x0000FF00) >> 8; 70 B1 = (*fg_p & 0x000000FF) >> 0; 71 72 bg_p = (uint32_t *) ((uint8_t*)&bg_data[fg_x] + bg_lock->pitch * (fg_y)); 73 R2 = (*bg_p & 0x00FF0000) >> 16; 74 G2 = (*bg_p & 0x0000FF00) >> 8; 75 B2 = (*bg_p & 0x000000FF) >> 0; 76 77 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 78 } 79 80 // Test Bottom of the rect 81 fg_y = rfy; 82 for (fg_x=rx; fg_x<=rfx; fg_x++) 83 { 84 fg_p = (uint32_t *) ((uint8_t*)&fg_data[fg_x-rx+ra] + fg_lock->pitch * (fg_y-ry+ra)); 85 R1 = (*fg_p & 0x00FF0000) >> 16; 86 G1 = (*fg_p & 0x0000FF00) >> 8; 87 B1 = (*fg_p & 0x000000FF) >> 0; 88 89 bg_p = (uint32_t *) ((uint8_t*)&bg_data[fg_x] + bg_lock->pitch * (fg_y)); 90 R2 = (*bg_p & 0x00FF0000) >> 16; 91 G2 = (*bg_p & 0x0000FF00) >> 8; 92 B2 = (*bg_p & 0x000000FF) >> 0; 93 94 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 95 } 96 97 // Test Left of the rect 98 fg_x = rx; 99 for (fg_y=ry; fg_y<=rfy; fg_y++) 100 { 101 fg_p = (uint32_t *) ((uint8_t*)&fg_data[fg_x-rx+ra] + fg_lock->pitch * (fg_y-ry+ra)); 102 R1 = (*fg_p & 0x00FF0000) >> 16; 103 G1 = (*fg_p & 0x0000FF00) >> 8; 104 B1 = (*fg_p & 0x000000FF) >> 0; 105 106 bg_p = (uint32_t *) ((uint8_t*)&bg_data[fg_x] + bg_lock->pitch * (fg_y)); 107 R2 = (*bg_p & 0x00FF0000) >> 16; 108 G2 = (*bg_p & 0x0000FF00) >> 8; 109 B2 = (*bg_p & 0x000000FF) >> 0; 110 111 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 112 } 113 114 // Test Right of the rect 115 fg_x = rfx; 116 for (fg_y=ry; fg_y<=rfy; fg_y++) 117 { 118 fg_p = (uint32_t *) ((uint8_t*)&fg_data[fg_x-rx+ra] + fg_lock->pitch * (fg_y-ry+ra)); 119 R1 = (*fg_p & 0x00FF0000) >> 16; 120 G1 = (*fg_p & 0x0000FF00) >> 8; 121 B1 = (*fg_p & 0x000000FF) >> 0; 122 123 bg_p = (uint32_t *) ((uint8_t*)&bg_data[fg_x] + bg_lock->pitch * (fg_y)); 124 R2 = (*bg_p & 0x00FF0000) >> 16; 125 G2 = (*bg_p & 0x0000FF00) >> 8; 126 B2 = (*bg_p & 0x000000FF) >> 0; 127 128 sse += (R1-R2)*(R1-R2) + (G1-G2)*(G1-G2) + (B1-B2)*(B1-B2); 129 } 130 } 131 132 if (best_sse > sse) 133 { 134 best_sse = sse; 135 m_x = bg_x; m_y = bg_y; 136 } 137 } 138 } 139 140 al_unlock_bitmap(bg); 141 al_unlock_bitmap(fg); 142 al_draw_bitmap(bg, 0, 0, 0); 143 al_draw_bitmap(fg, m_x, m_y, 0); 144 145 al_flip_display(); 146 al_rest(2); 147 148 return 0; 149}

It takes a lot less time than the last one, but I'm not sure if it's still fast enough... Increasing the search_skip makes it faster, but it might be less accurate. Putting it at an insane value like 900 would make it only search on the outer edges. It worked well so far in all cases. I'm not sure how it will perform in real time with enemies coming, but we'll see.

Is there anything else that can be optimized there?

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Thomas Fjellstrom
Member #476
June 2000
avatar

You're not actually going to use this in real time are you? Mario like maps are normally made out of several parallax scrolling layers, not a single bitmap like you show above. The background is usually at least one layer (counting the bushes, at least two), probably two or more, the platforms are another layer or two, the objects like bricks would be another, and the player and NPCs are yet another.

Or at least thats how I'd do it. And they'd all be able to move at a different rate.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Dario ff
Member #10,065
August 2008
avatar

I did a little hack on the emulator for the parallax backgrounds.

Consider this like part of a recording method, it doesn't need to be as fast as possible to keep a good FPS, but it shouldn't be killing the CPU.

And believe it or not, the bushes and the map are one single layer actually. ;) There's only a single parallax background.

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Thomas Fjellstrom
Member #476
June 2000
avatar

I still don't quite get what you're using this for.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Dario ff
Member #10,065
August 2008
avatar

You're one curious moose aren't you? :D

Here's a video to show off what I wanted to do, as well as the problem:

video

EDIT: The first koopa troopas aren't there because I killed them first. :P

The whole recording of this video is done on the emulator, but as you can see, there are some problems when aligning the screenshot when running and jumping. I assume the game uses something else to manage that apart from the Layer 1 X and Y position(which I've been able to track with the RAM Searcher), so my best solution to fix it would be aligning it with this.

The solution has to be as much game-independent as possible, so I can't just go around trying to figure out how SMW renders this. I'm planning on doing these videos with other games. Yeah, the recording does take a while, especially if you want to do a 1080p video, but time ain't the issue here. It has to be as automatic as possible. Still, optimizations are always welcome.

Anyway, I guess this means that there are no more Allegro-related optimizations to do? :P

EDIT: And before you ask, it's done in Allegro and not on the native emulator's routines because I wanted to port it to other emulators as well.

<Usefulness of the project not to be discussed>

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Thomas Fjellstrom
Member #476
June 2000
avatar

Ah. Interesting. I'm not sure how else to improve it, other than looking for some "computer vision" algorithms to more accurately detect the right area.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Dario ff
Member #10,065
August 2008
avatar

Awesome, it's working very nice!

Only by searching the edges everything was crap. But when using a precision of 10(rectangles separated by 10 pixels), the precision is amazing! I'd have to try out different values, since it does add a bit of overhead to each frame of recording, and look what would be the best balanced option.

Thanks for the help! Here's a short video of how it looks when aligned properly:

video

EDIT: How the hell does Youtube recognize it's a Mario related video??! I didn't even add those tags.

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Thomas Fjellstrom
Member #476
June 2000
avatar

Now try getting a little fancier and pull out the koopas and other things to remove them when they shouldn't be displayed ;D

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Dario ff
Member #10,065
August 2008
avatar

Well, that was a planned idea.

The problem is the maps from vgmaps.com have the objects already there. I could try contacting the author to remove that layer(surely they use some Gimp/Photoshop file). Or I would have to figure out a way to map the whole map using the emulator's layers. But then you'd only see what the player travelled, or I'd have to walk around the whole map. :P

Or maybe just blit the 2 leftmost columns onto the old world map? So many ways... :-/

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Thomas Fjellstrom
Member #476
June 2000
avatar

Use some fancy algorithm to detect objects like koopas, and see what should be there, and replace them with that.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Dario ff
Member #10,065
August 2008
avatar

If only it were as easy as it sounds...

So I tried drawing the leftmost 10 columns. Here's what I got:

video

There are a number of situations where it would probably screw up, but still it ain't a bad choice. 8-)

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Thomas Fjellstrom
Member #476
June 2000
avatar

Dario ff said:

If only it were as easy as it sounds...

Yeah, it isn't unless you're good with math, and can easily pick up Computer Vision topics.

What you have now is pretty close, at least it looks a lot less wrong than before.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Matthew Leverton
Supreme Loser
January 1999
avatar

Dario ff said:

Is there anything else that can be optimized there?

Without substantially changing the method, not really. With this brute force method, it's basically about lowering the amount of pixels to test. i.e., You want to test the fewest pixels as necessary to get an accurate result.

I'd try to avoid the vertical checks if possible, as those will be slower. It would be faster to do 20 horizontal checks than 10 of each. I only added them because I was doing an exact edge check.

You could break out of the loop slightly faster. As soon as sse > best_sse, you could skip to the next test, instead of waiting until the end. However, if you are in the general location, it's possible the values are so close, that would only prevent the last few pixels from being scanned.

It would actually be more trivial to match a complex image, because all you would have to do is align maybe two edges. But with 8 or 16 bit video games, you often have large blocks of colors, so you get a lot of area that matches.

Go to: