Latin Invaders

Leave a comment

I present you Latin Invaders. This was for the Adelaide University Game Development Club – Third Game Jam in 2010.
It took about an hour to adapt the existing code base I had from Space Invaders to fit the theme "Every Letter of the Alphabet"

Story
The Latin character sets from the planeta Marineris.
You are the last line of defence and must shoot them out of the sky.

Theme Usage
I choose instead of using the theme in a subliminal manner to go for the superliminal manner (superliminal is a word from the Simpsons)

How to Play
Left Arrow Key – Moves Left
Right Arrow Key – Moves Right
Space Bar – Fires

Download
I will post a download to the source and Window Binary at a later time.

 

Development

The first step I took was in the InitGame function where it loads the graphics for the Invaders, arrays of SDL_Surfaces were setup to hold the sprites for the Invaders, and setup a for loop to populate this, then changed the existing loading to instead just refer to the some sprites in this array for testing to ensure it rendered correctly. There were 3 structures one for the top set, one for the middle set and one bottom set, which held onto the frames for the particular type of invaders (since there are 3 types). Upon simply commented out or deleting it showed all the use cases. I realised that I could improve the system, I had originally had 2 arrays one for frame 1 and one for frame 2, then I simplified it to be vaderFrames[2][26] but upon realising the structure mentioned earlier took an array of SDL_Surfaces which are the frames so changed it to do vaderFrames[26][2] this allows  it to just go theFramesForVaderZ = invaderFrame[25];. The structure was removed and the code was simplified so each Vader Instance (which has weather its alive or dead), also held a pointer to the frames, which is what the theFramesForVaderZ really is its more invader[25].frames = invaderFrame[25]. That was it, just  fixed hte rendering code to use the new array. The next step was to replace the loading of the player and bonus ship graphics with text instead for added effect.

Cleanup on the data files were performance to removed the unused graphics, since the Bonus ship, invaders and the player graphics were now text based.

Since I had done all my development so far on Microsoft Windows with Visual Studio, I decided to boot up Canonical Ubuntu in Oracle VirtualBox, and quickly found there were a few problems with the Makefile, the first being it always produced SpaceInvaders.exe, so split this into two parts TARGET and EXT (these are variables), the TARGET would be latininvaders and on Windows_NT the EXT would be .exe. The next problem was the run target, on windows launching it with Release\latininvaders.exe is fine but on Linux it should be ./Release/latininvaders so added the RUN command to the if def and yes it uses TARGET and EXT variables.

I was planning on changing the background image with one generated from text but lost motivation and just wanted to get this little project completed. I then ran Radical Image Optimization Tool over certain images to make them smaller. It was quite successfully reduced entire size of all the images and the font to be half the file size of the background image original was. Very nice tool, that I recommend as it features a preview which you can zoom in so you can see the pixels closer to see the differences.

Yet Another Space Invader Clone Progress Update

Leave a comment

This update is very long overdue, the text actually has been sitting in a text file on my computer for quite some time.

It has been a while, currently waiting for a bed to arrive so decided as good as time as anyway to work on my Space Invaders game. A couple of nights ago I did do some work on it, I replaced all the menu graphics with ones Izzy and myself made. I also replaced the bullet and your turrent with ones I made.

My goal for this session is have the bonus ship that flies across the top from time to time, implemented both
in the movement code to allow it to fly as well as the
being able to shoot it. I spent a few moments making a sprite for it using the same style of the turrent

I don’t currently have internet at home/ on my computer so my ability to code is some what reduced.

The idea for handling the when the bonus mothership appears is on start randomly generate a number and store it, and find the perfect spot to decrement this number in, so when it hits 0 then the ship will appear on the screen and travel across it. Considered doing the seed based on time but really not that fussed. The formual I went for in the end was invaderBonusSpawn = ((RAND_MAX – rand()) >> 4) + 400; and then settled on invaderBonus.spawnCount = ((RAND_MAX – rand()) >> 4) + (1000 % rand() );.

Some slightly intresting trick I did is the movement of the bonus ship moves by generating a random number if it is even it will increment the ship by 1.
Comitted my work, at this stage i have spawning, rendering, translating of the bonus invader implemented. The next part is collision detection with the player’s bullet and if detected then increment score and set invader to dead. All up took me about 35 minutes. Most of which was spent playing with the velocity of the bonus invader and the spawning.

The collision detection part was a whole lot easier only took about 15 minutes all up, just required me to track where the collision detection code for the bullet occurs, add the apporiate if statements, and then if it is the bonus ship set the bullet/ship to dead, and increment the score and reset the spawn counter for the bonus ship.

Now for a quick summary of things to do to truely make this project complete is allow the invaders to shoot down at the player, and also implement the shield blocks so you can hide under, and shoot through, and also have them discitergrate when the invaders move through it.

As it stands the current media assets are 1.4MiB, the executable is 16.5KiB, and third party libraries (SDL) are 994KiB.

Okay Nexus will take a look, mainly just used it as a project to figure out ways to setup and use SDL, and how to structure some things, and was just aiming to replicate the basic game play.

Summer Project – Day 8

Leave a comment

13th of January

Due to the previous heat wave, I slept past my alarm and didn’t get in to uni until about 11 am. There are a couple of hours missing, since I didn’t want to take a break writing it up, and never got around to it that night or the next day.

An aside, I got close to having a working gentoo arm system setup on the machine, could run busybox and bzip2, I produced a 1.9GiB file from /dev/urandom, so the compressor would be put through its paces trying its best to compress random data. At first i mucked up and accidentally used /dev/zero by accident which results in, not a lot of work load. The test lasted for approximately 70 minutes, with the Augmented Qemu taking about 5 minutes slower. Both were run against the same data.

The specific results for this run was:

	[donno@qcore1 Tests]$ time qemu-arm -L /opt/gentoo64/usr/armv7a-softfloat-linux-gnueabi/ bzip2 -9 compressimage.bin
	real	73m35.599s,	user	72m57.410s	sys	0m9.324s
	[donno@qcore1 Tests]$ time ~/Research/qemu-async-llvm/arm-linux-user/qemu-arm -d in_asm \
		-L /opt/gentoo64/usr/armv7a-softfloat-linux-gnueabi/ bzip2 -9  compressimage.llvm.bin
	cpu_loop called, instantiating LLVM thread...
	real	78m31.286s	user	77m41.695s	sys	0m8.332s

Andrew recommended cscope which is kinda like grep but with C/C++ specifics, so I installed that on both machines, but didn’t set it up.

Next I setup a branch of ‘qemu-async-llvm’ on gitorious.com, where Joel, had already created a project, and uploaded Andrew’s work so far.

Ended the day with installing three different C/C++ for Linux, to see which will provide a better environment then terminal for make and scripts and gedit and started the download for the spec benchmarks going only to have it fail at 1 am, whilst i was sleeping.

Summer Project – Day 7

Leave a comment

12th of January

Started the day by working on cleaning up the runTests script, to remove the old for loop per (test, qemu-version) since testRunN takes that. Granted currently there is almost more lines of comments to lines of actual code so it kind of looks messy still.

Thinking for the future, think I will extend it to support, running comparison tests (well both llvm version and 0.10.6), and then single version, as well as run tests individually. As well as support for a post test action, such as invoking an analysis script.

Some ideas for analysis scripts are:

  1. Instruction Usage – count the number of each instruction used in the input asm
  2. Compare the Instruction Count – compare number of resulting instructions in qemu and qemu with async
  3. Produce Time Plot – produce a graph of the runtime of the tests with the different versions of qemu.

Made a start on the instruction usage script, made a simple finite state machine, with some added improvements to get the lines of code/ duplicated, so can successfully parse a Qemu log file. Next will get it to strip out the instructions mnemonics.

Brad stopped in to the labs for a brief chat, for ideas and to check on the progress. He mentioned that for by the up coming meeting I should have been able to replicate the results from Andrew, and learn about how Qemu instruction cache work and how it is stored, as well as an understanding of how the chaining process work, and raised the question of does it only work on unconditional statements or can it do handle conditional branches.

Instruction Usage

11535 ldr
2912 str
2892 add
2815 cmp
2793 mov
1627 sub
1139 beq
1086 bne
1025 lsl

Ends up the lab machine, that I had my eye on turned out to only have 32-bit edition of Fedora installed, which makes it unsuitable for this project, Brad and Yuval was going to sorting out getting it re-imaged with 64-bit. In the meantime, its still down to using my laptop for now, and it has got me this far already.

Looking over the code, and discussing it with Andrew, who explained over a few of the finer points. The first thing, that sparked me was what was the requirement for the the x86_64 disassembler used for, traced down a use for it in llvm_translate for x86_64_function_size and x86_64_block_disas. Looking over the function_size as Andrew first prompted what it is doing is quite simple and ingenious.

I have the machine, I decided to spare Yuval the time, and decided since I would be using it I would install Fedora 12 on it myself. Once up created, an account, and set-up the proxy. To do this I choose first set-up a proxy server on my laptop which then forwards to the university proxy. The main reason for this is it means my user name and password for the university proxy, is stored on my machine. Then set-up yum and Gnome to use my machine as the proxy. Success, I could then install packages and upgrade the system.

At the same time as setting up the test and development environment for AQ, I setup the Gentoo portage.

	# For /etc/make.conf so it uses the internode mirrors for free traffic at uni
	SYNC="rsync://mirror.internode.on.net/gentoo-portage"
	GENTOO_MIRRORS="http://mirror.internode.on.net/pub/gentoo"

	mkdir /opt/gentoo64
	cd /opt/gentoo64
	wget http://mirror.internode.on.net/pub/gentoo/releases/amd64/current-stage3/stage3-amd64-20091231.tar.bz2
	tar xvfj stage3-amd64-20091231.tar.bz2

	chroot .
	# modify the /etc/make.conf to be correct mirrors
	emerge-webrsync # since this one works with http proxy by default emerge --sync will use rsync so a pain
	emerge -av crossdev layman git subversion lzma-utils
	emerge -av crossdev-wrappers # this on amd64 is masked

	crossdev -t armv7a-softfloat-linux-gnueabi

	Not the guide I used the first time on my laptop but close
	http://www.mohdshakir.net/2006/11/29/building-a-gentoo-and-debian-chroot-environment
	I used the guide on the gentoo website.

qemu-async-llvm Compiling

    # prereq: llvm 2.5
    wget http://llvm.org/releases/2.5/llvm-2.5.tar.gz
    tar xvfz llvm-2.5.tar.gz
    cd llvm-2.5
    ./configure --enable-optimized
    make -j5
    sudo make install

    wget
    tar xvfz udis86-1.7.tar.gz
    cd udis86-1.7
    ./configure
    make
    sudo make install

    # checkout sources and configure/make
    git clone http://git.gitorious.org/qemu-async-llvm/qemu-async-llvm.git
    cd qemu-async-llvm
    ./configure --target-list=arm-linux-user
    make

For future – should only require llvm on x86_64 Linux (that is what its been developed on), two the dependencies for llvm and udis should be checked and able to disable our llvm support.

Summer Project – Day 6

Leave a comment

Week 2

11th of January

Started the day with a brief chat with Brad, who mentioned that the if all goes well the money will be sorted by this week, and also reminded to chase up Yuval again with respect to access to the quad core machine.

I spent the morning reading over the output assembly for the qemu and qemu with llvm, and realised that the assembly output from the llvm version was a lot longer then the standard qemu version. I looked into that for a while at first I thought I had labelled to files wrong way, then saw that the appropriate one ad the generated and replacing statements that only Andrew’s LLVM version has. Next I decided to check what the benchmark timing, and yes, there was that relation of instruction count to run time, the standard qemu one ran faster. I was confused as I was sure, Andrew had seen benefits. At this time I could not contact him, and wasn’t until late in the afternoon he confirmed that this was typical, and that the table in the thesis confirmed this.

In the meantime, there were two other tests I wanted to run (well one new test and one observation from the results of ones I had perform. The first was if you run qemu-arm multiple times will it indeed always produce the same output assembly, similarly with the llvm version. My thoughts would be yes for standard, but maybe not for llvm. Since qemu would always see the same code and apply the same template, where as llvm it depends on when the optimization thread is run, and when its replaced.

The results from this is standard qemu was how I thought, the only difference in assembly output was that the memory addresses were different. The llvm one was the same, the output code was the same, the added difference was where the lines saying generated and replacing were. The Other test I performed was to make sure the reason i was getting the results above (llvm version being slower), was not due to improvements in qemu-arm since 0.10.6 which qemu-async-llvm is based. So grabbed the source code for 0.10.6 compiled it and conducted the same tests. The results from this was the same as if you run the tests multiple times with qemu (the memory addresses were the only thing that different).

As additional step for further exploring and possibly more test cases, I setup a stage3 Gentoo for arm (extracted the system) and attempted to use that as the base path (-L) and binaries from that and the existing test binaries. Ran into problems with that it would just sit there with no output and seem to be doing something but not show anything. I used debootstrap (which is similar to above) but it pulls packages from the the internet. Same problem with that. I then stumbled on the useful strace tool, strace is a tool for tracing system calls and signals, so it can show you what system calls a given program is making.

Using this, it showed that qemu-arm was trying to open /opt/arm/dev/fd/3/dev/fd/3/dev/fd/3/dev/fd/3/….., and recursively going up, searching for files. Brief search on the internet, found this was a common problem, one that had since apparently been fixed, since 0.10.x, however I think this scenario was not 100 percent the same to the one described in the bug report (http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=297572), to solve i just deleted the dev directory, and presto it worked. It does however seem weird behaviour that its searching like that, but anyway, it worked. That fixed both the gentoo and Debian version.

debpackget – Script

The last thing I worked on was more a side-project of mine, that had an application for this project. A script for grabbing a package for Debian, that didn’t rely fully on dpkg/apt. Quite simply it grabs the page http://packages.debian.org/\$DISTRO/\$ARCH/\$NAME/download then finds the download link from the mirror we want, so http://ftp.au.debian.org/debian since this is free quota at the University. I then set it up to wget it. Thinking of it as I write this a bash script could of done, by wgeting the download page to tmp file, greping/awking the temp file for the download link, followed by another link. However I wrote it in python so it can be expanded, will probably drop the wget dependency (uses system(.)). Then I coupled this with a call to run dpkg-deb -x \$filename \$outputpath, so it can extract the deb file into the appropriate location. This is not the right place for further discussing this but, it the best place for me to write it down and have it tied. New features:

  • Grab the sources for packages, and extract them (like apt-get source packagename), but not limited to a Debian host
  • Command line options for specifying the destination path, arch and distrbution
  • Switch wget usage to use pythons file downloaded. (Done)

Summer Project – Day 3 to 5

Leave a comment

6th to 8th of January

Day 3 – 6th of January

Freed up my Windows 7 partition, by copying files over to the other one, and installing Win7 into a VHD (virtual hard drive image), and then I installed Ubuntu 9.10 AMD64 from DVD. Then proceeded to install the required packages on the machine to build qemu-async-llvm. I wrote this entry about a week or two after doing it so I am not sure what i did do. but most my time was installing Ubuntu then installing the packages again and copying over the source and trying to compile.

Day 4 – 7th of January

Entries for this day were not fully kept.

Upon searching for something in LLVM on Google, I found a paste-bin posting, which matched the output from the Makefile for this project, it was missing udis86 libraries, I then tracked the submitter of the post since he had attached his user name to it, and found him on IRC (Instant Relay Chat), started talking to him about it and he mentioned he was trying to get it to work with LLVM 2.6 which is what I had been using, he (Joel) was able to get me in contact with Andrew, and we all got talking about it. Andrew sent me the binary for the sjeng benchmark, using LLVM 2.6 this crashes however using LLVM 2.5 it does not. To save time mucking around fixing the project to work with the new version, we decided it was best to just use the old LLVM 2.5 since its still accurate and there should not be any major performance increases from using the newer version. Andrew also sent his source code notes which detail the executing path as well as where some things are located in QEMU and the most useful piece which is his diary that he kept and detailed his progress in. The diary is easier to understand then the thesis and adds extra information about the problems he ran into and how he overcome them. We also had a brief discussion on what I was currently working on and what my direction was at this point.

Day 5 – 8th of January

No entries for this day were not kept. This ends Week 1 of the project.

Summer Project – Day 2

Leave a comment

5th of January
Still unable to get it to run, I met with Brad (my supervisor) before the meeting with ASTC was scheduled and inform him about the problem I had. The problem being the lab machines were 32-bit so was the Linux on my laptop and that qemu-arm required super user access. He problem found a 64-bit quad core, that postgraduate student was using, in their research and requested that I have access, and also as such, access to to the honours labs. Brad and myself, went and meet with developers at ASTC at there meeting room. They discussed their ideas onto what my project could entail. It was decided that continuing on with Andrew’s work, would be most beneficial, since there is still plenty of ideas to expand on and research. and using it as a base to expand on is the logical idea, and would have been a waste of the implementation had it not been used. There where four main ideas and points of interest that they were most interest in looking into.

  • Instruction Set Expansion
  • Statistics/Comparisons
  • Off-line Translation
  • Translation Block Chaining

Instruction Set Expansion

The simplest and basic idea for something to look into, is the result for implementing a couple of more instructions to see if additional any significant performance can be squeezed out by doing the next five to ten percent of instructions.

Statistics

Run a series of tests to compare the efficiently and speed of different software. This would also be beneficial for finding the areas where some programs do additional things to get better performance.

Off-line Translation

This idea is apparently where StimulARM is strongest, the idea, is you take the translated blocks and cache/store them while the program is off-line, so when you rerun the program it can load it back in and run again. The ideal use case for this is for development, if the related blocks are indexed by a kind of checksum based on the original arm instructions, then if you change a line in a program and recompile, the code generated should be the same for all but that little part you changed, this the next time you run it would be faster. I am not sure if there was also the suggestion of optimizing off-line, I believe it was hinted at but not really discussed. Where the idea is you run the optimization passes while the program or library is not running.

Translation Block Chaining

This is the big idea and most appealing, being able to collect up blocks up blocks together so you can build a larger block out of smaller ones, then send the whole thing to the optimizer. The reason for this is the more code the optimizer can look the more informed it is to make better improvements to code.

Older Entries