1 Востаннє редагувалося FakiNyan (04.06.2017 10:33:22)

Тема: Розподілення фігурок на полі

Є поле, і купка фігурок, і от треба покласти їх на те поле таким чином, аби вони не перетинались, і щоб лягали на поле якомога рівномірніше. Як то зробити?
http://prntscr.com/ffouxx
а ще фігурки можуть бути різних розмірів

2

Re: Розподілення фігурок на полі

Можна визначати координати поля. Якщо двомірне, то Х і Y, тримірне - X, Y, Z. Потім викладати фігурки по координатах і брати різницю вершин цих координат - це буде довжина фігурки, а власне вершини - крайні точки фігури. Це якщо вам потрібно повертати ті фігурки, щоб вони лежали як вам потрібно.
І також перевіряти інші координати, щоб не виникало колізії. Можна ще використати ААВВ для виявлення колізій, але це краще для тривимірної графіки.
А ще можна зробити розмітку поля. Також за допомогою координат.

3 Востаннє редагувалося FakiNyan (04.06.2017 14:31:13)

Re: Розподілення фігурок на полі

LoganRoss написав:

Можна визначати координати поля. Якщо двомірне, то Х і Y, тримірне - X, Y, Z. Потім викладати фігурки по координатах і брати різницю вершин цих координат - це буде довжина фігурки, а власне вершини - крайні точки фігури. Це якщо вам потрібно повертати ті фігурки, щоб вони лежали як вам потрібно.
І також перевіряти інші координати, щоб не виникало колізії. Можна ще використати ААВВ для виявлення колізій, але це краще для тривимірної графіки.
А ще можна зробити розмітку поля. Також за допомогою координат.

вово, AABB крута штука. Про розмітку поля, Ви маєте на увазі розбити поле на квадратики, і при розміщенні фігурки помічати квадратики, котрі вона займає, як використані?
і чому це AABB краще для 3d ? В 2d ж все так само буде, тільки замість паралелепіпедів будуть прямокутнички

4

Re: Розподілення фігурок на полі

FakiNyan написав:
LoganRoss написав:

Можна визначати координати поля. Якщо двомірне, то Х і Y, тримірне - X, Y, Z. Потім викладати фігурки по координатах і брати різницю вершин цих координат - це буде довжина фігурки, а власне вершини - крайні точки фігури. Це якщо вам потрібно повертати ті фігурки, щоб вони лежали як вам потрібно.
І також перевіряти інші координати, щоб не виникало колізії. Можна ще використати ААВВ для виявлення колізій, але це краще для тривимірної графіки.
А ще можна зробити розмітку поля. Також за допомогою координат.

вово, AABB крута штука. Про розмітку поля, Ви маєте на увазі розбити поле на квадратики, і при розміщенні фігурки помічати квадратики, котрі вона займає, як використані?
і чому це AABB краще для 3d ? В 2d ж все так само буде, тільки замість паралелепіпедів будуть прямокутнички

Так, щось типу того.
Ну так, в принципі так само як і для 3D. Просто ніколи не використовував ААВВ для 2D, а робив розмітку, так легше.

5

Re: Розподілення фігурок на полі

LoganRoss написав:
FakiNyan написав:
LoganRoss написав:

Можна визначати координати поля. Якщо двомірне, то Х і Y, тримірне - X, Y, Z. Потім викладати фігурки по координатах і брати різницю вершин цих координат - це буде довжина фігурки, а власне вершини - крайні точки фігури. Це якщо вам потрібно повертати ті фігурки, щоб вони лежали як вам потрібно.
І також перевіряти інші координати, щоб не виникало колізії. Можна ще використати ААВВ для виявлення колізій, але це краще для тривимірної графіки.
А ще можна зробити розмітку поля. Також за допомогою координат.

вово, AABB крута штука. Про розмітку поля, Ви маєте на увазі розбити поле на квадратики, і при розміщенні фігурки помічати квадратики, котрі вона займає, як використані?
і чому це AABB краще для 3d ? В 2d ж все так само буде, тільки замість паралелепіпедів будуть прямокутнички

Так, щось типу того.
Ну так, в принципі так само як і для 3D. Просто ніколи не використовував ААВВ для 2D, а робив розмітку, так легше.

