1 Ostatnio edytowany przez xxl (2006-11-25 18:09:08)

witam,

dany jest labirynt 256x256 'komorek'.
labirynt jest tak skonstruowany, ze miedzy komorkami mamy sciany, 'drzwi' jednokierunkowe, dwukierunkowe, teleporty jednokierunkowe, dwukierunkowe, z jednej strony drzwi a z drugiej teleport. teleport to dzwi, ktore prowadza nie do tej komorki ktora jest obok tylko przez nas zdefiniowanej. z kazdej komorki mozna isc teoretycznie w 4 strony. kazda komorka przechowuje 'stan' np. odwiedzona/nieodwiedzona, z specjalnymi wlasciwosciami, liste przedmiotow (bardzo krotka lista 2-3 przemioty) itp.

robiac to na tablicach... polegniemy (tak mi sie wydaje) na standardowym atari 64kb moze okazac sie ze brakuje pamieci na sama reprezentacje labiryntu.
mysle o grafie, grafy maja sporo zalet i do tego co napisalem idealnie pasuja.

potrzebuje pomyslu jak stworzyc taki graf na atari i ile bedzie potrzebowal ramu 1,2,5,10 kb ? (nie chodzi o wygenerowanie labiryntu tylko o silnik trzymajacy w atari jego reprezentacje)

---
heh, no to troszke przesadzilem, szybkie obliczenia mowia ze graf o taich wlasciwosciach jak powyzej zajmie 576kb
ale za to wielkosci 64x64 to juz tylko 20 kb ...

http://atari.pl/hsc/ad.php?i=1.

2 Ostatnio edytowany przez laoo/ng (2006-11-25 21:01:31)

ale 64x64 to nie musi być już graf bo pamięci Ci starczy :)

Graf opłaca Ci się tylko wtedy, jak nie wszystkie pola błedą pełne. w stylu, że labirynt byłby np. generowany w czasie chodzenia w nim, że w pamięci byłyby pamiętane tylko komórki odwiedzone, a do generowania nieodwiedzonych mielibyśmy deterministyczny algorytm.

Pozatym określenie [i]graf[/f] jest baaardzo ogólne, bo jedną z reprezentacji grafu jest właśnie dwuwymiarowa tablica :)

3

tak, tablica ale w tej tablicy nie zapiszesz jak wygladaja polaczenia miedzy komorkami (bez wchodzenia w 3 wymiar) a to mi jest bardzo bardzo potrzebne dlatego graf - jest sporo anomali komorki lezace kolo siebie w tablicy nie koniecznie leza kolo siebie w labiryncie poza tym tak jak pisalem sa rozne sposoby 'przejscia' miedzy komorkami, poza tym mozna nadawac takim komorka 'specjalne wlasciwosci' i tak na 1 komorce mozna zasymulowac np dlugie korytarze, teleporty ...
dzieki Tobie uswiadomilem sobie ze mowiac 64x64 mialem na mysli 4096 komorek a to moze byc o wiele wiekszy labirynt niz dwuwymiarowa tablica 64x64 dzieki wlasnie tym pustym miejscom.
spostrzezenie: nawet 1000 'lokacji' to juz sporo do rownego rachunku 1024, wiec... to zaczyna miec rece i nogi w takim przypadku graf zajmie ok 5kb i moze reprezentowac labirynt z tymi wszystkimi wlasciwosciami o wiele wiekszy niz 64x64 :-)

http://atari.pl/hsc/ad.php?i=1.

4

Wszystko kwestia mądrego zakodowania danych. Jedna lokacja zakodowana na strukturze o zmiennym rozmiarze może pamiętać obszar o dowolnych wymiarach (1x1 czy korytarz 1xn) połączony przejściami z dowolnymi innymi obszarami. Wszystko może być oczywiście generowane przez jakiś program na piecu. Trzeba tylko porządnie przemyśleć

5

xxl - czy Ty chcesz po prostu zakodowac mape do gry?
Jesli tak, to przestan wyslec o niej jak o siatce wspolrzednych 64x64 czy 256x256! Po prostu narysuj sobie na kartce lokacje w postaci kwadracikow obok siebie, dorysuj drzwi, dlugimi strzalkami polacz kwadraciki miedzy ktorymi ma dzialac teleporter.  To wszystko juz pewnie masz.
A teraz zakoduj to tak:
- kazdej lokacji, ktora moze odwiedzic gracz, nadaj kolejny numer: 1, 2, 3... Kolejnosc nadawania moze sie miec nijak do polozenia "geograficznego" na mapie. Oczywiscie nie nadawaj numerow "pustym miejscom" miedzy lokacjami!
- Policz ile masz lokacji (oznaczmy to N).
- Robisz tablice Nx5. Wiersze tej tablicy (1..N) odpowiadaja kolejnym lokacjom. 4 kolumny odpowiadaja kierunkom: N,S,E,W. Dla kazdej lokacji wpisujesz w te kolumny, do ktorej lokacji trafi gracz kiedy pojdzie w danym kierunku. Niezaleznie czy beda to drzwi, czy teleporter.
Przyklad: wiersz 1 zawiera wpisy: 2,12,3,0. Oznacza to ze idac na polnoc wejdziemy do lokacji 2, na poludnie - 12, na wschod 3, a na zachod przejscia nie ma.
Kolumne 5-ta przeznacz na flagi oznaczajace np czy pomieszczenie bylo juz odwiedzone czy nie, itp.
Dodajac jeszcze 2 kolumny mozesz rozszerzyc mozliwosc chodzenia o Gore i Dol.
Teraz co do bajtow. Jesli masz N<256 to na kazda kolumne tabeli potzrebujesz 1 bajt. Czyli dla 1024 lokacji wyjdzie Ci 5kB. Jesli masz >=256 to na kazda z kolumn kierunku potrzebujesz 2B (moze byc mniej ale nameczysz sie przy programowaniu). Rozumiesz, musisz zapisac ze np. idac na polnoc trafisz do lokacji nr 789, a na to 1bajt nie wystarczy.

Teraz przedmioty. Ponumeruj wszystkie przedmioty w grze od 1 do M. Zrob sobie osobna tablice jednowymiarowa o dlugosci M. W kazdej komorce wpisujesz nr lokacji na mapie w ktorej znajduje sie przedmiot. 0 oznacza ze gracz ma przedmiot przy sobie. -1 oznacza ze przedmiot juz/jeszcze nie istnieje.

Ja tego wszystkiego bron boze nie wymyslilem ;) To bylo streszczenie z kursu kodowania gier przygodowych z Komputera z 88 roku o ile dobrze pamietam. Autora w tej chiwli nie pamietam, ale mam skany tych artykulow. Jak chcesz to podesle. Sprawdzone w praktyce.

6

podales przepis na graf.

wyobraz sobie ze gracz ma mozliwosc ingerencji w 'polaczenia' (w ograniczonym zakresie blokowaniem,otwieraniem drzwi, przekierowanie teleportow itp.), wpuscmy do labiryntu boty i dzieki dosc prostym algorytmom wykaza sie oni 'inteligencja' w dokopaniu graczowi :-)

jesli mozesz podesli mi skany tych artkow z komputera. dzieki

http://atari.pl/hsc/ad.php?i=1.

7

Sposobow jest mnostwo, wszystko zalezy od tego, jak dokladnie wyglada labirynt.

Jezeli sciany sa 'grube' (czyli zapelniajace cale komorki, jak np w DynaBlaster), mape 256x256 mozesz sobie zapisac widzac labirynt po prostu jako bitmape - 8KB. Specjalne pola zapisujesz sobie w dodatkowej tablicy, posortowane po indeksie tego pola (2 bajty) i zawierajace informacje co w tym polu jest jakos skompresowane (pewnie 1-2 bajty). Wiec jak masz 1000 takich pol pojdzie Ci na to z 4KB. Wyszukujesz ofkorz binarnie.

Jezeli sciany sa 'chude' (jak sciany np w wolfenstein), to trzeba inaczej. Jezeli sa to glownie 'zwykle' korytarze, a drzwi/teleporty itp sa stosunkowo rzadkie, mozesz sobie np zakodowac kazda komorke przy uzyciu 4 bitow na sciany, a specjalne pola znowu trzymamy w tablicy dodatkowej poindeksowanej pozycja pola.  Dla 64x64 masz 2KB na mape + jakies 2-4 bajty na kazde pole specjalne.
Podobnie, mozesz sobie policzyc np jakie kombinacje scian z poprzedniego przykladu sa najczestsze, bo moze sie okazac, ze zwykly korytarz pionowy i  poziomy przewazaja (znowu, zaleznie od labiryntu), i na przyklad 4 najbardziej popularne kombinacje zapisujesz na 2 bitach (albo nawet 2 na 1), a wyjatki w specjalnej tablicy. Ale to bedzie lepsze tylko jesli masz duzo powtarzajacych sie komorek (np dlugie waskie korytarze).

Inna metoda to powtarzajace sie fragmenty mapy.

No i jakies po prostu standardowe formy kompresji mozesz wyprobowac na tym wszystkim.

Metoda Nosty'ego bedzie dosc pamieciozerna, bo nawet dla 64x64 potrzebujesz 4 kierunki * 12 bitow -> 6 bajtow / komorke na sam ksztalt labiryntu. To bedzie dobre jesli bedziesz mial mape w wiekszosci pusta.

Ogolnie, przyjrzyj sie mapom, poanalizuj ich wlasciwosci, i wymyslisz cos.

Powodzenia!

: 404. Stopka not found