Kirjautuminen

Haku

Tehtävät

Keskustelu: Ohjelmointikysymykset: C++: Matopeliin itse madon tekeminen

Sivun loppuun

Lotto [23.03.2012 08:25:08]

#

Terve!

Väännän tässä C++:n ja SDL:n avulla matopeliä. Koodi alkaa olla jokseenkin valmis, mutta itse madon pituutta pitäisi saada kasvatettua kun syödään ruokia. Kuinka Herrat sen toteuttaisivat tämän ominaisuuden seuraavaan matopelin irvikuvan runkoon?

#include <SDL.h>
#include <windows.h>
#include <stdlib.h>
#include <time.h>

// ikkunan koko vakioina
const int LEVEYS = 640;
const int KORKEUS = 480;

// suuntamuuttujia
int lahdeX = 0;
int lahdeY = 0;
int kohdeX = 0;
int kohdeY = 0;
int leveys = 16;
int korkeus = 16;
int suunta = 1;

// luodaan uusia pintoja globaaleiksi
SDL_Surface* naytto = NULL;
SDL_Surface* tausta = NULL;
SDL_Surface* mato = NULL;
SDL_Surface* ruoka = NULL;
SDL_Surface* havio = NULL;
// SDL_Surface* testi = NULL;

void kaytaPintaa(int x, int y, SDL_Surface* lahde, SDL_Surface* kohde);
void piirra(int lahdeX, int lahdeY, int kohdeX, int kohdeY, int leveys, int korkeus, SDL_Surface* lahde, SDL_Surface* kohde);
int satunnaisluku(int suuruus);
void etene(int suunta, bool &osuma, int ruokalaskuri);
void piirraTeksti(char teksti[30], int x, int y, SDL_Surface* pinta);

int main(int argc, char *argv[]) {

    // alustetaan SDL
    SDL_Init(SDL_INIT_EVERYTHING);

    // asetetaan ikkunan koko, värisyvyys yms.
    naytto = SDL_SetVideoMode(LEVEYS, KORKEUS, 32, SDL_SWSURFACE);

    // ladataan BMP-kuvat pinnoille
    tausta = SDL_LoadBMP("tausta.bmp");
    mato = SDL_LoadBMP("mato.bmp");
    ruoka = SDL_LoadBMP("ruoka.bmp");
    havio = SDL_LoadBMP("havio.bmp");
    // testi = SDL_LoadBMP("testi.bmp");

    // asetetaan ikkunalle otsikoksi Matopeli
    SDL_WM_SetCaption("Matopeli", NULL);

    // asetetaan RGB-värille 200, 0, 200 läpinäkyvyys jotta madonruoan reunat lähtee pois.
    SDL_SetColorKey(ruoka, SDL_SRCCOLORKEY, SDL_MapRGB(ruoka->format, 200, 0, 200));
    SDL_SetColorKey(havio, SDL_SRCCOLORKEY, SDL_MapRGB(havio->format, 200, 0, 200));

    // annetaan randomiluvun luojalle siemenluku
    srand(time(0));

    //main-loopin muuttujan alustus.Alustetaan myös osumamuuttuja sekä ruoan muuttujat
    bool kaynnissa = true;
    bool osuma = false;
    bool onkoRuoka = true;
    int ruokaX = satunnaisluku(40) * 16;
    int ruokaY = satunnaisluku(30) * 16;
    int ruokalaskuri = 0;

    // main-looppi itse. koko pelin sydän.
    while(kaynnissa){
        SDL_Event event;

        if(SDL_PollEvent(&event)){
            if(event.type == SDL_QUIT){
                kaynnissa = false;
            }
            if(event.type == SDL_KEYDOWN){

                // valitaan suuntia ja annetaan suunta muuttujalle uusi arvo, mikäli käyttäjä painaa nappulaa.
                if(event.key.keysym.sym == SDLK_RIGHT){
                    suunta = 1;

                }
                if(event.key.keysym.sym == SDLK_LEFT){
                    suunta = 2;

                }
                if(event.key.keysym.sym == SDLK_UP){
                    suunta = 3;

                }
                if(event.key.keysym.sym == SDLK_DOWN){
                    suunta = 4;

                }

                // jos käyttäjä painaa ESC-nappulaa, suljetaan peli
                if(event.key.keysym.sym == SDLK_ESCAPE){
                    kaynnissa = false;
                }
            }
        }

        // vähän viivettä hommaan
        Sleep(100);

        // otetaan tausta käyttöön
        kaytaPintaa(0, 0, tausta, naytto);

        // etene-funktiolla edistetään madon liikkumista
        etene(suunta, osuma, ruokalaskuri);

        // piirretään madonpala näytölle
        piirra(lahdeX, lahdeY, kohdeX, kohdeY, leveys, korkeus, mato, naytto);

        // osutaanko ruokaan
        if(kohdeX >= ruokaX && kohdeX + 16 <= ruokaX + 16){
            if(kohdeY >= ruokaY && kohdeY + 16 <= ruokaY + 16){
                onkoRuoka = false;
                ruokalaskuri++;
            }
        }

        // tarkastetaan onko kentällä ruoka
        if(onkoRuoka != true){
            onkoRuoka = true;
            ruokaX = satunnaisluku(40);
            ruokaY = satunnaisluku(30);

            ruokaX = ruokaX * leveys;
            ruokaY = ruokaY * korkeus;
        }

        // piirretään ruoka
        kaytaPintaa(ruokaX, ruokaY, ruoka, naytto);

        // tarkistetaan onko pelaajan mato osunut reunoihin
        if(osuma){
            kaytaPintaa(0, 0, havio, naytto);
        }

        // päivitetään pinta näyttö
        SDL_Flip(naytto);
    }

    // vapautetaan pintoja
    SDL_FreeSurface(tausta);
    SDL_FreeSurface(mato);
    SDL_FreeSurface(ruoka);
    SDL_FreeSurface(havio);

    SDL_Quit();
    return 0;
}

// piirtofunktioita
void kaytaPintaa(int x, int y, SDL_Surface* lahde, SDL_Surface* kohde){
    SDL_Rect rect;
    rect.x = x;
    rect.y = y;
    SDL_BlitSurface(lahde, NULL, kohde, &rect);
}

void piirra(int lahdeX, int lahdeY, int kohdeX, int kohdeY, int leveys, int korkeus, SDL_Surface* lahde, SDL_Surface* kohde){
    SDL_Rect lahdeR;
    SDL_Rect kohdeR;

    lahdeR.x = lahdeX;
    lahdeR.y = lahdeY;
    lahdeR.w = leveys;
    lahdeR.h = korkeus;

    kohdeR.x = kohdeX;
    kohdeR.y = kohdeY;
    kohdeR.w = leveys;
    kohdeR.h = korkeus;

    SDL_BlitSurface(lahde, &lahdeR, kohde, &kohdeR);
}

int satunnaisluku(int suuruus){
    return rand() % suuruus;
}

void etene(int suunta, bool &osuma, int ruokalaskuri) {
    if(suunta == 1){
        // oikea
        if(kohdeX + 16 >= LEVEYS){
            osuma = true;
        }else{
            kohdeX += 16;
        }
    }

    if(suunta == 2){
        // vasen
        if(kohdeX <= 0){
            osuma = true;
        }else{
            kohdeX -= 16;
        }

    }

    if(suunta == 3){
        // ylös
        if(kohdeY <= 0){
            osuma = true;
        }else{
            kohdeY -= 16;
        }
    }

    if(suunta == 4){
        // alas
        if(kohdeY + 16 >= KORKEUS){
            osuma = true;
        }else{
            kohdeY += 16;
        }
    }
}

jalski [23.03.2012 09:56:40]

#

Matopelin tekemisestä onkin ollut puhetta viime aikoina...

Itse toteuttaisin madon tallentamalla sen (x, y) pareina taulukkoon. Madon häntä olisi pienimmässä taulukon alkiossa (0) ja pää olisi viimeisessä taulukon alkiossa (len mato - 1).

Madon liikutus:

Jos ruokaa on kerätty, niin kasvatat vain taulukon pituutta yhdellä. Tästä uudesta taulukon alkiosta tulee siis madon uusi pää. Jos ruokaa ei ole kerätty, niin siirrät tavaran mato taulukossa pykälän verran vasemmalle siten, että ykkösalkiosta tulee nolla-alkio jne. Madon uuden pään koordinaatit saadaan lisäämällä madon vanhalle päälle (len mato - 2) liikevektori (x, y) ja sijoittamalla tulos madon päälle (len mato - 1).

Macro [23.03.2012 13:41:19]

#

https://www.ohjelmointiputka.net/oppaat/opas.php?tunnus=cpp_mato_1

jalski [26.03.2012 23:16:41]

#

Pistäkääpäs noita valmiita matopelejä jonnekin näkyville, niin voidaan vertailla toteutuksia... :-) Itseltä kohta tulossa toteutukset Modula-2:lla ja PL/I:llä.

Modula-2 toteutuksesta uupuu vielä random funktio, kun ei taida standardikirjastosta löytyä. PL/I toteutus pohjautuu Modula-2 toteutukseen, tosin pienillä PL/I lisämausteilla höystettynä...

Ai niin... molemmat noista käyttävät putkalaisten rakastamaa WinAPI:a. ;-)

Lotto [27.03.2012 08:59:12]

#

jalski kirjoitti:

Jos ruokaa ei ole kerätty, niin siirrät tavaran mato taulukossa pykälän verran vasemmalle siten, että ykkösalkiosta tulee nolla-alkio jne. Madon uuden pään koordinaatit saadaan lisäämällä madon vanhalle päälle (len mato - 2) liikevektori (x, y) ja sijoittamalla tulos madon päälle (len mato - 1).

ihan en nyt ymmärtänyt mitä tuolla tarkoitit, miksi noin pitää tehä.

jalski [27.03.2012 09:59:56]

#

Tuohan saa siis madon yksinkertaisesti liikkumaan ruudun verran eteenpäin, kun siirrät tavaran taulukossa pykälän verran taaksepäin ja sijoitat uuden pään madolle.

User137 [27.03.2012 11:37:07]

#

Itselle ainakin on ollut helpompi käsittää asia niin, että madon pää on taulukon indeksissä 0. Kun mato liikkuu, niin nykyisestä hännänpäästä lähtien siirretään sitä seuraavan madonpalasen sijainti yhden indeksin taaksepäin. Paikka johon madon pää liikkuu, kirjoitetaan indeksiin 0.

Grez [27.03.2012 12:05:09]

#

Itse taas pidän turhana työnä kopioida taulukon dataa joka vuorolla pykälän verran eteenpäin. Sinänsä nykyprossuilla asialla ei ole mitään väliä, mutta toisaalta itseäni ei häiritse sekään että madon pää on indeksissä alku.

jalski [27.03.2012 14:17:40]

#

User137 kirjoitti:

Itselle ainakin on ollut helpompi käsittää asia niin, että madon pää on taulukon indeksissä 0. Kun mato liikkuu, niin nykyisestä hännänpäästä lähtien siirretään sitä seuraavan madonpalasen sijainti yhden indeksin taaksepäin. Paikka johon madon pää liikkuu, kirjoitetaan indeksiin 0.

Omassa tavassani, jos madon pituutta kasvatetaan ruoan syönnin jälkeen niin ei tarvitse siirtää taulukossa tavaraa. Riittää, että lisätään uusi pää madolle.

Makuasioitahan nämä ovat...

Grez kirjoitti:

Itse taas pidän turhana työnä kopioida taulukon dataa joka vuorolla pykälän verran eteenpäin. Sinänsä nykyprossuilla asialla ei ole mitään väliä, mutta toisaalta itseäni ei häiritse sekään että madon pää on indeksissä alku.

Kyllähän toki jotain listaa voi madon tallentamiseen käyttää taulukon sijaan, mutta taulukko on tähän hommaan paljon yksinkertaisempi ja riittävä ratkaisu kun puhutaan kuitenkin vain joistain kymmenistä indekseistä. Lisäksi ei tarvitse pelailla osoittimien kanssa, mikä on aina hyvä asia.

Omassa tapauksessani bonuksena PL/I osaa laskea taulukoilla ja struktuureilla suoraan, joten suuntavektorin lisääminen madon pisteeseen käy aika kivasti.

Grez [27.03.2012 14:46:52]

#

jalski kirjoitti:

Kyllähän toki jotain listaa voi madon tallentamiseen käyttää taulukon sijaan, mutta taulukko on tähän hommaan paljon yksinkertaisempi ja riittävä ratkaisu

En ehdottanutkaan minkään muun kuin taulukon käyttämistä. Mitä yksinkertaisuuteen tulee, niin mielestäni on yksinkertaisempaa muuttaa madon alkukohtaa taulukossa kuin jokaisella alkukohdan muuttumisella kopioida dataa taulukon sisällä.

User137 [28.03.2012 01:18:18]

#

Ajattelinkin matopeliä sellasena jossa mato ei kasva koko aikaa. Usein peli toteutetaan siten että n. sekunnin pari häntä kasvaa vain sen jälkeen kun on kerännyt ruokaa. Tuolla pelisäännöllä ei voi välttyä taulukon siirtelyltä.

Grez [28.03.2012 01:42:47]

#

En näe edelleenkään mitään tarvetta siirtää taulukkoa, vaikka mato kasvaa. Ainoa mikä muuttuu on "madon pituus" muuttujan arvo joka kasvaa sopivasti.

jalski [28.03.2012 08:16:18]

#

User137 kirjoitti:

Ajattelinkin matopeliä sellasena jossa mato ei kasva koko aikaa. Usein peli toteutetaan siten että n. sekunnin pari häntä kasvaa vain sen jälkeen kun on kerännyt ruokaa. Tuolla pelisäännöllä ei voi välttyä taulukon siirtelyltä.

Omassani versiossani ruoan syönnin jälkeen mato kasvaa yhdellä ruudulla. Jos kasvatetaan madon pituutta siten, että häntä on pienimmässä taulukon alkiossa ja pää jossain isommassa indeksissä, ei tarvitse siirrellä tavaraa taulukossa. Tällöin kasvatetaan vain madon pään indeksin tallentavaa muuttujan arvoa ja jätetetään madon häntä paikoilleen.

Jos ei ole syöty ja mato ei kasva niin tällöin toki siirrellään tavaraa...

Grez kirjoitti:

En näe edelleenkään mitään tarvetta siirtää taulukkoa, vaikka mato kasvaa. Ainoa mikä muuttuu on "madon pituus" muuttujan arvo joka kasvaa sopivasti.

Miten meinaat tuon toteuttaa ilman tavaran siirtelyä taulukossa? Madon hännän pitäisi kuitenkin seurata päätä järjestelmällisesti, enkä itse nopeasti keksi tapaa toteuttaa tuota järkevästi ilman siirtelyä.

Grez [28.03.2012 09:17:02]

#

jalski kirjoitti:

Miten meinaat tuon toteuttaa ilman tavaran siirtelyä taulukossa? Madon hännän pitäisi kuitenkin seurata päätä järjestelmällisesti, enkä itse nopeasti keksi tapaa toteuttaa tuota järkevästi ilman siirtelyä.

No nysväsin nyt tällaisen nopean matopelin. Kysymäsi riveillä 85-90

using System;
using System.Drawing;
using System.Windows.Forms;

namespace Mato
{
    public partial class Matopeli : Form
    {
        bool ruokaOn = false;
        const int ALUEWIDTH = 30;
        const int ALUEHEIGHT = 20;
        const int MATOMAX = ALUEWIDTH * ALUEHEIGHT;
        Color[] värit = { Color.White, Color.Black, Color.Red }; //Tyhjä, Mato, Ruoka
        int matopituus = 0;
        int tavoitepituus = 5;
        int pääIx = 0;
        Koordinaatti[] mato = new Koordinaatti[MATOMAX];
        Tila[,] lauta = new Tila[ALUEWIDTH, ALUEHEIGHT];
        Keys suunta = Keys.Up;
        Random random = new Random();
        private System.Windows.Forms.Timer matoTimer;

        public Matopeli()
        {
            InitializeComponent();
            mato[pääIx].X = ALUEWIDTH / 2;
            mato[pääIx].Y = ALUEHEIGHT / 2;
            matoTimer = new System.Windows.Forms.Timer(this.components);
            this.matoTimer.Tick += new System.EventHandler(this.matoTimer_Tick);
            this.KeyDown += new System.Windows.Forms.KeyEventHandler(this.Matopeli_KeyDown);
            matoTimer.Enabled = true;
            värit[0] = this.BackColor;
        }

        private void lisääRuoka()
        {
            Koordinaatti ruoka;
            do
            {
                ruoka.X = random.Next(ALUEWIDTH - 1);
                ruoka.Y = random.Next(ALUEHEIGHT - 1);
            } while (lauta[ruoka.X, ruoka.Y] != Tila.Tyhjä);
            setTila(ruoka, Tila.Ruoka);
            ruokaOn = true;
        }

