Contest #2: Space Invaders

Space Invaders

Einsendeschluss: 20.08.2011 - 23:59
Eure Aufgabe: Leitet von SpaceShip ab und implementiert eure eigene computeNextMove-Methode. Die Beispielimplementierung zeigt, wie es geht. Das Schiff, das am laengsten überlebt, wird zum Sieger erklaert.

Desweiteren:

Dies ist kein Softwaredesign-Wettbewerb. Dementsprechend habe ich den Code auch runtergehaxelt (char[],19/20,etc). Habt also bitte Nachsicht mit mir
Zudem ist die Methode SpaceField::printField() auf Linux ausgelegt. Würde mich freuen, wenn jemand diese mit ein paar #ifdefs auch für Windows möglich machen würde. Die Methode ist zwar nicht nötig, aber macht das ganze bissl schöner.
Pro tick kommen mit 50% Wahrscheinlichkeiten weitere Astroiden ins Feld. Zudem entscheidet die Variable difficulty über die maximale Anzahl von wahrscheinlichen Astroiden pro tick. difficulty wird immer nach 10 Runden erhöht. Wer dbzgl bessere Vorschlaege hat, her damit.
Ich werde dann in einer Woche alle SpaceShips mit 100 verschiedenen Seeds testen und die Statistik entscheidet dann wer gewinnt.
Einsendungen bitte über das Profil einschicken.
Es euch in der computeNextMove-Methode nur erlaubt moveRight/Left/Up/Down() zu benutzen. Sowie sich Informationen vom SpaceField über die Positionen aller Astroiden zu beschaffen.
Pro Tick ist nur ein moveX möglich.

Hier der Code:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <memory>
using namespace std;

#ifdef WIN32
extern "C" void __stdcall Sleep(unsigned long);
void sleep(int seconds)
{
    Sleep(1000u*seconds);
}
void cls()
{
    system("cls");
}
#else
#include <unistd.h>
void cls()
{
    cout << "\x1b[2J\x1b[H" << flush;
}
#endif // WIN32

struct Point
{
    size_t x, y;

    Point(size_t x_ = 0, size_t y_ = 0)
        : x(x_), y(y_)
    {}
};

class SpaceField;
class SpaceShip
{

private:
    Point position;
    bool aLive, recursionDetected;
public:
    SpaceShip()
    : position(8, 15)
    , aLive(true), recursionDetected(false)
    { }

	enum MoveDirection { Stay, Left, Right, Up, Down };

    void destroy() { aLive = false; }
    bool isAlive() const { return aLive; }

    void doMove(SpaceField &field);
	Point getPosition() const { return position; }

    virtual MoveDirection computeNextMove(const SpaceField &field) = 0;        
};

class Astroids
{
private:
    vector<Point> astroidsPosition;
    size_t difficulty;
    long seed;

    long randomy()
    {
        return (((seed = seed * 214013L + 2531011L) >> 16) & 0x7fff);
    }

    void generateNewAstroids()
    {
        if(randomy() % 2 == 0) return;

        int noOfAstroids = randomy() % (difficulty > 15 ? 15 : difficulty) +1;
        while(noOfAstroids--)
        {
            astroidsPosition.push_back(Point(randomy() % 20, 0));
        }

    }
public:
    Astroids()
    {
        difficulty = 1;
        seed = 1234;
    }

    void increaseDifficulty()
    {
        ++difficulty;
    }

    size_t getDifficulty() const
    {
        return difficulty;
    }

    void moveForward()
    {
        generateNewAstroids();

        for(vector<Point>::iterator it = astroidsPosition.begin(); it != astroidsPosition.end();)
        {
            if(++it->y > 20)
                it = astroidsPosition.erase(it);
            else ++it;
        }
    }

    vector<Point> getAstroidPosition() const
    {
        return astroidsPosition;
    }
};

class SpaceField
{
private:
    char spaceField[20][20];

    SpaceShip *spaceShip;

    Astroids astroids;
    Point lastShipPosition;

    void init()
    {
        for(size_t y = 0; y < 20; ++y)
            for(size_t x = 0; x < 20; ++x)
                spaceField[x][y] = '_';
    }

    void updateField()
    {
        init();
        spaceField[lastShipPosition.y][lastShipPosition.x] = 'S';

        vector<Point> astroPoints = astroids.getAstroidPosition();

        for(size_t i = 0; i < astroPoints.size(); ++i)
            spaceField[astroPoints[i].y-1][astroPoints[i].x] = 'A';
    }
public:
    SpaceField()
    {
        init();
    }

    void insertShip(SpaceShip *ship)
    {
        spaceShip = ship;
        spaceField[spaceShip->getPosition().y][spaceShip->getPosition().x] = 'S';

        lastShipPosition = spaceShip->getPosition();
    }

    void increaseLevel()
    {
        astroids.increaseDifficulty();
    }

    bool isAstroidHere(Point checkPoint) const
    {
        return spaceField[checkPoint.y][checkPoint.x] == 'A';
    }

    size_t getLevel() const
    {
        return astroids.getDifficulty();
    }

    size_t getSizeY() const { return 20-1; }
    size_t getSizeX() const { return 20-1; }

    void moveShip(Point to)
    {
        if(spaceField[to.y][to.x] == 'A')
        {
            spaceShip->destroy();
            return;
        }

		if(spaceField[lastShipPosition.y][lastShipPosition.x] != 'A')
            spaceField[lastShipPosition.y][lastShipPosition.x] = '_';

        spaceField[to.y][to.x] = 'S';
        lastShipPosition = to;
    }

    void moveAstroidsForward()
    {
        astroids.moveForward();
        updateField();
    }

    void printField() const
    {
        cls();
        for(size_t y = 0; y < 20; ++y)
        {
            for(size_t x = 0; x < 20; ++x)
                cout << spaceField[y][x];

            cout << endl;
        }
        cout << endl;
    }
};

void SpaceShip::doMove(SpaceField &field)
{
	if(recursionDetected) return;

	recursionDetected = true;
	SpaceField safeCopy = field;

	MoveDirection directionToMove = computeNextMove(safeCopy);

	switch(directionToMove)
	{
		case Left:  if(position.x > 0) --position.x; break;
		case Right: if(field.getSizeX() > position.x) ++position.x; break;

		case Up:    if(position.y > 0) --position.y; break;
		case Down:  if(field.getSizeY() > position.y) ++position.y; break;
		default:;
	}

	field.moveShip(position);
	recursionDetected = false;
}

class CustomSpaceShip : public SpaceShip
{ 
public:
	MoveDirection computeNextMove(const SpaceField &field)
    {
        Point checkPoint = this->getPosition();
        --checkPoint.y; 

		if(field.isAstroidHere(checkPoint))
		{
            if(field.getSizeX() > checkPoint.x)
                return Right;
            else
                return Left;			
        }

		return Stay;		
    }
};

int main()
{
    SpaceField spaceField;

    std::shared_ptr<SpaceShip> ship(new CustomSpaceShip());
    spaceField.insertShip(ship.get());

    long cycles = 0;
    while(ship->isAlive())
    {
        ++cycles;
        spaceField.printField();

        ship->doMove(spaceField);
		spaceField.moveAstroidsForward();

        if(cycles % 10 == false)
            spaceField.increaseLevel();

        cout << cycles << " light years survived" << endl;
        cout << "Level" << spaceField.getLevel() << endl;

        sleep(1);
    }

    cout << "\nYou survived " << cycles << " light years far!" << endl;

    return 0;
}

Viel Spaß und tobt euch aus

Edit: "Einsendungen bitte über das Profil einschicken."

camper

Hier der klare Gewinner:

class Enterprise : public SpaceShip
{
    public:
            Enterprise(size_t x, size_t y)
                : SpaceShip(x, y)
            { }

            long kobayashimaru()
            {
                long s = 0;
                for (;;)
                {
                    srand(s);
                    if ( rand() % 2 == 0 )
                        return s;
                    ++s;
                }
            }

            void computeNextMove(SpaceField &field)
            {
                srand(kobayashimaru());
            }
};

Ist die Lösung von camper wirklich die perfekte Lösung? Geht es nicht mehr besser?

volkard

Gewonnen. Wo ist der nächste Wettbewerb?

class PicardWarpTunnelFighter : public SpaceShip
{
public:
	PicardWarpTunnelFighter(size_t x, size_t y)
		: SpaceShip(x, y)
	{ }

	void computeNextMove(SpaceField &field) {
        /*
        struct MyAstroids{
            vector<Point> astroidsPosition;
            size_t difficulty;
        };
        struct MySpaceField{
            char spaceField[20][20];
            SpaceShip *spaceShip;
            MyAstroids astroids;
            Point lastShipPosition;
        };
        reinterpret_cast<MySpaceField&>(field).astroids.astroidsPosition.clear();
        */

	    while(field.isAstroidHere(getPosition()))
            field.moveAstroidsForward();
	}
};

edit: Mist, die Enterprise war schneller.

Es ist eine Weile her, dass ich einen Space-Invaders-Automaten gesehen habe, aber ich kann mich nicht daran erinnern, dass es darin Asteroiden gegeben hätte.

Man konnte allerdings durch den eigenen Schild nach oben schießen, wie mir Futurama beigebracht hat.

Natürlich zaehlen campers und volkards Schiffe nicht, da sie gezielt meine Implementierung ausnutzen. Vielleicht sollte ich somit dazu erwaehnen, dass man selbst nur moveR/L/U/D benutzen und sich die ganzen Informationen über field und somit die Positionen der Astroiden beschaffen darf.

Shade Of Mine

KasF schrieb:

Natürlich zaehlen campers und volkards Schiffe nicht, da sie gezielt meine Implementierung ausnutzen. Vielleicht sollte ich somit dazu erwaehnen, dass man selbst nur moveR/L/U/D benutzen und sich die ganzen Informationen über field und somit die Positionen der Astroiden beschaffen darf.

Oder vielleicht sollte der Code nicht so leicht abusebar sein.

bmario

Hinweis am Rande, ein Lichtjahr (light year) ist keine Zeiteinheit

*Edit: Wenn man der computeNextMove() das SpaceField als const -Referenz übergibt, ist immerhin Volkard's Hack dahin. Dann sollte aber besser SpaceField::isAstroidHere() auch const sein.

volkard

KasF schrieb:

Natürlich zaehlen campers und volkards Schiffe nicht, da sie gezielt meine Implementierung ausnutzen.

Natürlich...
Warptunneln ist doch was ganz normales.

Shade Of Mine schrieb:

Oder vielleicht sollte der Code nicht so leicht abusebar sein.

Solange ich das hier nicht an einen Kunden verkaufen, kann es mir herzlichst egal sein!

bmario schrieb:

Hinweis am Rande, ein Lichtjahr (light year) ist keine Zeiteinheit

Es dient auch hier der Entfernung, die das Raumschiff im Astroidenfeld schon zurückgelegt hat

bmario schrieb:

*Edit: Wenn man der computeNextMove() das SpaceField als const -Referenz übergibt, ist immerhin Volkard's Hack dahin. Dann sollte aber besser SpaceField::isAstroidHere() auch const sein.

Ja das stimmt. Aber waehrend des Programmierens kam irgendwann der Punkt, wo ich mir selbst gesagt habe: "Ach, ist doch egal. Es geht hier nur um den Spaß und ich bin gerade zu Faul, um es sauber zu machen" ...

Entweder du machst es sauber, oder du musst Lösungen zulassen, die die Implementierung ausnutzen

Das ist das einzig Kluge, sonst ist schwammig, was man darf und was nicht. Und statt dafür Regeln wie "man darf nur diese Methoden aufrufen" zu formulieren, kann man den Code gleich entsprechend gestalten. Worauf ich hingegen keine Rücksicht nehmen würde, sind tatsächliche Hacks mit U.B., const_cast, #define private public etc.

volkard

edit: Nagut, dann schreibe ich nicht, wie ich es machen würde. Kann ja nicht wissen, daß man das offensichtliche nicht sagen darf. Wobei ich eher denke, daß KasF kaum darüber nachgedacht hat, wie eine gute Lösung aussehen würde.

Rhombicosidodecahedron

