Poszukuję pomocy w ulepszeniu algorytmu umieszczania bloków o dziwnych kształtach. Moja domena problemowa jest dziwna, ale najlepszą analogią do moich bloków są kawałki Tetrisa, z tym, że mogą mieć więcej niż cztery kawałki. Bloki wciąż składają się tylko z kątów prostych, ale mogą być długie i kręte, mogą rozgałęziać się itp.Algorytm układu bloków
Próbuję rozmieścić wiele dużych, dowolnie ukształtowanych klocków w minimalnej przestrzeni (wiem, że to opakowanie problem), ale moje obecne rozwiązanie wygląda paskudnie. Zasadniczo umieszczam jeden, a potem brutalnie wymuszam resztę, próbując umieścić je u źródła mojej siatki, a następnie powoli popychając je w różnych kierunkach, dopóki nie będą już kolidować. Nie jest powolna, ale nie próbuje ładnie dopasować elementów, aby nie marnowały całej przestrzeni.
Jedyne, co mogę wymyślić, to zamówienie klocków według rozmiaru, umieszczenie największego jako pierwszego, a następnie dopasowanie najmniejszego na końcu do pozostałych otworów. Ale są na pewno sposoby, które mogą się przydać.
Czy są tutaj jakieś algorytmy heurystyczne lub aproksymacyjne, które mogą mi w tym pomóc?
Wyniki będzie wyglądał tak:
także, być może mój gravatar zdradza, że jest to związane z Mega Man ...
Proszę dodać zdjęcie – Navin
Twój obraz wydaje się sugerować, że chcesz mieć przestrzeń między blokami. Czy to prawda? –
@Andrew Tak, zrobię to, ale mam przeczucie, że nie wpłynie to na algorytm. Mogłem tylko udawać, że bloki są grubsze o 1 jednostkę ze wszystkich stron. – Tesserex