Wypełnianie terenu wodą

Odpowiedz Nowy wątek
2018-12-05 12:21
0

Cześć, na studia muszę napisać program, który będzie symulował jak teren wypełnia się wodą.
Napisałem wersję jednowątkową, teraz muszę to zrównoleglić.
Nie wiem jednak jak skutecznie podzielić mapę na fragmenty tak, aby nie było race condition.
Próbowałem blokować obszary w tablicy o rozmiarze 3x3, ale nic z tego nie wyszło.

Znacie może jakiś algorytm, który opisuje mój problem?
Szukałem w Internecie, ale to co znajdywałem zazwyczaj odnosiło się obliczania ile jednostek wody można zmieścić w terenie.

Uprzedzam, że nie szukam gotowca, a zwykłego naprowadzenia na rozwiązanie.

Dana jest macierz kodująca mapę, w której liczby oznaczają wysokości.

Wylicz ile punktów w macierzy zajmują lądy i oceany, największą i średnią głębokość oceanu, przy założeniu, że oceany
powstają poprzez wpuszczenie X jednostek wody w określonym punkcie:
- Woda spływa w dół (jeżeli może, tj. jeżeli wysokość+ilość wody jest większa od sąsiadujących punktów).
- Możliwe jest, że w punkcie jest jedna jednostka wody, a obok punkt ma taką samą wysokość. Woda wówczas nie spływa.
- Jeżeli woda może spłynąć w kilka miejsc naraz, początkowo spływa po równo w każdą stronę.
internal sealed class SingleThreadAlgorithm : IAlgorithm
    {
        public void FillArea(Map map, Coordinates centralCoordinates, int waterUnitCount)
        {
            for (int i = waterUnitCount; i > 0; i--)
            {
                map[centralCoordinates].IncreaseWaterLevel();
            }
 
            Fill(map, centralCoordinates);
        }
 
        private void Fill(Map map, Coordinates centralCoordinates)
        {
            var centralPoint = map[centralCoordinates];
 
            bool waterLevelDropped = true;
 
            // Rozlewamy równo wodę do sąsiadów tak długo jak możemy(robimy kółeczka)
            while(waterLevelDropped)
            {
                waterLevelDropped = FillAround(map, centralCoordinates, centralPoint);
            }
        }
 
        private bool FillAround(Map map, Coordinates centralCoordinates, Point centralPoint)
        {
            bool waterLevelDropped = false;
 
            var coordinates = new List<Coordinates>();
 
            for (int i = -1; i < 2; i++)
            {
                for (int j = -1; j < 2; j++)
                {
                    var neighbourCoordinates = new Coordinates(i + centralCoordinates.X, j + centralCoordinates.Y);
 
                    if (map.AreCoordinatesValid(neighbourCoordinates))
                    {
                        var neighbourPoint = map[neighbourCoordinates];
 
                        if (centralPoint.TotalLevel > neighbourPoint.TotalLevel + 1 && centralPoint.WaterLevel > 0)
                        {
                            centralPoint.DecreaseWaterLevel();
                            neighbourPoint.IncreaseWaterLevel();
 
                            coordinates.Add(neighbourCoordinates);
 
                            waterLevelDropped = true;
                        }
                    }
                }
            }
 
            // Woda spływa z sąsiadów do ich sąsiadów(jeśli może)
            foreach (var coordinate in coordinates)
            {
                Fill(map, coordinate);
            }
 
            return waterLevelDropped;
        }
    }

Input
Liczba jednostek wody: 20
Punkt startowy: 0,0
Mapa:
5,5,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2

Output
screenshot-20181205115517.png
Legenda - Wysokość: Wysokość terenu + Wysokość wody

Pozostało 580 znaków

2018-12-05 16:26
0

Trochę trudno jest czytać kod z telefonu, także niezbyt jestem świadom, co jest w Twojej implementacji - tak czy owak, jeżeli zrealizujesz algorytm w ten sposób, że komórki macierzy będą pamiętać stan poprzedni i nowy i ustalać stany na podstawie poprzedniego, lub będziesz wypełniać nową kopię macierzy na postawie stanu starej (na zasadzie automatu komórkowego, który opis zadania bardzo zresztą przypomina) to możesz rozłożyć zmianę stanu np. w poszczególnych wierszach czy blokach na wątki i synchronizować etap zastąpienia starych stanów nowymi np. barierą, bądź zamieniając starą i nową macierz w głównym wątku po zakończeniu pracy przez wszystkie wątki.

Warunek jest taki, by stary stan macierzy był read-only przez cały czas współbieżnej pracy wątków, a kolejne kroki były jakkolwiek zsynchronizowane - wtedy nie będziesz musiał się przejmować hazardami przy ustalaniu nowych stanów macierzy / stanów nowej macierzy.


Blocker wiszący od miesiąca? Mówisz o tym criticalu z zeszłego tygodnia? A, tak, zalogowaliśmy przedwczoraj tego minor buga. Pewnie, zajmę się ASAP tym enhancementem. Nie ma sprawy, jak tylko podomykam taski to wezmę się za ten ficzer, tylko go jeszcze wyestymujemy przed kolejnym sprintem.

Pozostało 580 znaków

2018-12-10 23:11
0

Może coś ci zaświta po spojrzeniu na algorytmy sortowania wielowątkowego.

edytowany 1x, ostatnio: Satanistyczny Awatar, 2018-12-10 23:11

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0