ну окей, розмітку можемо зробити, або перевірити колізії за допомогою AABB, а як тоді розраховувати позицію для нової фігурки? Бо якщо рандомно брати позицію, то ми ж можемо пів дня намагатись впихнути фігурку в невпіхуємоє місце

6

Re: Розподілення фігурок на полі

Є одна думка.
Ось наприклад, в нас є aabb
https://replace.org.ua/extensions/om_images/img/59342460485ce/14281726.png
В нього є висота і ширина.
Відповідно, в нас є поле, в яке ці aabb (фігурки) поміщаються. Це поле теж має ширину і висоту - координати X, Y.
Поміщаємо першу фігурку і додаємо до початкового значення Х її ширину, тобто ширину aabb. Відповідно, отримані координати Х тепер будуть початковими координатами для розміщення нової фігури і т.д. Коли ширина поля стане меншою за ширину наступної фігури, то переходимо на новий "рядок" - додаємо до Y висоту найвищої фігури в першому рядку. І так поміщаємо фігури поки X та Y не стане менше Width та Height aabb - тоді нова фігурка не "залізе".
Ось візуальне представлення, може буде краще зрозуміло:
https://replace.org.ua/extensions/om_images/img/59342460485ce/14236656.png

Подякували: 0xDADA11C7, FakiNyan2

7

Re: Розподілення фігурок на полі

FakiNyan написав:

Є поле, і купка фігурок, і от треба покласти їх на те поле таким чином, аби вони не перетинались, і щоб лягали на поле якомога рівномірніше.

Якомога рівномірніше — строго рівномірно чи щоб виглядали рівномірно?

8

Re: Розподілення фігурок на полі

quez написав:
FakiNyan написав:

Є поле, і купка фігурок, і от треба покласти їх на те поле таким чином, аби вони не перетинались, і щоб лягали на поле якомога рівномірніше.

Якомога рівномірніше — строго рівномірно чи щоб виглядали рівномірно?

щоб виглядало рівномірно

9

Re: Розподілення фігурок на полі

LoganRoss написав:

Є одна думка...]

небогано, тілько після цього може залишитись дірка

10

Re: Розподілення фігурок на полі

FakiNyan написав:
quez написав:
FakiNyan написав:

Є поле, і купка фігурок, і от треба покласти їх на те поле таким чином, аби вони не перетинались, і щоб лягали на поле якомога рівномірніше.

Якомога рівномірніше — строго рівномірно чи щоб виглядали рівномірно?

щоб виглядало рівномірно

  • Розбиваємо фігурки на невеликі фрагменти

  • Кожному фрагменту надаємо заряд

  • Також деякий заряд даємо межам поля

  • В результаті фігурки автоматично розподіляться рівномірно по полю.

Подякували: Arete1

11

Re: Розподілення фігурок на полі

а нащо межам поля давати? фігурки повинні мати змогу розміщуватись біля бортиків

12

Re: Розподілення фігурок на полі

FakiNyan написав:

а нащо межам поля давати? фігурки повинні мати змогу розміщуватись біля бортиків

Якщо в меж не буде заряду, то всі фігурки розмістяться рівномірно впритул до межі.

13

Re: Розподілення фігурок на полі

я так зрозумів, все це поле можна уявити в вигляді шматка пласкої землі, і при розміщення в якійсь позиції фігурки, ми піднімаємо в цьому місці землю, і при розміщенні інших фігурок ми знаходимо найнижчу точку, і ставимо в тій точці нову фігурку?

14

Re: Розподілення фігурок на полі

FakiNyan написав:

я так зрозумів, все це поле можна уявити в вигляді шматка пласкої землі, і при розміщення в якійсь позиції фігурки, ми піднімаємо в цьому місці землю, і при розміщенні інших фігурок ми знаходимо найнижчу точку, і ставимо в тій точці нову фігурку?

Якщо поставлена фігурка зміщує ті, які вже стоять, то так.

15

Re: Розподілення фігурок на полі

якийсь складний алгоритм виходе

16

Re: Розподілення фігурок на полі

нагуглив про метод Лойда. Там спочатку треба побудувати діаграму Вороного (до речі, це український математик, колись був), а потім ця діаграма типу нормалізується, ну таке.
Але це якось занадто для моєї гри. Тому я просто понаставляю на полі купу міток, на місці котрих потім будуть з'являтись об'єкти.