Category Archives: Algorithms

Make It Quick #4 – Stupid AI for Tic-Tac-Toe

It doesn’t sound like much, but I added a random computer player to the Tic-Tac-Toe game I made in an earlier MIQ. I had to refactor the entire application to be less of a monumental kludge and more object oriented. Then I could make the computer select a random move from the list of possible moves. Again, this took closer to 30 minutes than 15.

Here it is: http://jollyninja.com/Games/TicTacToe2015-06-08/

TicTacToe2

Midpoint Displacement Algorithm in Processing

This is the most basic possible algorithm to generate a “plasma” height map. Using the Midpoint Displacement Algorithm. Programmed in Processing. It doesn’t look too bad.

Plasma

 

You can see some grid artifacts here, so I’ll do a version of the Diamond-Square Algorithm soon.

 

void setup()
{
 size(N, N);
 noSmooth();
 noLoop();
 gHeights = new float[N][N];
}
final int N = 257;
float [][] gHeights;
void draw() {
 gHeights[ 0][ 0] = random(0.0, 1.0);
 gHeights[ 0][N - 1] = random(0.0, 1.0);
 gHeights[N - 1][ 0] = random(0.0, 1.0);
 gHeights[N - 1][N - 1] = random(0.0, 1.0);
 populateRect(0, 0, N - 1, N - 1);

 drawRect();
}
void populateRect(int a, int b, int c, int d) {
 int w = c - a;
 int h = d - b;

 if (w <= 1 || h <= 1) return;

 // (a, b) is top left
 // (c, d) is bottom right

 int ac = (a + c) / 2; // top middle
 int bd = (b + d) / 2; // side middle

 //top
 gHeights[ac][b] = (gHeights[a][b] + gHeights[c][b]) / 2.0;

 // left
 gHeights[a][bd] = (gHeights[a][b] + gHeights[a][d]) / 2.0;

 // right
 gHeights[c][bd] = (gHeights[c][b] + gHeights[c][d]) / 2.0;

 // bottom
 gHeights[ac][d] = (gHeights[a][d] + gHeights[c][d]) / 2.0;

 // middle
 gHeights[ac][bd] = (gHeights[ac][b] + gHeights[ac][d]) / 2.0 + random(-0.5, 0.5) * (h + w) / (N + N);
 gHeights[ac][bd] = constrain(gHeights[ac][bd], 0.0, 1.0);

 // top left
 populateRect(a, b, ac, bd); 
 // top right
 populateRect(ac, b, c, bd); 
 // bottom left
 populateRect(a, bd, ac, d); 
 // bottom right
 populateRect(ac, bd, c, d); 
}
void drawRect() {
 for (int x = 0; x < N; x++) {
   for (int y = 0; y < N; y++) {
     stroke(gHeights[x][y] * 256);
     point(x, y);
   }
 }
}