Autotiling: автоматические переходы тайлов

Буквально только что наткнулся на статью из песочницы о grid-tiling'е и решил написать свой аналог.
Мой метод распределения переходов несколько отличается от упомянутой в той статье.
Начало данной системы положено в небезызвестной игре WarCraft III.

image

На этом скриншоте редактора карт WC3 можно заметить швы, они обозначены красными стрелками. Судя по всему, логика тайлов в этой игре несколько иная, нежели в большинстве игр. Один тайл здесь не занимает целой клетки. Он находится как бы в точке, вокруг которой уже рисуются его углы.

Особенно хорошо это наблюдается со включенной сеткой.

image

Обычно в такой ситуации предлагается разделить тайл на 4 маленьких. Но есть одно но: что делать в подобном случае?

image

Когда все 4 окружающие один квад тайлы разные? Здесь явно видно, что большую часть занимает самый нижний тайл.
Взвесив все за и против, я пришел к своей, достаточно специфичной, системе. Добавим новую сетку, сетку переходов. В ней мы можем хранить, к примеру, тип int. В таком случае у нас будет возможно записать для каждого квада тайлов 16 ID окружающих 4 тайлов с 16 вариантами перехода. Этого более чем достаточно. Нет, если кому-то нужно больше ID — пожалуйста, используйте long. Я решил, что мне хватит по 16 автотайлов на игровую локацию, остальные будут без авто-переходов.

Далее, нам нужен сет тайлов. Можно, конечно, использовать маску, но с сетом тайлов, согласитесь, при хорошем навыке (не у меня, нет), можно добиться очень и очень неплохой картинки.

image

Себе я сделал вот такой тестовый набор тайлов. На один тайл приходится 12 вариантов перехода, можно добавить ещё свои 4. Ещё я зарезервировал слоты для будущей вариации тайлов, как в WC3, но эта часть довольно лёгкая и описывать здесь я её не буду.

Переходим к части программирования. Для начала, опишем функции, которые будут определять нужную битовую маску для выбора корректного индекса текстуры. Сразу оговорюсь, я свойственен выбирать довольно нестандартные решения. Тут будет использоваться Java + LWJGL.

Эта функция будет создавать маску битов для данного квада. Бит 1 означает, что в данном углу тайла есть смежный ему тайл (таким образом, можно комбинировать разные тайлсеты одной высоты). Ах, да. Высота, про неё-то я и забыл. Конечно, нам надо будет определять для каждого тайла его высоту, чтобы знать что рисовать поверх, а что внизу. Это решается просто добавлением очевидной переменной.

	public int getTransitionCornerFor(World world, int x, int y, int height) {
		int corner = 0;
		if (world.getTile(x-1, y).zOrder == height)
			corner |= 0b0001;
		if (world.getTile(x, y).zOrder == height)
			corner |= 0b0010;
		if (world.getTile(x, y-1).zOrder == height)
			corner |= 0b0100;
		if (world.getTile(x-1, y-1).zOrder == height)
			corner |= 0b1000;
		return corner;
	}


Каждый бит означает свой угол. 1 бит — левый верхний угол, 2 — нижний левый, 3 — нижний правый, ну и 4 — верхний правый.

Теперь, касаемо, самого метода определения нужных индексов текстуры для переходов. Метод у меня получился громоздкий и некрасивый, ну, всё в силу моих навыков. Хотя специально для статьи я разбил его на несколько методов, дабы не создавать огромное количество отступов.

public void updateTransitionMap(World world, int x, int y) {
		int w = 16, h = 16;
		int[] temp = new int[4];    //создаем массив, который будет хранить нам 4 угла с 4 битами под ID и 4 битами под переход (т.е. 32 бита в целом для всего тайла)
		for (int i = 0; i < 4; i++)    //на самом деле мне просто было лень нормально разбираться с побитовыми операциями
			temp[i] = 0; 
		
		if (tileID > 0) {
			for (int i = 1; i <= tilesNum; i++) {
				int corner = getTransitionCornerFor(world, x, y, i);
				int c = 0;
				if (corner > 0) {
					c = setPointTransition(world, temp, x, y, corner, c, i);  //сначала задаем маску для всех углов
					if (c == 3) 
						c = setCornerTransition(world, temp, x, y, corner, c, i);  //потом, если есть 3 смежных(!) угла, соединяем их в один большой
					if (c == 2) 
						c = setEdgeTransition(world, temp, x, y, corner, c, i); //если есть 2 смежных(!) угла, соединяем их в сторону
				}	
			}
		}
	}


