Jakie jest znaczenie inicjalizacji poniższych tablic kierunków z podanymi wartościami podczas tworzenia programu szachowego?

106

Nie mam doświadczenia w programowaniu konkurencyjnym i często zauważyłem, że wielu świetnych programistów ma w swoim kodzie te cztery wiersze (szczególnie w przypadku tablic):

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

Co to naprawdę oznacza i do czego służy technika?

ejjyrex
źródło
5
Często używam d={0,1,0,-1,0}do tego: pary przedmiotów, które d[i], d[i+1]dają mi cztery główne kierunki.
dasblinkenlight
14
To zaskakująco dobre pytanie. ... Czy można coś zrobić z tytułem?
luser droog
7
Więc nie pomyślałeś, żeby wspomnieć, że ten kod pochodzi z silnika szachowego? Nie pomyślałeś też, żeby spojrzeć na siebie, jak te wartości są używane?
trojanfoe
15
„wielu wspaniałych programistów ma te cztery wiersze […]” - jestem w tym miejscu, ale gdyby byli świetnymi programistami, ich kod nie powodowałby, że zastanawiałbyś się „wtf czy to jest konstrukcja ?!”
utnapistim
6
@utnapistim Pisząc zdecydowaną większość kodu, masz rację, ale tutaj nie rozumiesz. Ta sprawa jest uzasadnionym wyjątkiem od tej zasady. Jeśli piszesz kod dla zawodów i masz ograniczenia czasowe, szybkie i łatwe jest prawie zawsze lepsze niż czyszczenie i konserwacja. W tym przypadku czytelne dla Ciebie, teraz naprawdę się liczy . Świetny programista bardzo dobrze pisze w tym kontekście niemożliwy do utrzymania, nieczytelny bałagan , nawet jeśli większość jego zwykłego kodu jest bardzo czytelna i łatwa do utrzymania.
Ben Lee

Odpowiedzi:

84

Jest to technika kodowania wszystkich kierunków jako tablic - każdej pary di[i],dj[i] jest w innym kierunku.

Jeśli wyobrazimy sobie, że mamy kawałek w miejscu x, y i chcemy dodać do jego wartości x i y, aby przenieść go w pobliskie miejsce, 1,0 to wschód, -1,0 to zachód, 0,1 to południe, 0, -1 to północ i tak dalej.

(Tutaj powiedziałem, że górny lewy to 0,0, a dolny prawy to 4,4 i pokazałem, jaki ruch każdy indeks tablic wykona od centralnego punktu, X, na 2,2.)

.....
.536.
.1X0.
.724.
.....

Sposób, w jaki jest ustawiony, jeśli zrobisz ^1( ^będąc bitowym XOR) na indeksie, otrzymasz odwrotny kierunek - 0 i 1 to przeciwieństwa, 2 i 3 to przeciwieństwa i tak dalej. (Innym sposobem ustawienia jest pójście zgodnie z ruchem wskazówek zegara, zaczynając od północy - wtedy^4 dostajesz się w przeciwnym kierunku.)

Teraz możesz przetestować wszystkie kierunki z danego punktu, przechodząc nad di i djtablice, zamiast wpisywać każdy kierunek w osobnej linii (w sumie osiem!) (Tylko nie zapomnij sprawdzić granic :))

diKi djKformuj wszystkie kierunki rycerzy zamiast wszystkich sąsiednich kierunków. Tutaj ^1odwróci się wzdłuż jednej osi, ^4da przeciwny skok skoczka.

.7.6.
0...5
..K..
1...4
.2.3.
Patashu
źródło
3
co to są „kierunki rycerzy”?
David
4
Och, taki rycerz.
David
1
Dziękuję bardzo za odpowiedź .. Czy mógłbyś połączyć mnie z linkiem lub może pokazać mi jakiś kod, aby lepiej to zilustrować .. (jestem trochę nowicjuszem .. jeśli potrafisz to zrozumieć :)
Jeszcze
1
Podziwiam próbę odpowiedzi Patashu. Chociaż wydaje się, że wielu zrozumiało jego wyjaśnienie, nie byłem w stanie go dobrze zrozumieć. Byłbym bardzo wdzięczny, gdyby ktoś mógł coś dodać do tego, co już zostało powiedziane.
deepak
1
@deepak Wyobraź sobie, że pozycja jest reprezentowana przez x,ykrotkę w przestrzeni 2D. Dla każdej pary di[i], dj[i]dodaj ją do, x,ya zostaniesz x,ytransponowany w każdym kierunku jeden po drugim. Czy to ma sens?
Patashu
64

Spróbuję to wyjaśnić tym, którzy uważają wyjaśnienie Patashu za trudne do zrozumienia.

Wyobraź sobie, że próbujesz rozważyć każdy możliwy ruch z danego punktu na szachownicy.

Jeśli zapętlisz tablice di i dj, interpretując wartości di jako przesunięcia x, a wartości dj jako przesunięcia y, obejmiesz każdy z 8 możliwych kierunków.

Zakładając, że dodatnie x to wschód, a dodatnie y to południe (tak jak w odpowiedzi Patashu), otrzymamy:

  | di / x | dj / y | Kierunek
- + ------ + ------ + -----------
0 | 1 | 0 | Wschód
1 | -1 | 0 | Zachód
2 | 0 | 1 | południe
3 | 0 | -1 | północ
4 | 1 | 1 | południowy wschód
5 | -1 | -1 | północny zachód
6 | 1 | -1 | północny wschód
7 | -1 | 1 | południowy zachód

Tablice diK i djK mogą być interpretowane w ten sam sposób, aby ustalić możliwe ruchy dla figury skoczka. Jeśli nie jesteś zaznajomiony z szachami, rycerz porusza się w układzie L - dwa pola w jednym kierunku, a następnie jedno pole pod kątem prostym (lub odwrotnie).

  | diK / x | djK / y | Kierunek
- + ------- + ------- + ----------------
0 | -2 | -1 | 2 na zachód, 1 na północ
1 | -2 | 1 | 2 na zachód, 1 na południe
2 | -1 | 2 | 1 na zachód, 2 na południe
3 | 1 | 2 | 1 na wschód, 2 na południe
4 | 2 | 1 | 2 na wschód, 1 na południe
5 | 2 | -1 | 2 na wschód, 1 na północ
6 | 1 | -2 | 1 na wschód, 2 na północ
7 | -1 | -2 | 1 na zachód, 2 na północ
James Holderness
źródło
1

Mały fragment kodu do sprawdzania liczby możliwych ruchów we wszystkich kierunkach, który wykorzystuje zdefiniowane tablice.

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int movesPossible[8];
int move = 0;
int posx, posy; // position of the figure we are checking

for (int d=0; d<8; d++) {
  for (move = 1; board.getElt(posx+di[d]*move, posy+dj[d]*move)==EMPTY; move++) ;
  movesPossible[d] = move-1;
}
Dariusz
źródło