Okay, so I decided on a quick side project to my MMORPG engine - a 2D side scroller engine. I've spent three days on this, and so far, I have:

- sprite animation
- maps with automated collision detection
- shooting
- AI enemies that follow and attack (though they're a little bit thick)
- scrolling maps, but without *only* moving the map (if you know what I mean?) player moves freely, map scrolls when necessary

Not bad for three days work, eh?

I've got a small video demo available, which I'm updating regularly. It can be found at the following address:
http://gabehabe.com/sidescroller/demo.avi

The graphics are absolutely crap, but they do help to demonstrate the functionality quite well.

The engine is unique [I think] in that it requires absolutely no programming to create a game with it. So, [when it's finally complete] you'll be able to simply drop your maps in a certain folder and it'll read them systematically, detect collision points on the images, and play them one by one. You'll even be able to add video files as cutscenes between levels, and sound - all read in dynamically at runtime.

WARNING : CONTAINS SPOILERS!

Decided to blog about some of the more interesting project euler tasks here. Could lead to some interesting discussion on algorithms, too.

I won't be blogging about every problem I work on, and I don't spend too much time on there, but it's nice to try your hand at a challenge.

The least efficient part of this code is rotate_int which I threw together in about 5 minutes. I'm happy though, since it works and I can solve the problem in ~3.5 seconds using this program. (2.5s of which is used to determine all primes below 1,000,000)
Here's the code for the rotate_int function:

int rotate_int(int x, int rotations) {
    vector<int> vec;
    ostringstream ostr;
    ostr << x;
    string str = ostr.str();
    for(unsigned int i = 0; i < str.length(); i++) {
        vec.push_back(str[i]-48);
    }
    rotate(vec.begin(), vec.begin()+rotations, vec.end());
    int mul = 1;
    for(unsigned int i = 1; i < vec.size(); i++) {
        mul *= 10;
    }
    x = 0;
    for(unsigned int i = 0; i < vec.size(); i++) {
        x += vec[i] * mul;
        mul /= 10;
    }
    return x;
}

Told you it was inefficient!

The rest of the program is really just a wrapper for that prime bitset.

The final product is this:

/* WARNING - CONTAINS SPOILERS!
 * Project Euler - Problem 35
 * Circular primes
 * http://projecteuler.net/index.php?section=problems&id=35
 * Author: Danny Battison
 */
#include <iostream>
#include <bitset>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 1000000;

void output(bitset<MAX> primes) {
    for(int i = 0; i < MAX; i++) {
        if(primes[i] == 1) {
            cout << i << " ";
        }
    }
}

int get_nth_prime(int n, bitset<MAX> primes) {
    int count = 0;
    for(int i = 2; i < MAX; i++) {
        if(primes[i]) {
            count++;
        } if(count == n) {
            return i;
        }
    }
    return 0; // could not find
}

int rotate_int(int x, int rotations) {
    vector<int> vec;
    ostringstream ostr;
    ostr << x;
    string str = ostr.str();
    for(unsigned int i = 0; i < str.length(); i++) {
        vec.push_back(str[i]-48);
    }
    rotate(vec.begin(), vec.begin()+rotations, vec.end());
    int mul = 1;
    for(unsigned int i = 1; i < vec.size(); i++) {
        mul *= 10;
    }
    x = 0;
    for(unsigned int i = 0; i < vec.size(); i++) {
        x += vec[i] * mul;
        mul /= 10;
    }
    return x;
}

int main() {
    bitset <MAX> primes;
    for(int i = 2; i < MAX; i++) {
        primes[i] = 1;
    }
    // quick sieve of eratosthenes -- start it off
    int sieve[] = {2,3,5,7}; // give it a few primes to start with
    for(int mul = 0; mul < 4; mul++) {
        for(int i = 1; i < MAX; i++) {
            if(i % sieve[mul] == 0 && i != sieve[mul]) {
                primes[i] = 0;
            }
        }
    }

    // by now, we have a list of primes with some larger numbers still left
    // in order to remove those, we now need to run through primes and
    // make sure to remove multiples of primes up to sqrt(MAX)
    for(int i = 2; i < sqrt(MAX); i++) {
        if(primes[i]) {
            for(int j = i+1; j < MAX; j++) {
                if(j % i == 0) {
                    primes[j] = 0;
                }
            }
        }
    }

    // this section takes approx 1s - could be reduced GREATLY
    // but I'm lazy.
    ostringstream ostr;
    int len;
    bool t = 0;
    int count = 0;
    int x;
    for(int i = 1; i < MAX; i++) {
        if(primes[i]) {
            ostr.str("");
            ostr << i;
            len = ostr.str().length();
            for(int j = 0; j < len; j++) {
                x = rotate_int(i, j);
                t = primes[x];
                if(!t) break;
            }
            if(t) {
                count++;
            }
        }
    }cout << count;

    return 0;
}

Quick entry, posting it for safe keeping.

I've already found this useful in a few of the problems over at project euler so I figured I'd share it. Quick primes! I actually wrote this a few days ago in response to NickDMax's thread (check it out, it's pretty interesting), before I realised what he was trying to do. (I was hasty!)

This program runs in silly time, something like a tenth of a second. Not bad for finding all primes up to 100,000 and finding the nth prime number, huh?

/*
 * A fast method of producing a table of primes
 * using a bitset
 * Author: Danny Battison
 */

 #include <iostream>
#include <bitset>
#include <cmath>

using namespace std;

#define MAX 100000

void output(bitset<MAX> primes) {
    for(int i = 0; i < MAX; i++) {
        if(primes[i] == 1) {
            cout << i << " ";
        }
    }
}

int get_nth_prime(int n, bitset<MAX> primes) {
    int count = 0;
    for(int i = 2; i < MAX; i++) {
        if(primes[i]) {
            count++;
        } if(count == n) {
            return i;
        }
    }
    return 0; // could not find
}

int main() {
    bitset <MAX> primes;
    for(int i = 1; i < MAX; i++) {
        primes[i] = 1;
    }
    // quick sieve of eratosthenes -- start it off
    int sieve[] = {2,3,5,7}; // give it a few primes to start with
    for(int mul = 0; mul < 4; mul++) {
        for(int i = 1; i < MAX; i++) {
            if(i % sieve[mul] == 0 && i != sieve[mul]) {
                primes[i] = 0;
            }
        }
    }

    // by now, we have a list of primes with some larger numbers still left
    // in order to remove those, we now need to run through primes and
    // make sure to remove multiples of primes up to sqrt(MAX)
    for(int i = 2; i < sqrt(MAX); i++) {
        if(primes[i]) {
            for(int j = i+1; j < MAX; j++) {
                if(j % i == 0) {
                    primes[j] = 0;
                }
            }
        }
    }

    cout << get_nth_prime(1000, primes);

    return 0;
}

So, I'm finally uploading the source. It's a little buggy (still) but it should be stable. (Memory and CPU usage seem pretty stable too)

I'm intrigued to see if anyone can build it for their OS, or what errors they come across. I've included the Windows DLLs, and all references are relative (I hope) to the project, so *hopefully* it should build without problems. I've never released the code for a full project like this before, so let's see how it goes.

I don't know how other operating systems use dependencies like Windows DLLs, but I know they'll require some other stuff - no idea what.

To those of you willing to try to build a release for your OS - thank you. :') if you could email me the build (gabehabe@gmail.com), I'll upload it to SourceForge and credit you for your contribution.

Please note I'm not looking for any help on the project, I'm determined to do it by myself. That said, I'm open to suggestions on how to improve it.

download now

Not gonna give it all away yet, it needs an extreme cleanup. My code is a total mess!

Instead, I'm gonna give you a few tasters. Ready? Good.

First off, a little collision detection for that map. This took a while to perfect, I gotta admit. In fact to be honest, there's still a lot of room for improvement.

My code is a fucking disgrace to mankind here, please don't hate me for it!

int map::collision_check_bottom(int x, int y) {
    x+=SPRITE_WIDTH;
    vector<SDL_Rect>::iterator it;
    vector<object*>::iterator it2;
    vector<exit*>::iterator it3;
    int i = 0;

    for(it3 = this->exits.begin(); it3 != this->exits.end(); ++it3, i++) {
        if(((*it3)->offset.y+(*it3)->offset.h>y-9&&(*it3)->offset.y+(*it3)->offset.h<y+6)&&((*it3)->offset.x<x&&(*it3)->offset.x+(*it3)->offset.w+SPRITE_WIDTH>x))return INT_MAX-i;
    }

    for(it = this->off_limits.begin(); it != this->off_limits.end(); ++it) {
        if((it->y+it->h>y-9&&it->y+it->h<y+6)&&(it->x<x&&it->x+it->w+SPRITE_WIDTH>x))return -1;
    }

    i = 0;
    for(it2 = this->objects.begin(); it2 != this->objects.end(); ++it2, i++) {
        if(((*it2)->offset.y+(*it2)->offset.h>y-9&&(*it2)->offset.y+(*it2)->offset.h<y+6)&&((*it2)->offset.x<x&&(*it2)->offset.x+(*it2)->offset.w+SPRITE_WIDTH>x))return i;
    }

    return -2;
}

Aaaaannndddd, another piece of the engine. This is the player movement function, which utilises that nasty looking collision detection.

bool player::move(int direction) { // 1=up, 2=down, 3=left, 4=right
    int movement = this->running ? (VELOCITY*2)-3 : VELOCITY;
    int x = 0;
    switch(direction) {
        case 1:
            x = this->the_map->collision_check_bottom(this->_x, this->_y-movement+SPRITE_HEIGHT-5);
            if(x == -2) {
                this->_y -= movement;
            } else if(x >= INT_MAX / 2) {
                this->the_map->change_map(INT_MAX - x);
            }
            this->state = this->state == UP_ONE ? UP_TWO : UP_ONE;
            break;
        case 2:
            x = this->the_map->collision_check_top(this->_x, this->_y-movement+SPRITE_HEIGHT-5);
            if(x == -2) {
                this->_y += movement;
            } else if(x >= INT_MAX / 2) {
                this->the_map->change_map(INT_MAX - x);
            }
            this->state = this->state == DOWN_ONE ? DOWN_TWO : DOWN_ONE;
            break;
        case 3:
            x = this->the_map->collision_check_right(this->_x-movement+SPRITE_WIDTH-5, this->_y);
            if(x == -2) {
                this->_x -= movement;
            } else if(x >= INT_MAX / 2) {
                this->the_map->change_map(INT_MAX - x);
            }
            this->state = this->state == LEFT_ONE ? LEFT_TWO : LEFT_ONE;
            break;
        case 4:
            x = this->the_map->collision_check_left(this->_x-movement+SPRITE_WIDTH-5, this->_y);
            if(x == -2) {
                this->_x += movement;
            } else if(x >= INT_MAX / 2) {
                this->the_map->change_map(INT_MAX - x);
            }
            this->state = this->state == RIGHT_ONE ? RIGHT_TWO : RIGHT_ONE;
            break;

        default: break;
    }

    ostringstream q;
    q << "UPDATE users ";
    q << "SET screen_id = " << this->the_map->get_id() << ", ";
    q << "x = " << this->_x << ", y = " << this->_y << ", state = " << this->state;
    q << " WHERE username = '" << this->username << "' LIMIT 1";
    mysql_query(this->_mysql, q.str().c_str());

    return true;
}

And lastly, I give you main, which is a nice example on how to use it -- this bit's not so nasty!

#include "game.h"
#include "functions.h"

int do_mysql(void* foo);

// must be global for the sake of accessing in the thread
game* the_game;
SDL_Surface* players;

int main(int argc, char *argv[]) {
    players = SDL_CreateRGBSurface(SDL_SWSURFACE, SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_DEPTH, RMASK, GMASK, BMASK, AMASK);

    the_game = new game(players);

    map* m1 = new map(1, the_game->get_screen());
    m1->set_player_location(180,220);
    m1->set_map(IMG_Load(".\\img\\map.png"));
    m1->add_object(new object(the_game->get_screen(), ".\\img\\house.jpg", 272, 137, 96, 64));

    map* m2 = new map(2, the_game->get_screen());
    m2->set_map(IMG_Load(".\\img\\map2.png"));
    m2->set_player_location(300,290);
    m2->add_object(new object(the_game->get_screen(), ".\\img\\bed.png", 160, 180, 42, 72, &dont_sleep, &do_sleep));
    m2->add_exit(new exit((SDL_Surface*)NULL, 300, 300, 25, 32, m1));

    m2->add_collidable(0, 0, 120, SCREEN_HEIGHT);
    m2->add_collidable(0, 0, SCREEN_WIDTH, 120);
    m2->add_collidable(0, 302, SCREEN_WIDTH, SCREEN_HEIGHT-305);
    m2->add_collidable(SCREEN_WIDTH-120, 0, 120, SCREEN_HEIGHT);

    m1->add_exit(new exit((SDL_Surface*)NULL, 306, 177, 25, 25, m2));

    map* main = new map(m1);

    the_game->add_map(main);
    the_game->add_map(m1);
    the_game->add_map(m2);

    the_game->do_intro();
    SDL_CreateThread(&do_mysql, NULL);

    the_game->do_main();

    return EXIT_SUCCESS;
}

I'll even be working on a code generator for that, along with a map editor - I plan to develop something similar to RPG Maker when the engine is more complete. Also, a lot of that can be made redundant: in the end, I'll be keeping those methods, but also developing a way to load maps, etc, straight from a database, storing much more stuff in the cloud - easier to update your games, smaller downloads for users, etc.