class ReallyOutsideTheBox: public SpaceShip
{
public:
	ReallyOutsideTheBox(size_t x, size_t y)
		: SpaceShip(20 + 1, 20 + 1) // könnte sich noch ein wenig ändern.
	{
	}

	void computeNextMove(SpaceField &field)
	{
		static long i = 0;
		i++;
		if(i == MAX_LONG - 3 ) // -3 Sicherheitsabstand und mir reicht der fünfte Platz :)
			destroy();  //ungetestet aber ungefähr so sollte es sein :)
	}
};

Mal eine "Böse" Frage:
Wenn ich anstatt x und y konstante Werte > 19 nehme, dann wird ja irgendwo Speicher ein Byte mit einem 'S' überschrieben (typischer Buffer Overflow), aber gibt es nach der Klasse SpaceField einen definierten Bereich, der "problemlos" überschrieben / gelesen werden kann (d.h. nicht abstützt, aber Spieler außerhalb des Spielfeldes)? Sozusagen der "Subraum", um bei StarTrek zu bleiben.

Kleines Codeupdate für die Heulsusen unter uns.

Ich find das auch schade, dass ihr da so pedantisch wart. Statt da zu kritisieren oder euch lustig drüber zu machen, könntet ihr den Quelltext ja auch 100% perfekt refaktorisieren und als Beispiel für perfektes C++ den kommenden Jahrhunderten und Jahrtausenden übergeben als Mahnmal des menschlichen Intellekts!

volkard schrieb:

...

Du bist doch echt der tollste beschde und coolste Typ in diesem Forum und weißt auch echt alles besser als wir alle zusammen. Statt den Leuten lieber ihren Spaß zu lassen, musst du es ihnen kaputt machen, da du bei dieser für dich primitiven Aufgabe ja selbst kein Spaß hast und somit den anderen auch nicht das Vergnügen gönnen willst. Ich disqualifiziere dich jetzt schonmal. Ist immerhin mein Spiel und ich suche mir eben nun mal meine Mitspieler selbst aus ...

@Decimad: Leider ist dieses Verhalten ein Problem in diesem Forum und genau dieses Verhalten ist auch das Abbild des Informatikers in unserer Gesellschaft. Schade, wo ich doch auch auch ganz nette, normale und soziale Informatiker kenne ...

Aber genug Off-Topic

volkard

Taktik: Auf der Grundlinie bleiben. Asteroiden verglühen dann automatisch vor dem Aufprall.

void computeNextMove(const SpaceField &field)
            {
                if(getPosition().y<field.getSizeY())
                    moveDown();
            }

Überlebt beliebig lange.
Vermutlich Programmierfehler.

volkard

Taktik: Loch suchen und reinfahren.

class TomParisShuttle : public SpaceShip
{
    public:
            Point findSpace(const SpaceField &field)
            {
                for(size_t y=field.getSizeY()-1;y>=1;--y)
                    for(size_t x=0;x<field.getSizeX();++x)
                        if(!field.isAstroidHere(Point(x,y)))
                           return Point(x,y);
                return Point(3,3);
            }
            void computeNextMove(const SpaceField &field)
            {
                Point space=findSpace(field);
                while(getPosition().y<space.y)
                    moveDown();
                while(getPosition().y>space.y)
                    moveUp();
                while(getPosition().x>space.x)
                    moveLeft();
                while(getPosition().x<space.x)
                    moveRight();
            }
};

Überlebt extrem lange.
Vermutlich Regelfehler.

volkard schrieb:

Vermutlich Programmierfehler.

Behoben. Danke.

volkard schrieb:

Vermutlich Regelfehler.

Behoben. Danke.

Du bist echt unglaublich. Wieso kannst du mich nicht ganz normal - wie ein Erwachsener - schon in deinem ersten Post auf meine ganzen Fehler aufmerksam machen und zur Qualitaet dieses Threads beitragen. Wieso nicht!? Ehrlich, sags mir. Wieso musst du dich dermaßen arrogant profilieren? ... Ich weiß echt nicht, wie oft ich dich schon bzgl dieses kindische Verhalten hier im Forum angesprochen habe. Traurig