Autor Wątek: Szukanie jak najktrojszej drogi - POMOCY  (Przeczytany 5563 razy)

Offline Genesis72

  • Użytkownik

# Grudzień 11, 2006, 16:56:13
Czesc
Mam takie zadanie
Zrobic program w pacal/delphi/C++, ktory szuka i wyznacza jak najkrotszej drogi od punktu A do B na plaszczyznie np 10 na 10
Po drodze sa przeszkody, ktore sie przemieszczaja
Czy mozecie mi pomoc napisac taki program
Dziekuje

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Riddlemaster

  • Użytkownik
    • Moja strona domowa

# Grudzień 11, 2006, 16:58:10
Możemy Ci pomóc znaleźć rozwiązanie, ale wątpię, żeby ktokolwiek zgodził się napisać program.

Zapoznaj się z jednym z algorytmów:
- Dijkstry
- A*
Służą one do wyznaczania najkrótszej ścieżki w grafie (algorytmów takich jest oczywiście dużo więcej, ale te dwa są bardzo popularne).

Offline BTomasz92

  • Użytkownik
    • Wortal Majsterkowicza

# Grudzień 11, 2006, 17:03:10
A może to http://darkcult.republika.pl/alg/droga.html
Znowu złośliwiec będzie niezadowolony :D

Offline Lipek Samo Zło

  • Użytkownik

# Grudzień 11, 2006, 20:39:32
do takiego taska jest kilka algorytmów, ale najlepszym będzie A* - prosty i bardzo popularny więc znajdziesz sporo materiałów. Przede wszystkim jest sporo w perełkach (część pierwsza) i w AI Game Programming Wisdom (również część pierwsza). Jeśli potrzeba to poszukaj też w necie - to kilka ciekawych linków:
http://ai-depot.com/Tutorial/PathFinding.html
http://theory.stanford.edu/~amitp/GameProgramming/ <-- najlepsza stronka na początek
były też jakieś polsko-języczne, ale to już musisz doszukać w google'ach. Poza tym odwiedź serwisy gamedev.net i gamasutre tam jest bardzo dużo infosów, artów i postów na forach.
Good Luck :)
« Ostatnia zmiana: Grudzień 11, 2006, 20:41:07 wysłana przez L1p3q »

Offline Złośliwiec

  • Użytkownik
    • Dark Cult

# Grudzień 11, 2006, 20:45:56
A może to http://darkcult.republika.pl/alg/droga.html
Znowu złośliwiec będzie niezadowolony :D

Czemu, mój algorytm jest niezawodny i w miarę przystępnie opisany, może co najwyżej dałoby się znaleźć jakiś wydajniejszy :).

Offline Xion

  • Redaktor
    • xion.log

# Grudzień 11, 2006, 21:11:55
Złośliwiec: Gratuluję, wynalazłeś przeszukiwanie wszerz :D I najlepsze jest to, że dla opisanej planszy prostokątnej jest on optymalny ^^ (w sensie szybkości znalezienie bezwzględnie najlepszej drogi; jeśli chodzi o stosunek długość drogi / czas jej znajdowania to pewnie nie jest już tak dobrze).
« Ostatnia zmiana: Grudzień 11, 2006, 21:14:14 wysłana przez Xion »

Offline Złośliwiec

  • Użytkownik
    • Dark Cult

# Grudzień 11, 2006, 21:55:29
Złośliwiec: Gratuluję, wynalazłeś przeszukiwanie wszerz :D I najlepsze jest to, że dla opisanej planszy prostokątnej jest on optymalny ^^ (w sensie szybkości znalezienie bezwzględnie najlepszej drogi; jeśli chodzi o stosunek długość drogi / czas jej znajdowania to pewnie nie jest już tak dobrze).

Szczerze mówiąc to nie zastanawiałem się nad tym zbyt wiele, ten algorytm wymyśliłem wiele lat temu, a ostatnio tylko przetłumaczyłem go z Basica na C++. Zresztą prawdopodobnie tylko wyważyłem jakieś otwarte drzwi - nie wiem, nie interesowałem się nigdy algorytmiką :).

Offline Genesis72

  • Użytkownik

# Grudzień 12, 2006, 16:13:36
Tu znalazlerm kod do PathFinder
http://darkcult.republika.pl/alg/droga.html
W czy to jest napisane, czy we zwyklym C++ czy moze w vizual
i skad nmoze sciagnac ten jezyk

deX(ter)

  • Gość
# Grudzień 12, 2006, 17:09:45
W czy to jest napisane, czy we zwyklym C++ czy moze w vizual

Eee... Jakby..
No w sumie wiem, że Microsoft tworzy własne standardy, ale żeby własne C++ ?? :P

(...)i skad nmoze sciagnac ten jezyk

Może z www.c++-jezyksamwsobie.pl/download_language.php.
Można stąd pobrać też język angielski i niemiecki... ;)

Offline Genesis72

  • Użytkownik

# Grudzień 12, 2006, 18:03:01
Nie dziala ta linka


deX(ter)

  • Gość
# Grudzień 12, 2006, 19:26:54
Nie dziala ta linka

Szok  :o!! Wyjaśnię ci to:

1. Po pierwsze chciałem cię ośmieszyć...
2. Po drugie taka strona nie istnieje.
3. Po trzecie (na wypadek gdybyś nie zrozumiał żartu z linkiem) pod spodem napisałem jeszcze jeden, bardziej zrozumiały...

Jeśli nadal tego nie rozumiesz to dziwię się, że wiesz co to jest komputer (nie wspominając już o programowaniu...) ;)

Pozdr.

Offline Genesis72

  • Użytkownik

# Grudzień 12, 2006, 20:24:05
Sciagnalem TcLite
Mam Turbo C 2,01
ale nie chce sie skompilowac
Nie ma bibliotere m.in windows.h
pathfinde.h
Prosze o pomoc
Dziekuje

Offline Xion

  • Redaktor
    • xion.log

# Grudzień 12, 2006, 21:07:26
Jako że wątek już dawno od tematu i przechyla się niebezpiecznie w niepożądaną stronę - lock.
Genesis72: Zadaj swoje pytanie w osobnym wątku.