[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - symmetry detection

It is currently Fri Dec 15, 2017 9:39 pm Advanced search

symmetry detection

Share and discuss ideas for your entries here.

Re: symmetry detection

Postby Parasprites » Sun Dec 18, 2011 11:03 pm

Do you have any examples of a nontrivial nonsquare map with rotational symmetry? I don't think it's possible.
Parasprites
Major-General
 
Posts: 224
Joined: Mon Oct 24, 2011 3:08 pm

Re: symmetry detection

Postby Hippo » Sun Dec 18, 2011 11:52 pm

Hippo
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Re: symmetry detection

Postby Parasprites » Sun Dec 18, 2011 11:59 pm

I don't think that works, and anyway, if there's a nonrotational symmetry it doesn't matter.
Parasprites
Major-General
 
Posts: 224
Joined: Mon Oct 24, 2011 3:08 pm

Re: symmetry detection

Postby Hippo » Mon Dec 19, 2011 12:05 am

Hippo
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Re: symmetry detection

Postby swordfishBob » Mon Dec 19, 2011 6:09 am

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.
swordfishBob
Lieutenant
 
Posts: 10
Joined: Thu Nov 03, 2011 1:41 am

Re: symmetry detection

Postby Hippo » Tue Dec 20, 2011 8:23 am

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 ... .
Hippo
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Re: symmetry detection

Postby BenJackson » Tue Dec 20, 2011 9:28 am

BenJackson
Colonel
 
Posts: 94
Joined: Sat Oct 29, 2011 4:16 am

Re: symmetry detection

Postby Parasprites » Tue Dec 20, 2011 1:55 pm

Parasprites
Major-General
 
Posts: 224
Joined: Mon Oct 24, 2011 3:08 pm

Re: symmetry detection

Postby Hippo » Tue Dec 20, 2011 8:46 pm

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
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Re: symmetry detection

Postby Hippo » Sat Dec 24, 2011 7:03 pm

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
Hippo
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Previous

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron