Coding Challenge #89: Langton's Ant

References:

Videos:

Related Coding Challenges:

Timestamps:
0:00 Introduction and setup code!
1:46 Writing the algorithm for the motion of Langton's ant
9:09 Visualizing Langton's Ant
12:33 Debugging and testing!
14:53 Refactoring the code!
20:06 Things to try!
20:46 Outro!

Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound

#langtonsant #cellularautomata #processing #java

[msclrhd]

If you have two ants, they create interesting patterns depending on their positions. As well as the hive (blob) - highway (diagonal line) pattern, they can run a create/destroy loop on a partial hive, or they can start chasing each other in an expanding-collapsing diamond pattern.

It is worth creating an Ant class to support that. You can then extend that to encode the turn behaviour (left, right, no change, 180deg) and/or what colour to change to. These create some interesting behaviours -- I've had some ant variants build a "super highway" of a certain colour in a straight line, then zoom along it (using the "no change" turn rule). Combining ants with different rules is also interesting (but they need to support the same number of colours, otherwise they will stop if they get to an unsupported colour).

[kevnar]

Langton's Car. Set all pixels positions on screen to a random value of either 0, 1, 2, or 3. Set a particle "car" in the middle with an arbitrary velocity vector. On each frame, the car will move to a new position.

if the pixel is 0, increase speed slightly, but never more than maxSpeed.
If the pixel is 1, angle slightly to the right.
If the pixel is 2, decrease speed slightly, but never less than 1.
If the pixel is 3, angle slightly to the left.

Reset the pixel it's on to a new random value so no infinite loops occur, and then update position.

For bonus points, set up a "garage" somewhere (3 sides of a rectangle), and see if the car can drive into it. If you increase the increment of the angle to 90 degrees left or right, the car will drift sideways for a few frames before correcting. Add tire squealing sound effects as needed.

[Bunnys]

Instead of that single direction variable (and the 4 constants and that huge movement function) when just using a vector (dirX, dirY) everything becomes much simpler. Rotating is just swapping dirX and dirY and inverting one of them. Which you invert defines the direction you're rotating.

The movement is just adding dirX to x and dirY to y. Of course we still need the screen edge wrapping.

Something like this:

void Turn(boolean turnRight) {
int tmp = dirX;
if (turnRight) {
dirX = -dirY;
dirY = tmp;
} else {
dirX = dirY;
dirY = -tmp;
}
}
void moveForward() {
x = (x + dirX + width) % width;
y = (y + dirY + height) % height;
}

[paulkerrigan]

I like the beard, man! Your videos are always welcome!

[KitsumiTheFox]

My favorite way to set variables from a 1 or 0 value like this is doing (in this case)
int color = grid[x][y]*255
Since if its 0, it'll be 0 and if its 1, it'll be 255

[AnirudhGiri]

Finally! Processing is back, boys! :D :D

[alairock]

One way I implemented turning was with an array in js:

direction = [0, -1, 0, 1]

Then using some array management:

// turns one way
if (isWhite(img, loc.x + 1, loc.y + 1)) {
// if white, turn right (undoes the first turn that always happens)
// then turns again, effectively turning the way we wanted for this situation

Then if you play with the direction variable values you can come up with some really neat patterns some are just loosely similar to Langton's ant, and others are bizarre recursive/fractal patterns.

Loved this video. Fun inspiration, and had fun writing it for myself in p5!

[mikal_]

I don't even do that much coding, but this is so much fun and so very useful!

[MarkJay]

I'm a simple man, I see new coding train video, I like.

[FriedNoodlee]

I did this myself, and I thought I should see if you made a video on it! You actually did! I totally could've used this when making Langton's Ant haha.

[Bunnys]

I think more interesting would be to encode the two states (0, 1) as (negative, positive). That way to flip the state you literally just have to flip the sign. Further more we could encode how often we visit the same pixel by incrementing (/ decrementing) the pixel value. Now you can use a color code to draw the pixels. I guess we should still draw the "background" either black or white and the "foreground" with our color based on the cells value.

state = grid[x][y];
// flipping
state = -state;
// increment only when positive
if (state >= 0)
state++;
grid[x][y] = state;

The "(state >= 0)" condition also takes care of the initial "0" in the array. So "<=0" is considered white (background) and "> 0" is considered black (foreground)

[nahueljo]

Alright! This challenge was my suggestion! Thanks Daniel <3

[corruptconverter]

In JavaScript, I got it to run at 80 million steps/second, and including WebAssembly, I got it to 200 million/second.

[justgame]

Great video as always, speaking of "ants" could you do a video on an ant colony optimisation algorithm to follow up on your genetic algorithm and machine learning series.

[BedrockGateBreaker]

I've been going through the entire Internet looking for this, I build this in minecraft but couldn't remember what it was called

[gw_mc]

The reason why the image is rotated is because of the initial direction of the ant, if the ant dir is set to 0(up), then the first move will set the dir to 1(right) which makes the image rotated -90 degrees, so the initial dir should be 3(left) so that the first move will be upwards but not to the right.

[kenhaley]

Cool video, Dan. But one of the really amazing and fun things about Langton's Ant is what happens when there are two or more ants running around and interacting. Also, how to accept user input to set the initial position and direction of the ants. Maybe a followup video?

[TylerDunphy]

I played a pixel game and the ants made the same patterns, never knew it was this!

[ABaumstumpf]

Just tried it my self - 106 Lines, the area wrap around, '+' and '-' to change the speed, 'Space' to let it run as fast as it can, and highlighting of the ant.

it can do roughly 25 million iterations a second. was kinda fun using processing again for such a silly thing.

[MatthewHolevinski]

These are my favorite kinds of Coding Train videos!