Картограф для Minecraft на Python

Есть такая замечательная игра — Minecraft. В целом очень напоминает Lego — можно строить из различных кубиков всё что душа пожелает. На Youtube можно найти много очень впечатляющих построек. Более того, строить можно совместно на специальных серверах.

В общем, в последнее время я довольно много играю в Minecraft

Одна из особенностей игры — процедурная генерация ландшафта. Т.е. в каком бы направлении Вы ни пошли, окружающий пейзаж будет создаваться по мере надобности. Общая площадь карты в Minecraft в несколько раз больше площади поверхности Земли. Сама карта подгружается частями — держать в памяти такое количество данных целиком просто бессмысленно. Недавно я от нечего делать решил написать парсер файлов Minecraft, чтобы сделать карту своей территории (я знаю что для этого есть инструменты, тот же c10t, но самому же всегда интереснее). Чтобы не было скучно, писать решил на Питоне

Вообще к Питону я приглядываюсь достаточно давно, и русскоязычное издание Learning Python лежит у меня под столом уже полгода. Но до сих пор ничего сложнее пробного hello world я на нём не писал. Парсер и картограф будут неплохим началом.

Формат файлов

Карта в Minecaft, как понятно из вышеприведённого описания, может быть очень большой. Поэтому она разбита на куски (chunks) размером 16 x 16 x 128 метров — этакие высокие колонны. Чанки сложены в директории по хешу их координат. В целом всё выглядит так: в корневой папке лежит основной файл level.dat, в котором хранится в т.ч. random seed для генерации ландшафта, и 64 папки верхнего уровня. В каждой из них находится по 64 папки второго уровня, в которых и лежат gzip-нутые файлы чанков.

Я уже писал что чанк отправляется в папку, соответствующую хешу его координат. Вот так можно вычислить этот хеш:

def base36encode(number):
    sign = ''
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')
    if number < 0:
        #raise ValueError('number must be positive')
		sign = '-'
		number = number * -1

    alphabet = '0123456789abcdefghijklmnopqrstuvwxyz'

    base36 = ''
    while number:
        number, i = divmod(number, 36)
        base36 = alphabet[i] + base36

    return sign + base36 or sign + alphabet[0]

chunk_x = -13
chunk_y = 44
	
filename = base36encode(divmod(chunk_x, 64)[1])  + "\\" + base36encode(divmod(chunk_y, 64)[1]) + "\\c." + base36encode(chunk_x) + "." + base36encode(chunk_y) + ".dat"

print filename # выведет 1f\18\c.-d.18.dat

Код для преобразования в base36 взят с Википедии и допилен для отрицательных чисел.

Сам чанк (уже разархивированный) записан в специальном формате, называемом named binary tag — по сути, двоичный файл с именованными полями. В файле могут встречаться 11 видов стандартных тегов, последний из которых, compound, может содержать произволное количество других тегов (в том числе и типа compound). Стало быть, у нас будут структуры произвольного уровня вложенности.

Внутри самого файла, в поле с именем Blocks находится массив из 32768 байт — это и есть наша карта. На каджый блок, соответственно, отводится по одному байту, блоки идут вертикальными колоннами снизу вверх, с востока на запад и с севера на юг.

Кроме блоков в файле хранятся сущности, принадлежащие чанку — например, монстры. Но нас пока что это не интересует.

Разбор файла

Вначале я просто вырезал из файла байт за байтом, сверяясь со спецификацией формата, но когда освоился, переписал парсер нормально. Всего получилось 100 строк. Парсер целиком можно найти здесь. Основная функция выглядит так:

