Готовые наборы тайлсетов для игр

#c_sharp #xna #графика #разработка_игр #2d

                    
Доброго времени суток, Хэшкод.

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

Собственно у меня вопросы:


Есть ли сайты, на которых есть нормальные тайлсеты?
Есть ли нормальные редакторы для создания тайсетов? (можно конечно и в Paint-е(Gimp-е/Photoshop-е)
что-то наваять, но с моими навыками "рисования"... в общем, хотелось бы что-то более
специализированное)


Пример тайлсета, если кто не знает, что это такое:


[upd] Да, вопрос получился конечно не по программированию, но извиняюсь. Больше мне
спрашивать негде.
    

Ответы

Ответ 1

Вы когда нибудь пробовали собрать toolbar для оконного приложения с помощью сайта
который представляет бесплатные иконки от разных людей? Ваш toolbar получится не ахти,
так как все иконки будут нарисованы разными людьми в разном стиле и цветовой гамме.
Даже если вы будете долго копаться на нескольких таких сайтах в поисках единого стиля,
то наврятли получится что-то стоящее, т.к. совершенно не факт что вы найдете даже готовый
набор полностью удовлетворяющий вашим нуждам. Тоже самое и с тайлсетом. Их все должен
рисовать один человек в одном стиле по одному документу, на gamedev.ru и фриланс сайтах
есть десятки людей которые с радостью возьмутся выполнить такой заказ по вполне адекватной
цене(реальная рыночная цена тому что вы приводите в качестве примера не больше 100-300
рублей за полоску), да и качество будет вполне ничего, если вы конечно потрудитесь
отобрать достойного кандидата.
В качестве редактора можно использовать Photoshop и 3DSMax ну или Blender и GIMP
если вы красноглазик. Специальный редактор для тайлсетов это плохая идея потому что
непонятно чем собственно тайлсет отличается от обычной картинки.
Самому рисовать их ни в коем случае нельзя, так как если у вас нет хотя бы пары лет
опыта работы с графическими редакторами и хотя бы зачатков умений художника, то в лучшем
случае у вас получится результат которым можно только пугать других людей. С другой
стороны с попытки с 50ой может и получится что-нибудь хорошее, но тогда вы просто потеряете
время.
Правда есть и альтернативный вариант:
http://lunar.lostgarden.com/labels/free%20game%20graphics.html
http://hasgraphics.com/
http://cgtextures.com/
http://blogoscoped.com/archive/2006-08-08-n51.html
http://www.freewebs.com/teh_pro/sprites.htm
http://www.spriters-resource.com/
http://www.flyingyogi.com/fun/spritelib.html
http://www.gamedev.net/topic/272386-sprites-sprites-and-more-sprites/
P.S. Собирать игры в качестве хобби это плохая идея, так как это требует очень много
свободного времени и усилий. Нужно либо делать это нормально либо вообще не делать.


Ответ 2

Что касается сайтов с нормальными тайлсэтами - никогда не встречал, что касается
редакторов - такие, безусловно, есть, но они никак не изменяют того факта, что нужно
уметь рисовать, учитывая их более ограниченный функционал, большего смысла в них не
вижу, разве что, обычно, удобно сразу рисовать сэт.
Вообще, для того, что-бы научится хоть более менее нормально рисовать оные, великих
навыков художника не требуется, все, чему нужно научится - базовым навыкам передачи
светотени и объема. К тому-же, нет людей, которые не умеют рисовать, есть только те,
которые не научились.
Плюс ко всему, если рисовать не на бумаге, можно сделать, допустим, размерность 2к*2к
px, при уменьшении которой, многие косяки изображения исчезнут, главное правильно передать
объем и более менее правильно светотень.
Даже если совсем не будет получатся - можно поискать начинающего художника и попросить
нарисовать его, но, повторюсь - такое рисование не требует великих навыков, другой
вопрос в том, достаточно ли у вас времени и желания?..

Преобразование ломаной линии

#cpp #алгоритм #геометрия #2d

                    
Я имею неравномерную сетку в виде координат узлов в двумерном пространстве
Узлы сетки хранятся в одномерном векторе, где нумерация снизу-вверх слева-направо



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

Количество точек ломаной линии не совпадает с количеством точек результирующей ломаной.

