przez ostatni tydzień pracowałem nad systemem ekwipunku z Unity3D. Na początku otrzymałem pomoc od facetów z Design3, ale nie upłynęło dużo czasu, zanim podzieliliśmy ścieżkę, ponieważ tak naprawdę nie podobał mi się sposób, w jaki robili swój kod, nie miał żadnego zapachu OOP.
Zrobiłem to o krok dalej - przedmioty zajmują więcej niż jedno miejsce, zaawansowany system rozmieszczania (przedmioty starają się znaleźć najlepsze dopasowanie), lokalny system myszy (mysz zostaje uwięziona w aktywnym obszarze torby) itp.
Oto demo mojej pracy.
To, co chcielibyśmy mieć w naszej grze, to funkcja automatycznego organizowania, a nie automatyczne sortowanie. Chcemy tej funkcji, ponieważ nasze zapasy będą w czasie rzeczywistym - nie tak jak w Resident Evil 1,2,3 itd., Gdzie zatrzymasz grę i zrobisz rzeczy w swoim ekwipunku. Teraz wyobraź sobie siebie w lepkiej sytuacji w otoczeniu zombie, a nie masz pocisków, rozglądasz się, widzisz, że w pobliżu są pociski na ziemi, więc idź po nie i spróbuj je podnieść, ale nie nie pasuje! patrzysz na swój ekwipunek i dowiadujesz się, że jeśli reorganizujesz niektóre przedmioty, będzie pasować! - teraz gracz - w tej sytuacji nie ma czasu na reorganizację, ponieważ jest otoczony zombie i umrze, jeśli zatrzyma się i zorganizuje ekwipunek, aby zrobić miejsce (pamiętaj o ekwipunku w czasie rzeczywistym, bez pauzy) - czy byłoby miło, gdyby stało się to automatycznie? - Tak!
(Wierzę, że zostało to zaimplementowane w niektórych grach, takich jak oblężenie Dungeon lub coś takiego, więc na pewno jest to wykonalne)
spójrz na to zdjęcie na przykład:
Tak, więc jeśli automatycznie posortujesz problem, dostaniesz spacje, ale jest zły, ponieważ: 1 - Drogi: nie wymaga operacji sortowania, aby zwolnić te spacje, na pierwszym zdjęciu po prostu przesuń czerwony element na na dole po lewej stronie, a otrzymasz te same spacje, które otrzymałeś z automatycznego sortowania. 2- To irytuje gracza: „Kogo F powiedział ci, aby ponownie zamówić moje rzeczy?”
Nie pytam o to „Jak napisać kod”, po prostu proszę o wskazówki, gdzie szukać, jakie algorytmy są zaangażowane? Czy jest to związane z wykresami i najkrótszą ścieżką? Mam nadzieję, że nie, bo nie udało mi się kontynuować studiów: / Ale nawet jeśli tak jest, po prostu powiedz mi, a nauczę się rzeczy związanych z tym.
Zauważ, że może istnieć więcej niż jedno rozwiązanie. Sądzę więc, że pierwszą rzeczą, którą muszę zrobić, jest ustalenie, czy dana sytuacja jest „możliwa do rozwiązania” - jeśli wiem, jak ustalić, czy daną sytuację można rozwiązać, czy nie, to mogę ją „rozwiązać”. Muszę tylko poznać warunki, dzięki którym jest to „możliwe do rozwiązania”. I wierzę, że musi to być jakiś algorytm / struktura danych.
Oto zdjęcie przedstawiające więcej niż jedno rozwiązanie próby dopasowania przedmiotu 1x3:
Strzałki pokazują tylko jedno z rozwiązań, ale jeśli spojrzysz, znajdziesz więcej niż jedno. Tego ostatecznie nie sortuję automatycznie, ale znajduję rozwiązanie i stosuję je.
Zauważ, że jeśli spędzę nad tym czas, wymyślę sposób na rozwiązanie tego problemu, ale nie byłby to najlepszy sposób, to jakby trzymać koło samochodu stopami zamiast dłoni! XD Lub po prostu próbujesz rozwiązać problem, który wymaga tablic, ale jeszcze nie wiesz o ich istnieniu! Więc jakie jest właściwe podejście do tego?
Aktualizacje z komentarza
@Stephen Naprawdę nie jestem guru w Alogs, wspomniałeś o „plecaku” i @BlueRaja - Danny Pflughoeft wspominał o algo do pakowania bin 2D. Czy są w jakiś sposób spokrewnione / takie same? - Nadal jestem zdezorientowany, jak mam do tego podejść.
I tak, już korzystam z „heurystyki”, ale tak naprawdę nie wiedziałem, że jestem: D znajduje pierwszy dostępny slot i sprawdzam, czy przedmiot tam pasuje.
Nie wiem, czy zamawianie elementów na podstawie ich „objętościowości” (którą nazywam nSlotsRequired = nRowsReq * nColsRec) zadziałałoby, ponieważ na przykład masz elementy 2x2 i 1x4, mają one taką samą masowość, ale różne kształty i będą miały inny wpływ na przebieg pozostałych przedmiotów. WIĘC... :/
Obejrzałem ten film, bardzo spodobał mi się pomysł pełnego pakowania, ale zastanawiam się, jak sobie z tym poradzić, ponieważ inwentaryzacja jest 2D. Nie jestem nawet pewien, czy opakowanie na śmieci jest tutaj kluczem, ponieważ to prawda, że mogę mieć więcej niż jedną torbę, ale w naszej grze będzie to tylko jedna torba. Chodzi więc o umieszczenie przedmiotów w „jednej” torbie i nie więcej. Więc przykłady w tym vidie (rury i autobusy) tak naprawdę nie pasują do mojego problemu. Obejrzałem też kilka rzeczy o tym plecaku, nie widziałem, jak „wartość” jest powiązana z moimi przedmiotami / ekwipunkiem, ale wydaje mi się, że „waga” jest taka sama jak masowość, nie jestem pewien.
Odpowiedzi:
Jest to odmiana problemu plecakowego. Jak wspomina Danny Pflughoeft, jest to NP-Complete. Oznacza to, że nie da się tego rozwiązać w czasie liniowym, jeśli dobrze pamiętam.
Ale możesz spróbować rozwiązać to w kilku krokach. Zasadniczo jest to problem z sortowaniem.
Zacznę od obliczenia „objętości” każdego elementu: można to obliczyć na kilka sposobów:
puszystość = maks. (długość, szerokość);
puszystość = długość * szerokość
wielkość = sqrt (długość * szerokość)
Następnie zacznij umieszczać w ekwipunku przedmioty o najwyższym wyniku. Ponieważ najprawdopodobniej później nie zmieszczą się w pozostałej przestrzeni. Małe przedmioty zawsze będą pasować.
Potrzebujesz strategii heurystycznej (wymyślna nazwa dla zgadywanego zgadywania ;-)) do strategii umieszczania. Coś jak próba dopasowania przedmiotów w pierwszym wolnym miejscu od lewego górnego rogu lub coś takiego.
Myślę, że strategia sortowania zapasów w Diablo II działała nieco podobnie. Rzeczy takie jak miecze i włócznie kończyłyby się w lewym górnym rogu, potem ubrania i zbroje, a następnie puklerz i tak dalej.
Myślę, że naprawdę musisz to wypróbować i ulepszyć algorytm (różne obliczenia objętości, inna heurystyka), aż zadziała wystarczająco rozsądnie.
źródło
Haha, @ Każdy, kto pomógł, dzięki. W końcu udało mi się to rozwiązać. Oto, co właściwie zrobiłem:
AKTUALIZACJA:
Zrobiłem tablicę, która przechowuje indeksy wszystkich dodanych przedmiotów, dzięki czemu nie muszę iść i szukać zajętych miejsc, które mogę uwolnić - duże doładowanie.
nie trzeba dodawać na ostatnim polu, w rzeczywistości czasami może nie działać w ten sposób, dodałem poszukiwany przedmiot do pozostałych przedmiotów i posortowałem go razem z nimi.
Jak widać z wideo, wymaga to trochę optymalizacji, sortowanie nie jest idealne, chciałbym użyć pełnego pakowania bin, ale jest już chciwe pod względem wydajności. Jestem otwarty na wszelkie sugestie dotyczące optymalizacji, jeszcze raz dziękuję :)
źródło