Тайлинг прямоуголников со скругленными краями

[Furinax]

В общем, есть у меня такая нарезка из 12 тайлов.

https://api.monosnap.com/image/download?id=0x0Qxn0c0yWg2nQgh6NebPSsv

На вход получаю сетку в виде:
[
[0, 1, 1, 0, 0, 0, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 1, 1, 0, 1, 0]
]

Где 0 - это пустая ячейка. А 1 - это ячейка на которой есть тайл.
Задача состоит в том, чтобы по имеющимся данным построить из данных тайлов поле.

Пытался нагуглить какой-нибудь хитрый алгоритм для этого, но ничего не нашел.
Удалось написать это самому, но с очень большим количеством if`ов(что-то около 100) для проверки каждого возможного случая какой тайл надо поставить на данную позицию.
Прошу помочь найти изящное решение для этой задачи.

[ChuwY]

Вечером попробую сделать.
Кстати, у вас не хватает еще 3 тайлов для краев стен, типа последнего.
Ну или наоборот слишком много картинок, в том случае, если их можно поворачивать.

[Furinax]

Да тут нету жесткой привязки к количеству тайлов. Можно всегда добавить недостающие.
Поворачивать я задумал под конец, когда буду все это дело оптимизировать.
А вот найти/придумать алгоритм, который меня избавит почти от сотни if`ов как раз первый шаг к оптимизации.
Сначала мне эта задача тоже показалась очень легкой, но вот ничего кроме быдло-решения найти не смог.

[Akopalipsis]

А почему Вы говорите о ста ифоф, если нужно проверять только четыре или пять.
Сначала я подумал, что Вы хотите рамку сделать, а причитался и мне кажется, что тут алгоритм поиска путей подойдет. Проверять нужно только значения окружающих ячеек, которых только четыре может быть.

[Isfet]

я бы каждому тайлу присвоил значение( хранил их в ключевом массиве допустим) такого формата:

arr["1000"] = tile;



где "1000" - это набор из стен в тайле (верх/право/низ/лево).
Затем проверял ближайшие тайлы и составлял эту строку. и по ней вытаскивал необходимый тайл

[KumoKairo]

В принципе согласен с предыдущими комментаторами, но мне интересно, что делать с диагональными тайлами (кстати, Isfet, тайл - это tile. tail - это хвост :) ) В задании о таких случаях ничего не сказано. Считать оба таких тайла конечными? Но тогда если это какое-то подобие уровня, то на примере вашей "карты" будет много кусков, до которых никак не получится добраться

[Isfet]

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

[Wolsh]

Я вижу что скругляются только внешние углы. А что с внутренними?
Простой пример: как будет выглядеть дырка
1 1 1
1 0 1
1 1 1

[Furinax]

Я вижу что скругляются только внешние углы. А что с внутренними?
Простой пример: как будет выглядеть дырка
1 1 1
1 0 1
1 1 1

Внутренние углы не скругленные. Главное, чтобы вокруг дырки образовалась обводка.
На первый взгляд задача кажетя очень простой, но что-о ни одного решения в гугле найти не удалось.
Я делал следющим образом:проверял все восемь тайлов вокруг и выбирал нужный тайл, соответственно получилась огромная куча if`ов типа

if(topLeft && top && topRight && right && left && bottomLeft && top && bottomTight)
{
return тайл без обводки каких либо обводок
} else if(!topLeft && top && topRight && right && left && bottomLeft && top && bottomTight)
{
return еще какой-то тайл
} else if(!topLeft && !top && topRight && right && left && bottomLeft && top && bottomTight)
{
return еще какой-то тайл
} else
{
throw new Error("такой случай не определен - допиши новый if")
}


Сначала я думал, что смогу написать if`ы для всех возможных случаев, но потом убедился, что их может быть очень и очень много. Поэтому и ищу какой-нибудь хитрый алгоритм для этого.

А почему Вы говорите о ста ифоф, если нужно проверять только четыре или пять.
Сначала я подумал, что Вы хотите рамку сделать, а причитался и мне кажется, что тут алгоритм поиска путей подойдет. Проверять нужно только значения окружающих ячеек, которых только четыре может быть.

