wyznaczanie najkrótszej na osi liczbowej z przeszkodami

Odpowiedz Nowy wątek
2011-08-28 16:59
0

Szukałem w googlach na ten temat, ale jedyne co znalazłem to Algorytm Dijkstry. Chodzi mi o wyznaczenie najkrótszej trasy na osi liczbowej na której są pola przeszkody po których nie można chodzić. Umiem stworzyć algorytm wyznaczania najkrótszej trasy bez przeszkód, ale nie mam pojęcia jak zaimpletować do tego przeszkody. Ktoś mógłby mnie nakierować?

Pozostało 580 znaków

2011-08-28 17:32
0

Na osi liczbowej? Tzn przestrzeń jest jednowymiarowa? Jeśli tak to zadanie jest trywialne (po prostu wzięcie odpowiedniego odcinka, ew sprawdzenie czy nie leżą na nim przeszkody) i nie wiem w czym problem.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-08-28 17:43
0

No nie wiem :P może źle się wyraziłem

kod php jaki udało mi się zrobić:

while($x != $x2 || $y != $y2)
{
    $temp_x = $x;
    $temp_y = $y;
    if($x < $x2 && $y < $y2)
    {
        $temp_x++;
        $temp_y++;
        if(in_array($map[$temp_x][$temp_y]->m_surface, $obstacles))
        {
            $temp_x = $x;
            $temp_y = $y;
            $temp_x++;
            if(in_array($map[$temp_x][$temp_y]->m_surface, $obstacles))
            {
                //zerowanie tempa, temp_y++, itd.
            }
        }
    }
}

tym sposobem by mi wyszło chyba z tysiąc linijek żeby ręcznie sprawdzać wszystkie kierunki, można się poruszać w pionie, poziomie i po skosach

edytowany 1x, ostatnio: konrados, 2011-08-28 17:44

Pozostało 580 znaków

2011-08-28 17:52
0

Wikipedia:

Oś liczbowa to prosta, na której wyróżniono zwrot i punkt O zwany zerowym oraz ustalono odcinek jednostkowy.
Coś ci się bardzo mocno pomieszało z nazwami.

Mniemam, że to ci się przyda:
http://pl.wikipedia.org/wiki/A*
http://en.wikipedia.org/wiki/Pathfinding


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Też chciałem dać linka do A*, lecz po przeczytaniu "najkrótszej trasy na osi liczbowej" dałem sobie spokój... Co jednak nie zmienia faktu, że autor nieźle pokręcił nazwy :) - Patryk27 2011-08-28 18:47

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0