Langton's Ant Algorithm

Question

The problem of Langton's Ant is simple. An ant walks a board with white and black squares.

At a white square, turn 90° right, flip the color of the square, move forward one unit
At a black square, turn 90° left, flip the color of the square, move forward one unit

When the "game" starts the board is all white.

I have implemented the simulation but has a really ugly solution for walkning and turning that I need help improving. Right now the walk is as follows:

if (dir == "NORTH") {
    // Walk up
} else if (dir == "EAST") {
    // Walk right
} else if (dir == "SOUTH") {
    // Walk down
} else if (dir == "WEST") {
    // Walk left
}

And the function for changing direction:

private void turn(String leftOrRight){
    if(dir == "NORTH" && lor == "RIGHT" ){
        dir = "EAST";
    } else if (dir == "NORTH" && leftOrRight == "LEFT" ){
        dir = "WEST";
    } else if (dir == "EAST" && leftOrRight == "RIGHT" ){
        dir = "SOUTH";
    } else if (dir == "EAST" && leftOrRight == "LEFT" ){
        dir = "NORTH";
    } else if (dir == "SOUTH" && leftOrRight == "RIGHT" ){
        dir = "WEST";
    } else if (dir == "SOUTH" && leftOrRight == "LEFT" ){
        dir = "EAST";
    } else if (dir == "WEST" && leftOrRight == "RIGHT" ){
        dir = "NORTH";
    } else if (dir == "WEST" && leftOrRight == "LEFT" ){
        dir = "SOUTH";
    }
}

I have thought about using ints instead of strings, but not quite sure how i should do it. Any help or hints is appreciated.

EDIT: Now I have changed some. I Created an Ant class that has variables

int x, int y, Direction dir

And run it with the following method:

private void runAnt(Ant ant) {
    int x = ant.getX();
    int y = ant.getY();

    // Check rule 1
    if (matrix[x][y] == true) {
        matrix[x][y] = false;
        w.setDot(x, y, Color.WHITE);
        ant.setDirection(ant.getDirection().right());

    // Check rule 2
    } else if (matrix[x][y] == false) {
        matrix[x][y] = true;
        w.setDot(x, y, Color.BLACK);
        ant.setDirection(ant.getDirection().left());
    }

    // Moves one unit forward according to direction.
    if (ant.getDirection().equals(Direction.N)) {
        ant.setY((ant.getY() - 1 + wSize) % wSize);

    } else if (ant.getDirection().equals(Direction.E)) {
        ant.setX((ant.getX() + 1) % wSize);

    } else if (ant.getDirection().equals(Direction.S)) {
        ant.setY((ant.getY() + 1) % wSize);

    } else if (ant.getDirection().equals(Direction.W)) {
        ant.setX((ant.getX() - 1 + wSize) % wSize);
    }
}

And my very first enum:

public static enum Direction {
    N, E, S, W;
    private static Direction[] vals = values();

    public Direction right() {
        return vals[(this.ordinal() + 1) % vals.length];
    }

    public Direction left() {
        return vals[(this.ordinal() + vals.length - 1) % vals.length];
    }
}

Please read this carefully: http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java — Mat, Jul 23 '13 at 17:18
Also try using a boolean `isMovingLeft`. It'll make toggling easier. — Dan Pichelman, Jul 23 '13 at 17:19
Use `enum` or constants, using tons of similar literals is scary & error prone. — Display Name, Jul 23 '13 at 17:25

score 5 · Accepted Answer · edited May 23 '17 at 11:51

5

Combine using an enum with next() and prev() functions as explained in this answer. Then a right turn is just a next() call and a left turn is a prev() call.

edited May 23 '17 at 11:51

Community

1
1

answered Jul 23 '13 at 17:22

Jim Garrison

85,615
20
155
190

1

+1, I was just writing the same answer! Would probably rename `next()` and `prev()` to `left()` and `right()` though. – DannyMo Jul 23 '13 at 17:25
Thanks for your answer. I tried using your example. Can you check my update and see if i'm on the right track? – Goatcat Jul 24 '13 at 08:53
Looks good to me. You correctly handled the index going negative :-) – Jim Garrison Jul 24 '13 at 16:31

score 3 · Answer 2 · answered Jul 23 '13 at 17:19

3

You aren't going to get the results you expect when you use == to compare Strings in Java. Use the equals method instead.

I'd consider defining an enum for NORTH, SOUTH, EAST, and WEST.