Есть ли у кого-нибудь идеи по решению данной задачи?
    

Ответы

Ответ 1

Алгоритм:


Выбираем клетки, через которые проходит ломаная.





Циклично проверяем выбранные клетки:


2.1 Берем на границах клетки две точки, в которых ломаная пересекает эту клетку (или
одну из крайних точек ломаной) и соединяем отрезком.



2.2 Сдвигаем отрезок так, чтоб обе точки находились на границах клетки (в случае
с крайними точками ломаной).

2.3 Считаем углы между отрезком и границами к летки, к которым прилегает отрезок
(достаточно неточного расчета в три варианта >45|=45|<45).



2.4 "основная" граница будет та, у которой угол <45 (обведено красным). Если угол
=45, то обе границы равнозначны.

Повторяем для всех клеток




На основе полученных выборок по две границы строим ломаную




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


Ответ 2

Проведите дополнительные воображаемые вертикальные и горизонтальные линии посередине
каждого столбца и строки. У вас получится вдвое более плотная сетка. Каждый узел исходной
сетки окажется заключен в ячейку новой сетки.

Если синяя линия проходит через этот прямоугольник, значит, она задействует соответствующий
узел основной сетки.

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

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


Ответ 3

#include 
#include 
#include 
using namespace std;


int main()
{  
    // вообше то с такими задачами хранить лучше в std::valarray
    // допустим количество узловых точек = 4 * 4 и для примера приведу 
    //конкретные цифры
    // в задаче же уже заданы эти цифры, я лишь для демонстрации идеи
    const int n = 4;
    valarray< int > matrix(n * n);
    // инициализируем первую строку снизу от нулевого индекса `n` штук
    valarray row{ 2, 4, 7, 8 };
    // теперь учитываем что разница между соответствующим элементами
    // следующей строки должны быть одинаковыми.
    //  и допустим эти цифры заданы в векторе
    vector dif{ 3, 2, 4 };
    // инициализируем последовательность по срезам
    for (int i = 0; i < n; ++i) {
        matrix[slice(i * n, n, 1)] = row;
        if (i == n - 1) break;
        row += dif[i];
    }
   // точки на кривой лучше хранить в map, так как кривая монотонно растет
    map curve{{ 3.4, 2.7 }, {4.1, 6}, {5, 9.3}};
    // для первой точки на кривой
    auto para = curve.begin();
    // теперь берем  ближайшие целые этих точек
    int x = lround(para->first), y = lround(para->second);
    //...
    return 0;}


теперь чтобы знать к каким элементам нашей последовательности ближе точка с 
    координатами (x, y) всего лишь дело техники... для сравнения y наверняка понадобится
dif, а
    STL альгоритмы дадут нам возможность рассмотреть любое количество точек
    с соответствующими предикатами. Вообшем идея такая, дальше подумайте сами


Ответ 4

0) Учащаем точки ломаной: в цикле определяем расстояние между соседними точками (D)
у ломаной, если это расстояние больше, чем расстояние диагонали ячейки сетки (d), то
вставляем дополнительною точку.




Это шаг предобработки ломаной. В конце объясню зачем это нужно

1) Определяем ближайший узел (curr_node) к начальной точке (p) исходной ломаной


Далее в цикле:

2) Определяем соседние узлы для curr_node (соседями не считать предыдущий посещенный
узел)



3) Определяем расстояние от curr_node и от его соседних узлов до следующей точки
ломаной (p_next). 



4) Если расстояние от curr_node до p_next меньше, чем минимальное расстояние от его
соседей до p_next, то p_next станет следующей точкой ломаной, иначе "посещаю" следующий
узел сетки (тот соседний узел, который ближе всего к точке p_next)

Далее возвращаемся к шагу 2

В итоге получаем такую картину посещения узлов



т.е. собирая посещенные узлы (черные), получаем такую ломаную, проходящую по узлам сетки:



А теперь покажу зачем нужно было делать нулевой шаг:



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

Контур произвольного полигона

#2d #алгоритм #графика

Имеется векторный полигон в программе (в виде команд его рисования).
Задача - расширить этот полигон во все стороны на заданное расстояние. То есть, получить
его контур или окаёмку с учётом возможных внутренних коллизий. Интересует, собственно,
алгоритм сего действа. Желательно, не особо ресурсоёмкий. Либо просто литература, где
про это можно почитать.
Самое, что интересное:

