How to get a unique ID for a 8x8 grid in a 64bit int

[Zantal]

Ok so here's the problem,

I made a puzzle generator which generates grids based on tiles of various forms.

The first issue I encountered was that I had multiple generations of the same grid, and the only difference is that they are rotated by 90 degrees each

xxx | oxx | xxo | xxx
xxx | xxx | xxx | xxx
oxx | xxx | xxx | xxo

So at first i solved the problem generically by building a 2 dimensional array of bools, and calculating the hash for each side then combining it to get the overall hash
which would then be used in the puzzle hashmap.

The grid would be saved anyway in the puzzle data so in case of hash collisions it would do a cell by cell comparison for all 4 rotations.

I tried to generate all possible solutions, but it would just eat up all memory. So I implemented some generation rules so that not all puzzles would be saved.

I finished the work, but now I am wondering how I could optimize the problem even further.


So here is my current solution which I can't manage to implement correctly.

I noticed I didn't need puzzles with an area greater than 7x6 (so in total 42 cells) and if we treat a bool cell as a single bit the next thought that comes to mind is to map those bits to a number which would then be unique, if we calculate this Id for the 4 rotated puzzles and for example get the smallest one of those 4 ids it should be unique am I right?

By doing so I wouldn't need to hold the information of the grid, hell I wouldn't even create it and puzzle comparison would be a simple number comparison.

I have tried some approaches, but I am getting something wrong somewhere, is someone willing to help me? I am really curious to see by how much this optimization could speed things up <.<

 

[pcgamer4life]

(Fair warning, I'm not 100% clear on what you're trying to accomplish here).

In order to save memory and CPU cycles, try designing your 'grid' at the bit level (like you mentioned briefly). You can use bitwise operators to flip individual bits in a byte to simulate your grid, instead of allocating a bool (1-8 bytes, depending on the language) for each tile. Each row of bits will always equate to a unique value (can map to hex, ascii, decimal, whatever), so your comparison should be easy at that point.

 

[Zantal]

I already managed to map it to a 64bit value with bit shifting, the problem is with grids that are rotated as they are basically redundant and i do not need them during the generation (reducing the execution time by a lot) I already managed to calculate hash values for rotated grids and it works, although hashes can collide and in that case you have to compare the grids directly
(once for each rotation). the process is slow, and I bet I can shave a lot of processing time there if only I could find a way to reduce it to a single long integer comparison.

At that point the overhead would be only when calculating the unique Id for that grid.

 

[pcgamer4life]

The problem is that your grid is a variable length. You'll need a way to distinguish where a new row starts.

Think of it this way, a 2x3 grid of
[oldtable]0|1
1|0
1|1[/table]
Would be 011011 = 27 in decimal (assuming top left is MSB and bottom right is LSB).

You could get that same hash with a 6x1 grid, or a 3x2 grid. You could store your grid in an array (a 1D array, but still manipulate bits as if they are columns), then you can generate a hash for each row, and compare them to make certain your grid is unique. It's a little more processing, and a little more wasteful of RAM, but a more straightforward solution I think.

You could also reserve the first 6 bits of your 64bit value to tell you the size of the grid, and then calculate the hash for each row based on that. That would be a little more conscious of RAM.

 

[JrClocker]

This reminds me of the days WAY back when (I'm old) of generating unique checksums for firmware builds.

If I reverse two lines of code, I wanted to have a different checksum, even if the logic didn't change.

XOR is your buddy.

I created an algorithm that did an XOR of the address and the data at that address, and added (OR) this to a running value. The net effect is that I always got a unique checksum value.


I'm going WAY back here, but do you know what a logic "truth table" is? You can build a truth table and boil it down to 2 logical expressions.

 

[Zantal]

Well I needed the exact opposite of what you did with build checksums. If I reverse or mirror my grid it should generate the same hash.

I was trying to generate something like 200 billion grids, So to hurry up I came up with some rules to reduce the pool size while creating it and it sped up the process by a lot.
ended up with a pool size of 200k in about 10 minutes but we ended up using 6k of those only =(

I am kinda sad because in the end I didn't finish what I had in mind to do, I just didn't have enough time.

But my initial Idea to build a grid pool payed off in the end, some people who bought the game out was very amazed by how fast my puzzle generation code works, ofc I omit to say they are all pre-generated to avoid any stutter on puzzle swap