А вот и сами методы:

public int setPointTransition(World world, int[] temp, int x, int y, int corner, int c, int i) {
		for (int k = 0; k < 4; k++)
			if ((corner >> k & 1) == 1) {
				int idx = 8+k;
				int storage = 0;
				storage = (idx & 0xF) << 4 | (i & 0xF);
				temp[k] = storage;
				int t = 0;
				for (int l = 0; l < 4; l++) {
					t = (t << 8) | temp[l] & 0xFF;
				}
				world.setTransition(x, y, t);
				c++;
			}
		
		return c;
	}


Здесь всё просто. Пробегаемся по каждому углу, проверяем бит. Если он один — ставим индекс 8 + k, т.е. угол (выше я описывал номер для каждой стороны (NE, SE, SW, SE)). Далее костыльным методом через цикл обновляем нашу карту переходов.

Не забываем в конце отдавать обновленное число с. Спасибо Java, что в ней нету ни out, ни передачи простейших типов по ссылке.

Методы, соединяющие точки в углы и стороны:
	public int setEdgeTransition(World world, int[] temp, int x, int y, int corner, int c, int i) {
		for (int offset = 0; offset < 4; offset++) {
			boolean isSide = true;
			for (int k = 0; k < 2; k++) { //количество точек у стороны
				if ((corner >> ((k + offset) % 4) & 1) != 1)
					isSide = false;
				else if (k == 1 && isSide)  {
					int idx = (offset+1)%4;
					int storage = 0;
					storage = (idx & 0xF) << 4 | (i & 0xF);
					temp[offset] = storage;
					int t = 0;
					for (int l = 0; l < 4; l++) {
						t = (t << 8) | temp[l] & 0xFF;
					}
					world.setTransition(x, y, t);
				}
			}
		}
		
		return c;
	}
	
	public int setCornerTransition(World world, int[] temp, int x, int y, int corner, int c, int i) {
		for (int offset = 0; offset < 4; offset++) {
			boolean isCorner = true;
			for (int k = 0; k < 3; k++) { //количество точек у угла
				if ((corner >> ((k + offset) % 4) & 1) != 1)
					isCorner = false;
				else if (k == 2 && isCorner)  {
					int idx = 4+offset;
					int storage = 0;
					storage = (idx & 0xF) << 4 | (i & 0xF);
					temp[offset] = storage;
					int t = 0;
					for (int l = 0; l < 4; l++) {
						t = (t << 8) | temp[l] & 0xFF;
					}
					world.setTransition(x, y, t);
				}
			}
		}
		
		return c;
	}


Здесь абсолютно такой же принцип. Единственное отличие — стартовый номер индекса текстуры, чтобы нам взять нужный и ещё один цикл, который задает смещение, означающее с какой точки стартовать угол. Проверяется смежный угол (или сторона) против часовой стрелки, начинающийся с данной точки. Если хоть одна точка не является смежным тайлом — прерываемся, ни угла, ни стороны не получается.
Вот и всё, карта переходов у нас построена! На каждый тайл приходится по 5 бит. Один для хранения тайла (256 возможных вариаций) и по биту на каждый угол для хранения метаданных.

Осталось только отрендерить это дело. Я буду рассматривать старинный deprecated-метод через immediate-mode (планирую уйти на VBO, сейчас немножко надо разобраться со структурой и динамическим апдейтом VBO, а также отрисовкой лишь видимой его части).

Ну, тут нет ничего сложного:

public void renderTile(World world, int x, int y) {
		int w = 16, h = 16;
		int s = 0;

		if (tileID > 0) {
			for (int i = 0; i < 4; i++) {
				int t = world.getTransition(x, y);
				int src = ((t >> (3-i)*8) & 0xFF);
				int idx = src >> 4 & 0xF;
				int id = src & 0xF;
				int u = (idx%8)*16, v = 16 + 16*(idx/8) + (id-1)*48,
				u1 = u + w, v1 = v + h;
				if (id != 0) {
					GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144, u, v, u1, v1); //не обращайте внимания на хардкод, всё равно будет переписан под VBO 
				}
			}
		}
	}