обработка самопересечений в замкнутых областях (как внутренняя дырка в букве "я"
- заполнилась целиком).
закругления в углах. Как сделать без закруглений более-менее понятно (провести параллельные
линии на заданном расстоянии). Или концы отрезков с помощью безье соединить?..


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

Ответы

Ответ 1

Векторный случай

Если предположить, что вы уже перешли к векторному формату, то:

рассматриваете последовательно ребра полигона в одном направлении (например, против
часовой стрелки). Это важно, т.к. повлияет на ориентацию направляющих векторов ребер
полигона.
Для каждого ребра вычисляете нормаль (это нормализованный вектор, перпендикулярный
направляющему вектору ребра). В вашем случае также следует проследить, чтобы нормаль
была направлена "от" полигона, а не "внутрь" него.
умножаете каждую нормаль на коэффициент "расширения" k.
прибавляете нормаль к начальной (u) и к конечной (v) вершинам ребра (вершины рассматриваем
как векторы, исходящие из начала координат). Получаем "расширенные" вершины u' и v'.
Эти вершины определяют начало и конец "расширенного" ребра.
Кроме того, в итоге на каждую вершину полигона будет получено по две (в общем случае
неколлиниарных) "расширенных" вершины u' и u'' (они будут вычислены для смежных ребер
с общей вершиной u). Их можно использовать, чтобы сделать "закругление" (наиболее очевидный
способ: строить промежуточные вершины поворотом u' к u'' малым угловым шагом).
Нужно еще выявлять ситуации самопересечений и обрабатывать их. Боюсь соврать, но
по-моему тут надо смотреть знаки смешанных произведений нормалей ребер и вектора (0,0,1).
При выбранном направлении обхода полигона знак этого произведения должен меняться только
для "вогнутых" пар ребер (образующих "невыпуклости" полигона). Кажется так..

Почитать можно что-то по аналитической геометрии и векторной арифметике.
UPD: Как вариант можете еще глянуть эту книгу: Steven M. LaValle. Planning Algorithms.
В ней охвачен широчайший спектр вопросов, в т.ч. и работа с полигонами.
Растровый случай
Думаю, практически в любом случае есть смысл заняться преобразованием в векторное
представление. Для определения границ можно попробовать использовать алгоритм пересечения
полигона отрезком, паралелльным какой-либо оси координат + читать цвета пикселей. Еще
один вариант - как-то попробовать модифицировать алгоритм заливки полигона. Тут уже
менее очевидно, надо думать или искать готовый векторизатор:)

Соединить две окружности. В чём ошибка?

#javascript #svg #vector #геометрия #2d

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

Совет первый 
Совет второй

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

Jsfiddle проект 

Писал на JS, но подойдёт любое другое решение.
Даже без кода, в чистой теории, в чем неверен мой подход.



//

    

Ответы

Ответ 1

Поскольку нужны только внешние касательные (могут быть ещё внутренние), то подход
может быть не слишком сложным:

Пусть центр большей окружности CR, меньшей cr. Вектор разности d, его длина и нормализованный
вектор:

 d = cr - CR
 dlen = length(d)
 ud = d / dlen


Общие касательные к окружностям разного радиуса пересекаются где-то в точке OP. Касательная
вместе с радиусами к точкам касания образует два подобных прямоугольных треугольника
(поскольку радиус перпендикулярен касательной). Из подобия следует

Coeff = R / (R - r)
OP = CR + d * Coeff


Синус и косинус угла A этого треугольника  

ca = R / (dlen * Coeff)
sa = Sqrt(1-ca*ca)


Точки касания большой окружности могут быть получена поворотом вектора ud*R на A и -A

P.x = CR.x + ca * R * ud.x + sa * R * ud.y
P.y = CR.y - sa * R * ud.x + ca * R * ud.y
Q.x = CR.x + ca * R * ud.x - sa * R * ud.y
Q.y = CR.y + sa * R * ud.x + ca * R * ud.y


Аналогично для малой окружности с использованием её центра и радиуса. 

Тест:



fiddle:  (подправил последовательность точек и знаки углов)

let c1 = this.state.circles[0];
let c2 = this.state.circles[1];

