Snakes on a Manifold: Part 1

Have you every wondered what it would be like to live on a Mobius Strip? I was playing around with some polygonal schemas for various topologies awhile back and I was reminded of the game ‘Snake’ which I used to play on my dad’s phone when I was a kid. I realized that the game was set on a torus. So for fun, and to illustrate a talk I was giving, I decided to implement this game in python using a module called pygame where you could play with a variety of topologies.

It looks like this:

In this post we will implement the underlying logic of the game, and in the next post we will implement the input/output part with pygame. If you just want the code, click here.

The Code

We will create a Snake class, and a Snake will be composed of Snake_Segment objects. Each Snake_Segment is responsible for its behind, the Snake_Segment immediately behind it, so we have a sort of linked list.

Let’s start with the Snake_Segment.

class Snake_Segment(object):
    def __init__(self, initial_position, behind=None):
        self.position=initial_position #Position on the board.
        self.previous_position = initial_position #Keep track of to tell tail to move there.
        self.direction=None #This is for the head segment.
        if behind == None:
            self.behind=self #The tail of the snake.
        else:
            self.behind=behind

    def move(self, target_coords):
        self.previous_position = self.position
        self.position = target_coords
        #Once the segment moves, it passes along the message to its behind, along with its
        #previous coordinates.
        if not self.behind==self: #Checks that it is not the tail of the snake.
            self.behind.move(self.previous_position)

Now we can build a Snake. Its actions are to move and grow.

class Snake(object):
    def __init__(self, initial_position, opposite_directions, get_next_coords):
        #It is important to keep track of opposite_directions
        #because unless the Snake always moves forwards.
        #The head is the segment at the end of self.segments.
        self.segments=[]
        self.segments.append(Snake_Segment(initial_position))
        self.direction=None
        self.length=1
        #The snake keeps track of the head's board coordinates.
        self.head_position=initial_position
        self.opposite_direction = opposite_directions
        #We pass the snake a function from the Board class to tell it where to move next.
        self.get_next_coords =get_next_coords

    def move(self, direction=None):
        if direction==None:
            #This is the default action, the snake keeps going in the same direction.
            direction = self.direction
        elif self.direction==None:
            #This happens at the beginning before its first movement.
            self.direction=direction
        elif direction == self.opposite_direction[self.direction]:
            #Do nothing in this case because the snake only moves forwards.
            direction = self.direction
        else:
            #The snake turns.
            self.direction=direction
        #Now we get new coordinates for the head based on the direction.
        target_coords, self.direction = self.get_next_coords(self.head_position,
                                                             direction)
        #We then tell the head to move, and the command propagates down to the tail.
        self.segments[-1].move(target_coords)
        self.head_position = target_coords

    def grow(self):
        #We grow by adding a segment to the front of the snake,
        #becoming the new head.
        self.segments.append(Snake_Segment(self.head_position,
                                           self.segments[self.length-1]))
        self.length +=1

So now we have a Snake it needs somewhere to sliver, what we will call a Board. This is the most complicated part of the program because it is tasked with incorporating the topological information. This is handled by its get_next_coord method. Its other duty is to generate apples.

class Board(object):
    def __init__(self, size, topology):
        self.size =size
        #The board will be self.size x self.size squares.
        self.grid=[]
        self.topology = topology #A string like 'Disc', 'Torus', etc.
        self.init_topology()
        self.grid_init()
        self.opposite_direction = {'UP':'DOWN', 'DOWN':'UP', 'LEFT':'RIGHT',
                                   'RIGHT':'LEFT'}
    def init_topology(self):
        #The topological information is contained in self.edges, which tells the board
        #which edges are boundary, which edges are identified, and with what orientations.
        #self.edges is a dictionary with keys 'LEFT', 'RIGHT' , 'UP', 'DOWN',
        #and having values of the form ('edge name or boundary', -1/0/1) where -1 represents
        #identification with reversed orientation, 1 identification with orientation preserved and
        #0 for the boundary case.

        if self.topology =='Disc':
            self.edges ={'LEFT':('BOUNDARY',0), 'RIGHT':('BOUNDARY',0),
                         'UP':('BOUNDARY',0), 'DOWN':('BOUNDARY',0)}
        elif self.topology=='Torus':
            self.edges ={'LEFT':('RIGHT',1), 'RIGHT':('LEFT',1),
                         'UP':('DOWN',1), 'DOWN':('UP',1)}
        elif self.topology=='Sphere':
            self.edges ={'LEFT':('UP',1), 'RIGHT':('DOWN',1),
                         'UP':('LEFT',1), 'DOWN':('RIGHT',1)}
        elif self.topology=='Mobius Strip':
            self.edges ={'LEFT':('BOUNDARY',0), 'RIGHT':('BOUNDARY',0),
                         'UP':('DOWN',-1), 'DOWN':('UP',-1)}
        elif self.topology=='Klein Bottle':
            self.edges ={'LEFT':('RIGHT',-1), 'RIGHT':('LEFT',-1),
                         'UP':('DOWN',1), 'DOWN':('UP',1)}
        elif self.topology=='Projective Plane':
            self.edges ={'LEFT':('RIGHT',-1), 'RIGHT':('LEFT',-1),
                         'UP':('DOWN',-1), 'DOWN':('UP',-1)}

    def set_grid(self, coords, value):
        self.grid[coords[0], coords[1]]=value

    def grid_init(self):
        grid=np.zeros(shape=(self.size, self.size))
        #On the grid, 0s represent empty, 1s represent boundary, 2s represent snake and 3s apples.
        if self.edges['LEFT'][0]=='BOUNDARY':
            grid[::,0] = np.ones(shape=self.size)
        if self.edges['RIGHT'][0]=='BOUNDARY':
            grid[::,-1] = np.ones(shape=self.size)
        if self.edges['UP'][0]=='BOUNDARY':
            grid[0] = np.ones(shape=self.size)
        if self.edges['DOWN'][0]=='BOUNDARY':
            grid[-1] = np.ones(shape=self.size)
        self.grid=grid

    def generate_apple(self):
        x=random.randint(0, self.size-1)
        y=random.randint(0, self.size-1)
        if self.grid[x,y]==0: #Makes sure the square is not already occupied.
            self.grid[x,y]=3
            return [x,y]
        else:
            return self.generate_apple()

    def get_next_coord(self, coord, direction):
        #First handles how to move in a direction without worrying about boundaries.
        if direction == 'UP':
            change_coord = [-1,0]
        elif direction =='DOWN':
            change_coord = [1,0]
        elif direction == 'LEFT':
            change_coord = [0,-1]
        elif direction == 'RIGHT':
            change_coord = [0,1]
        else:
            print 'Invalid direction' #Just in case.
        #Calculate new coordinates optimistically.
        potential_new_coords = [coord[i] + change_coord[i] for i in range(2)]

        #First check to see if we are trying to travel through an edge.
        check=False
        if -1 in potential_new_coords:
            check=True
        elif self.size in potential_new_coords:
            check=True
        if not check:
            #We are in the interior so no problems.
            return [potential_new_coords, direction]

        #Now we know we are traveling through some edge,
        #and the direction tells us which.
        edge, orientation = self.edges[direction]
        #If the snake emerges from the LEFT edge, it will then be moving in the RIGHT direction,
        #and so on.
        new_direction = self.opposite_direction[edge]
        #We automatically know one coordinate because we know the new edge.
        left_or_right=False
        if edge=='BOUNDARY':
            print 'Error, boundary case should not happen here.'
        elif edge == 'LEFT':
            left_or_right=True
            potential_new_coords[1]=0
        elif edge =='RIGHT':
            left_or_right=True
            potential_new_coords[1]=self.size-1
        elif edge == 'UP':
            potential_new_coords[0]=0
        elif edge == 'DOWN':
            potential_new_coords[0]=self.size-1
        else:
            print 'Edge invalid'
        #Now we figure out the other coordinate, which depends on either
        #the old row or column, depending on whether the new edge is opposite
        #or perpendicular.
        if edge == self.opposite_direction[direction]:
            opposite=True
        else:
            opposite=False
        #Find out whether we want the old row or old column.
        if left_or_right:
            if opposite:
                coord_component = coord[0]
            else:
                coord_component = coord[1]
        else:
            if opposite:
                coord_component = coord[1]
            else:
                coord_component = coord[0]
        #Now we find out whether the the orientation is flipped.
        if orientation==-1:
            coord_component = self.size-1-coord_component
        if left_or_right:
            potential_new_coords[0]=coord_component
        else:
            potential_new_coords[1]=coord_component
        return [potential_new_coords, new_direction]

And we’re done! Next time we will make this pretty using pygame. If you want to test it before then, you can print the board grid to the console.
The source code is here.