Что мы делаем здесь? Ага, проходимся по каждым 8 битам и достаем 4 первых и 4 последних, для ID и перехода. Далее передаем параметры OpenGL, он уже распределяет отрисовку.

Результат:

image
(Да-да, LWJGL-канвас, встроенный в Swing).

Кажется, мы что-то забыли? Рисовать цельный кусок тайла, если 4 окружающие точки ему родны по высоте!

public void renderTile(World world, int x, int y) {
	int w = 16, h = 16;
		
	int s = 0;
	if (tileID > 0) {
		int c = 0;
		for (int i = 0; i < 4; i++) {
			int t = world.getTransition(x, y);
			int src = ((t >> (3-i)*8) & 0xFF);
			int idx = src >> 4 & 0xF;
			int id = src & 0xF;
			int u = (idx%8)*16, v = 16 + 16*(idx/8) + (id-1)*48,
			u1 = u + w, v1 = v + h;
			if (id != 0) {
				if (id == tileID)
					c++;
				GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144, u, v, u1, v1);
			}
		}
			
		if (c == 4) {
			GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144, 0, 48*(tileID-1), 16, (tileID-1)*48+16);
		}
	}
}


image

Чего-то не хватает? Верно, нам надо решить как отрисовывать нижний тайл. Если честно, у меня это получилось решить почти случайно, но именно этот момент ещё требует доработки. Пока это можно считать прикрученным костылем, но на результат он не влияет.

Немножко изменим наш метод:

	public void renderTile(World world, int x, int y) {
		int w = 16, h = 16;
		
		int s = 0;
		if (tileID > 0) {
			for (int i = 1; i <= tilesNum; i++) {
				int corner = getTransitionCornerFor(world, x, y, i);
				int c = 0;
				if (corner > 0) {
					for (int k = 0; k < 4; k++)
						if ((corner >> k & 1) == 1) {
							c++;
						}
				}
				
				boolean flag = false;
				int fill = getFillCornerFor(world, x, y, i);
				if (fill > 0)
					for (int k = 0; k < 4; k++)
						if ((fill >> k & 1) == 1) {
							c++;
							if (k == 4 && c == 4)
								flag = true;
						}
				
				if (c == 4) {
					GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144, 0, 48*(i-1), 16, (i-1)*48+16);
					if (flag)
						break;
				}
			}
			
			for (int i = 0; i < 4; i++) {
				int t = world.getTransition(x, y);
				int src = ((t >> (3-i)*8) & 0xFF);
				int idx = src >> 4 & 0xF;
				int id = src & 0xF;
				int u = (idx%8)*16, v = 16 + 16*(idx/8) + (id-1)*48,
				u1 = u + w, v1 = v + h;
				if (id != 0) {
					GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144, u, v, u1, v1);
				}
			}
		}
	}


Добавился ещё один метод. Он почти эквивалентен методу, который пишет биты смежных тайлов. Вот он:

	public int getFillCornerFor(World world, int x, int y, int height) {
		int corner = 0;
		if (world.getTile(x-1, y).zOrder > height)
			corner |= 0b0001;
		if (world.getTile(x, y).zOrder > height)
			corner |= 0b0010;
		if (world.getTile(x, y-1).zOrder > height)
			corner |= 0b0100;
		if (world.getTile(x-1, y-1).zOrder > height)
			corner |= 0b1000;
		return corner;
	}


Он определяет, все тайлы в округе, высота которых больше высота переданного тайла.

Т.е. мы перебираем все тайлы для данной клетки (естественно, перебирать стоит лишь автотайлы) и смотрим сколько тайлов находятся выше данного. Не забываем, что перед этим мы считаем количество точек, покрытых данным тайлом. Если количество точек данного тайла + сумма точек других тайлов перекрывающих данный == 4, то мы рисуем полный квад с данной текстуркой и прерываем цикл. Вот такие костыли.

Результат отличный:

image

Пожалуй, на этом всё.

P.S. Чем этот способ лучше того? Ну, WC3 наглядно демонстрирует, что с такой системой можно добиться ландшафта невообразимой красоты. Лично мне кажется, что она более гибкая, что, правда, создает некоторые сложности её реализации. И да, она всё же требует некоторой, как я сказал выше, доработки.

Комментарии 5

    0
    С красотой ландшата в WC3 у меня всегда ассоциируется The Kingdom Of Kaliron.
      +2
      > Результат отличный:

      Надеюсь Вы про код а не про картинку? Честно говоря, мне графический результат без последних изменений больше нравится…
        +3
        Вообще про результат с точки зрения работоспособности и правильной отрисовки.
        Кстати говоря, я пересмотрел свой код, немножко поменял условия. От последнего костыля я, вроде, избавился. Стоило перечитать свою же статью.
        Код
        public void renderTile(World world, int x, int y) {
        	int w = 16, h = 16;	
        	int s = 0;
        	if (tileID > 0) {
        		for (int i = 1; i <= tilesNum; i++) {
        			boolean isLowestTile = false;
        			int corner = getTransitionCornerFor(world, x, y, i);
        			int c = 0;
        			if (corner > 0) {
        				for (int k = 0; k < 4; k++)
        					if ((corner >> k & 1) == 1) {
        						c++;
        						isLowestTile = true;	//if we have at least one neighbor tile of this type - set this to lowest at this cell
        					}
        			}
        			
        			int fill = getFillCornerFor(world, x, y, i);
        			if (fill > 0)
        				for (int k = 0; k < 4; k++)
        					if ((fill >> k & 1) == 1) {
        						c++;
        					}
        				
        			if (c == 4 && isLowestTile) {
        				GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144, 0, 48*(i-1), 16, (i-1)*48+16);
        				break;
        			}
        		}
        			
        		for (int i = 0; i < 4; i++) {
        			int t = world.getTransition(x, y);
        			int src = ((t >> (3-i)*8) & 0xFF);
        			int idx = src >> 4 & 0xF;
        			int id = src & 0xF;
        			int u = (idx%8)*16, v = 16 + 16*(idx/8) + (id-1)*48,
        			u1 = u + w, v1 = v + h;
        			if (id != 0) {
        				GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144, u, v, u1, v1);
        			}
        		}
        	}
        }
        


        Хоть, визуально, вроде ничего и не изменилось. Я сейчас хочу добавить ещё переход между двумя противоположными углами, завтра отпишусь о результатах.
        0
        Поставил в редактор тайлы из старого доброго WC3 и заметил тучу багов.
        Самые плохие я уже устранил, надо было очищать все ненужные углы после создания смежных тайлов, т.к. они рисовались поверх нужной текстуры и создавался невообразимый хаос.
        image
        Сейчас осталась одна проблема — отсортировать углы. Скоро допишу и выложу код под спойлер.
          0
          Под спойлером полностью обновленный код.
          Не знаю как тут работает обновление статей, там внизу кнопочка опубликовать. Оно ведь не сделает новый топик мне, как в случае если я редактирую черновик?
          Методы определения переходов
          public int setPointTransition(World world, int[] temp, int x, int y, int corner, int c, int i) {
          		for (int k = 0; k < 4; k++)
          			if ((corner >> k & 1) == 1) {
          				int idx = 8+k;
          				int storage = 0;
          				storage = (idx & 0xF) << 4 | (i & 0xF);
          				temp[k] = storage;
          				int t = 0;
          				for (int l = 0; l < 4; l++) {
          					t = (t << 8) | temp[l] & 0xFF;
          				}
          				world.setTransition(x, y, t);
          				c++;
          			}
          		return c;
          	}
          	
          	public void setDiagonalTransition(World world, int[] temp, int x, int y, int corner, int i) {
          		if ((corner >> 0 & 1) == 1 && (corner >> 2 & 1) == 1) {
          			int idx = 12+1;
          			int storage = 0;
          			storage = (idx & 0xF) << 4 | (i & 0xF);
          			temp[0] = storage;
          			temp[2] = storage;
          			int t = 0;
          			for (int l = 0; l < 4; l++) {
          				t = (t << 8) | temp[l] & 0xFF;
          			}
          			world.setTransition(x, y, t);
          		}
          		else if ((corner >> 1 & 1) == 1 && (corner >> 3 & 1) == 1) {
          			int idx = 12;
          			int storage = 0;
          			storage = (idx & 0xF) << 4 | (i & 0xF);
          			temp[1] = 0;
          			temp[3] = storage;
          			int t = 0;
          			for (int l = 0; l < 4; l++) {
          				t = (t << 8) | temp[l] & 0xFF;
          			}
          			world.setTransition(x, y, t);
          			
          		}
          	}
          	
          	public void setEdgeTransition(World world, int[] temp, int x, int y, int corner, int i) {
          		for (int offset = 0; offset < 4; offset++) {
          			boolean isSide = true;
          			for (int k = 0; k < 2; k++) {
          				if ((corner >> ((k + offset) % 4) & 1) != 1)
          					isSide = false;
          				else if (k == 1 && isSide)  {
          					int idx = (offset+1)%4;
          					int storage = 0;
          					storage = (idx & 0xF) << 4 | (i & 0xF);
          					temp[offset] = 0;
          					temp[(offset+1)%4] = storage;
          					int t = 0;
          					for (int l = 0; l < 4; l++) {
          						t = (t << 8) | temp[l] & 0xFF;
          					}
          					world.setTransition(x, y, t);
          				}
          			}
          		}
          	}
          	
          	public void setCornerTransition(World world, int[] temp, int x, int y, int corner, int i) {
          		for (int offset = 0; offset < 4; offset++) {
          			boolean isCorner = true;
          			for (int k = 0; k < 3; k++) {
          				if ((corner >> ((k + offset) % 4) & 1) != 1)
          					isCorner = false;
          				else if (k == 2 && isCorner)  {
          					int idx = 4+offset;
          					int storage = 0;
          					storage = (idx & 0xF) << 4 | (i & 0xF);
          					temp[offset] = 0;
          					temp[(offset+1)%4] = 0;
          					temp[(offset+2)%4] = storage;
          					int t = 0;
          					for (int l = 0; l < 4; l++) {
          						t = (t << 8) | temp[l] & 0xFF;
          					}
          					world.setTransition(x, y, t);
          				}
          			}
          		}
          	}
          


          Обновление тайла
          public void updateTransitionMap(World world, int x, int y) {
          		int w = 16, h = 16;
          		int[] temp = new int[4];
          		for (int i = 0; i < 4; i++)
          			temp[i] = 0;
          		
          		if (tileID > 0) {
          			for (int i = 1; i <= tilesNum; i++) {
          				int corner = getTransitionCornerFor(world, x, y, i);
          				int c = 0;
          				if (corner > 0) {
          					c = setPointTransition(world, temp, x, y, corner, c, i);
          					
          					if (c == 2) 
          						setEdgeTransition(world, temp, x, y, corner, i);
          					
          					if (c == 2) 
          						setDiagonalTransition(world, temp, x, y, corner, i);
          					
          					if (c == 3) 
          						setCornerTransition(world, temp, x, y, corner, i);
          				}	
          			}
          		}
          	}
          


          Отрисовка
          public void renderTile(World world, int x, int y) {
          		int w = 16, h = 16;
          		
          		int s = 0;
          		if (tileID > 0) {
          			for (int i = 1; i <= tilesNum; i++) {
          				boolean isFullTile = false;
          				int corner = getTransitionCornerFor(world, x, y, i);
          				int c = 0;
          				if (corner > 0) {
          					for (int k = 0; k < 4; k++)
          						if ((corner >> k & 1) == 1) {
          							c++;
          							if (c == 4)
          								isFullTile = true;
          						}
          				}
          				
          				int fill = getFillCornerFor(world, x, y, i);
          				if (fill > 0)
          					for (int k = 0; k < 4; k++)
          						if ((fill >> k & 1) == 1) {
          							c++;
          						}
          				
          				if (c == 4) {
          					GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144+96, 0, 48*(i-1), 16, (i-1)*48+16);
          					if (isFullTile)
          						return;
          				}
          			}
          			
          
          			for (int j = 1; j <= tilesNum; j++) {
          				for (int i = 0; i < 4; i++) {
          					int t = world.getTransition(x, y);
          					int src = ((t >> (3-i)*8) & 0xFF);
          					int idx = src >> 4 & 0xF;
          					int id = src & 0xF;
          					int u = (idx%8)*16, v = 16 + 16*(idx/8) + (id-1)*48,
          					u1 = u + w, v1 = v + h;
          					if (id == j) {
          						GRenderEngine.drawTextureQuad(x*16, y*16, 128, 144+96, u, v, u1, v1);
          					}
          				}
          			}
          		}
          	}
          

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

          Самое читаемое