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...

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.

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).

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?

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.

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.

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.

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

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

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

FYI, MS Paint saves PNG.

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.

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.

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.

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...

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:

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...

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 63²⁵⁶. 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.

Hash collisions are fun.

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.

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'd sleep easier with a brute force operation. A missed tile would easily go unnoticed.

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

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.

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...

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've attached the output of my program.

Just looking at it, it appears to have duplicate tiles though. I'd have to check exact RGB values to see if they really are.

I wrote a simple tile ripper a while back for my own use. I needed a way to import old versions of worminator maps into the new build of the game, and since the tile sets had changed all the graphics were out of whack. So, I wrote a little program that would search through the old and new tilesets to find matches, and adjust the tile numbers for the older maps so they line up correctly with the most recent tileset.

Anyway, I adapted my code quickly to search for unique tiles. I get the same results for the first image (with 16*16 tiles), but I also get apparent 'duplicates' when running on the latest image 2 posts back (32 *32 tiles).

After examining the image closely, there is something wrong with the tile alignment on the latest image. I thought the tiles were dupes initially, but after looking closely at them, they are shifted up/down/left/right by 1 pixel. If you look carefully at the source image, some identical tiles are shifted slightly which is causing the duped tiles. For example, look at the upper left house, and compare it to the other 4 houses with the same graphics. If you compare them pixel by pixel, the house in the upper left is very slightly off from the rest when aligned to a 32*32 grid.

So, in this case I believe our tile rippers are working correctly, but there is something funky with the source image.

David Layne: I noticed that as well, sometime after making that post. It turns out I ripped the map from the game incorrectly. There is a border around the playable field of the map, 31 pixels on the top, 31 pixels on the left, 33 pixels on the right, and 28 pixels on the bottom. For the image that I posted, I had removed some pixels on the bottom to get the dimensions to be correct, but I did not notice that the other borders where off on whole tiles as well.