Zawartość strony
Strona główna Teoria Wzory klasa 7 Wzory klasa 8 Rozwiązania zadań z fizyki Symulacje z fizyki Tablice fizyczne Karta wzorów z fizyki Biologia C# Programowanie Kotlin Android Studio Programowanie 3D Arkusze INF.04

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.

Algorytm Dijkstry Unity

Ścieżka ruchu do punktu celu odbywa się po kolejnych polach od kosztu 1 do 58

ścieżka ruchu

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.

tablica komponentu grid Unity

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.

ścieżka ruchu swiat 2d unity

Do projektu importujemy grafikę, z której wygenerujemy paletę tilsów dla warstw. Sposób przygotowania grafiki znajdziesz w wielu internetowych poradnikach.

tils 2d unity

Kamera w grze 2D

Kamerę przygotowujemy do pracy w widoku 2D. Poniżej proponowany układ opcji

kamera swiat 2d unity

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)

kafle ruchu swiat 2d unity

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

Grid 2d unity

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.

Grid ruchu swiat 2d unity

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

algorytm dijkstry ścieżka ruchu swiat 2d unity

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);
        }
    }
}
Układ okresowy- kod qr
Układ okresowy

Układ okresowy pierwiastków- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
 Alkomat- wirtualny test kod qr
Alkomat- wirtualny test

Alkomat- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
 Taklarz- olinowanie stałe kod qr
Olinowanie stałe- kalkulator średnic

Olinowanie stałe- darmowa aplikacja na Androida

Pobierz ze sklepu Google Play
przepis na gogfry

Przepis na gofry

zobacz
przepis na bitą śmietanę

Przepis na bitą śmietanę

zobacz