answered Jul 23 '13 at 17:19

Bill the Lizard

398,270
210
566
880

Check my update. Is this what you meant? Is there other things that can be done in a smarter way? – Goatcat Jul 24 '13 at 08:56
@Goatcat I haven't tried running it, but that definitely looks much better. – Bill the Lizard Jul 24 '13 at 11:19

score 2 · Answer 3 · answered Jul 23 '13 at 17:25

2

Assign an int to each direction(go clockwise):

NORTH = 0;
EAST = 1;
SOUTH = 2;
WEST = 3;

Assign left as -1; right as 1:

LEFT = -1;
RIGHT = 1;

Then you can have a simple function to change directions:

private void turn(int leftOrRight){
    dir = (dir + leftOrRight) % 4;
}

This is assuming you don't want to use enums, for whatever reason.

answered Jul 23 '13 at 17:25

Geobits

22,218
6
59
103

Isn't this basically a bit mask? – Slater Victoroff Jul 23 '13 at 17:26
Somewhat, but simpler to understand if you don't grok bitshifts. – Geobits Jul 23 '13 at 17:31
Fair enough. Seems reasonable. I still think this is more elegant than an enum, but I guess it's less typical. – Slater Victoroff Jul 23 '13 at 17:32
This is basically the same as @JimGarrison's answer, but less type-safe since it's using ints instead of an enum. – DaoWen Jul 23 '13 at 17:33
True, and I upvoted his. Judging from the use of literals in the OP, I assumed type safety wasn't a huge concern, and went with the simplest-to-understand answer. – Geobits Jul 23 '13 at 17:36
@Geobits - I think the only reason type safety doesn't seem like a big concern in the OP's code is because he doesn't know any better. – DaoWen Jul 23 '13 at 17:46

score 1 · Answer 4 · edited May 23 '17 at 12:14

Consider using an enum instead of string literals for NORTH, SOUTH, etc.

Enumerations are type-safe, so the compiler will warn you if you accidentally type SUOTH instead of SOUTH. In addition, enum instances can be safely compared with == (barring some weird edge cases involving serialization). The way you're comparing strings with == instead of equals right now could cause some potential problems depending on where dir and leftOrRight come from. Take a look at this answer for an explanation of == vs equals on strings.

Strings, enums and ints are all supported in the switch construct, so you can also consider using that instead of the if/else branches to make the code a little cleaner.

score 1 · Answer 5 · answered Mar 27 '19 at 01:21

1

If your direction was stored as an dx,dy displacement such as {0, -1} Then turning left and right is :

Swap dx <=> dy

followed by either of :

2a. dx=-dx, or

2b. dy=-dy

(left and right turns)

No case statements, so it's simple and efficient. Simply x+=dx, y+=dy to move forwards - and use the swap/negate trick shown, to rotate.

Why needlessly overcomplicate things : /

answered Mar 27 '19 at 01:21

Langtons Aunt

11
1

I am happy that you found an efficient solution! – Goatcat Mar 27 '19 at 10:03

Slater Victoroff · Answer 6 · 2013-07-23T17:25:38.927

I feel like there's an elegant solution to be had here by using bitmasking. If you do that, then all of your turn operations could be done with simple bit operations instead. There's a really great tutorial on using bitmasks here: http://www.vipan.com/htdocs/bitwisehelp.html

For instance, if you represent your direction as a 4-bit number and turning as a simple boolean, then you could do this all in a single if/else statement:

if (leftOrRight == 0){
    //right shift one bit
}
else if (leftOrRight == 1){
    //left shift one bit
}

Alternately you could just have your left/right indicator be either 1 or -1 and just left shift by you indicator on every turn.

Java has no 4-bit numbers so shifting or actually rotating is is bit ugly. But it works fine when using a 32bit int: http://ideone.com/htgs2A (oops, rotation should be inverted at some point) — zapl, Jul 23 '13 at 18:04

score 0 · Answer 7 · edited May 23 '17 at 12:32

0

I would use an enum. Such as:

enum Directions {
    NORTH, 
    SOUTH, 
    EAST, 
    WEST
}

If you use Java 6 you can also use switches with that.

Oh, and also, never compare String with ==. Use equals. See reason here.

edited May 23 '17 at 12:32

Community

1
1

answered Jul 23 '13 at 17:19

Mena

47,782
11
87
106

Langton's Ant Algorithm

7 Answers7