I don't entirely understand A*, and I'm not sure what this method is called, if it is original, or if it works all of the time. In fact, this is just something I adopted from something I learned in 10th grade about using matrices when you have systems of competition to see who would win the matches. I'm not sure how useful it is or how it can be adopted and modified to be useful for other things.
You create a square matrix whose dimension is equal to the number of tiles. Each row of the matrix represents the tile you are in, and each column represents whether or not you can get to the adjacent tile in a single move from the current tile. If you can get to the adjacent tile you put a 1, otherwise a 0, and for itself put a zero because you cannot move to the same tile in a single step (you need at least two steps to get back to the current tile) . So, lets say you have four tiles A B C D.
-From A you can get to B C D
-From B you can get to A C
-From C you can get to A B D
-From D you can get to A C
The matrix will look like this:
Code:
A B C D
_______
A| 0 1 1 1
B| 1 0 1 0
C| 1 1 0 1
D| 1 0 1 0
Then, when you raise this matrix to a power (multiply it by itself) it gives you the number of different ways to get from one tile to any other tile in the number of moves (the power).
Raise the above matrix to the third power gives you the number of connections between tiles in three moves. Obviously, because this is such a small example, the connections involve a lot of crossing over the same tiles. But, if you have several thousand tiles where sometimes it isn't clear . Here's a program I just wrote demonstrating this idea:
Code:
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
#define NUM_TILES 4
//This does not modify the original matrix unless you put the original matrix as the output matrix
//assumes it is a square matrix and that the input matrix is a two dimensional array
void Multiply(int ** inputmatrix1,int ** inputmatrix2,int size,int ** outputmatrix);
void PrintMatrix(int ** inputmatrix,int size)
{
for(int row = 0; row < size; row++)
{
for(int col = 0; col < size; col++)
{
cout << inputmatrix[row][col] << " ";
}
cout << endl; //done with the line
}
}
void WriteMatrixToFile(int ** inputmatrix, int size,ofstream & fout)
{
for(int row = 0; row < size; row++)
{
for(int col = 0; col < size; col++)
{
fout << inputmatrix[row][col] << " ";
}
fout << "\n";
}
}
void MakeMatrixIdentity(int **inputmatrix,int size)
{
for(int x = 0; x < size; x++)
{
inputmatrix[x][x] = 1;
}
}
//if matrix element row,col is 1, then matrix element col,row is also 1
//make the initial matrix the zero matrix
int main(void)
{
int ** m;
int ** m_to_2; //connections when walked two steps
int ** m_to_3; //connections when walked three steps
int ** m_to_4; //connections when walked four steps
m = new int*[4];
for(int i = 0; i < 4; i++)
{
m[i] = new int[4];
m[i][0] = m[i][1] = m[i][2] = m[i][3] = 0;
}
m_to_2 = new int*[4];
for(i = 0; i < 4; i++)
{
m_to_2[i] = new int[4];
m_to_2[i][0] = m_to_2[i][1] = m_to_2[i][2] = m_to_2[i][3] = 0;
}
m_to_3 = new int*[4];
for(i = 0; i < 4; i++)
{
m_to_3[i] = new int[4];
m_to_3[i][0] = m_to_3[i][1] = m_to_3[i][2] = m_to_3[i][3] = 0;
}
m_to_4 = new int*[4];
for(i = 0; i < 4; i++)
{
m_to_4[i] = new int[4];
m_to_4[i][0] = m_to_4[i][1] = m_to_4[i][2] = m_to_4[i][3] = 0;
}
m[0][0]=0; m[0][1]=1; m[0][2]=1; m[0][3]=1;
m[1][0]=1; m[1][1]=0; m[1][2]=1; m[1][3]=0;
m[2][0]=1; m[2][1]=1; m[2][2]=0; m[2][3]=1;
m[3][0]=1; m[3][1]=0; m[3][2]=1; m[3][3]=0;
std::ofstream fout("MatrixData.txt");
if(fout.fail())
{
cout << "Could not create matrix data file" << "\a\n";
getch();
}
Multiply(m,m,4,m_to_2);
PrintMatrix(m_to_2,4);
fout << "M squared" << "\n";
WriteMatrixToFile(m_to_2,4,fout);
fout << "\n\n";
cout << endl << endl;
getch();
Multiply(m,m_to_2,4,m_to_3);
PrintMatrix(m_to_3,4);
fout << "M cubed" << "\n";
WriteMatrixToFile(m_to_3,4,fout);
fout << "\n\n";
cout << endl << endl;
getch();
Multiply(m,m_to_3,4,m_to_4);
PrintMatrix(m_to_4,4);
fout << "M to fourth power" << "\n";
WriteMatrixToFile(m_to_4,4,fout);
fout << "\n\n";
cout << endl << endl;
getch();
return 0;
}
//Note that when doing the matrix math out on paper, I usually traverse down the rows staying in the same column
//(i.e making the outer for loop 'column' instead of 'row') but the results are the same
void Multiply(int ** inputmatrix1,int ** inputmatrix2,int size,int ** outputmatrix)
{
for(int col = 0; col < size; col++)
{
for(int row = 0; row < size; row++)
{
for(int x = 0; x < size; x++)
{
outputmatrix[row][col] += inputmatrix1[row][x] * inputmatrix2[x][col];
}
}
}
}
Here is the output written to file:
Code:
M squared
3 1 2 1
1 2 1 2
2 1 3 1
1 2 1 2
M cubed
4 5 5 5
5 2 5 2
5 5 4 5
5 2 5 2
M to fourth power
15 9 14 9
9 10 9 10
14 9 15 9
9 10 9 10
and I posted a drawing of what the arrangement of such tiles might look like
I'm trying to come up with a more complicated example that involves about 100 tiles and also a way to 'solve' for the path. I'm not sure how computationall expensive it will be. The work I've shown above can be pre computed, but it doesn't actually solve for the path as of yet, just shows if there is a connection and how many ways you can get there (but, once it is computed, the only real problem is a memory foot pritn which can be combated by using a smaller sized variable, or just use bitfields which will say yes or no there's a connection but will not say how many ways it can be done)
Originally Posted by Salem