let l = getVectorLen(c1,c2);

let v = {x: c2.x-c1.x, y: c2.y-c1.y};
let uv = {x: v.x / l, y: v.y / l};

let ca = (c2.r - c1.r) / l;
let sa = Math.sqrt(1 - ca*ca);

let ps = [

    c1.x - ca * c1.r * uv.x - sa * c1.r * uv.y, 
    c1.y + sa * c1.r * uv.x - ca * c1.r * uv.y,
    c1.x - ca * c1.r * uv.x + sa * c1.r * uv.y,
    c1.y - sa * c1.r * uv.x - ca * c1.r * uv.y,

    c2.x - ca * c2.r * uv.x + sa * c2.r * uv.y,
    c2.y - sa * c2.r * uv.x - ca * c2.r * uv.y, 
    c2.x - ca * c2.r * uv.x - sa * c2.r * uv.y, 
    c2.y + sa * c2.r * uv.x - ca * c2.r * uv.y 
];


Ответ 2

На картинке 2 из вашего вопроса имеется две окружности с центрами в точках c1 и c2
радиусов r1 и r2. Центры окружностей соединены прямой. Необходимо в каждой окружности
провести 2 диаметра перпендикулярных отрезку, соединяющему центры. Точки пересечений
диаметров с окружностью образуют искомый четырехугольник (трапецию).

circles: [
        { r: 20, x: 50, y: 150, f: 'black'},   // c1
        { r: 50, x: 150, y: 100, f: 'black'}   // c2
    ]


Для решения необходимо определить угол alpha между вектором c1c2 и осью Х. После
чего будет понятно, под каким углом проходят диаметры. Нам потребуется поставить 4
точки, каждая из которых будет удалена от центра на расстояние радиуса под углом alpha
+ 90 или alpha - 90.

Как известно, тангенс угла в прямоугольном треугольнике равен отношению длины противолежащего
катета к прилежащему. Так что угол alpha достаточно просто вычисляется с помощью формулы
(не рассматриваем ситуацию когда x1=x2):

let alpha = Math.atan( (c2.y - c1.y) / (c2.x-c1.x) );


Если нам известна исходная точка (x0, y0), и нам надо сдвинуться на расстояние R
под углом a, то координаты новой точки будут иметь вид x1 = x0 + R*Cos(a) и y1 = y0
+ R*Sin(a).
В данном случае R будет принимать значения r1 и r2 (радиусов окружностей), а угол
с поворотом на 90 градусов -  alpha + PI/2 и alpha - PI/2.

В исходном виде формула для вычисления координат первой точки будет иметь вид

x1 = c1.x + Math.cos(alpha + Math.PI/2)*c1.r;
y1 = c1.y + Math.sin(alpha + Math.PI/2)*c1.r;


Для второй - то же самое с углом alpha - Math.PI/2. Затем аналогичные равенства для
окружности c2.

Вспомнив тригонометрические формулы приведения (про углы α ± π/2 и -α) все эти вычисления
сводятся к следующему:

let cosA = Math.cos(alpha);
let sinA = Math.sin(alpha);

let ps = [
    c1.x - sinA*c1.r, // x1 
    c1.y + cosA*c1.r, // y1    
    c1.x + sinA*c1.r, // x2 
    c1.y - cosA*c1.r, // y2

    c2.x + sinA*c2.r, // x3 
    c2.y - cosA*c2.r, // y3
    c2.x - sinA*c2.r, // x4 
    c2.y + cosA*c2.r, // y4        
];


jsfidlle

Угол между шарами одинаковой массы после столкновения (упругого)

#физика #2d

Симулирую столкновения шаров в 2D, сделал столкновения о стенки, теперь встал перед
проблемой определения угла между ними после нецентрального удара. Пусть векторы скоростей
шаров соответственно равны v1, и v2. Иза за одинаковой массы, как объясняется в матчасти,
следует, что шары после столкновения, в этом случае просто обменяются скоростями, а
угол между ними всегда будет прямым (как я понял, это угол между направляющими линиями(векторами)
шаров после удара). Мне не понятно почему говорится ВСЕГДА этот угол будет прямым ???
Везде даются картинки и пояснения когда этот угол выходит точно в 90 градусов.
Сомневаясь до отчаяния, нашёл таки пример удара когда угол не прямой. Например здесь
можно построить подобный удар. На рисунках показаны результаты до и после удара.

