Реализации алгоритмов/Муравей Лэнгтона

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

Муравей Лэнгтона — это двумерный клеточный автомат с очень простыми правилами, изобретённый Крисом Лэнгтоном. Муравья можно также считать двумерной машиной Тьюринга с 2 символами и 4 состояниями.

Реализации[править]

Python[править]

Муравья Лэнгтона с помощью библиотеки Pygame:

import time
import pygame
from time import sleep
from os import system # модули


bs = 5 # размер блока
run = True # переменная окна
color0 = [255, 255, 255] # белый
color1 = [0, 0, 0] # чёрный
color2 = [100, 100, 100] # серый, пройденные белые блоки
rot = 3 # поворот муравья


def mapcreate(map): # показ массива карты
    window.fill(color0) # заполнение фона
    inx = 0 # позиция массива x
    iny = 0 # позиция массива y
    sizey = bs * iny # положение клетки по y
    sizex = bs * inx # положение клетки по x
    for list in map: 
        for box in list:
            if box == 0:
                inx += 1
            elif box == 1: # черные блоки
                #pygame.draw.circle(window, color1, (sizex + bs // 2, sizey + bs // 2), bs) # круги
                pygame.draw.rect(window, color1, (sizex, sizey, bs, bs)) # квадраты
                inx += 1
            elif box == 2: # серые, пройденные блоки
                #pygame.draw.circle(window, color2, (sizex + bs // 2, sizey + bs // 2), bs)
                pygame.draw.rect(window, color2, (sizex, sizey, bs, bs))
                inx += 1

            sizex = bs * inx
        iny += 1
        sizey = bs * iny
        inx = 0
        sizex = bs * inx


n = 0.1 # время
auto = False # авто-режим
mw = 200 # количество клеток в ширину
mh = 200 # количество клеток в высоту
mhl = []
mwl = []

for i in range(mh): # заполнение массива
    for t in range(mw):
        mwl.append(0)
    mhl.append(mwl)
    mwl = []
map = mhl # карта с белыми и чёрными клетками
x = round(len(map[1]) / 2) * bs # центр положения муравья по x
y = round(len(map) / 2) * bs # центр положения муравья по y
print(x, y)

def step():
    global rot, x, y
    if rot == 4: # проверка максимального и минимального кровня поворота
        rot = 0
    elif rot == -1:
        rot = 3

    if rot == 0: # проверка поворотов
        y -= bs
    elif rot == 1:
        x += bs
    elif rot == 2:
        y += bs
    elif rot == 3:
        x -= bs


def next(): # переход на следующий шаг
    global rot
    nx = int(x / bs)
    ny = int(y / bs)
    if map[ny][nx] == 1: # проверка блока под муравьём
        rot -= 1
        map[ny][nx] = 2
        step()
    else:
        rot += 1
        map[ny][nx] = 1
        step()


pygame.init()
window = pygame.display.set_mode([mw * bs + 1, mh * bs + 1]) # размер окна
pygame.display.set_caption('game') # название окна
while run:
    for event in pygame.event.get():
        if event.type == pygame.QUIT: # при нажатии на крест игра будет выключаться
            run = False
        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_q: # следующий шаг
                next()
            elif event.key == pygame.K_f: # отчистка карты
                mhl = []
                mwl = []
                for i in range(mh):
                    for t in range(mw):
                        mwl.append(0)
                    mhl.append(mwl)
                    mwl = []
                map = mhl
            elif event.key == pygame.K_BACKSPACE: # выход
                run = False
            elif event.key == pygame.K_t: # ускорение времени
                n += 0.1
            elif event.key == pygame.K_g: # замедление времени
                n -= 0.1
            elif event.key == pygame.K_x: # переход в авто-обновление
                if auto:
                    auto = False
                else:
                    auto = True
    if auto: # авто-обновление
        sleep(n)
        next()
    mapcreate(map) # отрисовка клеток
    pygame.draw.rect(window, [255, 0, 0], (x, y, bs, bs), 2) # муравей
    pygame.display.flip()
    pygame.display.update() # обновление дисплея
pygame.quit()