[Source][Algorytm] Odnajdywanie najkrótszej drogi do celu na tablicy 2D by wefhy

[wefhy]

Skrypt wczytuje plik mapa.txt wyglądający przykładowo w ten sposób:

000000000000000000000000000000

0S0111111111111111111111110110

010100000010101010100000111110

010101101010000000101111110000

010100111010011110000000011110

011101101111110010111111001000

011000101000000110100001111110

00111010111101001010E101000010

011010000001010111101111111110

001011111101110100000000000010

011000000111000001111111111010

001111110101111101000000001110

001000011101000101011111111000

011111000001110111110000001110

000001011100010100000111101010

010111010111011101111100001000

010101000001110000001001101010

011101111111011111111011101110

000000000000000000000000000000

I odnajduje najkrótszą drogę(bądź jedną z najkrótszych jeśli istnieje kilka dróg o tej samej długości) od punktu S do E i zaznacza ją w GUI. W najbliższym czasie nieco to jeszcze przerobię, żeby był łatwy do dodania do własnej gry, ale na razie zaznacza tą drogę tylko w GUI

Od razu mówię, że cały algorytm wymyśliłem sam nie mając pojęcia, jak działają zazwyczaj takie algorytmy, więc na pewno da się to zrobić to nieco wydajniej. W moim wypadku może żeby nieco zwiększyć jeszcze prędkość zrobię zatrzymanie skryptu po dojściu do celu(teraz nadal szuka innych dróg) i jednoczesne szukanie drogi od 2 stron. No i oczywiście zastąpienie labeli GDI+ lub całkowite usunięcie GUI(zwracanie drogi w tablicy)

#include "file.au3"

#include "array.au3"

Global $map=_GetMapFromFile("mapa.txt")

$1=0xffffff

$0=0x000000

$S=0x0000ff

$E=0xff0000

;_ArrayDisplay($map)

$size=13

GUICreate("Odnajdywanie najkrótszej drogi do celu by wefhy", $size*(UBound($map, 1)+1), $size*(UBound($map, 2)+1))

;GUISetState(@SW_SHOW)

Global $labels[UBound($map, 1)][UBound($map, 2)]

For $licz1=1 to UBound($map, 2)-1

    For $licz2=1 to UBound($map, 1)-1

        $labels[$licz2][$licz1]=GUICtrlCreateLabel("", $size*$licz2, $size*$licz1, $size, $size)

        GUICtrlSetBkColor(-1, Eval($map[$licz2][$licz1]))

    Next

Next

GUISetState(@SW_SHOW)

Local $End[2]=[$Map[0][0],$Map[0][1]]

Local $Start[2]=[$Map[0][2],$Map[0][3]]

Global $Map2[UBound($map, 1)][UBound($map, 2)]

Global $aPoints[(UBound($map, 1)-1)*(UBound($map, 1)-1)*2][2]=[[$Map[0][0],$Map[0][1]]]

GUICtrlSetBkColor($labels[$Start[0]][$Start[1]], $S)

_CreateArrayFromMap()

_DrawTrack($Start, $End)


Do

    $nmsg=GUIGetMsg()

Until $nmsg=-3






Func _GetMapFromFile($Path)

    Local $File

    _FileReadToArray($Path, $File)

    Dim $aMap[StringLen($File[1])+1][$File[0]+1]

    For $licz1=1 to $File[0]

        For $licz2=1 to StringLen($File[1])

            $aMap[$licz2][$licz1]=StringMid($File[$licz1], $licz2, 1)

            If $aMap[$licz2][$licz1]="E" Then

                $aMap[0][0]=$licz2

                $aMap[0][1]=$licz1

            ElseIf $aMap[$licz2][$licz1]="S" Then

                $aMap[$licz2][$licz1]=1

                $aMap[0][2]=$licz2

                $aMap[0][3]=$licz1

            EndIf

        Next

    Next

    Return $aMap

EndFunc


