symmetry detection

[Parasprites]

Do you have any examples of a nontrivial nonsquare map with rotational symmetry? I don't think it's possible.

[Hippo]

[Parasprites]

I don't think that works, and anyway, if there's a nonrotational symmetry it doesn't matter.

[Hippo]

[swordfishBob]

I used the following to get fairly time-efficient symmetry dection..
Reflections:
- If there's a reflection, there's an opposite one in the same dimension. e.g. a vertical axis of symmetry at column N will have another one at (width / 2) + N. So, the number of possible V symmetry positions is halved, likewise H.
- Detect Vertical and Horizontal symmetry separately. One may exist without the other, and you only need a (width / 2) and a (height / 2) array of flags or counters to record possibilities
- Process of elimination. Once a row/column is proven not symmetric, don't test it again. As ant numbers increase, the number of possibilities reduce so CPU use remains low.
Translations:
- Offsets must be evenly divisible into the total width and height, or a multiple of same. In fact, (ignoring orthogonal translation for now - treat it as a separate case) you can say that if there's e.g. 7 repetitions, then the pattern repeats at (width/7) horizontally, and N x (height/7) vertically - just have to find N. Again, use a process of elimination at each round for efficiency. So, first eliminate factors that just don't divide into both the height and width. Then for each remaining factor, consider each option for N (up to that factor). In our example, N=7 is a special case for straight horizontal translation, but vertical needs additional logic.

Error detection:
- Due to the range of different symmetry types, and the fact I don't detect some, my world map distinguishes between land, water, expected land, expected water. As new areas are explored, expected is converted to actual. If a contradiction is found, the supposed symmetry can be undone without losing what I really know. It's rarely triggered these days, but was handy for tweaking/debugging.

What I haven't got around to:
- Diagonal reflections. Could be implemented using same logic and performance as V and H. Most (not all) worlds with diagonal reflection also have V and H, in which case much of the world is mapped as quickly anyway.
- Rotational. No harder to do, though needs to be considered for each possible centre within 1/4 of the world map. (There will be another rotation point offset by width/2,height/2). It would be slower though due to the number of candidate pivots to test and track.

Testing on my laptop, I rarely exceeded 50ms for a turn, even while detecting translations and reflections described above.

[Hippo]

Looking to the final set of maps, my symmetry detection codes more than was required .
What I missed most are nonsquare maps with rotational symmetry ... .

[BenJackson]

[Parasprites]

[Hippo]

If you don't use the symmetry, you don't need it at all.
I use the symmetry mainly to know where on unvisible map the food is ... and knowing more of the orbit informs me more about the food ...

[Hippo]

Example of situation when symmetry helps ... http://aichallenge.org/visualizer.php?g ... &user=6888 turns 259...,437 ... and at the ending as well.
Here it helped during the whole game: http://aichallenge.org/visualizer.php?g ... &user=6888