Flock/Shoal Simulation

The birds and the bees (and fish)

There are many animals that exhibit flocking behaviour, including humans. This is an attempt to recreate that behaviour using three simple rules:

  • Separation - avoid crowding neighbors (short range repulsion)
  • Alignment - steer towards average heading of neighbors
  • Cohesion - steer towards average position of neighbors (long range attraction)

Unfortunately, due to the nature of the problem this is an O(n^2) algorithm, as every fish/bird/thing has to check the position and velocity of every other entity (without doing special trickery like bin-lattice subdivision). Here's the link to the source code. If you're familiar with Java and LibGDX this should be pretty simple to run and modify. If not, it might be worth writing this in Javascript, I've seen some pretty successful examples online.

So what are the uses except for making pretty (but intensive) screensavers? Well I guess a similar, but probably more complex, simulation could be used to see how crowds of people react in certain situations. I can't for the life of me find the source, but I remember reading that putting a pillar in the middle of a doorway can speed up entry and exit of a tube station, as it forces commuters to line up. At present however, it just makes for a pretty video.


Experimenting with Edge Detection

Java Edge Detection

I'm experimenting with simple edge detection in Java. The result above is from an incredibly simple algorithm which subtracts the highest contrast neighbouring pixel from each pixel in the image: for each pixel, find the neighbour with the highest contrast relative to the original pixel and subtract its value from the original pixel. Pixels surrounded by similarly valued pixels will get a value of 0 whereas pixels with high contrast neighbours will get a higher value.

Where next? There's a lot that can be done to improve this simple algorithm, starting with pre-processing like increasing the contrast on the original image. I'd eventually like to turn this into a 'Camscanner' style application, which transforms an image of a document into an upright rectangular viewing format. To do this I'd need to find the four edges of the largest rectangle in the image (very likely to be the document), then use a simple transformation to do the rest of the work.


Adventures with Markov Chains

A Markov chain is an incredibly simple model describing a sequence of events in which the probability of each event depends only on the state attained in the previous event. And yes I did lift that from Wikipedia but it can explain it much better than I. Basically the idea is that you have a number of states, like whether it's raining or not, and the probability of a certain state tomorrow only depends on the state today. In other words the probability of it raining tomorrow depends on whether it's raining today.

I've used this model to generate text in particular styles. You feed the model a huge amount of text, and it builds up a probability table of what the next word may be given the previous word. You then use a random number generator to generate chains of text.

I experimented a bit with order and token choice. I found that training the model on individual letters produced pronouncable garbage. Any words more than a couple of letters long were not real words, it was incomprehensible but pronouncable. If I wanted to make an English-sounding fake language this is probably how I'd do it. I wanted some generated text chains that made sense, however, so I trained it on individual words instead. I found that a first order model (looking back only one word) didn't produce very good sentences, and a third-order model (looking back 3 words) tended to reproduce the input data because I didn't have enough of it. The second-order model seemed like a good middle ground.

I trained the model on a variety of corpuses. Generated wine tasting notes were suprisingly believable, as were generated Trump tweets and dreams. Here are some generated wine-tasting notes:

"This wine combines weight and a low altitude vineyard. It's packed with both power and makes it refreshing too. Drink now."

"A kitchen-sink blend of 90% Sangiovese and the wine is still closed but delivers a creamy, textural wine. Those body powder and lime aromas are less attractive."

"The voluble, opinionated Jean-Luc Colombo has crafted this classic Gewurztraminer. It's plush on the finish."

"Clove aromas are outweighed by a touch of volatility along with dried apricot while the palate shows ripe aromas of sweet oak tones that will age well. Drink from 2016."

These are, of course, hand-picked, but the generated sentences were of unreasonably good quality in general. The wine-tasting notes worked especially well, which may be because I had a huge amount of data.


My Attempt at a Chess Bot

My bot vs a randomly moving one

I made a chess bot in Java. Really I made a variety: randomly moving pieces around, greedily choosing the best next move, and finally using the minimax algorithm with alpha-beta pruning. The biggest challenge here was not the bot itself, but making a chess engine that efficiently generates possible moves, because even with alpha-beta pruning there is a massively fast growth in possible moves as you look more turns ahead. Consider generating moves for White's bishop. Not only do you need to generate the possible board positions, but for each board position you need to check that your King is not in check, or it is an illegal move. To do this you need to scan through the enemy pieces and see if, with the bishop in the new position, taking the white King is legal. It's easy to see how fast this grows as you go down the minimax tree.

I had grand plans to pit the bot against itself over and over again, until I realised that this deterministic machine would result in identical games on subsequent tries.

The result is a chess bot that beats me at chess, although I'm not the best benchmarking tool.


Easy Parallax Stars

Easy Parallax Stars

Don't these stars look great

I spent a long time messing around with chunks, loading, unloading, pooling, etc. before a friend suggested I came up with a much simpler way of getting parallax stars working easily.

Generate a load of random points in a square, each with a random z-value. Scale each point's speed according to the z-value to simulate the parralax (this way you can have as many layers of parallax as you want and to add more you can just increase the range of the z-value). Whenever a star leaves the screen, just spawn it in on the opposite side of the square. As long as your square is slightly bigger than the screen size then that's it, amazing-looking amazingly simple parallax stars. If you scale the star speed in the opposite way i.e. closer stars go faster then you get a king of underwater-y effect. Could be a nice look for a diving game.