.[ ČeskéHry.cz ].
Hledání místa s nejnižší hustotou
Jdi na stránku 1, 2  Další
 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
abuki



Založen: 31. 07. 2012
Příspěvky: 504
Bydliště: Praha

PříspěvekZaslal: 21. listopad 2017, 09:26:16    Předmět: Hledání místa s nejnižší hustotou Odpovědět s citátem

Ahoj,

potřeboval bych navést, pravděpodobně bude existovat nějaký algoritmus?
Mám plochu (jsem ve 2d) a na ní umístěné obdélníky (ale pro jednoduchost klidně můžeme říct body - středy obdélníků) a já hledám místo na té ploše, kde je nejmenší hustota těch bodů/obdélníků.

Nebo-li mám stůl s rozházenejma kartama a když přidávám další kartu tak chci najít nějaký nejvíc prázdný místo, kam plácnout novou kartu.

Stačila by mi asi nějaká fakt jednoduchá aproximace, nepotřebuju nic přesného, spíš jednoduchého a rychlého.
_________________
Twitter @abukac
www.circusatos.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
pcmaster



Založen: 28. 07. 2007
Příspěvky: 1782

PříspěvekZaslal: 21. listopad 2017, 10:13:04    Předmět: Odpovědět s citátem

Strelim od brucha.

Vytvor si uniform-grid s nejakym vhodnym rozlisenim. V kazdej bunke budes mat pocet stredov obdlznikov, ktore tam padli (vyroba: O(n)). Bunku s minimalnou hodnotou uz zistis velmi jednoducho. A mozes si v pripade, ze ich je viac, vybrat tu najblizsie k stredu. A tam uz urobit presnu koliziu s kartami, aby si zistil, ci ti to tam fakt vlezie. Bude to sakra rychle Smile

Pripadne nad tym (ci namiesto toho) mozes postavit nejaku hierarchicku strukturu (multi-level uniform-grid pripadne strom (kD, BVH, BSP, quad, ...)). Ale nekomplikoval by som to Smile
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.


Naposledy upravil pcmaster dne 21. listopad 2017, 13:19:59, celkově upraveno 1 krát
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
]semo[



Založen: 29. 07. 2007
Příspěvky: 1482
Bydliště: Telč

PříspěvekZaslal: 21. listopad 2017, 11:15:40    Předmět: Odpovědět s citátem

Nebo použít "multiple choice algoritmus": náhodně vygeneruješ X míst, ohodnotíš je a vybereš to nejlepší z nich. Ohodnocení by mohlo spočívat v nějaké funkci vzdáleností obdélníků a bodu (minimální vzdálenost, medián...?).

Jinou možnost bych viděl v nějakým odpuzování bodu. Hodit bod do plochy a provést N iterací, přičemž v každé iteraci by každý obdélník odpuzoval tento bod od svého středu (silou přímo úměrnou velikost plochy toho obdélníku). Po několika iteracích bude bod na správném místě.
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory


Naposledy upravil ]semo[ dne 21. listopad 2017, 11:17:46, celkově upraveno 1 krát
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
micky



Založen: 28. 02. 2008
Příspěvky: 345
Bydliště: Plzeň, Praha

PříspěvekZaslal: 21. listopad 2017, 11:17:18    Předmět: Odpovědět s citátem

A nebo použít Voronoi diagram/Delaunay triangulaci, přes něj se dá najít největší prázdná kružnice.



Ale ten uniform grid bude na implementaci jednodušší...
_________________
http://www.bluepulsar.cz/
https://twitter.com/bluepulsargames/
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Radis



Založen: 29. 03. 2014
Příspěvky: 228

PříspěvekZaslal: 21. listopad 2017, 13:12:38    Předmět: Odpovědět s citátem

Urcite se priklanim k pcmasterovi, vsechno ostatni je overkill. Pridani karty je O(1) a je to jednoduche na implementaci. Kdysi jsem neco podobneho resil presne timto zpusobem (dva gridy "pres sebe" - vetsi a mensi bunky).
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
]semo[



Založen: 29. 07. 2007
Příspěvky: 1482
Bydliště: Telč

PříspěvekZaslal: 21. listopad 2017, 13:41:32    Předmět: Odpovědět s citátem

Naopak mřížka je overkill. Buď ji musíš vždy vytvořit znovu, nebo řešit nějaký updaty pozic obdélníků (přesun, odebrání). Navíc bys musel laborovat s velikostí. I ta složitost O(1) neni podle mě pravda (nejde o přidání, ale o dotaz na volné místo). Ale je to intuitivní a fungovat to bude, o tom žádná.

Delaunay sice overkill taky je, ale je to skvělý nápad. Najde to skutečně dobré místo. Záleží, na co bys to potřeboval a jak přesně.

Multiple choice by mohl být na implementaci nejjednodušší a přitom by byl i dostatečně škálovatelný a rychlý.

Odpuzování bodu bude ve výsledku rychlé taky, i když má více průchodů. Iterace provádíš nad menší pamětí, která by mohla být navíc při dalším průchodu dobře nakešovaná (pokud zrovna nebudeš procházet pole pointerů na obdélníky, ale uložíš se pozice do pole).


Já bych to trochu zkombinoval: rozházel pár bodů náhodně, pár bodů podle mřížky, párkrát bych je odpudil těma kartma a nakonec bych vybral ten nejlepší :-D. A ten bych vložil do Delaunayovi triangulace, aby micky nebyl smutný ;-).
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
abuki



