Temat akademicki

#131

Author: Wojciech Kocjan
Date: Sun, 17 Jul 2005 10:55

144 lines
6582 bytes

Hej,

W związku z tym, że tu jest za cicho, postanowiłem podrzucić temat do 
dyskusji. Mianowicie chciałbym w ramach nadmiaru luzu w pracy stworzyć 
gierkę strategiczną. Pomijam narazie jaką, bo pewnie się poddam i 
pomyślę o czymś znacznie prostszym (chyba, że są chętni do robienia 
razem :-).

Jednakże najbardziej podobał mi się kiedyś pomysł takiej gierki "When 2 
Worlds War" z Amigi (ostatnio widzialem "Pocket War" na pocketpc, ale 
nie sprawdzałem jak to wygląda tam). Mianowicie gra polegała na 
napisaniu poleceń dla jednostek, potem dla baz i bardzo często potem 
piło się piwo/wino/kawę/herbatę/whatever, a one same sobie walczyły. Tam 
trzeba było głównie dzielić produkcję nowych na "squads" i sprawdzać na 
ile tam jest problemów z tym. Ale pomysł miodny i na mocnej Amidze 
(czyli 40MHz :) nieraz miało się tysiące jednostek. Tradycyjny klikacz 
myszką by sobie nie dał rady - chociaż można je było ręcznie też 
obsługiwać. No ale sytuacja, gdzie trzeba było spaceshipami 
transportował lądowe/lotnicze/morskie, eskortować je innymi spaceshipami 
etc to byłoby sadyzmem robić to ręcznie.

W każdym razie bardzo korci mnie napisanie jakiejkolwiek gierki 
napędzanej skryptami. No i myślałem sobie jak do tego Tcl wykorzystać. 
Jedyny myk jest taki, że nie chciałbym żeby jeden skrypt był w stanie 
wykorzystywać za dużo czasu (taki mini RTOS :), a też nie chciałbym 
odpalać milionów wątków dla każdej jednostki z osobna. Aha, skoro 
miałaby to być gra dla siedzących w pracy, zakładam, że tura byłaby i 
tak proporcjonalna do średniej ilości jednostki/gracz - z początku 
krótko, jak już się każdy rozwinie to dużo dłużej (co sprzyja czasowi 
wyznaczania działań).

Przyszło mi do głowy kilka pomysłow, ale może ktoś ma inny:

1/ Podmiana funkcji pętlowych - for, foreach, while i inne
To zaproponowali goście z comp.lang.tcl, ale ma duży minus - jak już 
przerwę pętlę to do niej nie wrócę. Nawet jeśli zapamiętam stan i 
wykonam później iterację, to sprawdza się to w:

for {set i 0} {$i < 30} {incr i} {
     puts X
}

ale nie sprawdzi się w:

for {set i 0} {$i < 3} {incr i} {
     for {set j 0} {$j < 10} {incr j} {
         puts X
     }
}

nie mógłbym przerwać wewn. pętli i jakoś wrócić do głównej. A może 
mógłbym, ale ilość magii przekraczałaby pisanie debuggera do Tcl chyba.

2/ Każdy gracz to jeden wątek
To daje w miare sprawiedliwy podział czasu, raczej załatwiany przez 
system (nie wiem co z tzw userspace threads, chyba BSD ma/miał takie). 
Ale jest jeden minus - jeden infinite loop pozwoli zabić całą ekipę. Co 
byłoby ciekawe, bo znając błędy w skryptach można byłoby exploitować 
wroga ;-)

Można połączyć 1/ z 2/ i np żaden loop nie mógłby trwać więcej niż 
określony czas.

3/ Napisanie od nowa
To jest najciekawsze, ale nie wiem ile niesie ze sobą babraniny.

Stworzyłbym safe interpreter, w którym zdefiniowałbym pętle i wszystko 
jako własne polecenia. To wiąże się z kilkoma obejściami, na przykład 
nie można byłoby bezpośrednio wykonywać poleceń i wyliczać, ale w znośny 
sposób dałoby się to obejść. Pozbyłbym się części poleceń Tcl, a 
stosował prostsze (np for/foreach/while), ale trudno.

Większość można zrobić parsując [info complete], natomiast nie mam 
pojęcia ile jest z tym zabawy. Na pewno parsowanie szukając ";" oraz \n 
i sprawdzanie [info complete] działa dobrze, ale potem każda 
pętla/warunek musi sobie rozbijać swoje polecenia i boję się o czas tego.