        private void Matopeli_KeyDown(object sender, KeyEventArgs e)
        {
            switch (e.KeyCode)
            {
                case Keys.Left: //37
                case Keys.Up:  //38
                case Keys.Right: //39
                case Keys.Down:  //40
                    suunta = e.KeyCode;
                    e.Handled = true;
                    break;
            }
        }

        private void matoTimer_Tick(object sender, EventArgs e)
        {
            var pää = mato[pääIx];
            int suuntaInt = (int)suunta;

            if ((suuntaInt & 1) == 1) { pää.X = (pää.X + suuntaInt - 38 + ALUEWIDTH) % ALUEWIDTH; }
            else { pää.Y = (pää.Y + suuntaInt - 39 + ALUEHEIGHT) % ALUEHEIGHT; }

            switch (lauta[pää.X, pää.Y])
            {
                case Tila.Mato:
                    matoTimer.Enabled = false;
                    MessageBox.Show("Game Over");
                    this.Close();
                    return;
                case Tila.Ruoka:
                    tavoitepituus += 5;
                    ruokaOn = false;
                    break;
            }
            pääIx = ((pääIx + 1) % MATOMAX);
            mato[pääIx] = pää;
            setTila(pää, Tila.Mato);
            if (matopituus < tavoitepituus) { matopituus++; }
            else
            {
                var häntä = mato[(pääIx + MATOMAX - matopituus) % MATOMAX];
                setTila(häntä, Tila.Tyhjä);
            }
            if (!ruokaOn) { lisääRuoka(); }
        }

        private void setTila(Koordinaatti paikka, Tila tila)
        {
            lauta[paikka.X, paikka.Y] = tila;
            this.CreateGraphics().FillRectangle(new SolidBrush(värit[(int)tila]), paikka.X * 10, paikka.Y * 10, 10, 10);
        }

    }
    struct Koordinaatti
    {
        public int X;
        public int Y;
    }
    enum Tila : int
    {
        Tyhjä = 0,
        Mato = 1,
        Ruoka = 2
    }
}

jalski [28.03.2012 10:04:41]

#

Grez kirjoitti:

Kysymäsi riveillä 78-80

Tosiaan modulon avullahan tuon voisi toteuttaa. :-) En tuota tullutkaan ajatelleeksi vaikka wrappaan tuon avulla madon tarvittaessa kentän toiselle puolelle (mato ei kuole kentän reunoista).

Käytän tällä hetkellä karttaa pelkästään törmäystarkastukseen ja piirrän koko kartan sijaan pelkästään peliobjektit (mato, ruoka, törmäys). Tällöin mielestäni tarvittaessa taulukossa tavaran siirtely on suoraviivaisempaa.

Täytyisi muuten joskus itse paneutua tuohon .NET alustaan paremmin.

User137 [28.03.2012 13:25:29]

#

Heh, jos oikein ymmärsin niin tuota voi olla hauska debugata. Mato ikäänkuin liikkuu siellä taulukossa, tullen toisesta päästä alkuun wrappaamalla. Tavallinen tilanne on siis että madon paikkaindeksit on jossain keskellä taulukkoa.

Ja siis olennainen kohta oli tuossa että koko ajan käytetään taulukon maksimikapasiteettia. Mietin tuota taulukon ympärikäymistä jo aiemmin mutta madon koon kasvaessa ei toimis jos käyttää indeksi-alueena vain madon pituuden verran soluja.

jlaire [28.03.2012 13:47:55]

#

Taulukon käyttäminen tuolla tavalla on ihan yleinen ja hyvä tapa toteuttaa kaksipäinen jono (deque). Tietorakenteista tuon toteuttaminen ja debuggaaminen on kyllä sieltä helpommasta päästä, mutta monille kielille löytyy valmiita kirjastojakin.

http://en.wikipedia.org/wiki/Double-ended_queue
http://en.wikipedia.org/wiki/Circular_buffer

Edit: Jos jonon maksimipituutta ei tiedetä alussa, voi rajan tullessa vastaan luoda uuden taulukon.

Grez [28.03.2012 14:21:34]

#

Debuggaaminen, mitä se on? :D

Tosiaan ei tuon debuggaaminen kovin vaikeaa ole.

Tällaisessa pikku projektissa ei edes pahemmin tarvitse debugata. Tuonkin kirjoitin suoraan noin puolessa tunnissa ja ensimmäisellä ajokerralla ainoa vika oli, että ylös ja alas -napit toimi väärin päin.. Sitten vielä tein mielessä pienen analyysin potentiaalisista ongelmista, ja kun ensimmäisessä versiossa ohjelma pyyhki häntää silloinkin kun mato piteni, niin n. 1/600 todennäköisyydellä ruoka olisi tullut juuri siihen hännän kohdalle ja pyyhitty pois. Eli korjasin senkin ennenkuin ongelma edes tuli vastaan käytännössä.

Mielestäni ei ole mitään järkeä tehdä taulukosta vain madon pituista ja kasvattaa taulukkoa aina kun madon pituus kasvaa. Kuitenkin madon maksimipituus on pelialueen koko ja mahdollinen lyhyemmän taulukon käytössä säästyvä muisti ei ole riittävä hyöty suhteessa säädön lisääntymiseen.

jalski [28.03.2012 15:01:37]

#

Grez kirjoitti:

Mielestäni ei ole mitään järkeä tehdä taulukosta vain madon pituista ja kasvattaa taulukkoa aina kun madon pituus kasvaa. Kuitenkin madon maksimipituus on pelialueen koko ja mahdollinen lyhyemmän taulukon käytössä säästyvä muisti ei ole riittävä hyöty suhteessa säädön lisääntymiseen.

Tuon säädön määrähän riippuu hyvin paljon ohjelmointikielestä ja alustasta.

esim. Infernolle Limbolla riittää:

newsnake := array[len snake + 1] of Point;
newsnake[0:] = snake;
snake = newsnake;

User137 [28.03.2012 15:52:19]

#

Ehkä tässä säädöllä ei tarkoitettu koodin määrää. Uuden taulukon luominen ja arvojen kopioiminen varmasti aiheuttaa prosessina paljon säätöä.

Metabolix [28.03.2012 16:05:08]

#

Jos peli sattuu olemaan ruutupohjainen, yksi ratkaisu on säilyttää jokaisessa ruudussa lukua, joka kertoo, milloin madon pää on käynyt siinä. Kun mato liikkuu, laitetaan uuteen ruutuun aina seuraava luku. Kun mato syö, kasvatetaan madon pituutta yhdellä. Menetelmän etu on, että muistia tarvitaan vakiomäärä eikä madon liikkuessa tarvitse koskaan tutkia tai muuttaa kuin yhtä ruutua.

Grez [28.03.2012 16:11:52]

#

Kuvittelenko vaan että sen häntäruudun hakemisen teko on sitten O(n^2) -operaatio pelialueen sivun n kasvaessa. Eli säästetään vähän muistia ja kulutetaan vähän prosessoriaikaa. Plus koodiakin taitaa kulua vähän enemmän.

Metabolix [28.03.2012 16:28:57]

#

Koodia ei kulu lainkaan enempää kuin muillakaan esitetyillä tavoilla – ehkä jopa vähemmän –, ja aikavaatimus ei suinkaan ole tuollainen. Madon pään sijainti kannattaa pitää erikseen muistissa, jolloin liike ja törmäystarkistus tapahtuvat ajassa O(1), kuten jo äsken sanoin. Häntäruutua ei nähdäkseni tarvitse missään tilanteessa hakea, vai tarvitseeko sinusta? Piirto tapahtuu edelleenkin yhdellä silmukalla (O(n) madon pituuden mukaan), jossa edetään päästä askel kerrallaan häntää kohti madon pituuden verran.

Grez [28.03.2012 16:53:02]

#

Joo, no ehkä sitten haluat koodata mallin matopelistä, joka käyttää tuota tapaa, niin sitten nähdään millainen koodi siitä tulee. Voi toki olla että en ihan ymmärtänyt logiikkaa, mutta mielestäni jo tuo madon hännänetsimislooppi on turhan monimutkainen suhteessa hyötyihin. Sanoit, että häntäruutua ei tarvitse missään tilanteessa hakea, mutta piirto tapahtuisi silmukalla jossa edettäisiin kohti häntää (=etsittäisiin häntä).

User137 [28.03.2012 18:35:36]

#

Eikös tuo kuitenkin aiheuta piirtovaiheeseen yhden laskutoimituksen joka vertaa madon aikaa nykyhetkeen (ja päättää piirretäänkö siihen tyhjää vai matoa). Vieläpä koko pelialueen ruudut pitäisi piirtää yksitellen.

Metabolix [28.03.2012 19:47:37]

#

User137 kirjoitti:

Vieläpä koko pelialueen ruudut pitäisi piirtää yksitellen.

Ei, koska luvuista nähdään suoraan, mikä neljästä ympäröivästä ruudusta on seuraava pala.

Grez kirjoitti:

Sanoit, että häntäruutua ei tarvitse missään tilanteessa hakea, mutta piirto tapahtuisi silmukalla jossa edettäisiin kohti häntää (=etsittäisiin häntä).

Tuolla logiikalla voi väittää yhtä hyvin, että myös taulukosta (tai listasta) pitää "etsiä häntä" piirtovaiheessa. Oikeasti ei koskaan tarvitse etsiä nimenomaan häntää, vaan aina etsitään vain seuraava pala (vakioajassa), kunnes on piirretty tarpeeksi monta palaa.

Grez kirjoitti:

Eli säästetään vähän muistia ja kulutetaan vähän prosessoriaikaa.

En sanonut, että muistia säästettäisiin. Sanoin, ettei sitä tarvitse varata lisää. Kyse on siis prosessoriajan säästämisestä, koska muistin varaaminen vie myös aikaa.

Grez kirjoitti:

Joo, no ehkä sitten haluat koodata mallin matopelistä, joka käyttää tuota tapaa, niin sitten nähdään millainen koodi siitä tulee.

Koodasinpa. Vähän ruma pikatoteutus tuli, mutta ymmärtänet tästä idean. Voit mielellään kokeilla, minkä verran koodi lyhenee toisenlaisella lähestymistavalla.

Jos piirtosilmukkani if-lauseet hirvittävät, voi uhrata lisää tilaa ja tallentaa jokaiseen ruutuun erikseen edellisen ruudun koordinaatit, jolloin saadaan madosta myös linkitetty lista.

#include <stdexcept>
#include <vector>
#include <limits>
#include <cstdlib>
#include <SDL.h>

struct piste {
	int x, y;
	piste(int x_ = 0, int y_ = 0):
		x(x_),
		y(y_) {
	}
	piste operator + (const piste& t) const {
		return piste(x + t.x, y + t.y);
	}
};

class matopeli {
public:
	const piste koko;
	enum sisalto { MATO = 1, TYHJA = 0, SEINA = -1, OMENA = -2 };

private:
	std::vector<int> ruudut;
	int pituus;
	piste paa, suunta, omena;
	int paan_arvo;

protected:
	matopeli(piste koko_):
		koko(koko_),
		ruudut(koko.x * koko.y, 0),
		pituus(3),
		paa(koko.x / 2 - pituus, koko.y / 2),
		suunta(1, 0),
		paan_arvo(pituus) {
		if (koko.x < 4 || koko.y < 4 || paa.x < 0) {
			throw std::logic_error("Liian pieni pelilauta!");
		}
		for (int i = 0; i < pituus; ++i) {
			liiku();
		}
	}

	int hae(piste p) const {
		if (p.x < 0 || koko.x <= p.x || p.y < 0 || koko.y <= p.y) {
			return SEINA;
		}
		int ruutu = ruudut[p.x + koko.x * p.y];
		// Erikoistapaukset (omena, seinä).
		if (ruutu <= 0) {
			return ruutu;
		}
		// Madon aiemmat paikat.
		if (ruutu < paan_arvo - pituus + 1) {
			return TYHJA;
		}
		// Palautetaan madosta luku niin, että pää = pituus ja häntä = 1.
		return pituus - (paan_arvo - ruutu);
	}

	void aseta(piste p, sisalto s) {
		ruudut[p.x + koko.x * p.y] = (s == MATO ? ++paan_arvo : s);
	}

	bool liiku() {
		int ruutu = hae(paa + suunta);
		if (ruutu == SEINA || ruutu > 1) {
			return false;
		}
		if (ruutu == OMENA) {
			++pituus;
		}
		paa = paa + suunta;
		aseta(paa, MATO);

		// Jos omenaa ei ole, yritetään tehdä uusi.
		if (hae(omena) != OMENA) {
			omena.x = random(koko.x);
			omena.y = random(koko.y);
			if (hae(omena) == TYHJA) {
				aseta(omena, OMENA);
			}
		}
		return true;
	}

	void piirra() const {
		if (hae(omena) == OMENA) {
			piirra_omena(omena);
		}

		piste p = paa;
		piirra_matoa(p, 1);
		for (int i = pituus; --i;) {
			if (hae(piste(p.x + 1, p.y)) == i) ++p.x; else
			if (hae(piste(p.x - 1, p.y)) == i) --p.x; else
			if (hae(piste(p.x, p.y + 1)) == i) ++p.y; else
			if (hae(piste(p.x, p.y - 1)) == i) --p.y;
			piirra_matoa(p, (i - 1.0) / (pituus - 1));
		}
	}

	void suuntaa(int dx, int dy) {
		if (dx < 0) suunta = piste(-1, 0); else
		if (dx > 0) suunta = piste(+1, 0); else
		if (dy < 0) suunta = piste(0, -1); else
		if (dy > 0) suunta = piste(0, +1);
	}

	static int random(int maksimi) {
		return std::rand() % maksimi;
	}

	virtual void piirra_matoa(piste const& p, float kohta) const = 0;
	virtual void piirra_omena(piste const& p) const = 0;
};

struct SDL_matopeli: protected matopeli {
	SDL_Surface* ruutu;
	bool quit;
public:
	SDL_matopeli():
		matopeli(piste(32, 24)),
		quit(false) {
		SDL_Init(SDL_INIT_VIDEO);
		ruutu = SDL_SetVideoMode(640, 480, 32, SDL_DOUBLEBUF);
	}
	~SDL_matopeli() {
		SDL_Quit();
	}

	void aja() {
		peli();
		loppu();
	}

protected:
	void peli() {
		Uint32 t = SDL_GetTicks();
		const Uint32 frame = 200;
		while (tapahtumat(), !quit) {
			Uint8* napit = SDL_GetKeyState(0);
			suuntaa(
				(int) napit[SDLK_RIGHT] - napit[SDLK_LEFT],
				(int) napit[SDLK_DOWN] - napit[SDLK_UP]
			);

			Uint32 dt = SDL_GetTicks() - t;
			if (dt < frame) {
				SDL_Delay(10);
				continue;
			}
			while (dt >= frame) {
				if (!liiku()) {
					return;
				}
				t += frame;
				dt -= frame;
			}
			piirra(0);
		}
	}

	void loppu() {
		const Uint32 t0 = SDL_GetTicks();
		Uint32 t = 0;
		while (tapahtumat(), !quit && (t = SDL_GetTicks() - t0) < 2500) {
			piirra(SDL_MapRGB(ruutu->format, t < 700 ? 0xcc * t / 700 : 0xcc, 0, 0));
			SDL_Delay(10);
		}
	}

	void tapahtumat() {
		for (SDL_Event e; SDL_PollEvent(&e);) {
			if (e.type == SDL_QUIT || (e.type == SDL_KEYDOWN && e.key.keysym.sym == SDLK_ESCAPE)) {
				quit = true;
			}
		}
	}

	void piirra(Uint32 tausta) const {
		SDL_FillRect(ruutu, 0, tausta);
		matopeli::piirra();
		SDL_Flip(ruutu);
	}

	void piirra_matoa(piste const& p, float kohta) const {
		SDL_Rect alue = {p.x * 20, p.y * 20, 19, 19};
		SDL_FillRect(ruutu, &alue, SDL_MapRGB(ruutu->format, 0, 0x33 + kohta * 0x66, 0x33 + (1 - kohta) * 0xcc));
	}

	void piirra_omena(piste const& p) const {
		SDL_Rect alue = {p.x * 20, p.y * 20, 19, 19};
		SDL_FillRect(ruutu, &alue, SDL_MapRGB(ruutu->format, 0x66, 0xff, 0));
	}
};

int main(int argc, char** argv) {
	SDL_matopeli peli;
	peli.aja();
}

Grez [28.03.2012 20:06:10]

#

Metabolix kirjoitti:

Tuolla logiikalla voi väittää yhtä hyvin, että myös taulukosta (tai listasta) pitää "etsiä häntä" piirtovaiheessa. Oikeasti ei koskaan tarvitse etsiä nimenomaan häntää, vaan aina etsitään vain seuraava pala (vakioajassa), kunnes on piirretty tarpeeksi monta palaa.

Yleensä olen lähtenyt siitä, että matoa ei tarvitse piirtää uudestaan joka kerta vaan riittää kun poistaa sen vanhan hännän. Toki on totta, että jos jostain syystä se mato pitää piirtää kokonaan uudestaan, niin häntää ei tarvitse "erikseen" etsiä.

Metabolix kirjoitti:

Eli säästetään vähän muistia ja kulutetaan vähän prosessoriaikaa.

En kyllä näe miten tuo toteutuksesi kuluttaa ainakaan vähemmän prosessoriaikaa kuin minun toteutukseni, jossa siis piirretään joka kierroksella vain kaksi palikkaa (ja mahdollisesti kolmas jos mato syö ruoan) ja nämä haetaan suoraan taulukosta, jonka sisältöä ei myöskään missään välissä siirrellä tai kopioida.

Metabolix kirjoitti:

En sanonut, että muistia säästettäisiin. Sanoin, ettei sitä tarvitse varata lisää. Kyse on siis prosessoriajan säästämisestä, koska muistin varaaminen vie myös aikaa.

Kommentoin, että omaan toteutukseeni verrattuna se säästää vain muistia. Eikä se mielestäni mitään muuta säästäkään. Omassani siis ainoastaan alustuksessa varataan kaksi laudan kokoista muistialuetta, kirjoitetaan 5 muuttujaa per kierros ja piirretään 2 lohkoa per kierros (syöntikierroksilla 6 ja 3)

Katso nyt ihmeessä tuon minun matopelini toimintalooppi (matoTimer_Tick) ja paljonko siinä prossu joutuu tekemään verrattuna tuohon omaan looppiisi.

Metabolix kirjoitti:

Koodasinpa. Vähän ruma pikatoteutus tuli, mutta ymmärtänet tästä idean. Voit mielellään kokeilla, minkä verran koodi lyhenee toisenlaisella lähestymistavalla.

No johan mulla oli toteutus toisenlaisesta lähestymistavasta. Sun koodi 202 riviä ja mun koodi 103 riviä. Eli noin tuplaksi kasvoi toteutuksellasi, jossa epäilit koodia kuluvan "ehkä jopa vähemmän".

Metabolix kirjoitti:

Jos piirtosilmukkani if-lauseet hirvittävät, voi uhrata lisää tilaa ja tallentaa jokaiseen ruutuun erikseen edellisen ruudun koordinaatit, jolloin saadaan madosta myös linkitetty lista.

Ja tämä linkitetty lista on esim. taulukkoon toteutettua dequeta järkevämpi, koska?

Pekka Karjalainen [28.03.2012 20:37:28]

#

Grez kirjoitti:

No johan mulla oli toteutus toisenlaisesta lähestymistavasta. Sun koodi 202 riviä ja mun koodi 103 riviä. Eli noin tuplaksi kasvoi toteutuksellasi, jossa epäilit koodia kuluvan "ehkä jopa vähemmän".

Nämä 103 riviä eivät kuitenkaan ole kokonainen ohjelma. Eihän sitä koodia voi edes kääntää annetussa muodossa, koska mm. matoTimerin määritelmä puuttuu kokonaan.

Muutenkin rivien määrän vertailu on vähän hassua, koska kyseessä ovat lyhyet ohjelmat, joissa ohjelmointityylien ja käytettyjen kielten ominaisuudet vaikuttavat pituuteen mahdollisesti aika paljonkin.

Lisäksi iso-O-analyysit voisi jättää vähemmälle tilanteessa, jossa n:n kasvaminen jo tuhanteen olisi naurettavaa. Tai en minä tiedä. Onko sinusta kokoa 1000x1000 oleva matopelin alue naurettava vai ei? Mahtuuhan se tarpeeksi isolle näytölle, jos madon palaset esittää yksittäisillä pikseleillä!

Toivon tässä siis vain järkevämpää vertailua ja oleellisten asioiden analyysiä. Jatkakaa toki :)

Grez [28.03.2012 20:57:44]

#

Oleellisten asioiden analysointia puolin ja toisin...

Se autogeneroitu koodi jäi tosiaan puuttumaan, lisäsin nyt ne ja koodi kasvoi muutamalla rivillä. Toki jos pistän kaikki projektitiedostot sun muut kääntämisen kannalta tarvittavat tiedostot mukaan niin rivimäärä kasvaa varmaan yli 200:n. Ajattelin lähinnä kuitenkin toiminnallista koodia.

Tiedostin kyllä, että kielet vaikuttaa jne, mutta jos perus piiretlyrutiinit ja muu kehystauhka jätetään pois ja ihan tuohon asiaan, mistä keskustelu lähti, käytettyjä rivejä katsot niin ero on vielä suurempi ja käyttäen ominaisuuksia jotka molemmissa kielissä on samanlaiset. En tosiaan käyttänyt mitään C#:n / .Net Frameworkin erikoisempia tietorakenteita yms. vaan ihan perus arraytä, joten siksi en jaksanut edes kommentoida käytetystä kielestä.

Summa summarum: Jos kirjoittaisin tuon saman toteutuksen tuohon Metabolixin runkoon, niin koodi lyhenisi. Jos Metabolixin toteutuksen laittaisi minun runkoon, niin koodi pitenisi.

Ja mitä noihin vertailuihin tulee, niin ihan yksinkertainen vertailu mielestäni osoittaa tuon "matokirjanpidon" toteutukseni monta kertaa tehokkaammaksi CPU-kulutuksen kannalta. Eli seison edelleen näkemykseni, josta koko homma lähti, takana: Metabolixin ratkaisu säästää vain mitättömän määrän muistia CPU-kulutuksen ja koodin määrän kustannuksella.

User137 [28.03.2012 21:21:14]

#

Tämä versio lienee perinteistä mallia. Toteutettu Lazaruksella:

unit matounit;

{$mode objfpc}{$H+}

interface

uses Classes, SysUtils, Forms, Controls, Graphics, Dialogs, ExtCtrls, LCLType;

const Koko = 16;
      Leveys = 640 div Koko;
      Korkeus = 480 div Koko;

type
  TPoint = record
    x, y: smallint;
  end;

  { TForm1 }

  TForm1 = class(TForm)
    Image1: TImage;
    Timer1: TTimer;
    procedure FormCreate(Sender: TObject);
    procedure FormKeyDown(Sender: TObject; var Key: Word; Shift: TShiftState);
    procedure Timer1Timer(Sender: TObject);
  private
    suunta, ruoka: TPoint;
    ruutu: array[0..Leveys-1, 0..Korkeus-1] of boolean;
    mato: array[0..Leveys*Korkeus-1] of TPoint;
    pituus: integer;
  public
    procedure ArvoRuoka;
    procedure PiirraPiste(x, y: integer; vari: TColor);
  end;

var Form1: TForm1;

implementation

{$R *.lfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize;
  ClientWidth:=640;
  ClientHeight:=480;
  Image1.Align:=alClient;
  Image1.Picture.Bitmap.Width:=ClientWidth;
  Image1.Picture.Bitmap.Height:=ClientHeight;
  with Image1.Picture.Bitmap.Canvas do begin
    Pen.Color:=clBlack;
    Brush.Style:=bsSolid;
    Brush.Color:=clBlack;
    Rectangle(ClientRect);
    Pen.Style:=psClear;
  end;
  pituus:=2;
  mato[0].x:=Leveys div 2;
  mato[0].y:=Korkeus div 2;
  mato[1]:=mato[0];
  suunta.x:=1;
  PiirraPiste(mato[0].x, mato[0].y, clSilver);
  ruutu[mato[0].x, mato[0].y]:=true;
  ArvoRuoka;
end;

procedure TForm1.FormKeyDown(Sender: TObject; var Key: Word; Shift: TShiftState);
begin
  if (key=VK_UP) and (suunta.y=0) then begin
    suunta.x:=0; suunta.y:=-1;
  end else if (key=VK_DOWN) and (suunta.y=0) then begin
    suunta.x:=0; suunta.y:=1;
  end else if (key=VK_LEFT) and (suunta.x=0) then begin
    suunta.x:=-1; suunta.y:=0;
  end else if (key=VK_RIGHT) and (suunta.x=0) then begin
    suunta.x:=1; suunta.y:=0;
  end;
end;

procedure TForm1.Timer1Timer(Sender: TObject);
var i: integer;
begin
  if (mato[pituus-1].x<>mato[pituus-2].x) or (mato[pituus-1].y<>mato[pituus-2].y) then begin
    ruutu[mato[pituus-1].x, mato[pituus-1].y]:=false;
    PiirraPiste(mato[pituus-1].x, mato[pituus-1].y, clBlack);
  end;
  for i:=pituus-1 downto 1 do
    mato[i]:=mato[i-1];
  mato[0].x+=suunta.x;
  mato[0].y+=suunta.y;
  if mato[0].x<0 then mato[0].x:=Leveys-1
  else if mato[0].x>=Leveys then mato[0].x:=0;
  if mato[0].y<0 then mato[0].y:=Korkeus-1
  else if mato[0].y>=Korkeus then mato[0].y:=0;
  if ruutu[mato[0].x, mato[0].y] then begin
    timer1.Enabled:=false;
    showmessage('Törmäys!');
  end else
    ruutu[mato[0].x, mato[0].y]:=true;
  PiirraPiste(mato[0].x, mato[0].y, clSilver);
  if (mato[0].x=ruoka.x) and (mato[0].y=ruoka.y) then begin
    for i:=1 to 5 do begin
      mato[pituus]:=mato[pituus-1];
      pituus+=1;
    end;
    ArvoRuoka;
  end;
end;

procedure TForm1.ArvoRuoka;
begin
  repeat
    ruoka.x:=random(Leveys);
    ruoka.y:=random(Korkeus);
  until not ruutu[ruoka.x, ruoka.y];
  PiirraPiste(ruoka.x, ruoka.y, clRed);
end;

procedure TForm1.PiirraPiste(x, y: integer; vari: TColor);
begin
  with Image1.Picture.Bitmap.Canvas do begin
    Brush.Color:=vari;
    Rectangle(x*Koko, y*Koko, (x+1)*Koko, (y+1)*Koko);
  end;
end;

end.

Metabolix [28.03.2012 21:21:55]

#

Grez kirjoitti:

Metabolix kirjoitti:

En sanonut, että muistia säästettäisiin. Sanoin, ettei sitä tarvitse varata lisää. Kyse on siis prosessoriajan säästämisestä, koska muistin varaaminen vie myös aikaa.

Verrattuna omaan toteutukseeni, jossa ainoastaan alustuksessa varataan kaksi laudan kokoista muistialuetta.

Keskustelussa on esitetty monta muutakin toteutusta. Esimerkiksi jalski näytti juuri, miten näppärästi varataan aina koko mato uudestaan.

Grez kirjoitti:

No johan mulla oli toteutus. Sun koodi 202 riviä ja mun koodi 103 riviä.

No niinpä olikin. Pituusero ei kylläkään liity tähän käsillä olevaan kysymykseen. Itse sentään tein samalla kielellä ja kirjastolla kuin kysyjä, annoin aivan kokonaisen ohjelman ja kirjoitin vieläpä logiikan ja käyttöliittymän erilleen. Lisäksi ohjelmissa on aika erilaiset ominaisuudet ja laajennusmahdollisuudet.

Grez kirjoitti:

Yleensä olen lähtenyt siitä, että matoa ei tarvitse piirtää uudestaan joka kerta vaan riittää kun poistaa sen hännän.

Yleensä olen lähtenyt peleissä siitä, että kaikki pitää piirtää uudestaan. Joissain ympäristöissä ikkunan peittäminen pyyhkii sisällön, joissain taas kaksoispuskurointi pakottaa pyyhkimään kaiken. Lisäksi peleissä usein toivotaan efektejä, jotka vaativat joka tapauksessa jatkuvaa päivittämistä. Tuossakin koodissani madon eri kohdat piirretään eri väreillä, joten koko mato täytyy väistämättä piirtää uudestaan.

Grez kirjoitti:

Ja tämä linkitetty lista on esim. taulukkoon toteutettua dequeta järkevämpi, koska?

Järkevyys riippuu tietenkin tarpeista. Linkitetty lista on yhtä tehokas ja siitä saa lisäksi vakioajassa haettua tietyssä ruudussa sijaitsevan osan madosta. Muistiin jää myös madon kulkuhistoria siltä osin, kuin sitä ei peitetä, joten laudalle voisi piirtää tämän avulla jonkin hauskan efektin. En nyt valitettavasti tehnyt niin hienoa peliä, että näistä ominaisuuksista olisi hyötyä.

Grez kirjoitti:

Ja mitä noihin vertailuihin tulee, niin ihan yksinkertainen vertailu mielestäni osoittaa tuon "matokirjanpidon" toteutukseni monta kertaa tehokkaammaksi.

Minkälainen yksinkertainen vertailu? Sekö, jossa tulkitaan madon piirto uudestaan jonkinlaiseksi virheeksi (vaikka se on välttämätöntä värityksen takia)? Jos nyt oikeasti noin ääliömäiselle linjalle lähdetään, niin vielä paljon tehokkaampaa on tehdä peli, jossa mato on yhden ruudun kokoinen eikä liiku ollenkaan. Koodiakin säästyy. Siinä on sitten vain vähemmän ominaisuuksia.

Grez kirjoitti:

Eli seison edelleen näkemykseni, josta koko homma lähti, takana: Ratkaisusi säästää vain mitättömän määrän muistia CPU-kulutuksen ja koodin määrän kustannuksella.

Nyt olet tulkinnut homman lähdön jotenkin omalla tavallasi. Homma lähti siitä, että esitin yhden vaihtoehdon muiden joukossa ja aloit juurikaan perustelematta väittää sitä hitaaksi ja huonoksi. En myöskään ole väittänyt, että muistia säästettäisiin. Yritin oikaista tätä harhaluuloasi jo edellisessä viestissä.

Mutta seison silti itsekin näkemykseni takana: jos toteutetaan tuollainen peli, kuin itse juuri toteutin, koodi ei lyhene taulukkoratkaisullasi käytännössä yhtään eikä myöskään CPU:n käytössä tai iso-O-analyyseissa ole mitään eroa.

Grez [28.03.2012 21:31:10]

#

Metabolix kirjoitti:

Minkälainen yksinkertainen vertailu? Sekö, jossa tulkitaan madon piirto uudestaan jonkinlaiseksi virheeksi (vaikka se on välttämätöntä värityksen takia)?

No ihan se, että
1) luetaanko madon koordinaatit järjestyksessä taulukosta
vai
2) tutkitaanko viimeksi katsotun pisteen neljä vierekkäistä pistettä ja verrataan missä oleva numero on yhden pienempi.

Kummallakin tavalla toteutettuna saa kyllä piirrettyä madon kokonaan uudestaan.

Ensimmäisellä tavalla toteutettuna on lisäksi mahdollista jättää välipalat piirtämättä, mutta en tietenkään "yksinkertaisessa vertailussani" enää huomioinut tätä mahdollisuutta.

Tuon mahdollisuuden jättää välipätkä piirtämättä toin esille vain kommenttina tähän: ...

Metaboix kirjoitti:

Oikeasti ei koskaan tarvitse etsiä nimenomaan häntää

... Eli alkuperäinen kommenttini hännän etsimistarpeeseen koski oman esimerkkini mukaista tilannetta, jossa piirretään vain pää ja pyyhitään häntä. Ja väitit ettei esimerkkini mukaista tilannetta koskaan ole.

Metaboix kirjoitti:

Nyt olet tulkinnut homman lähdön jotenkin omalla tavallasi. Homma lähti siitä, että esitin yhden vaihtoehdon muiden joukossa ja aloit juurikaan perustelematta väittää sitä hitaaksi ja huonoksi.

No joo, ehkä tässä on jotain väärinymmärryksiä. Tarkoitukseni ei ollut väittää että tekniikkasi olisi monimutkaisempi tai hitaampi kuin jokainen tässä ketjussa esitetty tekniikka. Kommentoin lähinnä sitä verraten itse esittämääni tekniikkaan.

Väitin, että se on hitaampi ja monimutkaisempi kuin esittämäni tapa. Toki esim. "hitauden" osalta tiedän ettei ole käytännön merkitystä meneekö hommassa 1 vai 3 nanosekuntia.

Metaboix kirjoitti:

En myöskään ole väittänyt, että muistia säästettäisiin. Yritin oikaista tätä harhaluuloasi jo edellisessä viestissä.

En väittänytkään että olisit niin väittänyt. Totesin vaan että en näe esittämässäsi ratkaisussa dequeen verrattuna muuta hyötyä, kuin muistin säästön.

Metabolix [28.03.2012 21:49:19]

#

Grez kirjoitti:

No joo, ehkä tässä on jotain väärinymmärryksiä. Tarkoitukseni ei ollut väittää että tekniikkasi olisi monimutkaisempi tai hitaampi kuin jokainen tässä ketjussa esitetty tekniikka. Kommentoin lähinnä sitä verraten itse esittämääni tekniikkaan.

Ahaa, User137:n väliin heittämä O(n^2) varmaan väritti tulkintaani, kun alunperin ajattelin esittää koko idean lähinnä jalskin ja User137:n kopiointiratkaisujen vaihtoehdoksi.

Grez kirjoitti:

Metaboix kirjoitti:

Oikeasti ei koskaan tarvitse etsiä nimenomaan häntää

...eli alkuperäinen kommenttini hännän etsimistarpeeseen koski oman esimerkkini mukaista tilannetta, jossa piirretään vain pää ja pyyhitään häntä.

Joo, en aluksi huomannut tätä olennaista näkemyseroa, kun en lukenut koodiasi.

Grez [28.03.2012 21:54:11]

#

No myönnän kyllä että minä(kin) heitin sen O(n^2), joskin täsmensin että n:llä tarkoitin pelialueen sivun pituutta. Se oli vähän kieli poskessa heitetty. Ja tietenkin madon ollessa lyhyempi kuin noin 1/10 - 1/4 maksimipituudesta olisi O(madon pituus) nopeampi kuin O(pelialueen sivu^2) pelkän hännänkin etsimiseen. Ja tämä kaikki siis silloin kun vielä ajattelin että madon välipaloja ei piirretä.

Sitä ei tosiaan ollut tarkoitettu ihan niin vakavasti otettavaksi.

jalski [30.03.2012 01:07:40]

#

Pistetäänpä vielä PL/I versio simppelistä matopelistä esille...

*PROCESS MARGINS(1,160) LANGLVL(SAA2) pp(macro);
*PROCESS LIMITS(EXTNAME(100) fixedbin(63) fixeddec(31) name(100) );
*PROCESS NOT('ª^') DFT(BYVALUE);
*PROCESS INCLUDE (EXT('CPY','INC'));

Snake: package;

   /* Include win32 stuff */
   %include winbase;
   %include wingdi;
   %include winuser;

   %include snake;  /* application include file */

   %replace MAP_SIZE  by 15;
   %replace TILE_SIZE by 49;
   %replace ID_TIMER  by  1;

 dcl (addr, binvalue, mod, iand, inot, ior, length, null, sysnull, ptrvalue, signed, unsigned, size, time, random) builtin;


/* Prototypes and constants*/
 define structure
   1 OBJINFO,
     2 width  type INT,
     2 height type INT;

 dcl 1 point_type based,
       2 x type INT,
       2 y type INT;

 dcl 1 ZERO,
       2 x type INT value (0),
       2 y type INT value (0);

 dcl 1 LEFT,
       2 x type INT value (-1),
       2 y type INT value (0);

 dcl 1 RIGHT,
       2 x type INT value (1),
       2 y type INT value (0);

 dcl 1 UP,
       2 x type INT value (0),
       2 y type INT value (-1);

 dcl 1 DOWN,
       2 x type INT value (0),
       2 y type INT value (1);


 define ordinal MAP_ID (EMPTY, SNAKE, FOOD, CRASH);

/**********************************************************************************************************************/
/* global variables */
 dcl g_hbmBuffer   type HBITMAP init (sysnull());

 dcl g_snakeInfo      type OBJINFO;
 dcl g_hbmSnake       type HBITMAP;
 dcl g_hbmMSnake      type HBITMAP;
 dcl g_szSnakeFilename  char (50) varz init ('..\data\api.bmp');

 dcl g_crashInfo      type OBJINFO;
 dcl g_hbmCrash       type HBITMAP;
 dcl g_hbmMCrash      type HBITMAP;
 dcl g_szCrashFilename  char (50) varz init ('..\data\crash.bmp');

 dcl g_map (0:MAP_SIZE - 1, 0:MAP_SIZE - 1) type INT;

 dcl g_snake (0:((MAP_SIZE - 1)*(MAP_SIZE - 1))) like point_type;
 dcl g_len_snake type INT;

 dcl g_dir like point_type;
 dcl g_ndir like point_type;

 dcl g_food like point_type;
 dcl g_crash like point_type;

 dcl g_leave_it type BOOL;
 dcl g_crashed  type BOOL;


 dcl wndclass  type WNDCLASSEX;

/**********************************************************************************************************************/
/* main procedure */
 WinMain: proc (hInstance, hPrevInstance, szCmdLine, iCmdShow) returns(type INT) options (winmain);
   dcl hInstance     type HINSTANCE;
   dcl hPrevInstance type HINSTANCE;
   dcl szCmdLine     ptr;
   dcl iCmdShow      type INT;

   /* local variables */
   dcl hwnd type HWND;
   dcl msg type MSG;
   dcl szAppName char (50) varz init ('Snake');
   dcl szAppTitle char (50) varz init ('Simple snake game in Windows PL/I!');

   /* initialize */
    wndclass.cbSize        = size(wndclass);
    wndclass.style         = ior(CS_HREDRAW, CS_VREDRAW);
    wndclass.lpfnWndProc   = WinProc;
    wndclass.cbClsExtra    = 0;
    wndclass.cbWndExtra    = 0;
    wndclass.hInstance     = hInstance;
    wndclass.hCursor       = LoadCursor(sysnull(), pli_b2z(binvalue(IDC_ARROW)));
    wndclass.hIcon         = LoadIcon(hInstance, pli_b2z(IDI_BALL));
    wndclass.hbrBackground = GetStockObject(WHITE_BRUSH);
    wndclass.lpszMenuName  = sysnull();
    wndclass.lpszClassName = addr(szAppName);
    wndclass.hIconSm       = LoadIcon(hInstance, pli_b2z(IDI_SBALL));

   /* register class */
   call RegisterClassEx (wndclass);

   /* Create a window */
   hwnd = CreateWindow(szAppName,                        /* window class name */
                        szAppTitle,                      /* window caption    */
                        ior(WS_OVERLAPPED, WS_SYSMENU),  /* window style      */
                        CW_USEDEFAULT,                   /* x pos             */
                        CW_USEDEFAULT,                   /* y pos             */
                        360,                             /* x size            */
                        240,                             /* y size            */
                        sysnull(),                       /* parent window hand*/
                        sysnull(),                       /* window menu hand  */
                        hInstance,                       /* pgm instance hand */
                        sysnull() );                     /* creation params   */

   /* Show the window */
   call ResizeClient(hwnd, MAP_SIZE * TILE_SIZE, MAP_SIZE * TILE_SIZE);
   call ShowWindow(hwnd, iCmdShow) ;
   call UpdateWindow(hwnd);

   /* Message Loop */
   do while (GetMessage(msg, sysnull(), 0, 0) ^= 0);
      call   TranslateMessage(msg);
      call   DispatchMessage(msg);
   end;  /* of do */

   return (msg.wParam);
 end WinMain;  /* of program */

/**********************************************************************************************************************/
/* Window procedure */
 WinProc: proc (hwnd, msg, mp1, mp2) options(byvalue, linkage (stdcall)) returns (type LRESULT);
   dcl hwnd    type HWND;
   dcl msg     type UINT;
   dcl mp1     type WPARAM;
   dcl mp2     type LPARAM;

   /* local variables    */
   dcl hdc     type HDC;
   dcl ps      type PAINTSTRUCT;
   dcl rectl   type RECT;
   dcl bm      type BITMAP;

    select (msg);
      when (WM_CREATE)
        do;
		  g_hbmSnake = LoadImage(sysnull(), g_szSnakeFilename, IMAGE_BITMAP, 0, 0, LR_LOADFROMFILE);
		  g_hbmMSnake = CreateBitmapMask(g_hbmSnake, RGB(255, 107, 250));
		  call GetObject(g_hbmSnake, size(bm), addr(bm));
          g_snakeInfo.width = bm.bmWidth;
          g_snakeInfo.height = bm.bmHeight;

		  g_hbmCrash = LoadImage(sysnull(), g_szCrashFilename, IMAGE_BITMAP, 0, 0, LR_LOADFROMFILE);
		  g_hbmMCrash = CreateBitmapMask(g_hbmCrash, RGB(255, 107, 250));
		  call GetObject(g_hbmCrash, size(bm), addr(bm));
          g_crashInfo.width = bm.bmWidth;
          g_crashInfo.height = bm.bmHeight;

          call InitSnake;
          call SetTimer(hwnd, ID_TIMER, 200);
        end; /* of when */
      when (WM_KEYDOWN)
          select (mp1);
		    when (VK_LEFT)
			  g_ndir = (LEFT);
			when (VK_RIGHT)
			  g_ndir = (RIGHT);
			when (VK_UP)
			  g_ndir = (UP);
			when (VK_DOWN)
			  g_ndir = (DOWN);
            when (VK_SPACE)
			  if g_crashed = TRUE then
			    do;
				  call InitSnake;
				  call SetTimer(hwnd, ID_TIMER, 200);
				end;
		  end; /* of select (mp1) */
      when (WM_TIMER)
        do;
          call GetClientRect(hwnd, rectl);
		  call UpdateSnake;
          call InvalidateRect(hwnd, rectl, FALSE);
		  if g_crashed = TRUE then call KillTimer(hwnd, ID_TIMER);
        end; /* of when */
      when (WM_PAINT)
        do;
          hdc = BeginPaint(hwnd, ps);
          call GetClientRect(hwnd, rectl);
		  if g_hbmBuffer = sysnull() then g_hbmBuffer = CreateCompatibleBitmap(hdc, rectl.right, rectl.bottom);
          call DrawSprites(hdc, rectl, g_hbmBuffer);
          call EndPaint(hwnd, ps);
        end; /* of when */
      when (WM_DESTROY)
        do;
          /* Terminate the application */
          call KillTimer(hwnd, ID_TIMER);
		  call DeleteObject(g_hbmSnake);
		  call DeleteObject(g_hbmMSnake);
          call DeleteObject(g_hbmBuffer);
          call PostQuitMessage(0);
        end; /* of when */
      otherwise
        return (DefWindowProc(hwnd,msg,mp1,mp2));
    end; /* of select (msg) */
   return (0);
 end WinProc; /* of procedure */

