Algorytmy podobne do dijkstry dla tablicy hexcells

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];
	}

Ja nie bardzo rozumiem co wy tu chcecie przerabiać. Zwyczajnie robicie z tego skierowany graf ważony (np. krawędź z zielonego do sąsiadów ma wagę X, z brązowego Y itd) a potem puszczacie tutaj zwykłego Dijkstre i nie ma siły żeby wam nie znalazł poprawnego rozwiązania, o ile oczywiście nie dacie ujemnych wag. Bo jeśli ustaliliscie wagi na ujemne to oczywiście optymalne byłoby kręcenie się w kółko i "obniżanie" wagi w nieskończoność ;]

Z tego co pamiętam, algorytm Dijkstry bierze pod uwagę wagi - być może źle go zaimplementowaliście, wrzuć na https://4programmers.net/Pastebin jak to Wam wyszło.

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).

To nie jest związane z wydajnością algorytmu.

Btw, aby znaleźć najbardziej optymalną ścieżkę, zawsze musiałbyś rozważyć każdą możliwą ścieżkę w grafie - co na ogół nie jest opłacalne ani pamięciowo, ani czasowo, to tak na marginesie.

@Patryk27 albo coś jest optymalne (najlepsze) albo nie jest. Nie ma tu gradacji :P A Dijkstra daje ścieżkę optymalną jeśli istnieje i nie sprawdza każdej możliwej ścieżki ;) Co do wydajności to wiadomo jaką Dijkstra ma złożoność. Jeśli jest za wysoka to może A*? Heurystyka tutaj będzie trywialna bo "kierunkowa".

Tutaj mam na razie kod znajdowania wszystkich ścieżek w grafie, ale ten algorytm albo się zapętla albo nie wyświetla nic:

 	public ArrayList<Integer> movesHex;
	public ArrayList<ArrayList<Integer>> pathHex;

	public void ShowPath( int idStart, int idEnd ) {
		movesHex = new ArrayList<Integer>();
		pathHex = new ArrayList<ArrayList<Integer>>();
		ShowPath( getCell( idStart ), getCell( idEnd ) );
		movesHex.clear();
		
		for ( int i=0; i<pathHex.size(); i++ ) {
			for ( int j=0; j<pathHex.get(i).size(); j++ ) {
				Main.getEditor().getFCmd().addText( Integer.toString( pathHex.get(i).get(j) ) + " " );
			}
			Main.getEditor().getFCmd().addText( "\n" );
		}
		
	}
	
	//----------------------------------------------------------------------------//
	public void ShowPath( Hex start, Hex end ) {

		if ( start == null ) {
			Main.showmessage("Null", "Krok", 1);
			return;
		}
		
		if ( start.type == Hex.statementTypeEmpty() ) {
			Main.showmessage("Empty", "Krok", 1);
			return;
		}
		
		if ( start.id == end.id ) {
			Main.showmessage("Znaleziono", "Krok", 1);
			pathHex.add( movesHex );
			movesHex.remove( movesHex.size()-1 );
			return;
		}
		
		if ( movesHex.contains( start.id ) ) {
			Main.showmessage("Zawiera", "Info +", 1);
			return;
		}
		
		Main.showmessage(Integer.toString( start.id ), "Element", 1);
                movesHex.add( start.id );
		ShowPath( getNextCell( start, "nw" ), end );
		ShowPath( getNextCell( start, "ne" ), end );
		ShowPath( getNextCell( start, "e" ), end );
		ShowPath( getNextCell( start, "se" ), end );
		ShowPath( getNextCell( start, "sw" ), end );
		ShowPath( getNextCell( start, "w" ), end );
                movesHex.remove( movesHex.size()-1 );
	}