Založen: 31. 07. 2012
Příspěvky: 504
Bydliště: Praha

PříspěvekZaslal: 21. listopad 2017, 13:55:45    Předmět: Odpovědět s citátem

Díky všam za návhry.

Multiple choice mi přijde nejjednodušší. Nicméně se vlastně trochu bojim tý šance na nepřesnost.

U mřížky si řikám, že bude snadný trefit buňku, která je sice prázdná, ale hraničí s hromadou jiných. Nevím jestli bych pak nemusel počítat celý obsah obdélníku (ne jen jeho střed) a tím by se to asi dost zkomplikovalo.

Voronoi už jsem viděl v nějakym příkladu pro generování levelů, tak možná nakonec půjdu do toho. Sice to je možná overkill, ale zas bych do toho rád proniknul.

micky: můžeš mě navést jak se to počítá? Normálně docela obstojně googlim, ale v matematickýh koutech internetu mi to moc nejde.
_________________
Twitter @abukac
www.circusatos.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
abuki



Založen: 31. 07. 2012
Příspěvky: 504
Bydliště: Praha

PříspěvekZaslal: 21. listopad 2017, 14:01:11    Předmět: Odpovědět s citátem

Je totiž fakt, že by bylo pěkný, kdyby se ta karta fakt dala na nejprázdnější místo, což odpovídá středu té nejprázdnější kružnice.
_________________
Twitter @abukac
www.circusatos.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Radis



Založen: 29. 03. 2014
Příspěvky: 228

PříspěvekZaslal: 21. listopad 2017, 14:08:33    Předmět: Odpovědět s citátem

citace:
U mřížky si řikám, že bude snadný trefit buňku, která je sice prázdná, ale hraničí s hromadou jiných.