Нужно проверять все 8 иначе гарантированно попадается ситуация, в которой тайл оказывается не там, где он должен быть.
Причем здесь алгоритм поиска путей? Я не ищу путь, от одной ячейки к другой, я на основе анализа окружающих ячеек пытаюсь выяснить какой тайл поставить на определенную позицию. То что это можно сделать проверяю значения окружающих ячеек - это очень и очень очевидно, только их может быть не только 4, а всегда 8. И из этих восьми какие-то могут быть пустые. Поэтому в случае с пустыми надо понять - отрисовывать прямоугольник со кругленными краями или простой без обводки или еще какой другой.

[Isfet]

покажите скрин как должна выглядеть карта по вашей маске,
а вообще задача абсолютно простая, прочитайте мой пост выше, храните тайлы как я писал выше, проверяете 4 ячейки слева справа сверху и снизу, и составляете строку, допустим если такой вариант:
--0
1 1 1
--0

сверху 0 значит там будет стенка , пишем в строку 1, справа 1 , значит там нет стенки, добавляем в строку "0" , получаем "10" , снизу 0 - > "101" , слева 1 - > "1010",

по полученной строке вытаскиваем тайл из массива


tile = arr["1010"];

[Furinax]

покажите скрин как должна выглядеть карта по вашей маске[/AS3]

Картинка может быть любой, она строится динамически по коду из того, что есть. Если каких-то видов тайлов не хватает, то их всегда можно дорисовать. И эти условия вполне достаточны для решения это задачи.


а вообще задача абсолютно простая, прочитайте мой пост выше, храните тайлы как я писал выше

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


роверяете 4 ячейки слева справа сверху и снизу, и составляете строку, допустим если такой вариант:
--0
1 1 1
--0

сверху 0 значит там будет стенка , пишем в строку 1, справа 1 , значит там нет стенки, добавляем в строку "0" , получаем "10" , снизу 0 - > "101" , слева 1 - > "1010",

по полученной строке вытаскиваем тайл из массива
tile = arr["1010"];

И приходим ровно к тому же решению что у меня сейчас, только вместо сотни if`ов - будет массив с сотней ячеек типа:


arr["0000"]
arr["0001"];
arr["0011"];
arr["0111"];
arr["1111"];
arr["1000"];
arr["1100"];
arr["1110"];
arr["1110"];
arr["0101"];
...
и так далее

[Isfet]

это не массив всевозможных комбинаций (а их 256), это массив который хранит данные о том, с какой стороны у вашего тайла-картинки - есть стена. допусти левый верхний тайл из вашего изображения должен лежать в ячейке arr["0011"]

[Akopalipsis]

Тут вот (http://flashpress.ru/blog/puzzle-part1/) про генерацию пазла и внизу пример, может Вам пригодится.

[Furinax]

это не массив всевозможных комбинаций (а их 256), это массив который хранит данные о том, с какой стороны у вашего тайла-картинки - есть стена. допусти левый верхний тайл из вашего изображения должен лежать в ячейке arr["0011"]

И получается у меня будет ассоциативный массив с 256 ячейками, каждая из которых сответствует какой-то комбнации?
А как мне понять, что, допустим надо в arr["1111"] положить именно FieldTileMM.png, самому предварительно рассмотрев все случаи "на глаз"?

Тут вот (http://flashpress.ru/blog/puzzle-part1/) про генерацию пазла и внизу пример, может Вам пригодится.

спасибо, хоть и не совсем то, но тоже очень интересно. Возможно поможет.

[Isfet]

массив будет с вашим количеством тайлом, то есть 12, и класть их туда нужно относительно стен в рисунке тайла

[Akopalipsis]

И получается у меня будет ассоциативный массив с 256 ячейками
Почему вас смущает массив с 256 элементами, но не смущает 256 картинки?
Или Вы как то насчитали, что у Вас элементов будет больше чем картинок??

[udaaff]

Решал похожую задачу, только строил границу отдельно от тайлов, как в этом приложении https://apps.facebook.com/farmheroes. Не совсем то, что тебе надо, но если сгодится опишу как построить. По твоей задаче, я бы разбил каждый из тайлов на четыре участка. Получилось бы всего три разных типа: две линии и уголок. Тип каждого участка зависел бы от наличия соседних с этим участком тайлов. У меня по моей задаче это выглядит как-то так:

/**
* @param data Array of Boolean - массив показывающий наличие клеток по сторонам
* 0 1 2
* 7 X 3
* 6 5 4
*/
public function setBorder(a:Array):void
{
this.setGrid(this._gridTL, a[7], a[0], a[1]); // grid - это мувик с вариантами границы
this.setGrid(this._gridTR, a[1], a[2], a[3]); // можно использовать один для всех четырех участков,
this.setGrid(this._gridBR, a[3], a[4], a[5]); // повернутый под нужным углом
this.setGrid(this._gridBL, a[5], a[6], a[7]);
}

private function setGrid(grid:MovieClip, a:Boolean, b:Boolean, c:Boolean):void
{
if (a && c)
grid.gotoAndStop(1);
else if (a)
grid.gotoAndStop(2);
else if (c)
grid.gotoAndStop(4);
else if (b)
grid.gotoAndStop(3);
else
grid.gotoAndStop("empty");
}

[Wolsh]

Почему не сделать просто восьми(четырех?)мерный массив со ссылками на тайлы? То есть не непонятный какой то arr["1010"] а arr[1][0][1][0]. И никаких if'ов.
А, понял в чем проблема.
Вам же мало знать, что вверху 1. Вам надо знать, какого типа там тайл. Это вообще ТАК не решается.

[Furinax]

Решал похожую задачу, только строил границу отдельно от тайлов, как в этом приложении https://apps.facebook.com/farmheroes.

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

[silin]

я бы собирал эти тайлы 'на лету' из 9ти элементов
навскидку попробовал упрощенный вариант,
на самом деле все будет сложнее из-за линий каймы, но всяко проще, чем собирать из готовых, да и многовато их нужно, имхо 256(2^8), ну может за вычетом каких-то нереальных, но никак не 12 же
package
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.display.StageScaleMode;
import flash.geom.Rectangle;

public class Main extends Sprite
{
private var size:Number = 30;

private var srcRounded:Sprite = new Sprite();
private var srcCorner:Sprite = new Sprite();

public function Main():void
{
stage.scaleMode = StageScaleMode.NO_SCALE;
srcRounded.graphics.beginFill(0xC0C0C0);
srcRounded.graphics.drawRoundRect(0, 0, size, size, 0.5 * size, 0.5 * size);
//srcRounded.graphics.endFill();
//srcRounded.graphics.lineStyle(1, 0);
//srcRounded.graphics.drawRoundRect(size/6, size/6, 2*size/3, 2*size/3, size/3, size/3);

srcCorner.graphics.beginFill(0xC0C0C0);
srcCorner.graphics.drawRect(0, 0, size, size);


var grid:Array = [
[0, 1, 1, 0, 0, 0, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 1, 1, 0, 1, 0]]



for (var j:int = 0; j < grid.length; j++)
{
var line:Array = grid[j];
for (var i:int = 0; i < line.length; i++)
{
if (line[i])
{
var tile:Bitmap = getTile(
line[i - 1],
grid[j - 1] ? grid[j - 1][i] : 0,
line[i+1],
grid[j + 1] ? grid[j + 1][i] : 0
);
tile.x = size * i;
tile.y = size * j;
addChild(tile);
}
}
}
}

private function getTile(l:Boolean,t:Boolean,r:Boolean,b:Boolean):Bitmap
{
var bmd:BitmapData = new BitmapData(size, size, true, 0);


drawSegm(bmd, 0, 0, l || t);
drawSegm(bmd, 1, 0, t);
drawSegm(bmd, 2, 0, r || t);
drawSegm(bmd, 0, 1, l);
drawSegm(bmd, 1, 1, false);
drawSegm(bmd, 2, 1, r);
drawSegm(bmd, 0, 2, l || b);
drawSegm(bmd, 1, 2, b);
drawSegm(bmd, 2, 2, b || r);


return new Bitmap(bmd);


}

private function drawSegm(bmd:BitmapData, i:int, j:int, corner:Boolean):void
{

var s:Number = size / 3;
var rec:Rectangle = new Rectangle(i * s, j * s, s, s);
var src:Sprite = corner ? srcCorner : srcRounded;
bmd.draw(src, null, null, null, rec);
}

}

}

[udaaff]

Держи пример.
forum.swf

[Isfet]

вот решение без запихивания в массив, но можно и в массив положить


package
{
import flash.display.Bitmap;
import flash.display.Sprite;
import flash.events.Event;

/**
* ...
* @author Isfet
*/
public class Main extends Sprite
{

[Embed(source = '../imgs/0000.png')] private var Tile0000 :Class;
[Embed(source = '../imgs/0001.png')] private var Tile0001 :Class;
[Embed(source = '../imgs/0010.png')] private var Tile0010 :Class;
[Embed(source = '../imgs/0011.png')] private var Tile0011 :Class;
[Embed(source = '../imgs/0100.png')] private var Tile0100 :Class;
[Embed(source = '../imgs/0101.png')] private var Tile0101 :Class;
[Embed(source = '../imgs/0110.png')] private var Tile0110 :Class;
[Embed(source = '../imgs/0111.png')] private var Tile0111 :Class;
[Embed(source = '../imgs/1000.png')] private var Tile1000 :Class;
[Embed(source = '../imgs/1001.png')] private var Tile1001 :Class;
[Embed(source = '../imgs/1010.png')] private var Tile1010 :Class;
[Embed(source = '../imgs/1011.png')] private var Tile1011 :Class;
[Embed(source = '../imgs/1100.png')] private var Tile1100 :Class;
[Embed(source = '../imgs/1101.png')] private var Tile1101 :Class;
[Embed(source = '../imgs/1110.png')] private var Tile1110 :Class;
[Embed(source = '../imgs/1111.png')] private var Tile1111 :Class;

public static const TILE_SIZE:uint = 60;


public function Main():void
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}

private function init(e:Event = null):void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
// entry point

var grid:Array = [
[0, 1, 1, 0, 0, 0, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 1, 1, 0, 1, 0]
];

gridParsing(grid);

}
private function gridParsing(grid:Array):void {

var str:String;
var columnLen:uint = grid.length;
var tile:Bitmap;

for (var j:int = 0; j < columnLen; j++)
{
var rowLen:uint = grid[j].length;
for (var i:int = 0; i < rowLen; i++)
{
str = "";
if (grid[j][i]) {

str += grid[j - 1] ? getWall(grid[j - 1][i]) : 1;
str += getWall(grid[j][i + 1]);
str += grid[j + 1] ? getWall(grid[j + 1][i]) : 1;
str += getWall(grid[j][i - 1]);

tile = new this["Tile"+str] ;
tile.x = TILE_SIZE * i;
tile.y = TILE_SIZE * j;
addChild(tile);
}
}
}
}

private function getWall(val:uint):uint {

if (val) {

return 0;
}
else {
return 1;
}
}

}
}

30356

Итого получаем 16 тайлов, и соответственно если класть в массив будет 16 элементов, а не 256 как вы многократно твердили

[Furinax]

Ребят, всем большое спасибо за помощь, очень интересные решения.

silin, udaff, это реально гениально, вместо того, чтобы увеличивать количество тайлов - наоборот уменьшить да еще и затайлить их самих, никогда бы не догадался), по настоящему изящные решения.

Isfet, извиняюсь и признаю, что был не прав. Мне почему-то проблематично визуально представить все возможные виды тайлов. Могли бы вы, пожалуйста, поделиться картинкой со всеми видами тайлов? Я собираюсь использовать решение silin`а, дописав обводку. Но все равно очень интересно как у вас сделано.

[silin]

Isfet, дада не 256, сори
256 это всего возможных, а их в таком раскладе просто нет и твое решение может и поудобнее будет
но если придется, например, еще 'внутренние' скругления (в дырках) учесть, то вариантов прибавится..

хотел по-простому вариант с бордюром нарисовать, но по-простому не выходит - надо еще и диагональные клетки анализировать
package
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.display.StageScaleMode;
import flash.geom.Rectangle;

public class Main extends Sprite
{
private var size:Number = 30;

private var srcRounded:Sprite = new Sprite();
private var srcCorner:Sprite = new Sprite();
private var srcVLine:Sprite = new Sprite();
private var srcHLine:Sprite = new Sprite();

public function Main():void
{
stage.scaleMode = StageScaleMode.NO_SCALE;
srcRounded.graphics.beginFill(0xC0C0C0);
srcRounded.graphics.drawRoundRect(0, 0, size, size, 0.5 * size, 0.5 * size);
srcRounded.graphics.endFill();
srcRounded.graphics.lineStyle(2, 0);
srcRounded.graphics.drawRoundRect(size/6, size/6, 2*size/3, 2*size/3, size/3, size/3);

srcCorner.graphics.beginFill(0xC0C0C0);
srcCorner.graphics.drawRect(0, 0, size, size);

srcVLine.graphics.lineStyle(2, 0);
srcVLine.graphics.moveTo(size / 6, 0);
srcVLine.graphics.lineTo(size / 6, size);
srcVLine.graphics.moveTo(5 * size / 6, 0);
srcVLine.graphics.lineTo(5 * size / 6, size);

srcHLine.graphics.lineStyle(2, 0);
srcHLine.graphics.moveTo(0, size / 6);
srcHLine.graphics.lineTo(size, size / 6);
srcHLine.graphics.moveTo(0, 5 * size / 6);
srcHLine.graphics.lineTo(size, 5 * size / 6);



var grid:Array = [
[0, 1, 1, 0, 0, 0, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 1, 1, 0, 1, 0]]



for (var j:int = 0; j < grid.length; j++)
{
var line:Array = grid[j];
for (var i:int = 0; i < line.length; i++)
{
if (line[i])
{
var tile:Bitmap = getTile(
line[i - 1],
grid[j - 1] ? grid[j - 1][i] : 0,
line[i+1],
grid[j + 1] ? grid[j + 1][i] : 0
);
tile.x = size * i;
tile.y = size * j;
addChild(tile);
tile.alpha = 1 - 0.25 * ((j * 9 + i) % 2);

}
}
}
}

private function getTile(l:Boolean,t:Boolean,r:Boolean,b:Boolean):Bitmap
{
var bmd:BitmapData = new BitmapData(size, size, true, 0);


drawSegm(bmd, 0, 0, l || t, (t && !l), l&&!t);
drawSegm(bmd, 1, 0, t);
drawSegm(bmd, 2, 0, r || t, t && !r, r && !t);
drawSegm(bmd, 0, 1, l);
drawSegm(bmd, 1, 1, false);
drawSegm(bmd, 2, 1, r);
drawSegm(bmd, 0, 2, l || b, b && !l, l && !b);
drawSegm(bmd, 1, 2, b);
drawSegm(bmd, 2, 2, b || r, b && !r, r && !b);


return new Bitmap(bmd);


}

private function drawSegm(bmd:BitmapData, i:int, j:int, corner:Boolean, vLine:Boolean=false,hLine:Boolean=false):void
{

var s:Number = size / 3;
var rec:Rectangle = new Rectangle(i * s, j * s, s, s);
var src:Sprite = corner ? srcCorner : srcRounded;
bmd.draw(src, null, null, null, rec);
if (vLine)bmd.draw(srcVLine, null, null, null, rec);
if (hLine)bmd.draw(srcHLine, null, null, null, rec);


}

}

}

[Isfet]

вот виды тайлов на вашем примере

30361

название тайла отображает наличие стен в нем, в порядке, как в margin в html (top/right/bottom/left).

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