До удара:



после

Так что же тут происходит ?? Какой тут угол будет всегда прямым ?? Я не вижу тут
никаких прямых углов! Что я не понимаю ?? Поясните пожалуйста поподрбней.
    

Ответы

Ответ 1

В моём понимании задачки подобного рода решаются очень просто.

На рисунке вверху два изображения. До удара (слева) и после удара (справа). 
Исходные вектора скоростей взяты произвольно. 
Кратко разъясню суть.


Шары как-то движутся.
Шары ударяются. В момент удара шары деформируются в месте контакта.
Энергия деформации на все 100% переходит в кинетическую энергию шаров. 


Работает закон сохранения импульса и закон сохранения энергии. Что касается импульса
- это величина векторная. Поэтому её(как и скорость) можно разложить на две составляющие.
Ось ОХ совмещается с линией, которая соединяет центры шаров. Ось OY ⊥ OX. 

Вертикальная(OY) составляющая импульса на удар влияния не оказывает. Поэтому она
остается неизменной. А горизонтальными составляющими импульса шары просто обмениваются.
Итого:


V2OY = V2*OY
V1OY = V1*OY
V2OX = V1*OX
V1OX = V2*OX


А под 90 градусов шары разлетятся в случае если один из шаров неподвижен.

Высококачественное масштабирование двумерных текстур

#cpp #windows #directx #2d #texture

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

P.S. Возможно использование сторонних библиотек.
    

Ответы

Ответ 1

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




Не забудьте закрасить фон



проверить, что текст влезает в полученную текстуру, иначе уменьшить его


Ответ 2

Наилучший результат как при уменьшении, так и при увеличении дают свёрточные фильтры.

При их использовании уменьшение изображения очень похоже на наивное уменьшение, когда
мы просто выбираем пиксели с определённым интервалом. Но чтобы не появилась некрасивая
рябь, фильтр берёт не просто пиксели, а взвешенную сумму всех соседей на некотором
расстоянии от этого пикселя:



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

Источник изображения: https://habrahabr.ru/post/142818/

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

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



Соответственно, вам подойдёт любая библиотека, работающая с этим фильтром. Вот несколько
примеров:


avir,
fpresize.


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


Ответ 3

Переношу в ответ информацию из комментариев, для истории.


  Да в общем-то, в текущем виде, ответ на вопрос - "никак". Текстура
  DirectX - обычное растровое изображение, уменьшение растрового
  изображения в 2 раза означает потерю 50% информации. Для шрифта 10
  размера при стандартном DPI это значит, что он будет нечитаем - тут
  ничего не поделать. Но, более общая задача - представить информацию с
  рабочего стола пользователя в таком виде, что ее можно отобразить в
  любом масштабе, скорее всего решаема. Ведь текст в приложениях не
  зарождается изначально в растровом виде, а выводится вызовом вполне
  определенного набора функций из GDI, GDI+ и DirectWrite.





  Про механику DWM мало знаю. Но для текущей задачи он бесполезен, так
  как оперирует теми же текстурами. Я намекаю на другое - замена на
  целевой системе библиотек gdi и DirectWrite на свои взломанные версии,
  которые бы логировали аргументы, передаваемые функциям вывода текста,
  чтобы потом вызвать их с другим масштабом.

Готовые наборы тайлсетов для игр

Доброго времени суток, Хэшкод.
В свободное от работы время начал потихоньку изучать xna. Подготовил двумерный изометрический тайловый движок, даже нашел подходящий редактор под него, однако осталась одна проблема - нашел очень мало нормальных тайлсетов. Художник и дизайнер из меня, прямо скажу, аховый, так что вариант "нарисовать самому" я оставляю на самый крайний случай. При попытке найти что-то в сети в основном получаю какой-то лохматый "ужос"... В общем - не нашел.
Собственно у меня вопросы:
Есть ли сайты, на которых есть нормальные тайлсеты? Есть ли нормальные редакторы для создания тайсетов? (можно конечно и в Paint-е(Gimp-е/Photoshop-е) что-то наваять, но с моими навыками "рисования"... в общем, хотелось бы что-то более специализированное)
Пример тайлсета, если кто не знает, что это такое:
[upd] Да, вопрос получился конечно не по программированию, но извиняюсь. Больше мне спрашивать негде.

Ответ

Вы когда нибудь пробовали собрать toolbar для оконного приложения с помощью сайта который представляет бесплатные иконки от разных людей? Ваш toolbar получится не ахти, так как все иконки будут нарисованы разными людьми в разном стиле и цветовой гамме. Даже если вы будете долго копаться на нескольких таких сайтах в поисках единого стиля, то наврятли получится что-то стоящее, т.к. совершенно не факт что вы найдете даже готовый набор полностью удовлетворяющий вашим нуждам. Тоже самое и с тайлсетом. Их все должен рисовать один человек в одном стиле по одному документу, на gamedev.ru и фриланс сайтах есть десятки людей которые с радостью возьмутся выполнить такой заказ по вполне адекватной цене(реальная рыночная цена тому что вы приводите в качестве примера не больше 100-300 рублей за полоску), да и качество будет вполне ничего, если вы конечно потрудитесь отобрать достойного кандидата. В качестве редактора можно использовать Photoshop и 3DSMax ну или Blender и GIMP если вы красноглазик. Специальный редактор для тайлсетов это плохая идея потому что непонятно чем собственно тайлсет отличается от обычной картинки. Самому рисовать их ни в коем случае нельзя, так как если у вас нет хотя бы пары лет опыта работы с графическими редакторами и хотя бы зачатков умений художника, то в лучшем случае у вас получится результат которым можно только пугать других людей. С другой стороны с попытки с 50ой может и получится что-нибудь хорошее, но тогда вы просто потеряете время. Правда есть и альтернативный вариант: http://lunar.lostgarden.com/labels/free%20game%20graphics.html http://hasgraphics.com/ http://cgtextures.com/ http://blogoscoped.com/archive/2006-08-08-n51.html http://www.freewebs.com/teh_pro/sprites.htm http://www.spriters-resource.com/ http://www.flyingyogi.com/fun/spritelib.html http://www.gamedev.net/topic/272386-sprites-sprites-and-more-sprites/ P.S. Собирать игры в качестве хобби это плохая идея, так как это требует очень много свободного времени и усилий. Нужно либо делать это нормально либо вообще не делать.

Преобразование ломаной линии

Я имею неравномерную сетку в виде координат узлов в двумерном пространстве Узлы сетки хранятся в одномерном векторе, где нумерация снизу-вверх слева-направо

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

Ответ

0) Учащаем точки ломаной: в цикле определяем расстояние между соседними точками (D) у ломаной, если это расстояние больше, чем расстояние диагонали ячейки сетки (d), то вставляем дополнительною точку.

Это шаг предобработки ломаной. В конце объясню зачем это нужно
1) Определяем ближайший узел (curr_node) к начальной точке (p) исходной ломаной
Далее в цикле:
2) Определяем соседние узлы для curr_node (соседями не считать предыдущий посещенный узел)

3) Определяем расстояние от curr_node и от его соседних узлов до следующей точки ломаной (p_next).

4) Если расстояние от curr_node до p_next меньше, чем минимальное расстояние от его соседей до p_next, то p_next станет следующей точкой ломаной, иначе "посещаю" следующий узел сетки (тот соседний узел, который ближе всего к точке p_next)
Далее возвращаемся к шагу 2
В итоге получаем такую картину посещения узлов

т.е. собирая посещенные узлы (черные), получаем такую ломаную, проходящую по узлам сетки:

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

Контур произвольного полигона

Имеется векторный полигон в программе (в виде команд его рисования). Задача - расширить этот полигон во все стороны на заданное расстояние. То есть, получить его контур или окаёмку с учётом возможных внутренних коллизий. Интересует, собственно, алгоритм сего действа. Желательно, не особо ресурсоёмкий. Либо просто литература, где про это можно почитать. Самое, что интересное: обработка самопересечений в замкнутых областях (как внутренняя дырка в букве "я" - заполнилась целиком). закругления в углах. Как сделать без закруглений более-менее понятно (провести параллельные линии на заданном расстоянии). Или концы отрезков с помощью безье соединить?.. Чёрным обозначена исходная область, а синим - итоговая (для различной толщины контура). В крайнем случае, можно отталкиваться и от готового растра исходного полигона.