4/ Zdarzenia
To z kolei da największy hardcore dla piszących skrypty.

Teoretycznie to najbardziej pasuje do Tcla, ale bardziej naturalne 
wydaje się zapisanie:

while {1} {
     while {[damage] < 0.6} {
         set pos [me nearest_enemy]
         move_to_weapons_range $pos
         attack $pos
     }
     go_to_base
}

Eventami:

proc repairmode {} {
     on newturn {}
     on idle {repairmode2}
}

proc repairmode2 {} {
     start_repair
     on newturn {}
     on idle {sop}
}

proc sop {} {
     on newturn {
         if {[damage] >= 0.6} {repairmode}
     }
     on idle {
         set pos [me nearest_enemy]
         move_to_weapons_range $pos
         attack $pos
     }
}

Chociaż to drugie jest faktycznie ciekawe :) No i prostsze do 
zaimplementowania. Plus nie wyrzuciłbym na śmietnik optymalizacji do 
bytecode.

Analizowałem też problem interpretatorów. Stworzenie 10000 
interpretatorów ([interp create -safe] + 50 interp alias) zżera 400MB 
pamięci. Natomiast interp dla każdej kombinacji gracz,rodzaj_obiektu 
plus namespace dla każdej instancji (dla zmiennych lokalnych etc) to już 
dobre rozwiązanie. 20000 jednostek + 10 zmiennych lokalnych każda (i 50 
interp alias dla każdego interpa) zajmuje 30MB. To jest do 
zaakceptowania bez problemu.

Oczywiście każdy team musi mieć innego interpa, żeby nie czytać sobie 
wzajemnie zmiennych :-) To by był dopiero hardcore - mimo, że [info] nie 
będzie ;-)

Czy ktoś chciałby podyskutować co tu można ciekawego wymyślić? Albo ktoś 
chciałby się dołączyć?

ps. Na studiach miałem "najkrótszą drogę", ale tu już za dużo nie 
pamiętam, a też podręcznikowe metody pewnie mają się kiepsko do realiów 
i optymalizacji kodu. Ma ktoś dobry algorytm na to? Chodzi głównie o 
mapy np 160x80, gdzie podane są "koszty" ścieżki (wolę nie bawić się w 
drogi jak w civ/freeciv, bo to utrudnia alrogytm AFAIR). Tu akurat 
chętnie wsparłbym się kodem w C, żeby było szybciej.

-- 
WK

Re: Temat akademicki

#132

Author: Googie
Date: Sun, 17 Jul 2005 23:44

31 lines
2270 bytes

Wojciech Kocjan wrote:

> W związku z tym, że tu jest za cicho, postanowiłem podrzucić temat do
> dyskusji. Mianowicie chciałbym w ramach nadmiaru luzu w pracy
> stworzyć gierkę strategiczną. Pomijam narazie jaką, bo pewnie się
> poddam i pomyślę o czymś znacznie prostszym (chyba, że są chętni do
> robienia razem :-).

Od dłuższego czasu pracuję nad pewnym rodzajem takiej gierki - walka
programowalnych (ro)botów, które wcześniej się uzbraja w bronie,
tarcze, dodatki, itp. Tyle że ja użyłem własnej implementacji pętli
zdarzeń (w oparciu o [after]), co w efekcie jest odrobinę
procesoro-żerne, ale działa :) Cóż, nie przyszło mi nic lepszego na
myśl. Nie kumam do końca metody, którą Ty chcesz użyć. Jakby dokładnie
miało się odbywać wykonywanie poszczególnych rozkazów, zapisanych w
formie skryptu Tcl?

> ps. Na studiach miałem "najkrótszą drogę", ale tu już za dużo nie
> pamiętam, a też podręcznikowe metody pewnie mają się kiepsko do
> realiów i optymalizacji kodu. Ma ktoś dobry algorytm na to? Chodzi
> głównie o mapy np 160x80, gdzie podane są "koszty" ścieżki (wolę nie
> bawić się w drogi jak w civ/freeciv, bo to utrudnia alrogytm AFAIR).
> Tu akurat chętnie wsparłbym się kodem w C, żeby było szybciej.

Heh... też bym chętnie poznał, choćby "podręcznikowy" czy "akademicki",
bo nawet takiego na googlach nie znalazłem :/

