Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » BITMAP* Comparison

Credits go to CGamesPlay, Kibiz0r, and Matthew Leverton for helping out!
This thread is locked; no one can reply to it. rss feed Print
 1   2 
BITMAP* Comparison
Jeff Bernard
Member #6,698
December 2005
avatar

Is there a way to test if two BITMAP* objects point to the same image?

ie-

BITMAP* bmp1 = create_bitmap(32, 32);
clear_to_color(bmp1, makecol(0,0,0));

BITMAP* bmp2 = create_bitmap(32, 32);
clear_to_color(bmp2, makecol(0,0,0));

if (bmp1 == bmp2) // they are the same image, so I want this to be true...

--
I thought I was wrong once, but I was mistaken.

Kibiz0r
Member #6,203
September 2005
avatar

Yes, by using

if (bmp1 == bmp2)

However, the code you posted will not yield that result, because those two BITMAP* objects do NOT point to the same image. They point to two different images that happen to have the same color values.

If you want to check for that, you will need some (expensive) function to check for you.

I would suggest you rethink your design if you need this function. Perhaps keep a global array of BITMAP*s and instead of checking to see if two objects have the same color info, you can just check the index of their pointer.

ie.

BITMAP* bmpArr[20];
...
class Object
{
private:
    int m_bmpIndex;
    ...
};
...
if (Obj1.GetGfxIndex() == Obj2.GetGfxIndex())

A more creative solution for if you are doing a lot of putpixel-y stuff, wrap the BITMAP object in a class that puts pixel for you and adds the color value (adjusted with the x-y coordinates of where it's putting it) into a long int (maybe more memory, even) that can keep track of the value stored in a compact fashion. In effect, what you're doing here is hashing the BITMAP, so you only need to make a couple cheap integer comparisons.

Jeff Bernard
Member #6,698
December 2005
avatar

I'm trying to rip terrain sprites from a game right now. So the idea was, instead of going through each map and visually having to determine if each 16x16 tile was unique, I could just write a program that would go through each map and grab each unique tile for me.

So I suppose the only solution to this condition would be to go through and check each (or every other, every third, etc) pixel to determine if the BITMAP* objects are the same? Of course I would remove each duplication of a unique tile after having determined it's unique (in other words I wouldn't check every single tile against every single tile after the first run through checking).

--
I thought I was wrong once, but I was mistaken.

Kibiz0r
Member #6,203
September 2005
avatar

If this is a large-scale deal, I bet there's a magical pattern-detection algorithm somewhere on Google/Wikipedia. If you just want it done, just go brute-force and _getpixel and compare everything.

Hm.

pseudocode:

make a scratch BITMAP
while there are tiles to get
  while possibilities > 0
    get the next pixel and put it to the scratch BITMAP
      for every BITMAP in possibilities
        check current pixel with same pixel from possibly-matching BITMAP
        if it's not a match, remove possibly-matching BITMAP from possibilities
      if we're on the last pixel, and there is still a BITMAP in possiblities,
        we have a match, so ignore this tile (since we already have it)
    if we're not ignoring this tile,
      we have a tile that doesn't match any already in memory,
      so copy the scratch BITMAP to the list of unique tiles
    re-fill possibilities with all unique tiles you've found
  get the next tile

Questions?

Matthew Leverton
Supreme Loser
January 1999
avatar

I would assign a unique hash to each tile and go from there. You might be able to just use one row or column or diagonal to build the hash. It depends on how similar the tiles are. And if that sounds like too much work, a simple brute force will get the job done.

If you post a sample bitmap, perhaps we could help determine the optimal approach.

Kibiz0r
Member #6,203
September 2005
avatar

I would just go with my pseudocode, I don't think he's looking for anything high-performance. A hash would be optimal in terms of performance, but for performance vs. time spent coding, I think a brute force method that at least weeds out non-matches is good.

I guess it does depend on the tileset, though.

Jeff Bernard
Member #6,698
December 2005
avatar

http://luneknight.com.ru/games/test.jpg
Each tile is 16x16. This image is 20x15 tiles. Most of the maps will be around this size or smaller. There's only a couple bigger, I think. Of course the tiles in this image may be a bit off from the actual thing due to saving it as a JPG.

Kibiz0r: I wrote up a quick little thing that's similar to what it says. Of course it crashes almost instantly, but if I work on it long enough I think I can work the kinks out.

--
I thought I was wrong once, but I was mistaken.

Kibiz0r
Member #6,203
September 2005
avatar

Wow, there are a lot of repeats. Maybe you should use a hash.

Matthew Leverton
Supreme Loser
January 1999
avatar

If you attach a lossless image (BMP or PNG) I'll try a few things with it.

Jeff Bernard
Member #6,698
December 2005
avatar

http://luneknight.com.ru/games/test.PNG
OK, here's a BMP. I originally didn't post a BMP because, well, you know the filesize on these things is huuuuuuuuge.

The check that I've implemented (still crashes though because I can't seem to get it find the right number of unique tiles before saving them. It says there are 650 unique tiles...but crashes when it tries to save the 130th because it doesn't exist) says there are 129 unique tiles in this map. I'm not sure if that's true, I guess I'll have to manually check each to see if this working properly.

EDIT-- Made the image a PNG

--
I thought I was wrong once, but I was mistaken.

CGamesPlay
Member #2,559
July 2002
avatar

Quote:

I originally didn't post a BMP because, well, you know the filesize on these things is huuuuuuuuge.

FYI, MS Paint saves PNG.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Jeff Bernard
Member #6,698
December 2005
avatar

I didn't think Paint was any good at saving PNGs. I seem to remember trying to save one before it getting a bigger filesize than BMP. Oh well, guess I'm corrected here. Image editted to be a PNG.

--
I thought I was wrong once, but I was mistaken.

Kibiz0r
Member #6,203
September 2005
avatar

Quote:

says there are 129 unique tiles in this map. I'm not sure if that's true

That's almost half.

Actually, that might be right. I assumed all the grass was the same, but I took it into Photoshop, made a pattern from the upper-left tile and did a difference filter and it only nullified about 1/5th of the grass.

The trees also have some variation. The one-tile castles are all the same, though.

Jeff Bernard
Member #6,698
December 2005
avatar

Got something that works (let's just assume it does because I don't want to manually check). Even made it output the tiles into a nice little tileset (although a little disorganized and that grass is a bit too variable, making it seem like there are repeats. I may ease the test so that it might eliminate some of this that are so similar.):
http://luneknight.com.ru/games/set.PNG

What I did was divide the map into each tile. Then I took the first tile and compared it to the rest, comparing every other pixel. If a pixel was not the same, I aborted the test for that tile and went to the next. If the testing tile was determined to be the same as the first tile, I deleted the testing tile. I then put that first tile aside and chose the next non-eliminated tile and repeated the process.

I think that's pretty much the same as Kibiz0r's psuedo-code.

Thanks, everyone.

--
I thought I was wrong once, but I was mistaken.

Matthew Leverton
Supreme Loser
January 1999
avatar

592261

That's what my first pass came up with.

I first got all the unique colors and indexed them. (This image has 63 colors.) [edit: bad math]

My tiles are different from yours. Did you use the same image you posted? It's possible I've got a bug somewhere...

Jeff Bernard
Member #6,698
December 2005
avatar

Yeah, I used the same image.

Looking at your method, I'm guessing that you added 63*pixel_number in an effort to not miss out on a unique tile because it happens to use the same colors the same amount of times as another tile. But couldn't a tile be set up in a way that it is different from another tile, but still generate the same hash? I don't really understand how the hash in generated...

What I did was first ripped EVERY tile from the image and put them into an array. Then I ran through this loop:

1#define TILEW 16
2#define NUMTESTS 16 // square-root of number of tests to run on each tile.
3 
4std::vector<BITMAP*> unique;
5unique.push_back(array[0]);
6array[0] = NULL;
7
8int deadTiles = 0;
9 
10for (int k = 0; array; k++)
11 {
12 for (int i = 0; i < height; i++)
13 for (int j = 0; j < width; j++)
14 if (array[j+i*width])
15 {
16 bool kill = false;
17 for (int m = 0; m < TILEW; m+=TILEW/NUMTESTS)
18 {
19 for (int n = 0; n < TILEW; n+=TILEW/NUMTESTS)
20 if (getpixel(array[j+i*width], m, n) != getpixel(unique[unique.size()-1], m, n))
21 {
22 kill = true;
23 break;
24 }
25 if (kill)
26 break;
27 }
28 if (!kill)
29 array[j+i*width] = NULL;
30 }
31 while (!array[k])
32 {
33 k++;
34 if (k >= width*height)
35 {
36 k = -1;
37 break;
38 }
39 deadTiles++;
40 }
41 if (k == -1)
42 break;
43 unique.push_back(array[k]);
44 }

It's entirely possible (and I hate to say this, but probably likely) that there's a bug somewhere in my check. First off, unique.size() returns a value of 650, which is why I added the incrementation of deadTiles, so that I can just subtract that from the total of the number of tiles in the map to get the number of unique tiles so that I don't go out of bounds of the vector unique. Plus there's a lot of embedded loops which only complicate things...

--
I thought I was wrong once, but I was mistaken.

Matthew Leverton
Supreme Loser
January 1999
avatar

Quote:

But couldn't a tile be set up in a way that it is different from another tile, but still generate the same hash?

Not if I wrote the function correctly, but now that I look at my implementation again, I don't think I did.

Edit: Duh, I wasn't considering 63256. I'll have to revise my hash. It may or may not have been giving false dupes, but it is definitely too simple as is.

Kibiz0r
Member #6,203
September 2005
avatar

Hash collisions are fun. :D

Matthew Leverton
Supreme Loser
January 1999
avatar

After adjusting my hash function, I now get the same number of unique tiles as Jeff's brute force method. My program executes instantly, but I doubt the brute force is very slow.

Jeff Bernard
Member #6,698
December 2005
avatar

Yeah, the brute force is pretty much instant. Maybe if the maps were super huge with even more unique tiles then it would be slower, but it gets the job done.

--
I thought I was wrong once, but I was mistaken.

ImLeftFooted
Member #3,935
October 2003
avatar

I'd sleep easier with a brute force operation. A missed tile would easily go unnoticed.

Fladimir da Gorf
Member #1,565
October 2001
avatar

At least Matthew's method seems to arrange the tiles nicely...

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

Matthew Leverton
Supreme Loser
January 1999
avatar

That's because the hash was closely associated with the color information. I used a map<unsigned int, BITAMP *> to store them, so they naturally came out sorted nicely. The updated hash which pretty much guarantees no false positives is much more chaotic, and as such, the tiles are random.

Of course, sorting the tiles with either the brute force method or my updated hash wouldn't be problematic. Just assign a sort id to the tile that is similar to my original hash. In this case, duplicate values wouldn't matter at all.

Thomas Harte
Member #33
April 2000
avatar

Neil Walker has done work on this sort of thing — see his Game Mapping Tool. VB source is included with his download if you want to check out whatever he is doing...

Jeff Bernard
Member #6,698
December 2005
avatar

I seem to have run into a bit of a snafu when trying to rip the tiles from a map of a different game. My method does not appear to work for another game. This time the tiles are 32x32 instead of 16x16, but that really shouldn't make a difference. :-/

Here's the map. 736x640, so 23x20 tiles.
http://allegro.cc/files/attachment/592323

When I try to rip the tiles with a brute force method, comparing all 1024 pixels of each tile, I end up with this:
http://allegro.cc/files/attachment/592324
I've no idea where those black tiles at the end came from, nor do I know why there are so many duplicates (I've examined the fronts of those houses and several of the wall tiles and I can't see any pixel differences). The gray tiles are just extra space from when the tiles were arranged.

So yeah...umm...help?

--
I thought I was wrong once, but I was mistaken.

 1   2 


Go to: