Kontrollera om en figur får plats i ett fält

C, C++, Pascal, Assembly, Raspberry, Java, Matlab, Python, BASIC, SQL, PHP, etc.
Användarvisningsbild
MadModder
Co Admin
Inlägg: 29902
Blev medlem: 6 september 2003, 13:32:07
Ort: MadLand (Enköping)
Kontakt:

Kontrollera om en figur får plats i ett fält

Inlägg av MadModder »

Har funderat lite till och från på hur man programmatiskt snabbast kollar om olika figurer uppbyggda av rutor, som tetris-block ungefär, får plats på ett fält som består av 10x10 rutor.
Fältet fylls på med figurerna man plockar upp (som slumpas fram) och släpper ner och när det finns en hel rad försvinner den, utan att andra rader flyttar efter. Till sist får inga av de framslumpade figurerna plats och spelet är över.
Det går inte att vrida på figurerna, utan de dyker upp färdigvridna så att säga.
Allra enklast är ju några nestade loopar som kollar om figurens rutor för varje position överlappar fyllda rutor i fältet, men det blir långsamt.
I språket som används finns inga matriser eller multidimensionella variabler. Det finns dock ett litet "arbetsminne" på 256 positioner som är till för att stoppa numeriska data i och plocka fram vid behov.
Det finns inga möjligheter alls att jobba med bits.
Nån som har en klurig idé?

I värsta fall får jag väl helt enkelt sätta en tidsgräns på varje drag och inte kolla alls utan bara vänta på att man inte kan lägga någon figur. :D
Användarvisningsbild
arvidb
Inlägg: 4537
Blev medlem: 8 maj 2004, 12:56:24
Ort: Stockholm

Re: Kontrollera om en figur får plats i ett fält

Inlägg av arvidb »

Intressant. :)

Dåligt med arbetsminne, men finns det plats för tabeller och liknande i ROM/const/text-segment?

Vad är det för bredd på heltalsvariablerna (i bitar)?

Edit: Hur stora kan figurerna vara maximalt?
Användarvisningsbild
MadModder
Co Admin
Inlägg: 29902
Blev medlem: 6 september 2003, 13:32:07
Ort: MadLand (Enköping)
Kontakt:

Re: Kontrollera om en figur får plats i ett fält

Inlägg av MadModder »

Man kan inte lagra text någonstans. Text kan endast skrivas direkt till skärmen med PRINT.

Man kan skriva in statiska datatabeller man läser ur. De indexeras lätt, så det går bra att direkt läsa in data nummer 14 t.ex.
Man kan också ha flera olika datatabeller under varsin etikett, så det går att läsa in t.ex tabell 3, data nummer 14.
Det går dock inte att välja tabell utifrån en variabel, utan det skrivs statiskt i koden "data at L001" t.ex.

Påminner lite om assembler i uppbyggnaden, eller maskinkod kanske.
Exempelvis finns IF X=0 THEN SKIP NEXT
Precis som
CPX #$0
BEQ

Det finns bara heltalsvariabler (a-z), och de är 8 bitar. Det finns dock två "variabler" som heter score1 och score2 som kan innehålla värden från 0 till 999999. :)

Figurerna får plats på 5x5 rutor, men ingen består av fler än 9 rutor totalt.
1x1, 1x2, 1x3, 1x4, 1x5, 2x2, 3x3, 2x2 i L-form, och 3x3 i L-form.

Programminnet är ca 1500 positioner. Lite sådär kryptiskt... Oftast tar en programrad en position, men kan ta fler positioner om det är en komplex instruktion... :roll:
Användarvisningsbild
arvidb
Inlägg: 4537
Blev medlem: 8 maj 2004, 12:56:24
Ort: Stockholm

Re: Kontrollera om en figur får plats i ett fält

Inlägg av arvidb »

Hmm, där föll de ideér jag hade bort. Är det typ GW-BASIC? :)

Blir det verkligen för långsamt att kolla som mest 8x8x9 = 576 rutor (3x3-biten)? Du kan ju dessutom avbryta sökningen på den aktuella positionen så fort du stöter på en redan ifylld ruta. Fast är det flera figurer tillgängliga så måste det förstås göras för varje figur...

Det enda jag kan komma på annars är om du skriver specifika algoritmer för varje figur:

T.ex.: 1x5-figuren: istället för att kolla, vad blir det, 5[rutor]*10*6=300 positioner så kan du kolla varje rad uppifrån och ner efter 5 fria rutor i rad. Det borde bli 10*10=100 positioner att kolla, maximalt. Du kan dessutom hoppa fram 5 rutor varje gång du hittar en ifylld ruta och söka bakåt istället vilket borde kunna kapa tiden ordentligt också, om jag inte tänker fel.

Eller 3x3: Börja söka på position (3,3) och sök "bakåt" (3,2)->(3,1)->(2,3) o.s.v. Så fort du hittar en redan ifylld ruta så kan du flytta biten tre positioner till höger om den ifyllda rutan och fortsätta därifrån.
Användarvisningsbild
MadModder
Co Admin
Inlägg: 29902
Blev medlem: 6 september 2003, 13:32:07
Ort: MadLand (Enköping)
Kontakt:

Re: Kontrollera om en figur får plats i ett fält

Inlägg av MadModder »

Nej inte GW. Där är möjligheterna större. :D
Det är Garry Kitchen’s gamemaker, från 1986 eller nåt sånt. :)

Jo jag funderade också på en algoritm för varje typ av figur, men raderna går fort åt.
1x-figurerna är ju ingen större konst.
Jag får helt enkelt bita i det sura äpplet och se om det får plats.
Skriv svar