Func _CreateArrayFromMap() ;Potrzebuje tablic globalnych - $Map, $Map2, aPoints, $labels(do narysowania)

    $a=TimerInit()

    $bufor=1

    $licz=0

    $Map2[$aPoints[0][0]][$aPoints[0][1]]=0


    Do

        ;GUICtrlSetBkColor($labels[$aPoints[$licz][0]][$aPoints[$licz][1]], 0x00ff00)

        $now=$Map2[$aPoints[$licz][0]][$aPoints[$licz][1]]

        If $Map[$aPoints[$licz][0]+1][$aPoints[$licz][1]]=1 And Not IsNumber($Map2[$aPoints[$licz][0]+1][$aPoints[$licz][1]]) Then

                $Map2[$aPoints[$licz][0]+1][$aPoints[$licz][1]]=$now+1

                $aPoints[$bufor][0]=$aPoints[$licz][0]+1

                $aPoints[$bufor][1]=$aPoints[$licz][1]

                $bufor+=1

                GUICtrlSetData($labels[$aPoints[$licz][0]+1][$aPoints[$licz][1]], $now+1)

        EndIf

        If $Map[$aPoints[$licz][0]-1][$aPoints[$licz][1]]=1 And Not IsNumber($Map2[$aPoints[$licz][0]-1][$aPoints[$licz][1]]) Then

                $Map2[$aPoints[$licz][0]-1][$aPoints[$licz][1]]=$now+1

                $aPoints[$bufor][0]=$aPoints[$licz][0]-1

                $aPoints[$bufor][1]=$aPoints[$licz][1]

                $bufor+=1

                GUICtrlSetData($labels[$aPoints[$licz][0]-1][$aPoints[$licz][1]], $now+1)

        EndIf

        If $Map[$aPoints[$licz][0]][$aPoints[$licz][1]+1]=1 And Not IsNumber($Map2[$aPoints[$licz][0]][$aPoints[$licz][1]+1]) Then

                $Map2[$aPoints[$licz][0]][$aPoints[$licz][1]+1]=$now+1

                $aPoints[$bufor][0]=$aPoints[$licz][0]

                $aPoints[$bufor][1]=$aPoints[$licz][1]+1

                $bufor+=1

                GUICtrlSetData($labels[$aPoints[$licz][0]][$aPoints[$licz][1]+1], $now+1)

        EndIf

        If $Map[$aPoints[$licz][0]][$aPoints[$licz][1]-1]=1 And Not IsNumber($Map2[$aPoints[$licz][0]][$aPoints[$licz][1]-1]) Then

                $Map2[$aPoints[$licz][0]][$aPoints[$licz][1]-1]=$now+1

                $aPoints[$bufor][0]=$aPoints[$licz][0]

                $aPoints[$bufor][1]=$aPoints[$licz][1]-1

                $bufor+=1

                GUICtrlSetData($labels[$aPoints[$licz][0]][$aPoints[$licz][1]-1], $now+1)

        EndIf

        $licz+=1

        ;Sleep(1)

    Until $aPoints[$licz][0]=""

    ConsoleWrite(TimerDiff($a))

EndFunc


Func _DrawTrack($now, $x) ;now - punkt rozpoczęcia(z najwyższym numerkiem), x-punkt zakończenia; wymaga tablic globalnych Map2, $labels(do narysowania)

    For $licz=$Map2[$now[0]][$now[1]] to 2 step -1

        GUICtrlSetBkColor($labels[$now[0]][$now[1]], 0x00ff00)

        Switch $licz-1

            Case $Map2[$now[0]+1][$now[1]]

                $now[0]+=1

            Case $Map2[$now[0]-1][$now[1]]

                $now[0]-=1

            Case $Map2[$now[0]][$now[1]+1]

                $now[1]+=1

            Case $Map2[$now[0]][$now[1]-1]

                $now[1]-=1

        EndSwitch

        sleep(1)

    Next

    GUICtrlSetBkColor($labels[$now[0]][$now[1]], 0x00ff00)

    GUICtrlSetBkColor($labels[$x[0]][$x[1]], 0x00ff00)


EndFunc

Jak by ktoś chciał stworzyć własne mapy, to na razie może się posłużyć czymś takim: (należy narysować rysunek w paincie w kolorach białym(można iść), czarnym(ściana), zielonym 0x00ff00(początek) i czerwonym 0xff0000(koniec)(najlepiej nie większy niż 30x30, bo skanowanie jest dość wolne), uruchomić ten skrypt i ustawić muszkę nad obrazkiem(przy przybliżeniu 100%))

sleep(5000)

$sdf=MouseGetPos()

Do

    $sdf[1]+=1

    MouseMove($sdf[0], $sdf[1], 0)

    $color=PixelGetColor($sdf[0], $sdf[1])

    ToolTip("Czekaj...")

Until $color=0x000000

Do

    $sdf[0]-=1

    MouseMove($sdf[0], $sdf[1], 0)

    $color=PixelGetColor($sdf[0]-1, $sdf[1])

    ToolTip("Czekaj...")

Until not $color=0x000000

$adfa=$sdf

Do

    $sdf[1]+=1

    MouseMove($sdf[0], $sdf[1], 0)

    $color=PixelGetColor($sdf[0], $sdf[1]+1)

    ToolTip("Czekaj...")

Until not $color=0x000000

For $y=$adfa[1] to $sdf[1]

    $sdf[0]=$adfa[0]

    $line=""

    Do


        MouseMove(0, 0, 0)

        $color=PixelGetColor($sdf[0], $y)

        $color2=PixelGetColor($sdf[0]+1, $y)

        If $color=0x000000 Then

            $line&=0

        ElseIf $color=0xffffff Then

            $line&=1

        ElseIf $color=0x00ff00 Then

            $line&="S"

        Else

            $line&="E"

        EndIf

        $sdf[0]+=1

        ToolTip("Czekaj...")

    Until Not ($color2=0x000000 Or $color2=0xffffff Or $color2=0xff0000 Or $color2=0x00ff00)

    FileWriteLine("mapa.txt", $line)