/**********************************************************************************************************************/
/* Resize client rectangle */
 ResizeClient: proc (hwnd, nWidth, nHeight);
   dcl hwnd type HWND;
   dcl (nWidth, nHeight) type INT;

   dcl (rcClient, rcWindow) type RECT;
   dcl ptDiff type POINT;

   call GetClientRect(hwnd, rcClient);
   call GetWindowRect(hwnd, rcWindow);
   ptDiff.x = (rcWindow.right - rcWindow.left) - rcClient.right;
   ptDiff.y = (rcWindow.bottom - rcWindow.top) - rcClient.bottom;
   call MoveWindow(hwnd, rcWindow.left, rcWindow.top, nWidth + ptDiff.x, nHeight + ptDiff.y, TRUE);
 end ResizeClient;

/**********************************************************************************************************************/
/* Create bitmap mask function */
 CreateBitmapMask: proc (hbmColour, crTransparent) returns (type HBITMAP);
   dcl hbmColour type HBITMAP;
   dcl crTransparent type COLORREF;

   /* local variables */
   dcl (hdcMem, hdcMem2) type HDC;
   dcl hbmMask           type HBITMAP;
   dcl bm                type BITMAP;

   call GetObject(hbmColour, size(bm), addr(bm));
   hbmMask = CreateBitmap(bm.bmWidth, bm.bmHeight, 1, 1, sysnull());

   hdcMem = CreateCompatibleDC(sysnull());
   hdcMem2 = CreateCompatibleDC(sysnull());

   call SelectObject(hdcMem, hbmColour);
   call SelectObject(hdcMem2, hbmMask);

   call SetBkColor(hdcMem, crTransparent);

   call BitBlt(hdcMem2, 0, 0, bm.bmWidth, bm.bmHeight, hdcMem, 0, 0, SRCCOPY);
   call BitBlt(hdcMem, 0, 0, bm.bmWidth, bm.bmHeight, hdcMem2, 0, 0, SRCINVERT);

   call DeleteDC(hdcMem);
   call DeleteDC(hdcMem2);

   return (hbmMask);
 end CreateBitmapMask;

/**********************************************************************************************************************/
/* Draw sprites procedure */
 DrawSprites: proc (hdc, prc, hbuffer);
   dcl hdc          type HDC;
   dcl prc          type RECT;
   dcl hbuffer      type HBITMAP;

   /* local variables */
   dcl hdcBuffer    type HDC;
   dcl hbmOldBuffer type HBITMAP;
   dcl i type INT;

   hdcBuffer = CreateCompatibleDC(hdc);
   hbmOldBuffer = SelectObject(hdcBuffer, g_hbmBuffer);

   call FillRect(hdcBuffer, prc, GetStockObject(WHITE_BRUSH));

   do i = 0 to g_len_snake;
     call DrawSprite(hdcBuffer, g_snake(i).x * g_snakeInfo.Width, g_snake(i).y * g_snakeInfo.Height, g_hbmSnake, g_hbmMSnake);
   end;

   /* Draw crash image if snake crashed */
   if g_crashed = TRUE then
     call DrawSprite(hdcBuffer, g_crash.x * g_crashInfo.Width, g_crash.y * g_crashInfo.Height, g_hbmCrash, g_hbmMCrash);

   /* Draw "food" using just snake image mask */
   call DrawSprite(hdcBuffer, g_food.x * g_snakeInfo.Width, g_food.y * g_snakeInfo.Height, g_hbmMSnake, g_hbmMSnake);

   /* Blit memory buffer to screen */
   call BitBlt(hdc, 0, 0, prc.right, prc.bottom, hdcBuffer, 0, 0, SRCCOPY);

   call SelectObject(hdcBuffer, hbmOldBuffer);
   call DeleteDC(hdcBuffer);
 end DrawSprites;

/**********************************************************************************************************************/
/* Init snake procedure */
 InitSnake: proc;
   dcl (i, j) type INT;
   dcl seed float bin (53) static init (0);

   if seed = 0 then seed = random(time());

   do i = 0 to MAP_SIZE - 1;
     do j = 0 to MAP_SIZE - 1;
	   g_map (i, j) = binvalue(EMPTY);
     end;
   end;

   g_len_snake = 0;
   g_dir = (RIGHT);
   g_ndir = g_dir;

   g_snake(g_len_snake).x = (MAP_SIZE - 1) * random();
   g_snake(g_len_snake).y = (MAP_SIZE - 1) * random();
   g_map(g_snake(g_len_snake).y, g_snake(g_len_snake).x) = binvalue(SNAKE);

   g_crash = (ZERO);

   g_leave_it = TRUE;
   g_crashed = FALSE;

   g_food.x = (MAP_SIZE - 1) * random();
   g_food.y = (MAP_SIZE - 1) * random();

   g_map(g_food.y, g_food.x) = binvalue(FOOD);

 end InitSnake;

/**********************************************************************************************************************/
/* Update snake procedure */
 UpdateSnake: proc;
   dcl i type INT;
   dcl np like point_type;

   if (g_dir.x * (-1) ^= g_ndir.x) & (g_dir.y * (-1) ^= g_ndir.y) then g_dir = g_ndir;

   np = g_snake(g_len_snake) + g_dir;
   np  = mod(np + MAP_SIZE, MAP_SIZE);

   if g_map(np.y, np.x) = binvalue(SNAKE) then
     do;
       g_crashed = TRUE;
       g_map(np.y, np.x) = binvalue(CRASH);
	   g_crash = np;
	   g_leave_it = TRUE;
     end;
   else if g_map(np.y, np.x) = binvalue(FOOD) then
     do;
       do loop;
	     g_food.x = (MAP_SIZE - 1) * random();
	     g_food.y = (MAP_SIZE - 1) * random();
	     if g_map(g_food.y, g_food.x) = binvalue(EMPTY) then leave;
	   end;
	   g_map(g_food.y, g_food.x) = binvalue(FOOD);
	   g_leave_it = TRUE;
     end;

   if g_leave_it = TRUE then
     do;
	   g_len_snake += 1;
	   g_leave_it = FALSE;
     end;
   else do;
	   g_map(g_snake(0).y, g_snake(0).x) = binvalue(EMPTY);
	   do i = 0 to g_len_snake - 1;
	     g_snake(i) = g_snake(i+1);
       end;
   end;

   g_snake(g_len_snake) = np;
   g_map(np.y, np.x) = binvalue(SNAKE);

 end UpdateSnake;

/**********************************************************************************************************************/
/* Draw sprite procedure */
 DrawSprite: proc (hdc, x, y, hBitmap, hMask);
   dcl hdc type HDC;
   dcl (x, y) type INT;
   dcl (hBitmap, hMask) type HBITMAP;

   dcl hdcMem type HDC;
   dcl hbmOld type HBITMAP;
   dcl bm     type BITMAP;

   call GetObject(hBitmap, size(bm), addr(bm));
   hdcMem = CreateCompatibleDC(hdc);
   hbmOld = SelectObject(hdcMem, hMask);
   call BitBlt(hdc, x, y, bm.bmWidth, bm.bmHeight, hdcMem, 0, 0, SRCAND);
   call SelectObject(hdcMem, hBitmap);
   call BitBlt(hdc, x, y, bm.bmWidth, bm.bmHeight, hdcMem, 0, 0, SRCPAINT);

   call SelectObject(hdcMem, hbmOld);
   call DeleteDC(hdcMem);
 end DrawSprite;

/**********************************************************************************************************************/
end Snake; /* of package */

Sivun alkuun

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta