Project

General

Profile

Download (10.6 KB) Statistics
| Branch: | Revision:

distorted-objectlib / src / main / java / org / distorted / objectlib / tablebases / TablebasesCreator.java @ 431ee33b

1
///////////////////////////////////////////////////////////////////////////////////////////////////
2
// Copyright 2023 Leszek Koltunski                                                               //
3
//                                                                                               //
4
// This file is part of Magic Cube.                                                              //
5
//                                                                                               //
6
// Magic Cube is proprietary software licensed under an EULA which you should have received      //
7
// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html        //
8
///////////////////////////////////////////////////////////////////////////////////////////////////
9

    
10
package org.distorted.objectlib.tablebases;
11

    
12
import org.distorted.library.main.QuatHelper;
13
import org.distorted.library.type.Static3D;
14
import org.distorted.library.type.Static4D;
15
import org.distorted.objectlib.helpers.QuatGroupGenerator;
16

    
17
import java.util.ArrayList;
18

    
19
///////////////////////////////////////////////////////////////////////////////////////////////////
20

    
21
public abstract class TablebasesCreator
22
{
23
  private Tablebase mTablebase;
24
  private final Static3D[] mAxis;
25
  private final int mSize;
26
  private final int[][] mAngles;
27
  private final int mNumAxis;
28
  private final int[] mNumLayers;
29
  private final int mNumQuats;
30
  private final Static4D[] mQuats;
31
  private final int[][] mRotRow;
32
  private final int mNumCubits;
33
  private final float[][] mPosition;
34
  private final float[][] mCuts;
35
  private final int[] mNumCuts;
36
  private final boolean[][] mRotatable;
37

    
38
  private int[][] mQuatMult;
39

    
40
  private static final float[] mTmp = new float[4];
41

    
42
///////////////////////////////////////////////////////////////////////////////////////////////////
43

    
44
  abstract int[][] getBasicAngles();
45
  abstract Static3D[] getRotationAxis();
46
  abstract float[][] getPosition();
47
  abstract float[][] getCuts();
48

    
49
  abstract boolean[][] getRotatable();
50

    
51
  abstract int getSize();
52
  abstract int[] getQuats(int index);
53
  abstract int getIndex(int[] quats);
54

    
55
///////////////////////////////////////////////////////////////////////////////////////////////////
56

    
57
  public TablebasesCreator()
58
    {
59
    mSize = getSize();
60
    mAngles = getBasicAngles();
61
    mAxis = getRotationAxis();
62
    mNumAxis = mAxis.length;
63
    mNumLayers = new int[mNumAxis];
64
    for(int i=0; i<mNumAxis; i++) mNumLayers[i] = mAngles[i].length;
65
    mQuats = QuatGroupGenerator.computeGroup(mAxis,mAngles);
66
    mNumQuats = mQuats.length;
67
    mPosition = getPosition();
68
    mNumCubits = mPosition.length;
69
    mRotatable = getRotatable();
70
    mCuts = getCuts();
71
    mNumCuts = new int[mNumAxis];
72

    
73
    for(int i=0; i<mNumAxis; i++)
74
      {
75
      mNumCuts[i] = (mCuts==null || mCuts[i]==null ? 0 : mCuts[i].length);
76
      }
77

    
78
    mRotRow = new int[mNumCubits][mNumAxis];
79
    }
80

    
81
///////////////////////////////////////////////////////////////////////////////////////////////////
82

    
83
  private int computeRow(float[] pos, int quat, int axisIndex)
84
    {
85
    int ret=0;
86
    int len = pos.length/3;
87
    Static3D axis = mAxis[axisIndex];
88
    float axisX = axis.get0();
89
    float axisY = axis.get1();
90
    float axisZ = axis.get2();
91
    float casted, xoff=0, yoff=0, zoff=0;
92
    Static4D q = mQuats[quat];
93

    
94
    for(int i=0; i<len; i++)
95
      {
96
      QuatHelper.rotateVectorByQuat(mTmp,pos[3*i],pos[3*i+1],pos[3*i+2],1.0f,q);
97
      casted = (mTmp[0]+xoff)*axisX + (mTmp[1]+yoff)*axisY + (mTmp[2]+zoff)*axisZ;
98
      ret |= computeSingleRow(axisIndex,casted);
99
      }
100

    
101
    return ret;
102
    }
103

    
104
///////////////////////////////////////////////////////////////////////////////////////////////////
105

    
106
  private int computeSingleRow(int axisIndex,float casted)
107
    {
108
    int num = mNumCuts[axisIndex];
109

    
110
    for(int i=0; i<num; i++)
111
      {
112
      if( casted<mCuts[axisIndex][i] ) return (1<<i);
113
      }
114

    
115
    return (1<<num);
116
    }
117

    
118
///////////////////////////////////////////////////////////////////////////////////////////////////
119
// remember about the double cover or unit quaternions!
120

    
121
  private int mulQuat(int q1, int q2)
122
    {
123
    Static4D result = QuatHelper.quatMultiply(mQuats[q1],mQuats[q2]);
124

    
125
    float rX = result.get0();
126
    float rY = result.get1();
127
    float rZ = result.get2();
128
    float rW = result.get3();
129

    
130
    final float MAX_ERROR = 0.1f;
131
    float dX,dY,dZ,dW;
132

    
133
    for(int i=0; i<mNumQuats; i++)
134
      {
135
      dX = mQuats[i].get0() - rX;
136
      dY = mQuats[i].get1() - rY;
137
      dZ = mQuats[i].get2() - rZ;
138
      dW = mQuats[i].get3() - rW;
139

    
140
      if( dX<MAX_ERROR && dX>-MAX_ERROR &&
141
          dY<MAX_ERROR && dY>-MAX_ERROR &&
142
          dZ<MAX_ERROR && dZ>-MAX_ERROR &&
143
          dW<MAX_ERROR && dW>-MAX_ERROR  ) return i;
144

    
145
      dX = mQuats[i].get0() + rX;
146
      dY = mQuats[i].get1() + rY;
147
      dZ = mQuats[i].get2() + rZ;
148
      dW = mQuats[i].get3() + rW;
149

    
150
      if( dX<MAX_ERROR && dX>-MAX_ERROR &&
151
          dY<MAX_ERROR && dY>-MAX_ERROR &&
152
          dZ<MAX_ERROR && dZ>-MAX_ERROR &&
153
          dW<MAX_ERROR && dW>-MAX_ERROR  ) return i;
154
      }
155

    
156
    return -1;
157
    }
158

    
159
///////////////////////////////////////////////////////////////////////////////////////////////////
160

    
161
  private int getMultQuat(int index1, int index2)
162
    {
163
    if( mQuatMult==null )
164
      {
165
      mQuatMult = new int[mNumQuats][mNumQuats];
166

    
167
      for(int i=0; i<mNumQuats; i++)
168
        for(int j=0; j<mNumQuats; j++) mQuatMult[i][j] = -1;
169
      }
170

    
171
    if( index1<mNumQuats && index2<mNumQuats )
172
      {
173
      if( mQuatMult[index1][index2]==-1 ) mQuatMult[index1][index2] = mulQuat(index1,index2);
174
      return mQuatMult[index1][index2];
175
      }
176

    
177
    return -2;
178
    }
179

    
180
///////////////////////////////////////////////////////////////////////////////////////////////////
181

    
182
  private boolean belongsToMove(int cubit, int axis, int layer)
183
    {
184
    return mRotRow[cubit][axis] == layer;
185
    }
186

    
187
///////////////////////////////////////////////////////////////////////////////////////////////////
188
// assumption: all layers have the same basicAngles!
189

    
190
  private int insertAllChildren(int index, byte level)
191
    {
192
    int ret = 0;
193
    int[] quats = getQuats(index);
194
    int numQuats = quats.length;
195
    int[] tmpQuats = new int[numQuats];
196
    byte newLevel = (byte)(level+1);
197
    boolean[] belongs = new boolean[mNumCubits];
198
    int quatBasis = 0;
199

    
200
    for(int ax=0; ax<mNumAxis; ax++)
201
      {
202
      for(int layer=0; layer<mNumLayers[ax]; layer++)
203
        {
204
        if( !mRotatable[ax][layer] ) continue;
205
        int bitLayer = (1<<layer);
206

    
207
        for(int cubit=0; cubit<mNumCubits; cubit++)
208
          {
209
          mRotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);
210
          belongs[cubit] = belongsToMove(cubit,ax,bitLayer);
211
          }
212

    
213
        int maxAngle = mAngles[ax][layer];
214

    
215
        for(int angle=1; angle<maxAngle; angle++ )
216
          {
217
          System.arraycopy(quats, 0, tmpQuats, 0, numQuats);
218
          int quat = quatBasis + angle;
219

    
220
          for(int cubit=0; cubit<mNumCubits; cubit++)
221
            if( belongs[cubit] )
222
              {
223
              int currQuat = tmpQuats[cubit];
224
              int newQuat = getMultQuat(quat,currQuat);
225
              tmpQuats[cubit] = newQuat;
226
              }
227

    
228
          int childIndex = getIndex(tmpQuats);
229
          if( mTablebase.insertUnpacked(childIndex,newLevel) ) ret++;
230
          }
231
        }
232

    
233
      quatBasis += (mAngles[ax][0]-1);
234
      }
235

    
236
    return ret;
237
    }
238

    
239
///////////////////////////////////////////////////////////////////////////////////////////////////
240

    
241
  public void createTablebase()
242
    {
243
    mTablebase = new Tablebase(mSize);
244
    mTablebase.insertUnpacked(0,(byte)0);
245

    
246
    int numInserted;
247
    byte insertingLevel = 0;
248

    
249
    do
250
      {
251
      numInserted = 0;
252

    
253
      for(int i=0; i<mSize; i++)
254
        {
255
        byte level = mTablebase.retrieveUnpacked(i);
256
        if( level==insertingLevel ) numInserted += insertAllChildren(i,level);
257
        }
258

    
259
      insertingLevel++;
260

    
261
      android.util.Log.e("D", "inserted "+numInserted+" positions at level "+insertingLevel);
262
      }
263
    while( numInserted>0 );
264

    
265
    mTablebase.pack();
266
    }
267

    
268
///////////////////////////////////////////////////////////////////////////////////////////////////
269

    
270
  private void addMove(ArrayList<int[]> moves, int axis, int layer, int angle)
271
    {
272
    int maxAngle = mAngles[axis][layer];
273
    angle = maxAngle-angle;
274
    if( angle> 0.5f*maxAngle ) angle -= maxAngle;
275

    
276
    int[] move = new int[] { axis, (1<<layer), angle };
277
    moves.add(move);
278
    }
279

    
280
///////////////////////////////////////////////////////////////////////////////////////////////////
281

    
282
  private int[][] convertMoves(ArrayList<int[]> moves)
283
    {
284
    int len = moves.size();
285
    int[][] ret = new int[len][];
286
    for(int i=0; i<len; i++) ret[i] = moves.get(i);
287
    return ret;
288
    }
289

    
290
///////////////////////////////////////////////////////////////////////////////////////////////////
291

    
292
  public int[][] solution(int index)
293
    {
294
    byte level = mTablebase.retrievePacked(index);
295
    ArrayList<int[]> moves = new ArrayList<>();
296
    int quatBasis = 0;
297
    int[] quats = getQuats(index);
298
    int numQuats = quats.length;
299
    int[] tmpQuats = new int[numQuats];
300
    boolean[] belongs = new boolean[mNumCubits];
301

    
302
    while(index!=0)
303
      {
304
      for(int ax=0; ax<mNumAxis; ax++)
305
        {
306
        int numLayers = mNumLayers[ax];
307
        int[] angles = mAngles[ax];
308

    
309
        for(int layer=0; layer<numLayers; layer++)
310
          {
311
          if( !mRotatable[ax][layer] ) continue;
312
          int bitLayer = (1<<layer);
313

    
314
          for(int cubit=0; cubit<mNumCubits; cubit++)
315
            {
316
            mRotRow[cubit][ax] = computeRow(mPosition[cubit],quats[cubit],ax);
317
            belongs[cubit] = belongsToMove(cubit,ax,bitLayer);
318
            }
319

    
320
          int maxAngle = angles[layer];
321

    
322
          for(int angle=1; angle<maxAngle; angle++ )
323
            {
324
            System.arraycopy(quats, 0, tmpQuats, 0, numQuats);
325
            int quat = quatBasis + angle;
326

    
327
            for(int cubit=0; cubit<mNumCubits; cubit++)
328
              if( belongs[cubit] )
329
                {
330
                int currQuat = tmpQuats[cubit];
331
                int newQuat = getMultQuat(quat,currQuat);
332
                tmpQuats[cubit] = newQuat;
333
                }
334

    
335
            int childIndex = getIndex(tmpQuats);
336
            byte newLevel = mTablebase.retrievePacked(childIndex);
337

    
338
            if( ((newLevel-level+1)%3) == 0 )
339
              {
340
              addMove(moves,ax,layer,angle);
341
              angle=maxAngle;
342
              layer=numLayers;
343
              ax=mNumAxis;
344
              index = childIndex;
345
              level = (level==0 ? 2 : (byte)(level-1));
346
              }
347
            }
348
          }
349

    
350
        quatBasis += (angles[0]-1);
351
        }
352

    
353
      quatBasis = 0;
354
      quats = getQuats(index);
355
      }
356

    
357
    return convertMoves(moves);
358
    }
359
}
(2-2/3)