-- 
Pozdrawiam (Greetings)!
Googie

Re: Temat akademicki

#133

Author: Wojciech Kocjan
Date: Mon, 18 Jul 2005 06:19

44 lines
3022 bytes

Googie napisał(a):
> Wojciech Kocjan wrote:
> 
> 
> 
>>W związku z tym, że tu jest za cicho, postanowiłem podrzucić temat do
>>dyskusji. Mianowicie chciałbym w ramach nadmiaru luzu w pracy
>>stworzyć gierkę strategiczną. Pomijam narazie jaką, bo pewnie się
>>poddam i pomyślę o czymś znacznie prostszym (chyba, że są chętni do
>>robienia razem :-).
> 
> 
> Od dłuższego czasu pracuję nad pewnym rodzajem takiej gierki - walka
> programowalnych (ro)botów, które wcześniej się uzbraja w bronie,
> tarcze, dodatki, itp. Tyle że ja użyłem własnej implementacji pętli
> zdarzeń (w oparciu o [after]), co w efekcie jest odrobinę
> procesoro-żerne, ale działa :) Cóż, nie przyszło mi nic lepszego na
> myśl. Nie kumam do końca metody, którą Ty chcesz użyć. Jakby dokładnie
> miało się odbywać wykonywanie poszczególnych rozkazów, zapisanych w
> formie skryptu Tcl?

No dokładnie też nie wiem - wolę pomyśleć dłużej niż potem pisać, że 
jest "odrobinę procesożerne" :-). Ja myślę albo o zdarzeniowości - bo na 
logikę to albo w momencie jak np dojdzie do celu albo jak coś się 
wydarzy to zmieni plan działania. Może jakaś prostsza maszyna stanów ze 
zdarzeniami i implementacjami stanów - wtedy sam edytor stanów mógłby 
być graficzny i wypasiony nawet ;-)

Jak wymyślę to dam znać i postaram się zrobić w miarę uniwersalny. Skoro 
już robisz jakieś gry to może połączymy jakoś siły? :-)

>>ps. Na studiach miałem "najkrótszą drogę", ale tu już za dużo nie
>>pamiętam, a też podręcznikowe metody pewnie mają się kiepsko do
>>realiów i optymalizacji kodu. Ma ktoś dobry algorytm na to? Chodzi
>>głównie o mapy np 160x80, gdzie podane są "koszty" ścieżki (wolę nie
>>bawić się w drogi jak w civ/freeciv, bo to utrudnia alrogytm AFAIR).
>>Tu akurat chętnie wsparłbym się kodem w C, żeby było szybciej.
> Heh... też bym chętnie poznał, choćby "podręcznikowy" czy "akademicki",
> bo nawet takiego na googlach nie znalazłem :/

:-)

-- 
WK

Re: Temat akademicki

#134

Author: Googie
Date: Mon, 18 Jul 2005 21:57

54 lines
3070 bytes

Wojciech Kocjan wrote:

> No dokładnie też nie wiem - wolę pomyśleć dłużej niż potem pisać, że
> jest "odrobinę procesożerne" :-).

Z projektowaniem jest taki problem, że dopóki jest to sfera teorii, to
wszystko wydaje się "do zrobienia"i oczywiste, ale gdy przychodzi
praktyka, to jednak wiele faktów wypływa na wierzch i okazuje się że
"tak się nie da", lub "nie jest to zbyt udane rozwiązanie". Tak było
właśnie w moim przypadku. Choć oczywiście nie jest to reguła.

> Ja myślę albo o zdarzeniowości - bo 
> na logikę to albo w momencie jak np dojdzie do celu albo jak coś się
> wydarzy to zmieni plan działania.

No u mnie w gruncie rzeczy jest to zdarzeniowość - w końco
zaimplementowałem własną pętlę zdarzeń i dla każdego cyklu tej pętli
każdy z obiektów na mapie wykonuje swój cykl (ruch, obrót,
strzał, ...). Procesorożerność wynika raczej ze stosunkowo
zaawansowanej (jak na Tcl) grafiki i krótkich odstępów pomiędzy
cyklami pętli zdarzeń (boda 50ms), a gdy np jeden z botów zaczyna
naparzać z MachineGuna (gdzie każdy pocisk to obiekt ITcl) to nagle na
mapie liczba obietków rośnie z (np.) 3 do 15 :) Dochodzi sprawdzanie
kolizji dla każdego z nich, itd, itd...

Nie wiem jak sobie poradzisz z setkami, a nawet tysiącami obiektów (jak
to pisałeś na początku). Chyba że to ma być gra ASCII-Art?

Jak Ty chciałbyś takie problemy ominąć? Chyba że nie planujesz
"Real-Time Figting" (to takie wymyślone określenie, tu i teraz) ?

> Może jakaś prostsza maszyna stanów 
> ze zdarzeniami i implementacjami stanów - wtedy sam edytor stanów
> mógłby być graficzny i wypasiony nawet ;-)

A tego już nie kumam ;)

> Skoro już robisz jakieś gry to może połączymy jakoś siły? :-)

Zawsze jestem chętny. Ostatnio niestety jednak cierpię na brak czasu.
Kiedy nieco się rozluźni, to dam znać, o ile będziesz nadal
zainteresowany współpracą.

>> Heh... też bym chętnie poznał, choćby "podręcznikowy" czy
"akademicki",
>> bo nawet takiego na googlach nie znalazłem :/

> :-) 

Się tak nie uśmiechaj :) Znasz jakiś? Podziel się :)

-- 
Pozdrawiam (Greetings)!
Googie

Re: Temat akademicki

#135

Author: Wojciech Kocjan
Date: Tue, 19 Jul 2005 06:31

75 lines
4419 bytes

Googie napisał(a):
> Wojciech Kocjan wrote:
> 
> 
>>No dokładnie też nie wiem - wolę pomyśleć dłużej niż potem pisać, że
>>jest "odrobinę procesożerne" :-).
> Z projektowaniem jest taki problem, że dopóki jest to sfera teorii, to
> wszystko wydaje się "do zrobienia"i oczywiste, ale gdy przychodzi
> praktyka, to jednak wiele faktów wypływa na wierzch i okazuje się że
> "tak się nie da", lub "nie jest to zbyt udane rozwiązanie". Tak było
> właśnie w moim przypadku. Choć oczywiście nie jest to reguła.

Wiem. Dlatego przy większych projektach dawniej siedziałem miesiąc nad 
bawieniem sie wszystkimi detalami i próbowaniem robienia z nimi tego co 
chciałem. Pomagało tego unikać.

>>Ja myślę albo o zdarzeniowości - bo 
>>na logikę to albo w momencie jak np dojdzie do celu albo jak coś się
>>wydarzy to zmieni plan działania.
> No u mnie w gruncie rzeczy jest to zdarzeniowość - w końco
> zaimplementowałem własną pętlę zdarzeń i dla każdego cyklu tej pętli
> każdy z obiektów na mapie wykonuje swój cykl (ruch, obrót,
> strzał, ...). Procesorożerność wynika raczej ze stosunkowo
> zaawansowanej (jak na Tcl) grafiki i krótkich odstępów pomiędzy
> cyklami pętli zdarzeń (boda 50ms), a gdy np jeden z botów zaczyna
> naparzać z MachineGuna (gdzie każdy pocisk to obiekt ITcl) to nagle na
> mapie liczba obietków rośnie z (np.) 3 do 15 :) Dochodzi sprawdzanie
> kolizji dla każdego z nich, itd, itd...

Ja właśnie wolałbym uniknąć Itcl do tego. Zostałbym przy zmiennej np
::objects::spaceship1234 i w niej pamiętać wszystko. A jakieś pseudoapi 
byłoby na zasadzie

interp alias ... spaceship1234 \
     {} ::objects::handle_spaceship ::objects::spaceship1234

Jeszcze nie wiem, dlatego się bawię w testy.

> Nie wiem jak sobie poradzisz z setkami, a nawet tysiącami obiektów (jak
> to pisałeś na początku). Chyba że to ma być gra ASCII-Art?

Planowałem na wyrost, żeby potem nie klnąć na design kilku rzeczy. Sam 
jeszcze nie wiem.

> Jak Ty chciałbyś takie problemy ominąć? Chyba że nie planujesz
> "Real-Time Figting" (to takie wymyślone określenie, tu i teraz) ?

Ja myślałem o strategii, dostosowanej do realiów siedzenia w firmie. Nie 
wiem co z trzymaniem mapy - bo do jej renderowania pewnie musiałbym na 
canvas wrzucić ok 30000 obiektów. Sadze, ze skonczy sie na wygenerowaniu 
na sztywno mapy do obrazka - wtedy pamiętanie tego zajmie 30MB, ale 
będzie śmigało. Można też to potem pociąć (np na kawałki 200x200). 
Zobaczymy.

>>Może jakaś prostsza maszyna stanów 
>>ze zdarzeniami i implementacjami stanów - wtedy sam edytor stanów
>>mógłby być graficzny i wypasiony nawet ;-)
> A tego już nie kumam ;)

Klikacz kodu :D

>>Skoro już robisz jakieś gry to może połączymy jakoś siły? :-)
> Zawsze jestem chętny. Ostatnio niestety jednak cierpię na brak czasu.
> Kiedy nieco się rozluźni, to dam znać, o ile będziesz nadal
> zainteresowany współpracą.

> Się tak nie uśmiechaj :) Znasz jakiś? Podziel się :)

Właśnie się koduje w C. Nie szuka optymalnej, ale w miare dobrą i robi 
to szybko. Tylko jest minus - to trwa ok 1 sekundy na planszy 200x100 
(0,0 do 199,99). Aha i nie przewiduje, ze planety sa okragle i mozna 
przesmigac z prawej strony do lewej - ale i do tego dojdę.

-- 
WK

Re: Temat akademicki

#136

Author: Wojciech Kocjan
Date: Tue, 19 Jul 2005 08:07

33 lines
2058 bytes

Wojciech Kocjan napisał(a):
> Właśnie się koduje w C. Nie szuka optymalnej, ale w miare dobrą i robi 
> to szybko. Tylko jest minus - to trwa ok 1 sekundy na planszy 200x100 
> (0,0 do 199,99). Aha i nie przewiduje, ze planety sa okragle i mozna 
> przesmigac z prawej strony do lewej - ale i do tego dojdę.

Ok.

Kod właśnie przeszedł drobną optymalizację (duża wpadka w jednej pętli) 
i 160x80 przeszukuje mi w 0,02s (zaczyna myslec 0,2s przy 400x200, ale 
to juz szalenstwo troche - a tez zazwyczaj ktos chce sie przesunac o 
50-60 pol, co daje zabojczo krotki czas).

www.zoro2.org/_chwilowe/shortestpath.c

To jeszcze i tak mozna mocno zoptymalizowac (szybkosc kosztem 
czytelnosci), ale nie chce mi sie.

Wystarczy skompilowac i smiga.

set map [list \
     [list 1 2 3 4 5 6 7] \
     [list 4 3 2 1 3 2 1] \
     [list 2 3 1 4 5 3 2] \
     [list 4 5 6 3 2 7 1] \
     ]

set path [shortestpath::shortestpath $map 0 0 6 3]

foreach {x y} $path {puts "Krok: $x, y"}

-- 
WK

Re: Temat akademicki

#137

Author: Wojciech Kocjan
Date: Tue, 19 Jul 2005 08:21

34 lines
1978 bytes

Wojciech Kocjan napisał(a):

 > Właśnie się koduje w C. Nie szuka optymalnej, ale w miare dobrą i 
robi to szybko. Tylko jest minus - to trwa ok 1 sekundy na planszy 
200x100 (0,0 do 199,99). Aha i nie przewiduje, ze planety sa okragle i 
mozna przesmigac z prawej strony do lewej - ale i do tego dojdę.


Ok.

Kod właśnie przeszedł dużą (przedtem wysłałem po drobnej, ale teraz to 
już power!) optymalizację. Analizuje 500x500 w 0,2s (na P4 2,8GHz). 
Natomiast 200x200 już w 0,04s.

www.zoro2.org/_chwilowe/shortestpath.c

To jeszcze i tak mozna mocno zoptymalizowac (szybkosc kosztem 
czytelnosci), ale nie chce mi sie.

Wystarczy skompilowac i smiga.

set map [list \
     [list 1 2 3 4 5 6 7] \
     [list 4 3 2 1 3 2 1] \
     [list 2 3 1 4 5 3 2] \
     [list 4 5 6 3 2 7 1] \
     ]

set path [shortestpath::shortestpath $map 0 0 6 3]

foreach {x y} $path {puts "Krok: $x, y"}

-- 
WK

🚀 go-pugleaf

Thread View: pl.comp.lang.tcl

Temat akademicki

Re: Temat akademicki

Re: Temat akademicki

Re: Temat akademicki

Re: Temat akademicki

Re: Temat akademicki

Re: Temat akademicki

Thread Navigation