Next

Potem może znajdę sposób na tworzenie mapy bezpośrednio z pliku bmp lub stworzę coś w rodzaju edytora map.

Dodatkowe 2 mapki są w załączniku

mapa.old.txt

Bez tytułu.bmp

mapa.txt

[Sopelek997]

Nieźle, tym bardziej, że własny pomysł na rozwiązanie. Fajniej jest czasem coś samemu wymyślić, niż ciągle z neta kopiować ;p. Więcej zabawy.

 

 

btw. Widziałem, że nie masz generatora jeszcze, to ja wrzucę swój jakby komuś się nie chciało pisać. Generuje z jedną możliwą drogą w każde miejsce, ale lepiej chyba przerobić sobie jak kto potrzebuje niż rysować całe od zera ;d.

Musicie jedynie zaznaczyć początek i koniec.

C style C++ code ;d

 

 

 

#include <iostream>
#include <cstdlib>
using namespace std;
void maze(bool** m, int w, int h, int x, int y)
{
    int r = rand()%4;
    int t[4][2] = {{-2, 0},{2,0},{0,-2},{0,2}};
    for(int i = 0; i<4; ++i)
    {
        r = (r + 1) % 4;
        if(x + t[r][0] > 0 && x + t[r][0] < w && y + t[r][1] > 0 && y + t[r][1] < h)
        {
            if(m[x + t[r][0]][y + t[r][1]] == false)
            {
                m[x + (t[r][0]>>1)][y + (t[r][1]>>1)] = m[x + (t[r][0])][y + (t[r][1])] = m[x][y] = true;
                maze(m, w, h, x + t[r][0], y + t[r][1]);
            }
        }
    }
    return;
}
bool** generateMaze(int w, int h, int& x1, int& y1)
{
    int x, y;
    x = (rand()%w)*2+1;
    y = (rand()%h)*2+1;
    w = w*2+1;
    h = h*2+1;
    x1 = w;
    y1 = h;
    bool** m = new bool*[w];
    for(int i = 0; i<w;++i)
        m[i] = new bool[h];
    for(int i = 0; i<w; ++i)
        for(int j = 0; j<h;j++)
            m[i][j] = false;
    maze(m, w, h, x, y);
    return m;
}
int main()
{
    int seed, w ,h;
    cout << "Podaj seed: ";
    cin >> seed;
    cout<< "Podaj szerokosc: "; //szerokosc i wysokosc oznacza ile korytarzy ma sie miescic w danym wymiarze
    cin >> w;
    cout << "Podaj wysokosc: ";
    cin >> h;
    bool** m = generateMaze(h, w, w, h);
    for(int i = 0; i<w; ++i, cout << '\n')
    {
        for(int j = 0; j<h;j++)
        {
            if(m[i][j]) cout << '1'; //wolne pole
            else cout << '0'; //sciana
        }
    }
    return 0;
}
 

 

 

exe download
http://www33.zippyshare.com/v/67914373/file.html

skan
https://www.virustotal.com/pl/url/77242a09c8fd242c8b437fadddf995331099619fcf038deda922f1d60ab781db/analysis/1364914242/

 

Wersja dla tych co lubią mieć graficzny rysunek. podajecie width i height. Jak wpiszecie za dużą wartość, lub w dziwnych proporcjach to się sypie z różnych powodów. Najlepiej potęgi dwójki. (U mnie 512 to za dużo bo stackoverflow ;/) I nie każdemu musi w ogóle działać bo to allegro, więc nie miejcie pretensji ;3

exe download
http://www33.zippyshare.com/v/15786853/file.html

skan
https://www.virustotal.com/pl/url/e22a2b4c3325a0c1d2ff78651a91aa15c347adc30b91d191d9af132b12202af9/analysis/1364914440/

miłej zabawy!

 

 

 

@edit. Jak ktoś lubi krok po kroczku patrzeć na generowanie to proszę

http://www54.zippyshare.com/v/14030540/file.html

[metin1998]

        if(x + t[r][0] > 0 && x + t[r][0] < w && y + t[r][1] > 0 && y + t[r][1] < h)
        {
            if(m[x + t[r][0]][y + t[r][1]] == false)
            {
                m[x + (t[r][0]>>1)][y + (t[r][1]>>1)] = m[x + (t[r][0])][y + (t[r][1])] = m[x][y] = true;
                maze(m, w, h, x + t[r][0], y + t[r][1]);
            }
        }
    }
 

niezłe, miss kodu 2013.