Toegankelijke cellen

Toegankelijke cellen

> Programmeren

Dit algoritme probeert de cellen te vinden die een prei kan bereiken uitgaande van een gegeven cel en aantal PM.

Dit resulteert in een functie die een cel en een getal als parameter neemt, en die een reeks cellen teruggeeft.

Als u wordt verteld over de functies "getAccessibleCells" of "getReachableCells", of een andere vergelijkbare naam, weet u nu wat het is.

Gebruik

Vanaf het moment dat u uw reizen wilt plannen, is deze functie essentieel.

Als je de cellen kent waar je heen kunt, kun je bijvoorbeeld de cel kiezen waar je de minste potentiële schade zult oplopen, of om te zien waar je naartoe zou kunnen gaan om je tegenstander schade toe te brengen.

Dit algoritme wordt met name gebruikt in het Cache-cache-algoritme (Le cache-cache).

Eerste methoden

Principe

Op zichzelf is het vrij eenvoudig om een manier te implementeren om de cellen toegankelijk te maken. De eenvoudigste methode is om de afstand tot elke cel op de kaart te testen met getPathLength.

Maar deze functie heeft hoge operationele kosten. Dus gebruik het op elke cel van de kaart... Uw bedrijfsverbruik zou omhoogschieten.

Een iets slimmere oplossing zou zijn om eerst de cellen binnen het bereik van PM te zoeken en vervolgens te controleren of ze bereikbaar zijn via getPathLength.

Als deze twee oplossingen haalbaar zijn, hebben ze een bedrijfskost die snel hoog wordt.

Als u een beginner bent en de oplossing die we hierna gaan bespreken nog steeds een beetje ingewikkeld lijkt, neem dan eerst gerust genoegen met deze oplossingen. Aan het begin van het spel heb je niet noodzakelijkerwijs veel berekeningen te doen, en op een laag niveau heb je niet veel MP. U kunt het zich dus veroorloven om deze oplossingen te gebruiken.

Het probleem

Uw cellen toegankelijk maken via deze methoden zal probleemloos zijn.

Maar een eerste probleem doet zich voor wanneer je aantal PM toeneemt. Hoe hoger hij klimt, hoe meer vakjes er natuurlijk zijn om te testen. In het ergste geval, als je de hele kaart doorloopt met getPathLength, zou je een rekening moeten krijgen van ongeveer 4 miljoen operaties, "slechts".

Het volstaat te zeggen dat dit de beschikbare bewerkingen voor andere algoritmen zoals Combo's of de Schadekaart aanzienlijk vermindert.

En dat is niet alles ! Er is nog een probleem: je bent niet alleen in een gevecht. Je zult zeker de toegankelijke cellen van je tegenstanders nodig hebben om jezelf tegen hun aanvallen te kunnen beschermen. En als de verschillende preien bollen beginnen op te roepen, zijn dat nog meer cellen om te berekenen.

Kortom, als je met deze methoden de toegankelijke cellen van heel deze kleine wereld wilt berekenen, kost dat je veel meer dan een arm.

Daarom gebruiken we een andere methode, veel effectiever: ga van buurman naar buurman!

Buurmanmethode

Vereisten

Ten eerste, wat is een "buurman"? De buren van een cel zijn gewoon de aangrenzende cellen. En we hebben het natuurlijk over de cellen die een gemeenschappelijke zijde hebben, de cellen die er direct naast staan, en niet die diagonaal.

De cellen in de hoeken van de kaart hebben dus één buur. Cellen aan de randen hebben er twee. En alle anderen hebben er vier.

Het eerste dat u moet weten, is het ophalen van de buren van een cel. Door de functies getCellX, getCellY en getCellFromXY te gebruiken, kunt u deze beroemde buren eenvoudig bepalen.

Zodra u de buren van een cel kunt ophalen, moet u bepalen of die cel "begaanbaar" is. Het is duidelijk dat als de cel een obstakel is of er een prei is, je prei er niet overheen kan bewegen.

Om dit te weten heb je de functies isObstacle, isLegeCell, isLeek of getCellContent nodig.

Principe

Het principe is eigenlijk vrij eenvoudig. Zelfs als het niet per se eenvoudig is om in te stellen voor een beginner in programmeren.

Je prei bevindt zich daarom op een cel en heeft een bepaald aantal MP om te verplaatsen. De cel waar hij momenteel op staat, bevindt zich op een afstand van 0 PM; Tot nu toe zo goed...

Als je prei 1 MP heeft, waar kan hij dan heen? Nou ja, op de vrije buren van zijn startcel.

Wat als hij 2 MP heeft? Het kan dus voor 1 PM bewegen op de vrije buren van zijn startcel. Maar ook, voor 2 PM, op de vrije buren van de vrije buren van de startcel.

Enzovoort...

<img src="https://i.ibb.co/7jdzBZr/Tuto-Cell-Accessible-Iteration.gif" alt="Tuto-Cell-Accessible -Iteratie" bor