To bys prave resil tim, ze bys mel vic gridu s ruznymi velikostmi bunek. Dejme tomu, ze bys mel pole rozdelene na 4 kvadranty. Pak by ses mohl zeptat, ve kterem kvadrantu je nejmin karet. A z toho kvadrantu vybrat zase kvadrant, ve kterem je jich nejmin. A mel bys treba tri urovne takhle. Ale nevim, jestli je to pro tebe pouzitelne reseni.

]semo[ to fakt zalezi na tom, co presne abuki potrebuje. O(1) by to podle me bylo - kazde bunky v nejvetsim gridu by ses zeptal, kolik obsahuje karet. A to same bys potom udelal pro "mensi" bunky uvnitr tehle.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 550

PříspěvekZaslal: 21. listopad 2017, 14:19:12    Předmět: Odpovědět s citátem

]semo[ napsal:
Já bych to trochu zkombinoval: rozházel pár bodů náhodně, pár bodů podle mřížky, párkrát bych je odpudil těma kartma a nakonec bych vybral ten nejlepší Very Happy. A ten bych vložil do Delaunayovi triangulace, aby micky nebyl smutný Wink.

Laughing

Taky bych se přiklonil k náhodným bodům, pak ohodnotit podle vzdálenosti a vybrat nejvzdálenější, bude to mít variabilitu a dobrou distribuci (nebude to O(1), ale pro malé n je to jedno) a naprosto triviální na implementaci.

DT je zajímavý nápad, ale
1) deterministické
2) kde vezmeš první 3 body
3) pro 3 body vrátí bod uvnitř (tj. blízko)
4) ukaž mi, jak naimplementuješ robustní a rychlou DT za jedno odpoledne Wink
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
]semo[



Založen: 29. 07. 2007
Příspěvky: 1482
Bydliště: Telč

PříspěvekZaslal: 21. listopad 2017, 14:26:09    Předmět: Odpovědět s citátem

Radis napsal:
to fakt zalezi na tom, co presne abuki potrebuje. O(1) by to podle me bylo - kazde bunky v nejvetsim gridu by ses zeptal, kolik obsahuje karet. A to same bys potom udelal pro "mensi" bunky uvnitr tehle.

Tak to je quadtree. A tím, že se ptáš každé buňky v tom levelu, takto neni O(1) ale nějaký log. Ale rychlý to samozřejmě je.

abuki: Hledej Delaunay triangulation. Má to s Voronoi úzkou souvislost. Algoritmů je vícero (rozděl a panuj, iterativní zvětšování od středu, vkládání do existující triangulace...). Případně v rastru tohle: http://blackpawn.com/texts/cellular/. Matematika tam složitá neni. Rychlé to nebude, ale je fakt, že když do toho pronikneš, objevíš celou řadou věcí, na který se to hodí. I negrafický.

Sorry, že sem trochu odpověděl za mickyho, ale dneska se v práci trcohu nudím a navíc tohle taky používám.
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
micky



Založen: 28. 02. 2008
Příspěvky: 345
Bydliště: Plzeň, Praha

PříspěvekZaslal: 21. listopad 2017, 14:26:30    Předmět: Odpovědět s citátem

Ono je to hezky vidět na Voronoi, ale implementoval bych to asi přes Delaunayho triangulaci, jak říkal ]semo[. Je to de facto ta samá struktura, jen jsou spojeny středy buněk úsečkami a tvoří tak trojúhelníkovou síť.



Vlastností Delaunay je, že kružnice opsaná kolem libovolného trojúhelníku neobsahuje žádný vrchol jiného trojúhelníku.



Algoritmy/ukázky sestrojení jsou na internetu, určitě budou lepší než moje polovičaté vysvětlení v pár větách. Nic složitého to opravdu není.

Pak stačí všechny ty trojúhelníky projít a vybrat ten s největší kružnicí opsanou. Na to jsou vzorečky. Smile

https://www.mathopenref.com/trianglecircumcircle.html

Do toho trojúhelníku vložíš nový bod/kartu. Může to být přesně do středu té kružnice opsané, ale trochu randomizovat není ve hře na škodu. Vkládání do Delaunay sítě se dá opět někde vyhledat. Druhá možnost je jí zkonstruovat celou znovu, nečekám, že budeš mít na ploše desetitisíce karet. Smile

Osobně se mi teď líbí nejvíc ta semova iterativní metoda, jen by se muselo dát bacha, aby ta karta neodputovala pryč z obrazu. Vyladit parametry.
_________________
http://www.bluepulsar.cz/
https://twitter.com/bluepulsargames/


Naposledy upravil micky dne 21. listopad 2017, 14:36:38, celkově upraveno 2 krát
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
micky



Založen: 28. 02. 2008
Příspěvky: 345
Bydliště: Plzeň, Praha

PříspěvekZaslal: 21. listopad 2017, 14:29:05    Předmět: Odpovědět s citátem

Proboha, matematická otázka a my se můžem přetrhnout Very Happy

V rastru jsem si s tím kdysi hrál, na školním webu je to pořád dostupné. http://home.zcu.cz/~zakm7/voronoi/
_________________
http://www.bluepulsar.cz/
https://twitter.com/bluepulsargames/
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
abuki



Založen: 31. 07. 2012
Příspěvky: 504
Bydliště: Praha

PříspěvekZaslal: 21. listopad 2017, 14:36:31    Předmět: Odpovědět s citátem

Bohužel jsem zjistil, že vlastně asi nakonec to místo s nejmenší hustotou nehledám Very Happy
Asi budu dávat kartu vždy na stejné místo (kvůli konsistenci UX), ale vyřeším to tím, že kam dopadne, tam se ty ostatní odsunou trochu stranou.

Ale je mi to skoro až líto, protože jste tady popsali dost zajímavý věci. Ale asi si na to budu muset vymyslet jinou hru Smile
_________________
Twitter @abukac
www.circusatos.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
micky



Založen: 28. 02. 2008
Příspěvky: 345
Bydliště: Plzeň, Praha

PříspěvekZaslal: 21. listopad 2017, 14:40:55    Předmět: Odpovědět s citátem

Použij, co bude pro hru/aplikaci nejlepší. My už jsme si zamachrovali a jsme spokojení. Very Happy
_________________
http://www.bluepulsar.cz/
https://twitter.com/bluepulsargames/
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné Časy uváděny v GMT + 1 hodina
Jdi na stránku 1, 2  Další
Strana 1 z 2

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna