21.10.2024 22:44
[#32]
Re: Astar w BB
@tukinem, post #31
Mozesz pogadac z meynaf-em:
link
Tylko nie pamietam, czy on mi nie mowil kiedys, ze jego wersja uzywa instrukcji bitfields, czyli tylko 68020+.
Choc byc moze daloby sie przerobic na 68000, ale operacje na bitach na 68000 sa wolne.
BTW. A jak reaguje Twoja procedura, gdy nie ma zadnego polaczenia pomiedzy punktem A a punktem B?
Wiesza sie, nic nie robi, podchodzi do sciany najblizej jak sie da do punktu B?
link
Tylko nie pamietam, czy on mi nie mowil kiedys, ze jego wersja uzywa instrukcji bitfields, czyli tylko 68020+.
Choc byc moze daloby sie przerobic na 68000, ale operacje na bitach na 68000 sa wolne.
BTW. A jak reaguje Twoja procedura, gdy nie ma zadnego polaczenia pomiedzy punktem A a punktem B?
Wiesza sie, nic nie robi, podchodzi do sciany najblizej jak sie da do punktu B?
21.10.2024 23:18
[#33]
Re: Astar w BB
@Don_Adan, post #32
Przy braku drogi funkcja nic nie zwraca. Był mały problem, gdy pewne pola były ogrodzone murem (wartością 1 w tablicy), ale wyeliminowałem to dzięki zmiennej checkMore. Połaszczyłbym się do przepisania do do asemblera, ale problem stanowi głównie działanie list dynamicznych. W tym przypadku mam jedną taką którą nazwałem t(). No i też nie bardzo potrafiłbym się poruszać szybko po tablicy dwuwymiarowej bez mnożenia dla pozycji Y.
Wszystko, co dotyczy samego algorytmu znajduje się w funkcji. Na początku jedynie trzeba wstawić stałą #XMAX i #YMAX oraz strukturę .coords. Następnie otwieram ekran Intuition, a na końcu kodu po zadeklarowaniu funkcji rysuję mapę tablicy, rysuję WBoxami pola startu, końca oraz ściany, potem resetuję timer (nie chciało mi się pisać funkcji asemblerem), następnie następuje oczekiwanie, bo tam jest NPrint Astar{startX,startY,stopX,stopY} czyli ma wypisać zmienną tekstową, którą wypluje funkcja. Po wypisaniu od razu wypisuję stan timera i napis "PRESS ESC" aby wyjść z programu.
Jeśli chcesz, mogę opisać krok po kroku co się dzieje w tej funkcji, jak się zabezpieczam przed wyskokiem poza tablicę, po co są dodatkowe zmienne check i checkMore, po co jest zmienna a, b, XT i YT itd.
Ostatnia aktualizacja: 21.10.2024 23:26:34 przez tukinem
Wszystko, co dotyczy samego algorytmu znajduje się w funkcji. Na początku jedynie trzeba wstawić stałą #XMAX i #YMAX oraz strukturę .coords. Następnie otwieram ekran Intuition, a na końcu kodu po zadeklarowaniu funkcji rysuję mapę tablicy, rysuję WBoxami pola startu, końca oraz ściany, potem resetuję timer (nie chciało mi się pisać funkcji asemblerem), następnie następuje oczekiwanie, bo tam jest NPrint Astar{startX,startY,stopX,stopY} czyli ma wypisać zmienną tekstową, którą wypluje funkcja. Po wypisaniu od razu wypisuję stan timera i napis "PRESS ESC" aby wyjść z programu.
Jeśli chcesz, mogę opisać krok po kroku co się dzieje w tej funkcji, jak się zabezpieczam przed wyskokiem poza tablicę, po co są dodatkowe zmienne check i checkMore, po co jest zmienna a, b, XT i YT itd.
Ostatnia aktualizacja: 21.10.2024 23:26:34 przez tukinem
22.10.2024 12:15
[#36]
Re: Astar w BB
@tukinem, post #35
Nie mam dostepu do Amigi, zeby zdeasemblowac, tylko pliki ASM sa dla mnie czytelne.
Ogolnie to na pewno jest za wolne, zeby byc uzyteczne do gry w takiej formie, bo przeciez to bylaby tylko jedna jednostka na ekranie, a tych moze byc kilka lub kilkanascie.
Zreszta to jest problem chyba wszystkich tego typu gier, typu UFO (2) czy Sabre Team.
Ze komputer ma do wykonania duza ilosc ruchow przeciwnika, ktore musi przeliczyc.
To musi byc jakos sprytnie porobione, zeby nie bylo zbyt dlugiego czasu oczekiwania na ruch.
Byc moze mapa musi byc w jakis specjalny sposob stworzona.
Ogolnie to na pewno jest za wolne, zeby byc uzyteczne do gry w takiej formie, bo przeciez to bylaby tylko jedna jednostka na ekranie, a tych moze byc kilka lub kilkanascie.
Zreszta to jest problem chyba wszystkich tego typu gier, typu UFO (2) czy Sabre Team.
Ze komputer ma do wykonania duza ilosc ruchow przeciwnika, ktore musi przeliczyc.
To musi byc jakos sprytnie porobione, zeby nie bylo zbyt dlugiego czasu oczekiwania na ruch.
Byc moze mapa musi byc w jakis specjalny sposob stworzona.
22.10.2024 13:03
[#37]
Re: Astar w BB
@Don_Adan, post #36
Im mniej jest wolnych pól tym szybciej algorytm wyeliminuje niepotrzebne liczenia. Np. w labiryncie, gdzie będzie kilka rozgałęzień, to powinien szybko wyliczyć taką drogę. Natomiast na otwartej przestrzeni będzie długo liczyć.
Co do gier typu HoM&M, jeśli mamy np maksymalnie ruch o 10 pół, to wtedy nie golimy całej mapy, a jedynie jej wycinek, co znacznie przyspieszy drogę. Wtedy taki kod trzeba zmienić, bo u mnie oblicza dystans z A do B, a gra narzucałaby maksymalny dystans do przebycia, czyli te 10 kroków.
Ostatnia aktualizacja: 22.10.2024 13:05:29 przez tukinem
Co do gier typu HoM&M, jeśli mamy np maksymalnie ruch o 10 pół, to wtedy nie golimy całej mapy, a jedynie jej wycinek, co znacznie przyspieszy drogę. Wtedy taki kod trzeba zmienić, bo u mnie oblicza dystans z A do B, a gra narzucałaby maksymalny dystans do przebycia, czyli te 10 kroków.
Ostatnia aktualizacja: 22.10.2024 13:05:29 przez tukinem
22.10.2024 14:33
[#38]
Re: Astar w BB
@tukinem, post #37
Co do HOMM2 to sa 2 rozne rzeczy.
Mozesz zaznaczyc ruch przez cala mape o ile jest ona widoczna. I tutaj jest robiony path finding.
Ale wykona Ci sie tylko taki ruch na ile masz punktow ruchu.
Tam jest to bardziej skomplikowane, bo zasieg ruchu jest zalezny po czym sie poruszasz hirkiem np. droga, pole, bagno itp oraz jakie najwolniejsze jednostki masz w poruszajacej sie armii.
Mozesz zaznaczyc ruch przez cala mape o ile jest ona widoczna. I tutaj jest robiony path finding.
Ale wykona Ci sie tylko taki ruch na ile masz punktow ruchu.
Tam jest to bardziej skomplikowane, bo zasieg ruchu jest zalezny po czym sie poruszasz hirkiem np. droga, pole, bagno itp oraz jakie najwolniejsze jednostki masz w poruszajacej sie armii.
22.10.2024 18:01
[#40]
Re: Astar w BB
@tukinem, post #39
No i to tam działa bardzo szybko
well dr Watson
Lista Procesorow z lat 80/90 i ich moc obliczeniowa.
HoMM 2 wymaga pentium 90
a wiec :
Pentium 75 89 Mips
Pentium 90 107 Mips
Pentium 100 112 Mips
Pentium 120 134 Mips
i Amiga rulez (nie tym razem
):68020/16 2 Mips
68020/20 3 Mips
68020/25 4 Mips
68020/30 6 Mips
68020/33 7 Mips
68030/50 12 Mips
68040/25 21 Mips
co pan panie poradzisz jak nic nie poradzisz...
22.10.2024 18:22
[#41]
Re: Astar w BB
@selur, post #40
No ale ten sam algorytm był w Heroes of Might and Magic 1, a jego wymagania to:
Źródło
u mnie test na A630 z 68030/50 MHz to dobre kilka sekund.
Przypomnę dodatkowo, że jeśli kliknęliśmy w miejsce, do którego szło się okrężną drogą, to pięknie ścieżka się rysowała poza ekran i wychodziła z drugiego końca, jeśli wykraczała sporo poza obszar
W moim algorytmie miejsca raczej nie braknie, bo zrobiłem listę na 10 tys kafelków
gorzej z szybkością.
No ale chyba jedynie Ty jesteś pozytywnie nastawiony do tego. A może ktoś by chciał przetestować na swojej realnej Amidze? Tyle macie różnych dopalonych sprzętów, więc może warto uruchomić takiego execa u siebie na maszynie i podzielić się informacją o szybkości? A może FPU dużo da?
CPU: 486DX, 33 MHz
RAM: 8 MB
STO: 25 MB
RES: SVGA, 640x480, 256 Colors
Źródło
u mnie test na A630 z 68030/50 MHz to dobre kilka sekund.
Przypomnę dodatkowo, że jeśli kliknęliśmy w miejsce, do którego szło się okrężną drogą, to pięknie ścieżka się rysowała poza ekran i wychodziła z drugiego końca, jeśli wykraczała sporo poza obszar
W moim algorytmie miejsca raczej nie braknie, bo zrobiłem listę na 10 tys kafelków
gorzej z szybkością.No ale chyba jedynie Ty jesteś pozytywnie nastawiony do tego. A może ktoś by chciał przetestować na swojej realnej Amidze? Tyle macie różnych dopalonych sprzętów, więc może warto uruchomić takiego execa u siebie na maszynie i podzielić się informacją o szybkości? A może FPU dużo da?
22.10.2024 18:34
[#42]
Re: Astar w BB
@tukinem, post #41
na PC gry na minimalnych wymaganiach zawsze sie slimaczyly ale nie wiem jak Homm 1 chodzi na 486 Dx.
no to troche dlugo, trzeba by to przepisac do asemblera i dopiero policzyc czas.
Ogolnie RTS'y na Amidze klasycznej sie slimacza niemilosiernie, nawet w grach turowych nie bylo rewelacji (patrz UFO).
u mnie test na A630 z 68030/50 MHz to dobre kilka sekund.
no to troche dlugo, trzeba by to przepisac do asemblera i dopiero policzyc czas.
Ogolnie RTS'y na Amidze klasycznej sie slimacza niemilosiernie, nawet w grach turowych nie bylo rewelacji (patrz UFO).
22.10.2024 19:03
[#43]
Re: Astar w BB
@selur, post #42
Więc jedynie labiryntówka się nada, gdzie mamy ze 3 różne drogi do wyboru ale ciekawi mnie jakby sobie radziły takie procki 040, 060.
W Settle The World koder też napisał własny algorytm w Ami Blitz i widocznie jakoś mu to śmiga, skoro go używa a gra jest stale rozbudowywana o nowe rzeczy.
ale ciekawi mnie jakby sobie radziły takie procki 040, 060.W Settle The World koder też napisał własny algorytm w Ami Blitz i widocznie jakoś mu to śmiga, skoro go używa a gra jest stale rozbudowywana o nowe rzeczy.
22.10.2024 20:05
[#45]
Re: Astar w BB
@Don_Adan, post #44
o tym zapomnialem, ze przeciez powstaje ta nowa strategia turowa w Blitzie "Settle The World" wiec na pewno jakis zaimplementowal, trzeba by zapytac.
moze Minniat ma jeszcze gdzies jakies dane o pathfinderze z Dune 2. To byl bardzo dobry pathfinder jak na Amige a Minniat kiedys duzo grzebal i rozpracowywal Dune2.
amosowa turowa Genesia ma dobry pathfinder na bank jako wstawka asemblerowa ale autor nigdy nie udostepnil zadnych zrodel gry wiec tu lipa.
rozkodowalem Legion pare lat temu i niestety nie ma tam pathfindera
,postac lezie wprost do celu po lini prostej, co zreszta widac od razu w grze.
Ostatnia aktualizacja: 22.10.2024 20:10:44 przez selur
moze Minniat ma jeszcze gdzies jakies dane o pathfinderze z Dune 2. To byl bardzo dobry pathfinder jak na Amige a Minniat kiedys duzo grzebal i rozpracowywal Dune2.
amosowa turowa Genesia ma dobry pathfinder na bank jako wstawka asemblerowa ale autor nigdy nie udostepnil zadnych zrodel gry wiec tu lipa.
rozkodowalem Legion pare lat temu i niestety nie ma tam pathfindera
,postac lezie wprost do celu po lini prostej, co zreszta widac od razu w grze.Ostatnia aktualizacja: 22.10.2024 20:10:44 przez selur
22.10.2024 20:21
[#46]
Re: Astar w BB
@selur, post #45
W Legionie, mi chodzi o path finding przeciwnikow (te truposze), oni sie jakos tam ruszali, zarowno na mapie jak i w czasie walki, chyba, ze zle pamietam. Da sie napisac path finding pod gre. Najprostszy to prosto z punktu A do B, a jak przeszkoda to obejscie przeszkody lewa strona. Oczywiscie wtedy mapy musza byc dobrze zrobione. Niezbyt skomplikowane, jesli chodzi o przeszkody, bez labiryntow.
Ostatnia aktualizacja: 22.10.2024 20:22:14 przez Don_Adan
Ostatnia aktualizacja: 22.10.2024 20:22:14 przez Don_Adan
22.10.2024 20:49
[#48]
Re: Astar w BB
@selur, post #45
W Dune 2 z tego co wiem nie ma path-findingu. Jeżeli jednostka napotka na przeszkodę, po prostu stara się ją ominąć w jednym z kierunków.
W Dune 2 nie ma ramp, więc wszędzie jest dostęp po linii prostej (pomijając ściany i budynki i nieliczne góry).
Dune 2 ma bardzo fajny generator mapy. Generuje skały, góry, piasek oraz pola przyprawowe w całkiem ciekawy sposób. Tak żeby były to spójne obszary. Następnie ustala grafikę kafelków licząc sąsiednie klocki o tym samym typie.
Pamiętam, jak mnie to fascynowało, generowałem mapkę według algorytmu na kartce papieru.
Ostatnia aktualizacja: 22.10.2024 21:02:02 przez Hexmage960
W Dune 2 nie ma ramp, więc wszędzie jest dostęp po linii prostej (pomijając ściany i budynki i nieliczne góry).
Dune 2 ma bardzo fajny generator mapy. Generuje skały, góry, piasek oraz pola przyprawowe w całkiem ciekawy sposób. Tak żeby były to spójne obszary. Następnie ustala grafikę kafelków licząc sąsiednie klocki o tym samym typie.
Pamiętam, jak mnie to fascynowało, generowałem mapkę według algorytmu na kartce papieru.
Ostatnia aktualizacja: 22.10.2024 21:02:02 przez Hexmage960
22.10.2024 23:53
[#52]
Re: Astar w BB
@Don_Adan, post #46
...oni sie jakos tam ruszali
owszem ruszali ale wszystko w Legionie to magiczne Rnd(n).
Procedura ruchu postaci/potworoww kodzie jest jedna, zwie sie 'Procedure A_RUCH[A,I]' i samego ruchu jest tam 30 linijek kodu i nie nadaje sie tak naprawde do niczego sensownego (ot taka magiczna sztuczka, ktora tworzy iluzje tego, ze postac umie sie poruszac i na tym koniec).
Da sie napisac path finding pod gre
no oczywiscie, ze sie da. Trzeba go tylko napisac
#Hexmage960
W Dune 2 z tego co wiem nie ma path-findingu
jakby nie bylo to by jednostki sie nie poruszaly. Moze nie ma zadnego algorytmu wagowego ale jakis jest i to sprawny, bo jednostki potrafia omijac baze oraz inne jednostki, zeby dotrzec do celu. Co wiecej w Diunie masz w krytycznym momencie grubo ponad 50 jednostek wiec algorytm nie moze byc dziadowski, bo by sie wszsytkie zablokowaly na pierwszej lepszej przeszkodzie.
23.10.2024 00:08
[#53]
Re: Astar w BB
@selur, post #52
W Dune 2 jednostki "na pałę" jadą do bazy gracza, nie patrzą którędy tylko najprostszą drogą :). W wersji PC w której chyba były większe limity ze względu na większą moc obliczeniową, całe sznureczki jednostek szły na śmierć jedną ścieżką. Ale w wersji Amigowej wcale nie było lepiej tylko tych jednostek było mniej na raz i mniej to było widać. Wystarczyło walnąć kilka wieżyczek rakietowych w odpowiednim miejscu i cała reszta bazy mogła być praktycznie nie chroniona.
Był za to rzeczywiście jakiś algorytm omijania jednostek który powodował, że przy większym ataku gracza, jego czołgi potykały się o własne nogi bo próbowały się jednocześnie wyminąć i zwykle jeździły na boki zajeżdżając drogę innym czołgom, które w podobny sposób próbowały się wymijać :).
Był za to rzeczywiście jakiś algorytm omijania jednostek który powodował, że przy większym ataku gracza, jego czołgi potykały się o własne nogi bo próbowały się jednocześnie wyminąć i zwykle jeździły na boki zajeżdżając drogę innym czołgom, które w podobny sposób próbowały się wymijać :).
23.10.2024 00:58
[#54]
Re: Astar w BB
@selur, post #52
Widzisz Selur magia wszystko zalatwia, w Kings Bounty magowie i smoki potrafia latac, wiec nie ma przeszkod dla nich.
A tak na serio to spytaj sie tego Amigowego AI, zobaczymy co odpisze.
Edycja, Albo daj konkurs na EAB o szybki path finding w ASM 68k
Ostatnia aktualizacja: 23.10.2024 01:02:01 przez Don_Adan
A tak na serio to spytaj sie tego Amigowego AI, zobaczymy co odpisze.
Edycja, Albo daj konkurs na EAB o szybki path finding w ASM 68k
Ostatnia aktualizacja: 23.10.2024 01:02:01 przez Don_Adan
23.10.2024 00:59
[#55]
Re: Astar w BB
@bfgmatik, post #53
W Dune 2 jednostki "na pałę" jadą do bazy gracza
a owszem ale to akurat byla kwestia AI komputera a nie pathfindera. Pamietam, ze pozniej gralem w Wacrafta 1, ktory powstal 2 lata pozniej i AI w sumie tez bylo 'glupie'. Komputer scigal nasza jednostke, az do samej smierci i z uporem jakiegos maniaka ganial ja obok calego naszego regimentu i notorycznie budowal te same budynki w tym samym miejscu, w Dune 2 tak wkurzalo odbudowywanie fabryk.
W ogole cale AI np. w Warcrafcie polegalo na budowaniu tych samych jednostek i co jakis czas wysylaniu ich sznurkiem na baze gracza czyli tak samo jak w Dune 2. Przez to na mostach mozna bylo urzadzac zasadzki i wyrzynac cale ekspedycje komputera. A pamietajmy, ze minimalne wymagania dla WC 1, to bylo juz pozniejsze 386 z 10 razy szybsze niz A500, wiec Dune 2 na A500 to byla wtedy bardzo dobra gra nawet z takim AI.
23.10.2024 08:26
[#56]
Re: Astar w BB
@selur, post #55
W Warcrafcie mogło to być jeszcze inaczej. Na mapie mamy stałe elementy: trawa, budynki, rzeki. Podczas ładowania gry już wtedy program mógł obliczać sobie ścieżki drogi. Jeśli po drodze był las to po wycince lekko droga do naszej mapy mogła się modyfikować. Jeśli na drodze stał nasz żołnierz to wiadomo: komputer nas atakował.
Przytoczę jeszcze inną ciekawostkę. Settlers 1. Podczas gry budowaliśmy własny system dróg. Wtedy już musiał być obliczany pathfinding do animacji budowniczych którzy od razu szli w zaparte budować kolejny budynek. Teraz przykładowo nabudowaliśmy pajęczynę dróg i od razu stawiamy jakiś budynek. Bez zająknięcia po chwili wychodzi taki osadnik z zamku i zmierza na teren budowy najkrótszą drogą. A tam nie ma prostych dróg góra-dół-lewo-prawo.
Ostatnia aktualizacja: 23.10.2024 08:28:16 przez tukinem
Przytoczę jeszcze inną ciekawostkę. Settlers 1. Podczas gry budowaliśmy własny system dróg. Wtedy już musiał być obliczany pathfinding do animacji budowniczych którzy od razu szli w zaparte budować kolejny budynek. Teraz przykładowo nabudowaliśmy pajęczynę dróg i od razu stawiamy jakiś budynek. Bez zająknięcia po chwili wychodzi taki osadnik z zamku i zmierza na teren budowy najkrótszą drogą. A tam nie ma prostych dróg góra-dół-lewo-prawo.
Ostatnia aktualizacja: 23.10.2024 08:28:16 przez tukinem
23.10.2024 10:42
[#57]
Re: Astar w BB
@tukinem, post #56
W Settlers gralem tylko troche, ale path finding po drogach jest latwiejszy niz po calym terenie.
Do tego jak ktos buduje tartak, to zwykle tam blisko musza byc drzewa.
Jak kamieniolom/kopalnie to tez powinny byc blisko surowce.
No i o ile dobrze pamietam to budowa troche trwala, wiec np. przy budowie tartaku, gra moze juz szukac najblizszych drzew.
Ciekawe pewnie moze byc zagranie zle w Settlers, czyli budowa tartaku tam gdzie nie ma drzew.
Ale tam sie chyba tez wysylalo pracownikow do pracy wskazujac im cel.
Do tego jak ktos buduje tartak, to zwykle tam blisko musza byc drzewa.
Jak kamieniolom/kopalnie to tez powinny byc blisko surowce.
No i o ile dobrze pamietam to budowa troche trwala, wiec np. przy budowie tartaku, gra moze juz szukac najblizszych drzew.
Ciekawe pewnie moze byc zagranie zle w Settlers, czyli budowa tartaku tam gdzie nie ma drzew.
Ale tam sie chyba tez wysylalo pracownikow do pracy wskazujac im cel.
23.10.2024 10:50
[#58]
Re: Astar w BB
@Don_Adan, post #57
Nie chodziło mi o drwala, który wychodzi z tartaku po chwili, a o budowniczego, który od razu po wskazaniu miejsca budowli wychodzi z zamku i zmierza do miejsca budowy. A drogi moim zdaniem są bardziej skomplikowane. Plansza również jest podzielona na kafle, a dodatkowo są ruchy na ukos, tak jak ścieżki biegną po mapie, a nie tylko w 4 kierunkach:
23.10.2024 11:45
[#59]
Re: Astar w BB
@tukinem, post #58
Zawsze mnie w tej grze fascynował poziom skomplikowania decyzji jakie towary nosić, w jakiej kolejności, do których budynków najpierw, kto ma pierwszeństwo kiedy się wymijają, co robić kiedy pod chorągiewką już nie ma miejsca, kiedy wojsko idzie do ataku i zajmuje całą przepustowość drogi, itp. Wszystko można ustawić w okienkach konfiguracji i rzeczywiście ludziki robią dokładnie to co im się każe. Trzeba było wiele wieczorów, żeby to opanować do poziomu, żeby optymalnie rozwijać wioskę, szczególnie dużych rozmiarów. Autor był geniuszem :).
23.10.2024 12:12
[#60]
Re: Astar w BB
@tukinem, post #58
No ale ludki w Settlersach mogą chodzić tylko drogami. Więc drogi tworzą graf, krawędzie grafu to drogi, a długość każdej drogi to "koszt" przebycia krawędzi. I można Astar zapuścić na tym grafie, co będzie dużo mniej złożone obliczeniowo. Siatka kwadratowych pól to tylko szczególny przypadek tego algorytmu.