Psyco == Awesome

As I mentioned in my last post, Project Euler is dominating my coding time as of late. I have currently solved 20 out of the 268 on there. The last being this one. The code I wrote was slow, taking around a minute to get to the correct answer. It did get the job done, but I decided there had to be a way to speed things up. That was when I remembered reading about Psyco.

"So what does Psyco do?" I hear you cry. In a nutshell it claims to speed up Python code by a factor of 2 to 4 times. Being a natural sceptic I tested it on the code in my last post. It took my code only 0.047 seconds using Psyco which is a pretty good improvement over the 0.5 seconds it takes with vanilla Python.

Quite impressed with the performance increase I decided to try it with the game I have been working on. This is when I became very impressed. I do not have exact figures, but it runs A LOT faster now. Which means I get to add more particle effects, more explosions and generally more stuff on screen without suffering massive lag.

On a completely different, but somewhat related topic all this Psyco talk reminded me of a classic tune from my youth, way back when Hip-Hop was actually worth listening to. I remember this tune was playing on my stereo the first ever time I got over 300 lines in Tetris. All done on the original Gameboy no less. I know, I am old! Anyway here is a link to Psycho by Lords of the Underground.

Project Euler. A good distraction!

I am currently taking a break from coding the game. I have reached a point where my lack of artwork, sound FX, music is impacting development. In the new year my artist finishes her MA in animation and will commence providing me with concept designs and sprites to work with. So fear not! My commitment has not waned at all.

I realised that I needed some bite-sized programming projects to work on. I needed something fun and challenging to sink my teeth into. This is when I remembered the brilliant website http://projecteuler.net.

Project Euler is a website that contains a number of maths problems that can be solved via programming. So far I have solved 10 of the 267 problems. In doing so, it has reminded me how badly I suck at mathematics. Luckily I am focused and never give up until I have figured something out even if that takes me a lot longer than most.

Yesterday I solved problem 5.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

### SPOILER ALERT ###

I will now explain how I solved it using Python. If you don't want to know the answer and wish to solve it yourself stop reading now. Do come back when you have finished it just to compare notes though.

First we need to define a win condition.

def checkFactors(value, factors):

    """Returns True if value is evenly divisible

by all numbers within factors.

"""

    if value == 0: ## Because 0 divided by any number in Python returns 0.

        return False

    for n in factors:

        if value%n != 0:

            return False

        elif value%n == 0:

            pass

    return True

All well and good, but we still need a way to pass values to the checkFactors function until we find the correct answer. The first step we could take is a brute force approach as outlined below:

def bruteForce(factors):

    answer = factors[-1]

    while True:

        divisible = []

        for number in factors:

            if checkFactors(answer, factors):

                return answer

        answer += 1

This technique works quite well for the example given in the problem. For the range 1-20 however it takes ages. I left it running, boiled the kettle, made coffee, had a chat with my girlfriend's dad about the paper and it still hadn't finished. Clearly there is room for improvement.

We can speed it up by increasing the variable answer by the maximum value in factors each round of the loop. We know that the number we are looking for has to be divisible by 20. So we can eliminate the next 19 possible values straight away.

def bruteForce(factors):

    answer = 0

    increase = factors[-1]

    while True:

        if checkFactors(answer, factors):

            return answer

        answer += increase

I timed this method and it took Python just over 38 seconds on my dual-core laptop with 2GB of RAM. While 38 seconds falls within the one minute rule of Project Euler I still thought that there must be a faster way. Not only does the number we are looking for have to be divisible by 20, it also has to be divisible by 19 as well. 19 multiplied by 20 equals 380. So we can be even faster by increasing answer by 380 on each iteration of the loop. We can amend the function like so:

def bruteForce(factors):

    answer = 0

    increase = factors[-1] * factors[-2]

    while True:

        if checkFactors(answer, factors):

            return answer

        answer += increase

This time around it only took just under 2 seconds to produce the correct answer. However it occurred to me that for each iteration of the while loop the checkFactors function has to iterate over 20 different values and that a lot of the checks are actually redundant, because some of the numbers in the range 1-20 are factors of other numbers already within the range. For example:

2 is a multiple of 20

4 is a multiple of 20

5 is a multiple of 20

10 is a multiple of 20

If the value being passed to checkFactors is evenly divisible by 20 it is also evenly divisible by 2, 4, 5 or 10 so we don't need to check them. What we need is another function.

def findUniqueFactors(factors):

    ufactors = list(n for n in factors)

    for n1 in factors:

        for n2 in factors:

            if n1 == n2:

                pass

            elif n1%n2 == 0:

                if n2 in ufactors:

                    ufactors.remove(n2)

    return ufactors

When we call this function with the variable twenty the ouput in the interpreter is the following.

>>>twenty = range(1,21)

>>>uTwenty = findUniqueFactors(twenty)

>>>print uTwenty

[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

>>>len(uTwenty)

10

That means we have halved the number of values we need to check for each loop. So, lets put it all together!

def checkFactors(value, factors):

    """Returns True if value is evenly divisible

by all numbers within factors.

"""

    if value == 0: ## Because 0 divided by any number in Python returns 0.

        return False

    for n in factors:

        if value%n != 0:

            return False

        elif value%n == 0:

            pass

    return True

def bruteForce(factors):

    answer = 0

    increase = factors[-1] * factors[-2]

    while True:

        if checkFactors(answer, factors):

            return answer

        answer += increase

def findUniqueFactors(factors):

    ufactors = list(n for n in factors)

    for n1 in factors:

        for n2 in factors:

            if n1 == n2:

                pass

            elif n1%n2 == 0:

                if n2 in ufactors:

                    ufactors.remove(n2)

    return ufactors

twenty = range(1,21)

answer = bruteForce(findUniqueFactors(twenty))

print answer

When I timed this final version, Python found the correct answer in about half a second! While there still exist faster methods. I am more than happy to move on to the next challenge.

Behold, the plasma cannon mark 2

New this time around;

-- Options can fire in both left and right directions.
-- Particle effect when enemies are hit.
-- Even bigger particle effect when they die.
-- The plasma cannon has been reimplemented as a beam weapon.

I want more options....and a PLASMA WAVE CANNON!

Despite there being no update for a while I have not forgotten this project.

Here is a vid of my latest endeavours.



New this time around:
- Bit Mask for pixel perfect collisions
- Enemies can fire
- Player can die
- More power ups.
- The plasma wave cannon
- Two escort options that can shoot and remove enemy bullets.

Bigger and better guns!

As promised an update. A combination of Cam Studio and Youtube has absolutely destroyed the quality. The starfield looks tonnes better on my laptop.

Vid 1 - Better weapons for the player.



Vid2 - Collectable powerups.

USB broadband dongles SUCK!

I currently have at least two videos to upload, but I am unable to because of my crappy connection. As soon as I get near a real broadband connection I will be uploading and updating on here.

Animated Sprite

Another step in the right direction!!!!

An animated sprite! Obviously my animation skills are very very crude. However my girlfriend is doing the final year of her Masters in Animation. I can sense a "Honey, can you help me please. Pretty pretty please!" coming on! ;-)

What good are guns if there is nothing to shoot?

Did a little work on the collison detection for my side scrolling shooter. The code is not perfect yet, but it is another step in the right direction.

I want to shoot!

Here we have my next tiny milestone. A sprite that can shoot!

2D Scrolling Shooter - Pygame

Here is a quick clip of me tinkering with pygame and parallax scrolling...



...and here we have something similar to the video above but with a movable sprite!



I will be posting more videos as development moves along. I intend to tinker away trying to implement a single feature at a time in a test script. At least until I feel comfortable that I have the knowledge to glue it all together and make a shooter I can be proud of and is hopefully fun to play.

The scope of what can be done is daunting. For example...
- Collision detection
- Power Ups
- Multi Player
- Boss Fights
- Enemy A.I.
- Environments
- Port to XNA? iPhone? <--- LOL even if I knew how I wouldn't make an app for iPhone.

I'm not promising that I will implement anything into a final product, I am a hobbyist and don't code for a living after all, but I am going to try. Watch this space!

Until next time...

Peace

Big Grizzle