Znajdowanie drogi w siatce mapy 2D
W tym temacie poruszę problem znajdowania ścieżki dotarcia z punktu A do B w siatce mapy gry 2D. Rozwiązanie oparte jest na algorytmie Dijkstry zrealizowanym liniowo a nie rekurencyjnie. Ścieżka zwracana jest w formie listy z zawartością informacji o kolejnych kafelkach siatki gry 2D. Kafelki są tilsami komponentu Tilemap, który jest składową komponentu Grid. Więcej o komponencie Grid znajdziesz pod tym linkiem
Algorytm Dijkstry
O algorytmie Dijkstry znajdowania drogi czy też kosztów przechodzenia grafu znajdziesz wiele szeroko omówionych materiałów na różnych portalach. Ogólnie algorytm po zaadoptowaniu do mapy świata gry 2D działa w ten sposób, że dla każdego kafelka począwszy od wyznaczonego punktu startu sprawdza graniczących z nim sąsiadów czy jest możliwość wykonania ruchu, czy sąsiad był już odwiedzony, czy nie ma w sąsiedzie punktu celu. Przy każdorazowym sprawdzaniu tworzona jest nowa kolejka odwiedzin wraz z sumą kosztów dojścia. Powtarzanie trwa do momentu znalezienia celu lub sprawdzeniu wszystkich możliwych kafelków.
Zwracana ścieżka to lista kafelków (pól siatki 2D) oparta na wartościach najmniejszego kosztu dojścia. Poniżej ilustracja dojścia do celu z kosztem (złożonością) o wartości 58.
Ścieżka ruchu do punktu celu odbywa się po kolejnych polach od kosztu 1 do 58
W rozwiązaniu dostosowanym do organizacji komponentu Grid silnika Unity należy zwrócić uwagę i dostosować rozwiązanie do innego numerowania (indeksowania) kafli mapy 2D. Kafelki numerowane są od (0,0) od środka siatki. Przykładowo jeżeli siatka rozpięta jest na mapie 26x14 (26 kolumn, 14 wierszy) to indeksacja przebiega jak poniżej.
Inna indeksacja wymaga przeliczenia na standardowe indeksowanie tablicy dwuwymiarowej, co ułatwi oprogramowanie algorytmu szukania drogi. Ponadto w Unity pojedynczy kafel sitaki 2D jest obiektem klasy Vector3Int. Dane przechowamy w omawianym rozwiązaniu w przygotowanej strukturze o postaci
Wskazówka:
struct TPoint
{
//dane dla tablicy mapy swiata
public int x,y;
//dane dla tablicy Tilsów
public Vector3Int pozycja;
}
Tworzymy świat 2D
Po utworzeniu nowego projektu 2D w silniku Unity na scenę dodajemy komponent Grid, w którym dodajemy co najmniej dwie warstwy. Ja dodałem trzy. Warstwa pierwsza jest warstwą do układania kafli wyglądu świata. Czyli kafelki muru, trawy itp. Druga warstwa posłuży do ryzowania wyznaczonej ścieżki drogi. Trzecia warstwa przechowuje ikonki flag startu i celu- mety.
Do projektu importujemy grafikę, z której wygenerujemy paletę tilsów dla warstw. Sposób przygotowania grafiki znajdziesz w wielu internetowych poradnikach.
Kamera w grze 2D
Kamerę przygotowujemy do pracy w widoku 2D. Poniżej proponowany układ opcji
Tworzymy świat 2D
W pierwszej warstwie układamy świat z pojedynczych kafelków. Wybieramy kafelki na te, po których nie można chodzić (np. ściany) i na te, po których można chodzić (np. trawa)
Skrypt szukania drogi- algorytm Dijkstry
Inicjujemy skrypt o nazwie Droga2D. Serializujemy kilka pól, które będą widoczne w edytorze Unity. Patrz poniżej.
Wskazówka:
struct TPoint
{
//dane dla tablicy mapy swiata
public int x,y;
//dane dla tablicy Tilsów
public Vector3Int pozycja;
}
public class Droga2D : MonoBehaviour
{
//SteTile-metoda ustaw kafla w mapie
//SwapTile- zmienia kafle jednego typu na inne
//WorldToCell- przełożenie pozycji w grze
/// </summary>
[SerializeField] private Grid grid;
[SerializeField] private Tilemap warstwaGruntu,
warstwaSciezki,
warstwaRzeczy;
[SerializeField] private TileBase bmpStart, bmpMeta, bmpSciezka;
//lista z kafelkami po których można chodzić
[SerializeField] private List<Tile> listaKafleDrogi;
private Kafel kafel;
private int ileKolumn, ileWierszy;
private bool fStart = false;
int[,] kierunek=new int[4, 2] { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
//int[,] kierunek = new int[8, 2]{{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0}};
byte[,] MapaSwiata = null;
Vector3Int pozycjaStartu, pozycjaMety;
Podpinamy skrypt do komponentu Grid
Ważne aby prawidłowo w podpiętym skrypcie osadzić kafelki przedstawiające grafikę flagi startu, mety, ścieżki i kafelki drogi. W tym przypadku są to dwa pola o kolorze jasno i ciemno zielonym.
Można więcej dodać kafelków po których się chodzi. Skrypt przechowuje te kafelki w liście, której ilość jest elastyczna.
Do skryptu dopisujemy dwie funkcje. Jedna z nich przelicza indeksy standardowej tablicy dwuwymiarowej na indeks w mapie tilsów, czyli Vector3Int. Druga funkcja to tworzenie mapy 2D w tablicy dwuwymiarowej opartej na wartościach 0, 1. Zero oznacza, że można chodzi po kafelku, jeden oznacza, że przejścia nie ma. Patrz kod poniżej
Wskazówka:
void RobMape(Tilemap warstwa)
{
MapaSwiata = new byte[ileWierszy, ileKolumn];
for (int w = 0; w < ileWierszy; w++)
{
string s = null;
for (int k = 0; k < ileKolumn; k++)
{
//przyjmij że jest mur
MapaSwiata[w, k] = 1;
Tile t = (Tile)warstwaGruntu.GetTile(pozycja_z_Wiersza_i_Kolumny(w, k));
foreach(Tile tt in listaKafleDrogi)
{
if (t == tt)
{
//wstaw drogę
MapaSwiata[w, k] = 0;
break;
}
}
//wyślij do podglądu debugera
s += MapaSwiata[w, k]+" ";
}
Debug.Log(s);
}
}
Vector3Int pozycja_z_Wiersza_i_Kolumny(int wiersz, int kolumna)
{
Vector3Int vektor3int = new Vector3Int();
vektor3int.x = kolumna - ileKolumn / 2;
vektor3int.y = ileWierszy / 2 - 1 - wiersz;
return vektor3int;
}
Modyfikujemy metodę Start()- tu wywołamy utworzona funkcję RobMape() oraz odczytamy ile jest wierszy i kolumn.
Wskazówka:
void Start()
{
//warstwaGruntu.CompressBounds();
ileKolumn = warstwaGruntu.size.x;
ileWierszy = warstwaGruntu.size.y;
RobMape(warstwaGruntu);
Debug.Log("Rozmiar swiata: " + warstwaGruntu.size);
Debug.Log("Ile kolumn: " + ileKolumn);
Debug.Log("Ile wierszy: " + ileWierszy);
Debug.Log("Mapa swiata: " + MapaSwiata);
}
Funkcja zwracająca drogę
Poniżej kod funkcji, która zwróci szlak dojścia od wybranego punktu startu do wybranego punktu celu. Uwaga. Lista zwraca kafle od końca, czyli od mety do startu. Kod funkcji
Wskazówka:
List<TPoint> Szlak(byte[,] Mapa,
Vector3Int pozycjaStartu,
Vector3Int pozycjaMety
)
{
bool fMeta=false;
int row,col,Zalazek,L;
List<TPoint> tabKolejka=new List<TPoint>(),
tabBufor= new List<TPoint>();
TPoint _Start,_Cel;
TPoint p = new TPoint();
int ileWierszy=Mapa.GetLength(0);
int ileKolumn=Mapa.GetLength(1);
int[,] ileOdwiedzin=new int[ileWierszy, ileKolumn];
bool[,] tabOdwiedzin = new bool[ileWierszy, ileKolumn];
//wypelnij tablice odwiedzin ZERAMI,tablicę testu logicznego ustaw na false
for (int w = 0; w < ileWierszy; w++)
for (int k= 0; k < ileKolumn; k++)
{
ileOdwiedzin[w, k] = 0;
tabOdwiedzin[w, k] = false;
}
_Start.x = ileKolumn / 2 + pozycjaStartu.x;
_Start.y = ileWierszy / 2 - pozycjaStartu.y - 1;
_Start.pozycja = pozycjaStartu;
tabKolejka.Add( _Start );
tabOdwiedzin[_Start.y, _Start.x]= true;
_Cel.y= ileWierszy / 2 - pozycjaMety.y - 1;
_Cel.x= ileKolumn / 2 + pozycjaMety.x;
_Cel.pozycja= pozycjaMety;
int ile = 0;
while (!fMeta)
{
for(int j=0;j<tabKolejka.Count;j++)
{
//pętal dla 4 lub 8 kierunków szukania drogi
for(int k = 0; k < kierunek.GetLength(0);k++)
{
col= tabKolejka[j].x + kierunek[k, 0];
row= tabKolejka[j].y + kierunek[k, 1];
if (col < 0 || col > ileKolumn - 1 || row < 0 || row > ileWierszy - 1 || Mapa[row, col] != 0) continue;
if (tabOdwiedzin[row, col] == false)
{
ileOdwiedzin[row, col]= ileOdwiedzin[tabKolejka[j].y,tabKolejka[j].x]+1;
tabOdwiedzin[row, col] = true;
p.x = col;
p.y= row;
p.pozycja = pozycja_z_Wiersza_i_Kolumny(p.y, p.x);
tabBufor.Add(p);
if (_Cel.x == col && _Cel.y == row)
{
fMeta = true;
break;//wyskocz z pętli k
}
}//koniec if-a tabodwiedzin
//}//koniec glownego if-a
}//koniec petli dla kierunkow
}//koniec petli dla biezacej kolejki
tabKolejka.Clear();
//skopijuj bufor tablicy kolejki
for (int i = 0; i < tabBufor.Count; i++)
tabKolejka.Add(tabBufor[i]);
tabBufor.Clear();
ile++;
//nie znaleziono drogi
if (ile > ileWierszy * ileKolumn) return tabKolejka;
}//koniec while
Zalazek = ileOdwiedzin[_Cel.y, _Cel.x];
tabKolejka.Clear();
p.x = _Cel.x;
p.y = _Cel.y;
p.pozycja = _Cel.pozycja;
//UWAGA. Szlak budowany jest od końca, czyli od mety do startu
//i zapisywany jest w tabKolejka
tabKolejka.Add(p);
fMeta = false;
ile = 0;
while (!fMeta)
{
//pętal dla 4 lub 8 kierunków szukania drogi
for (int k = 0; k < kierunek.GetLength(0); k++)
{
col = tabKolejka[tabKolejka.Count - 1].x + kierunek[k, 0];
row = tabKolejka[tabKolejka.Count - 1].y + kierunek[k, 1];
if (col < 0 || col > ileKolumn - 1 || row < 0 || row > ileWierszy - 1 || Mapa[row, col] != 0) continue;
{
L = ileOdwiedzin[row,col];
if (L == Zalazek-1)
{
Zalazek = L;
p.x = col;
p.y = row;
p.pozycja = pozycja_z_Wiersza_i_Kolumny(p.y, p.x);
tabKolejka.Add(p);
}
if (col == _Start.x && row == _Start.y)
{
fMeta = true;
//wyskocz z pętli k
break;
}
}
ile++;
if (ile > ileWierszy * ileKolumn) return tabKolejka;
}
}//koniec while
//pokaz w debugerze licznik odwiedzin
for (int w = 0; w < ileWierszy; w++)
{
string s = null;
for (int k = 0; k < ileKolumn; k++)
{
s = s + ileOdwiedzin[w, k]+" ";
}
Debug.Log(s);
}
//zwróć szlak
return tabKolejka;
}
Znaleziony szlak rysowany jest po kliknięciu myszką w dowolny kafel świata 2D
Pełny kod skryptu szukającego drogi
Poniżej przedstawiam pełny kod skryptu wykorzystującego algorytm Dijkstry, mam nadzieję że przedstawione rozwiązanie pomorze Karolowi K. z uporaniem się z problemem owcy i wilka.
Wskazówka:
using Microsoft.Unity.VisualStudio.Editor;
using Newtonsoft.Json.Linq;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.ConstrainedExecution;
using TMPro;
using Unity.VisualScripting;
using UnityEngine;
using UnityEngine.Tilemaps;
struct Kafel
{
//testowa struktura
//z infem o pojedynczym kaflu
public int kolumna, wiersz;
public Tile tile;
}
struct TPoint
{
//dane dla tablicy mapy swiata
public int x,y;
//dane dla tablicy Tilsów
public Vector3Int pozycja;
}
public class Droga2D : MonoBehaviour
{
//SteTile-metoda ustaw kafla w mapie
//SwapTile- zmienia kafle jednego typu na inne
//WorldToCell- przełożenie pozycji w grze
/// </summary>
[SerializeField] private Grid grid;
[SerializeField] private Tilemap warstwaGruntu,
warstwaSciezki,
warstwaRzeczy;
[SerializeField] private TileBase bmpStart, bmpMeta, bmpSciezka;
//lista z kafelkami po których można chodzić
[SerializeField] private List<Tile> listaKafleDrogi;
private Kafel kafel;
private int ileKolumn, ileWierszy;
private bool fStart = false;
int[,] kierunek=new int[4, 2] { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
//int[,] kierunek = new int[8, 2]{{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0}};
byte[,] MapaSwiata = null;
Vector3Int pozycjaStartu, pozycjaMety;
List<TPoint> Szlak(byte[,] Mapa,
Vector3Int pozycjaStartu,
Vector3Int pozycjaMety
)
{
bool fMeta=false;
int row,col,Zalazek,L;
List<TPoint> tabKolejka=new List<TPoint>(),
tabBufor= new List<TPoint>();
TPoint _Start,_Cel;
TPoint p = new TPoint();
int ileWierszy=Mapa.GetLength(0);
int ileKolumn=Mapa.GetLength(1);
int[,] ileOdwiedzin=new int[ileWierszy, ileKolumn];
bool[,] tabOdwiedzin = new bool[ileWierszy, ileKolumn];
//wypelnij tablice odwiedzin ZERAMI,tablicę testu logicznego ustaw na false
for (int w = 0; w < ileWierszy; w++)
for (int k= 0; k < ileKolumn; k++)
{
ileOdwiedzin[w, k] = 0;
tabOdwiedzin[w, k] = false;
}
_Start.x = ileKolumn / 2 + pozycjaStartu.x;
_Start.y = ileWierszy / 2 - pozycjaStartu.y - 1;
_Start.pozycja = pozycjaStartu;
tabKolejka.Add( _Start );
tabOdwiedzin[_Start.y, _Start.x]= true;
_Cel.y= ileWierszy / 2 - pozycjaMety.y - 1;
_Cel.x= ileKolumn / 2 + pozycjaMety.x;
_Cel.pozycja= pozycjaMety;
int ile = 0;
while (!fMeta)
{
for(int j=0;j<tabKolejka.Count;j++)
{
//pętal dla 4 lub 8 kierunków szukania drogi
for(int k = 0; k < kierunek.GetLength(0);k++)
{
col= tabKolejka[j].x + kierunek[k, 0];
row= tabKolejka[j].y + kierunek[k, 1];
if (col < 0 || col > ileKolumn - 1 || row < 0 || row > ileWierszy - 1 || Mapa[row, col] != 0) continue;
if (tabOdwiedzin[row, col] == false)
{
ileOdwiedzin[row, col]= ileOdwiedzin[tabKolejka[j].y,tabKolejka[j].x]+1;
tabOdwiedzin[row, col] = true;
p.x = col;
p.y= row;
p.pozycja = pozycja_z_Wiersza_i_Kolumny(p.y, p.x);
tabBufor.Add(p);
if (_Cel.x == col && _Cel.y == row)
{
fMeta = true;
break;//wyskocz z pętli k
}
}//koniec if-a tabodwiedzin
//}//koniec glownego if-a
}//koniec petli dla kierunkow
}//koniec petli dla biezacej kolejki
tabKolejka.Clear();
//skopijuj bufor tablicy kolejki
for (int i = 0; i < tabBufor.Count; i++)
tabKolejka.Add(tabBufor[i]);
tabBufor.Clear();
ile++;
//nie znaleziono drogi
if (ile > ileWierszy * ileKolumn) return tabKolejka;
}//koniec while
Zalazek = ileOdwiedzin[_Cel.y, _Cel.x];
tabKolejka.Clear();
p.x = _Cel.x;
p.y = _Cel.y;
p.pozycja = _Cel.pozycja;
//UWAGA. Szlak budowany jest od końca, czyli od mety do startu
//i zapisywany jest w tabKolejka
tabKolejka.Add(p);
fMeta = false;
ile = 0;
while (!fMeta)
{
//pętal dla 4 lub 8 kierunków szukania drogi
for (int k = 0; k < kierunek.GetLength(0); k++)
{
col = tabKolejka[tabKolejka.Count - 1].x + kierunek[k, 0];
row = tabKolejka[tabKolejka.Count - 1].y + kierunek[k, 1];
if (col < 0 || col > ileKolumn - 1 || row < 0 || row > ileWierszy - 1 || Mapa[row, col] != 0) continue;
{
L = ileOdwiedzin[row,col];
if (L == Zalazek-1)
{
Zalazek = L;
p.x = col;
p.y = row;
p.pozycja = pozycja_z_Wiersza_i_Kolumny(p.y, p.x);
tabKolejka.Add(p);
}
if (col == _Start.x && row == _Start.y)
{
fMeta = true;
//wyskocz z pętli k
break;
}
}
ile++;
if (ile > ileWierszy * ileKolumn) return tabKolejka;
}
}//koniec while
//pokaz w debugerze licznik odwiedzin
for (int w = 0; w < ileWierszy; w++)
{
string s = null;
for (int k = 0; k < ileKolumn; k++)
{
s = s + ileOdwiedzin[w, k]+" ";
}
Debug.Log(s);
}
//zwróć szlak
return tabKolejka;
}
// Start is called before the first frame update
void Start()
{
//warstwaGruntu.CompressBounds();
ileKolumn = warstwaGruntu.size.x;
ileWierszy = warstwaGruntu.size.y;
RobMape(warstwaGruntu);
Debug.Log("Rozmiar swiata: " + warstwaGruntu.size);
Debug.Log("Ile kolumn: " + ileKolumn);
Debug.Log("Ile wierszy: " + ileWierszy);
Debug.Log("Mapa swiata: " + MapaSwiata);
}
void RobMape(Tilemap warstwa)
{
MapaSwiata = new byte[ileWierszy, ileKolumn];
for (int w = 0; w < ileWierszy; w++)
{
string s = null;
for (int k = 0; k < ileKolumn; k++)
{
//przyjmij że jest mur
MapaSwiata[w, k] = 1;
Tile t = (Tile)warstwaGruntu.GetTile(pozycja_z_Wiersza_i_Kolumny(w, k));
foreach(Tile tt in listaKafleDrogi)
{
if (t == tt)
{
//wstaw drogę
MapaSwiata[w, k] = 0;
break;
}
}
//wyślij do podglądu debugera
s += MapaSwiata[w, k]+" ";
}
Debug.Log(s);
}
}
Vector3Int pozycja_z_Wiersza_i_Kolumny(int wiersz, int kolumna)
{
Vector3Int vektor3int = new Vector3Int();
vektor3int.x = kolumna - ileKolumn / 2;
vektor3int.y = ileWierszy / 2 - 1 - wiersz;
return vektor3int;
}
void StartMeta(Vector3Int pozycja)
{
if (!fStart)
{
//usuń stary kafel startu
warstwaRzeczy.SetTile(pozycjaStartu, null);
//ustwa kafel startu
pozycjaStartu = pozycja;
warstwaRzeczy.SetTile(pozycjaStartu, bmpStart);
}
else
{
//usuń stary kafel mety
warstwaRzeczy.SetTile(pozycjaMety, null);
//ustwa kafel mety
pozycjaMety = pozycja;
warstwaRzeczy.SetTile(pozycjaMety, bmpMeta);
}
fStart =!fStart;
}
void PodajStartMeta()
{
Vector3 mp=Camera.main.ScreenToWorldPoint(Input.mousePosition);
Vector3Int pozycja= warstwaGruntu.WorldToCell(mp);
if(warstwaGruntu.GetTile(pozycja) != null )
{
//testowe info o klikniętym kaflu
kafel.kolumna = ileKolumn/2 + pozycja.x;
kafel.wiersz= ileWierszy/2 - pozycja.y -1;
kafel.tile = (Tile)warstwaGruntu.GetTile(pozycja);
Debug.Log("pozycja " + pozycja);
Debug.Log("klikniety kafel "+kafel.tile);
Debug.Log("klikniety kafel kolumna " + kafel.kolumna);
Debug.Log("klikniety kafel wiersz " + kafel.wiersz);
StartMeta(pozycja);
}
}
// Update is called once per frame
void Update()
{
//kliknij lewym w kafel mapy
if (Input.GetMouseButtonDown(0))
{
//
PodajStartMeta();
//czysc stary szlak
warstwaSciezki.ClearAllTiles();
//rysuj nowy szlak
foreach (TPoint p in Szlak(MapaSwiata, pozycjaStartu, pozycjaMety))
warstwaSciezki.SetTile(p.pozycja, bmpSciezka);
}
}
}
