Witam.
Wraz z kolegą piszemy mini grę komputerową i szukamy algorytmu dzięki któremu będziemy mogli znaleźć najbardziej optymalną ścieżkę od punktu A do punktu B.
Mapa jest zbudowana jako tablica dwuwymiarowa z przesunięciem x+1 co nie parzysty rząd (y).
Rozważaliśmy algorytm Dijkstry ale albo nie potrafimy go przerobić na ten model, albo nie jest on w tym przypadku wydajny (szukając najkrótszej ścieżki może obchodzić puste pola zamiast przejść przez pola o wartości 2 lub 3 za którymi natychmiast znajduje się punkt docelowy).
Każde pole posiada swój własny Index, współrzędne, liczba ruchów na wydostanie się z niego:
Zielony (-1)
Ciemno Zielony (-2)
Żółty (-3)
Brązowy (-4)
Jest to mniej więcej tak zaimplementowane:
array[y][x].id = ?;
y = id/width;
x = id%width;
A tak wygląda dostęp do pól wokół:
public Hex getNextCell( Hex hex, String direction ){
int tX, tY;
int tXm = -1;
int tYm = -1;
if ( hex == null ) { return null; }
tX = hex.posX;
tY = hex.posY;
if (direction.equals("nw")) {
tYm = this.array[tY][tX].posY - 1;
if ((tY%2)==0) {
tXm = this.array[tY][tX].posX-1;
} else {
tXm = this.array[tY][tX].posX;
}
if ((tXm<0)||(tXm>=this.width)) { return null; }
if ((tYm<0)||(tYm>=this.height)) { return null; }
}
if (direction.equals("ne")) {
tYm = this.array[tY][tX].posY - 1;
if ((tY%2)==0) {
tXm = this.array[tY][tX].posX;
} else {
tXm = this.array[tY][tX].posX+1;
}
if ((tXm<0)||(tXm>=this.width)) { return null; }
if ((tYm<0)||(tYm>=this.height)) { return null; }
}
if (direction.equals("sw")) {
tYm = this.array[tY][tX].posY + 1;
if ((tY%2)==0) {
tXm = this.array[tY][tX].posX-1;
} else {
tXm = this.array[tY][tX].posX;
}
if ((tXm<0)||(tXm>=this.width)) { return null; }
if ((tYm<0)||(tYm>=this.height)) { return null; }
}
if (direction.equals("se")) {
tYm = this.array[tY][tX].posY+1;
if ((tY%2)==0) {
tXm = this.array[tY][tX].posX;
} else {
tXm = this.array[tY][tX].posX+1;
}
if ((tXm<0)||(tXm>=this.width)) { return null; }
if ((tYm<0)||(tYm>=this.height)) { return null; }
}
if (direction.equals("w")) {
tYm = this.array[tY][tX].posY;
tXm = this.array[tY][tX].posX-1;
if ((tXm<0)||(tXm>=this.width)) { return null; }
if ((tYm<0)||(tYm>=this.height)) { return null; }
}
if (direction.equals("e")) {
tYm = this.array[tY][tX].posY;
tXm = this.array[tY][tX].posX+1;
if ((tXm<0)||(tXm>=this.width)) { return null; }
if ((tYm<0)||(tYm>=this.height)) { return null; }
}
return this.array[tYm][tXm];
}
- Obraz.png (26 KB) - ściągnięć: 96
Java 