Ответ

Векторный случай Если предположить, что вы уже перешли к векторному формату, то: рассматриваете последовательно ребра полигона в одном направлении (например, против часовой стрелки). Это важно, т.к. повлияет на ориентацию направляющих векторов ребер полигона. Для каждого ребра вычисляете нормаль (это нормализованный вектор, перпендикулярный направляющему вектору ребра). В вашем случае также следует проследить, чтобы нормаль была направлена "от" полигона, а не "внутрь" него. умножаете каждую нормаль на коэффициент "расширения" k. прибавляете нормаль к начальной (u) и к конечной (v) вершинам ребра (вершины рассматриваем как векторы, исходящие из начала координат). Получаем "расширенные" вершины u' и v'. Эти вершины определяют начало и конец "расширенного" ребра. Кроме того, в итоге на каждую вершину полигона будет получено по две (в общем случае неколлиниарных) "расширенных" вершины u' и u'' (они будут вычислены для смежных ребер с общей вершиной u). Их можно использовать, чтобы сделать "закругление" (наиболее очевидный способ: строить промежуточные вершины поворотом u' к u'' малым угловым шагом). Нужно еще выявлять ситуации самопересечений и обрабатывать их. Боюсь соврать, но по-моему тут надо смотреть знаки смешанных произведений нормалей ребер и вектора (0,0,1). При выбранном направлении обхода полигона знак этого произведения должен меняться только для "вогнутых" пар ребер (образующих "невыпуклости" полигона). Кажется так.. Почитать можно что-то по аналитической геометрии и векторной арифметике. UPD: Как вариант можете еще глянуть эту книгу: Steven M. LaValle. Planning Algorithms. В ней охвачен широчайший спектр вопросов, в т.ч. и работа с полигонами. Растровый случай Думаю, практически в любом случае есть смысл заняться преобразованием в векторное представление. Для определения границ можно попробовать использовать алгоритм пересечения полигона отрезком, паралелльным какой-либо оси координат + читать цвета пикселей. Еще один вариант - как-то попробовать модифицировать алгоритм заливки полигона. Тут уже менее очевидно, надо думать или искать готовый векторизатор:)

Угол между шарами одинаковой массы после столкновения (упругого)

Симулирую столкновения шаров в 2D, сделал столкновения о стенки, теперь встал перед проблемой определения угла между ними после нецентрального удара. Пусть векторы скоростей шаров соответственно равны v1, и v2. Иза за одинаковой массы, как объясняется в матчасти, следует, что шары после столкновения, в этом случае просто обменяются скоростями, а угол между ними всегда будет прямым (как я понял, это угол между направляющими линиями(векторами) шаров после удара). Мне не понятно почему говорится ВСЕГДА этот угол будет прямым ??? Везде даются картинки и пояснения когда этот угол выходит точно в 90 градусов. Сомневаясь до отчаяния, нашёл таки пример удара когда угол не прямой. Например здесь можно построить подобный удар. На рисунках показаны результаты до и после удара.
До удара:
после
Так что же тут происходит ?? Какой тут угол будет всегда прямым ?? Я не вижу тут никаких прямых углов! Что я не понимаю ?? Поясните пожалуйста поподрбней.

Ответ

В моём понимании задачки подобного рода решаются очень просто. На рисунке вверху два изображения. До удара (слева) и после удара (справа). Исходные вектора скоростей взяты произвольно. Кратко разъясню суть.
Шары как-то движутся. Шары ударяются. В момент удара шары деформируются в месте контакта. Энергия деформации на все 100% переходит в кинетическую энергию шаров.
Работает закон сохранения импульса и закон сохранения энергии. Что касается импульса - это величина векторная. Поэтому её(как и скорость) можно разложить на две составляющие. Ось ОХ совмещается с линией, которая соединяет центры шаров. Ось OY ⊥ OX.
Вертикальная(OY) составляющая импульса на удар влияния не оказывает. Поэтому она остается неизменной. А горизонтальными составляющими импульса шары просто обмениваются. Итого:
V2OY = V2*OY V1OY = V1*OY V2OX = V1*OX V1OX = V2*OX
А под 90 градусов шары разлетятся в случае если один из шаров неподвижен.