def read_tag(chunk):
	type = ord(chunk.read(1)) # Chunk starts with "10" byte
	print "Found tag type: %s" % (tag_types[type], )
	if (type > 0):
		name = read_string(chunk)
		if (name != None):
			print "Name: %s" % name
	else:
		name = ''
		
	payload = None
	# Read payload of each tag. "0" tag has no payload
	if (type == 1):
		payload = read_byte(chunk)
	elif (type == 2):
		payload = read_short(chunk)
	elif (type == 3):
		payload = read_int(chunk)
	elif (type == 4):
		payload = read_long(chunk)
	elif (type == 5): # no separate float for now
		payload = read_long(chunk)
	elif (type == 6): # no separate double for now
		payload = read_long(chunk)
	elif (type == 7):
		payload = read_byte_array(chunk)
	elif (type == 8):
		payload = read_string(chunk)
	elif (type == 9):
		payload = read_list_payload(chunk)
	elif (type == 10):
		payload = read_compound(chunk)
		
	return (type, name, payload)

Каждый тег состоит из байта, указывающего на его тип, pascal-строки с именем тега и содержанием, которое зависит от типа тега. Нулевой тег — особый, ему не положено даже имя. Он завершает списки тегов внутри compound-тега.

Сначала мы читаем тип, если он ненулевой — читаем ещё и имя, и достаём содержание согласно типу. Чтение содержания для каждого типа я выделил в отдельную функцию (кроме типов 4,5 и 6, которые хранят длинные числовые значения в том или ином виде). Функция read_list_payload должна по хорошему называться read_list, но в принципе и так сойдёт.

Если мы прогоним этот скрипт по файлу какого нибудь чанка (предварительно распаковав его Winrar’ом или 7zip’ом), мы увидим что теги внутри compound-тега Level идут не в том порядке, который указан в спецификации. Т.к. все теги помечены именем, найти тег Blocks мы всё равно сможем, просто не получится взять его по заранее вычисленному смещению.

Вот примерная схема одного чанка:

Found tag type: Compound
	Found tag type: Compound
	Name: Level
		Found tag type: Byte array
		Name: Data
		Array length: 16384
		Found tag type: List
		Name: Entities
		0 items of type Byte
		Found tag type: Long
		Name: LastUpdate
		Found tag type: Int
		Name: xPos
		Found tag type: Int
		Name: zPos
		Found tag type: List
		Name: TileEntities
		0 items of type Byte
		Found tag type: Byte
		Name: TerrainPopulated
		Found tag type: Byte array
		Name: SkyLight
		Array length: 16384
		Found tag type: Byte array
		Name: HeightMap
		Array length: 256
		Found tag type: Byte array
		Name: BlockLight
		Array length: 16384
		Found tag type: Byte array
		Name: Blocks
		Array length: 32768
	Found tag type: End
	Read 12 elements in compound
Found tag type: End
Read 2 elements in compound

Для обрамляющего compound-тега названия нет — на соответствуюшем месте просто записан нулевой байт (длина строки — 0).

Разбираем блоки

Получив наконец блоки, мы увидим что в результате python преобразовывает массив байт в строку. Нас это вполне устраивает. Теперь нам надо сориентироваться в их пространственном расположении. Для начала, Minecraft своеобразно подходит к определеению осей координат: ось Y у него вертикальна. Вики по Minecraft нам подсказывает, что в массиве блоков можно найти нужный элемент по такой формуле:

Blocks[ y + ( z * ChunkSizeY(=128) + ( x * ChunkSizeY(=128) * ChunkSizeZ(=16) ) ) ]

Находим тег с блоками в результатах разбора:

for level in output[2]:
	# skip end tags
	if (level[0] == 0): 
		continue
		
	for tag in level[2]:
		if (tag[0] == 0):
			continue
		print tag[1]
		if tag[1] == "Blocks":
			blocks = tag[2]

Система типов Питона мне пока немного непривычна, поэтому я использовал простые кортежи и списки. Хотя, по хорошему, теги надо было бы сохранять в виде словаря — их порядок нам всё равно не важен, а обращаться по имени тега было бы легче.

Вооружившись приведенной выше формулой, сделаем срез чанка на высоте, к примеру, 16. В обычном ландшафте это как раз самая толща породы внизу, с редкими пещерами и лавой.

for z in range(0, 16):
  for x in range (0, 16):
    print ord(blocks[ y + ( z * 128 + (x * 128 * 16)) ]),
  print 

Фиксируем высоту (координату y) на 16, и выводим получившуюся матрицу чисел 16 на 16. Потом смотрим в таблицу значений блоков, чтобы узнать что именно мы увидели.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 15 15 1 1 1 1 1 1
1 1 1 1 1 1 1 1 15 15 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1 1 1 1 73 1 1 1 1
3 1 1 1 1 1 1 1 1 1 73 73 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 73 73
1 1 1 1 1 1 1 1 56 1 1 1 1 1 73 15
1 1 1 1 1 1 1 1 1 56 1 1 1 1 1 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Видим много камня и немного руды, сгруппированной в депозиты. Что ж, похоже на правду Теперь надо отобразить результат покрасивее.

Генерация карты

Чтобы сохранять изображения, нам потребуется Python Imaging Library. Устанавливается она без проблем. После установки можно будет приступить к генерации карты среза.

Изображения мы не задумываясь возьмём прямо из стандартного набора текстур Minecraft Идём в %appdata%\.minecraft, распаковываем minecraft.jar и достаём оттуда terrain.png. Выглядит он вот так:

Нам надо нарезать этот набор на аккуратные квадраты 16 на 16, и составить из них новое изображение. Вначале получаем тайлы:

import Image

def get_cropbox(x, y):
	return (x*16, y*16, x*16 + 16, y*16 + 16)

terrain = Image.open("terrain.png")

stone = terrain.crop(get_cropbox(0,0))
dirt = terrain.crop(get_cropbox(2,0))
gravel = terrain.crop(get_cropbox(3,1))
sand = terrain.crop(get_cropbox(2,1))
coal = terrain.crop(get_cropbox(2,2))
iron = terrain.crop(get_cropbox(1,2))
gold = terrain.crop(get_cropbox(0,2))
redstone = terrain.crop(get_cropbox(3,3))
diamond = terrain.crop(get_cropbox(2,3))

Вот примерно так. Функция get_cropbox написана для вычисления координат вырезания и вставки. Это не все блоки, которые могут встретиться в игре, но с файлом текстур дополнить этот список Вы сможете и самостоятельно. Я пока остановлюсь на том что может встретиться под землёй.

Теперь, примерно так же как мы выводили текстовые значения блоков, мы заполняем изображение карты:

map = Image.new("RGB", (256, 256))

for x in range(0, 16):
  for z in range (0, 16):
	block_id = ord(blocks[ y + ( z * 128 + (x * 128 * 16)) ])
	if block_id == 1:
		map.paste(stone, get_cropbox(x, z))
	elif block_id == 3:
		map.paste(dirt, get_cropbox(x, z))
	elif block_id == 13:
		map.paste(gravel, get_cropbox(x, z))
	elif block_id == 12:
		map.paste(sand, get_cropbox(x, z))
	elif block_id == 16:
		map.paste(coal, get_cropbox(x, z))
	elif block_id == 15:
		map.paste(iron, get_cropbox(x, z))
	elif block_id == 14:
		map.paste(gold, get_cropbox(x, z))
	elif block_id == 73:
		map.paste(redstone, get_cropbox(x, z))
	elif block_id == 56:
		map.paste(diamond, get_cropbox(x, z))
		
try:
	map.save('.\map.png', 'PNG')
except:
	print "Something went wrong on save"

Здесь опять не все идентификаторы блоков, и если встретится что то незнакомое, на карте будет просто чёрный квадрат. И ещё тут надо помнить про систему координат, в частности, не путать y и z . В результате этих манипуляций должен получиться PNG-файл со срезом карты:

Вот как то так Это конечно не полноценный картограф, но уже неплохое начало. На его основе можно например сделать маленький скрипт для поиска наиболее богатых рудой чанков или оптимальной глубины шахты.

Ссылки по теме

• Официальный сайт Minecraft
• Полный код картографа
• Структура файла NBT
• Структура чанка
• Список блоков с их ID
• AI, Minecraft и Node.js (пишем сервер для Minecraft)