Grossly Annoyed by the new Sonic Ultimate Genesis Collection’s version of Space Harrier

So, I bought this for ONE thing.

Namely, the unlockable Space Harrier – one of my favorite arcade games of all time.

And guess what? The music & audio are all OFF. Something’s wrong with the pitch. Someone massively screwed up. It’s all off key. And it sounds like the bass-line may even be out of sync.

Oh, and the sampled speech? Too high.

Bah humbug. And this is even after I had to complete the first level of Super Thunder Blade to unlock the damn thing. Quite why I’d need to unlock it, I have no idea.

If Space Harrier is the only reason you want this compilation, don’t buy it. It’s like they got the wrong ROMs, compiled MAME, and then shipped it. Not only that, but there’s the occasional audio glitch on the attract screen which certainly wasn’t there on the arcade.

Oh, and it looks like (as with many versions of Space Harrier, including the Mame one) they’ve not got the gamma right.

*sigh*

Now if only the Sega Ages remake of Space Harrier would come out on the 360.

(more...)

Quick rules for Cache-Friendly Algorithms

Games programming on current architectures require that a certain amount of attention be paid to your algorithms to make sure that they’re cache friendly.

It takes a long time for a memory access to be brought back from a page that isn’t in the cache. And cache lines are getting longer and longer.

Interestingly, software engineers solved this problem a long time ago, with algorithms meant for databases with really really slow IO pipes, and disk sector sizes of anywhere from 128 to 1024 bytes.

Those sizes should be a big hint to any seasoned programmer; they’re similar to the size of cache lines in modern systems. Which means that we can take algorithms that were designed to work really well for those old systems and later discarded, dig them up, dust them off and use them to create really blazingly fast routines for handling in-memory data.

Everything that’s old is new again.

So without further ado, here’s a few recommendations:

Prefer M-ary trees to Binary or Red/Black trees.

M-ary trees store several keys per node. Binary trees only store one key per node. If you store as many keys per node as you can fit into a single cache line, you’ll benefit.

If data you need to search changes rarely, use Indexed Sequential Access

This is a bi-level lookup scheme. It’s related to M-ary trees.

If your data needs to be flexible and searchable, use B-Trees

B-trees are M-ary trees, but you don’t require that each node has M items.

If you really must use a hashtable, consider using Extendible Hashing

Extendible hashing combines the properties of B-Trees, Indexed Sequential access and Hashtables to help keep pages coherent.

If you need to do lots of data filtering, and then perform the same operation on each object, use a Gather/Scatter approach

  1. Filter your dataset using a given set of criteria
  2. Generate a sequential list of matching objects in scratch space.
  3. Prime the cache as you start processing the list, and keep pumping it every few objects.
  4. Generate a sequential list of results if further processing is necessary, or Scatter the results back out to the objects (priming the N+Wth object as you go; you’ll need to tune W based on the size of your cache).

Consider Batch Sorting Operations instead of Quicksort

Don’t use Quicksort. If you have a large dataset, you’ll quickly run into cache issues as it bounces all over the place. Use Merge Sort instead (look it up in Knuth if you don’t remember that one) – which also has the nice property that you can run it in parallel on multiple cores.

Shadow Your Most Accessed Data Inside Your Keys When Necessary

Store data you need for your most common comparisons alongside the pointers to the objects – make them part of your key. You can ignore that part of the key if you’re searching the database for anything else, and your most common operation will be optimized because you won’t have to hit a random chunk of memory to pull out the value for comparison. (Good candidates for this might include an NPC’s location and bounding-sphere radius, which could be stored alongside the pointer to the NPC itself).

Defrag / Sort your Data On the Fly

As you operate on data, if you keep a secondary buffer around, you can generate a new data set. At the end of the operation, you just swap the pointer to the first dataset for your new one. This massively reduces cache thrashing, and if you plan it right and your data is temporally coherent, if you perform a sort of the data each frame, you’ll keep most of it sorted naturally for minimal cost – it just kind of drops out in the mix. You can always perform this check as you go along, and only re-sort if necessary. (If you’re clever, you can even figure out if you just need to resort the current cache-line, or if you need to be more exhaustive).

Another advantage here is that your secondary buffer? You don’t need to synchronize on it. Your first buffer? You don’t need to synchronize on that either, so you can get MASSIVELY parallel. You’re performing something akin to finite element analysis on your dataset. The only time you need to worry is when one calculation affects the output of the other – but if you make a list of those, you can special-case them.

If you’re dealing with small chunks of data, go Linear

With small amounts of data, the cost of accessing main memory to pull it into the cache massively dwarfs the cost of performing calculations on the data.

So don’t be afraid to use bubble-sorts, or linear searches on data that’s tiny and doesn’t use indirection. Of course, use this in moderation, and test first.

Further Reading

Look up “Batch Processing Algorithms” and “External Searching” on Google.

Read Database books. I personally can recommend the “Inside SQL Server” books for ideas on how to handle slow memory access (just take anything that refers to disk IO, and replace that with cache-line).

(more...)

Playing with your food: More fun with Onomatopoeia

(This article is part 2 of a series)

Back to “Argh!” or “Arrggghhhh!!!!!”:

You can make an Arrggghhhh!!!! sound much more frustrated by mixing it up a bit. Try this:

Arrghghhhgghgggggghhhh!!!!

Although now we’re descending into the realm of sillyness, but it does kind of convey a blood-curdling (or at least, blood in the throat) scream filled with rage much more than even Arrggghhhh!!!!! does. The mixing of the g’s and the h’s swirl around as if one were gargling.

Here’s another trick I came up with a while back… How to make something sound as if it’s fading in:

He could hear it coming down the corridor towards him…

.         .        .       .    .   . .. ... .... ...t ..th .thu thud thuD thUD tHUD THUD THUDD THUDDD THUDDD THUDDDDD

It helps if you can keep it to a single line, but it’s interesting how this works. The number of spaces between the initial period drops by one for each one, until there’s none left. Then we get more periods until we hit the length of the word… then the letters start coming in, in lower case. Then, the uppercase comes in (which always sounds like shouting anyway), and then finally, alliteration of the final letter of the syllable which gives the word THUD its … well... thuddy sound.

The cool thing is, done right, this will pretty nicely convey something getting louder – or nearer. Visually at first it’s all to do with the space. You could go further than this with a little typography – italics would help convey more of a silent sound (the font weight is lighter), from which you’d go to a normal font, and then to something bold, and finally, use italics again for stress. Eg:

thud thud THUD THUD THUD!

… but it doesn’t work quite so well straight; you’ll need to mix and match. In the above example, the italics give a sense of surprise – like the thud is off beat, or unexpectedly louder – not a fade in.

So in closing… play with your words. It’s fun :)

(more...)

Playing with your food: Alliteration and Onomatopoeia for Pirates

What’s the best way to write “Argh”?

I guess it depends on how you’re using it. To me, “Argh” sounds like a groan, in response to a bad joke.

“Argh!” is a little better, but it’s kind of a suprised yelp more than anything else. A little like someone jumped up in front of you and smacked you over the head with a shovel – and then you drop. It’s curt.

I much prefer – if I’m going for some kind of blood-curdling scream as if all of your fingers got ripped off in some kind of threshing machine – something like this:

Arrggghhhh!!!!!

I was in secondary school when I started playing with words in this way. Something about the number of repeats of each of the letters works really really well in the word “argh”.

It works even better when italicized:

Arrggghhhh!!!!!

Now that’s a blood curdling scream.

Here’s where it gets interesting though. Any word which is meant to have emotional impact – or a sound – can be modified in this way. You can take regular words and make them onomatopoeical (sp?). Or you can even stress the hell out of them, and make them even more boisterous.

For example:

Howl becomes Howwwwwl

Growl becomes Grrrrrrrrrowl

Words convey emotion and images. They trigger memories. You shouldn’t be afraid to occasionally screw around with them for effect. The trick is not doing it so often that you piss your reader off.

(more...)

Short Story: The Beginning (part 3)

This is the final part of the short story I promised to post quite a while back (the last installment was in April 2008). When I get the chance, I’ll be ripping it to shreds… but for now, here’s the end of the story. Why did it take so long? I only had a hard-copy, but I finally found a CD full of burned docs including all of my old articles from various news-stand magazines in the UK! (Yay!)

In case you’re coming into this late, or don’t have the memory of an elephant, and the patience of Job, here’s some links to the First Part and the Second Part.


“Finally you wake” I heard a man's voice say. Slowly the world came into focus, and I could see that I was in a large, well furnished room with a tall roof and a wooden floor.

I was laid out on a large leather couch, a cushion beneath my head. Behind the man was a large wood fire, banked up and spreading its flickering glow throughout the room. Above him was a stag's head, flanked by two portraits in gouache. He was standing, wearing immaculately polished shoes on a bearskin rug, between two leather upholstered chairs pointed towards the fire.

"I do hope that you will not even think of trying anything as rash as violence - it would be most... " he paused "Inconvenient".

I did not feel I had the strength - nor the will - to even consider fighting him. And anyway... why should I? I felt confused, disorientated and suddenly so cold... so very cold...

Without conscious thought, I rose from the couch and started to move towards the warmth of the fire. My limbs moved with no input from my mind to make them do so - my body desired the warmth.

"Good." I heard the man whisper, as much to himself as to me. "My name is Alexander Potter, and I feel we may get to know each other a lot more ... intimately in the next few hours."

I moved forward faster, the fire's warmth inexorably pulling my body towards it, its incandescent glow dragging me onwards.

I reach Alexander, and stop. Standing where he is, he is preventing me from reaching the warmth... and then, inexplicably, I am no longer cold. I no longer need the fire.

He reaches down and tilts my head to the side, exposing my neck. And I realise what it is that is happening.

I try and break away, try to push him back, and I succeed, except it is not him that moves, it is I, stumbling backwards. I try and ask him what is going on, why is he doing this, but I cannot. Instead, I find myself moving back to him, tilting my head for him, watching him bend towards me, his fangs bared, glistening in the dancing light of the flames nearby.

Again I push away, but this time I am not able to break his grip. Again, my head tilts to the side for him, but this time I cannot break away from his grasp. Transfixed, as if I were an animal trapped in the gaze of its predator, I cannot do anything.

Incision.

Pain floods my neck, head and wracks my torso. I stiffen, my body spasms and my back arches with the feeling of the two intrusive needle-like points. Further in they burrow, piercing the living flesh below the dead skin, digging into the thin sheaf of muscle fibre and nerves, into my pulsing artery. White hot lights dance in my vision, as the artery is opened, my life blood spilling out of the twin channels broached by my captor.

His lips close over the open wound, teeth withdrawing as he sucks and drinks deep. His mouth curls into a gruesome smile, smearing blood over his cheeks and chin in the process. The pain, still incessant surmounts me, and as he drinks further of my very life essence, I thankfully grasp at the curtain unconsciousness lowers over my mind.

* * *

I awaken in a dungeon-like room. The walls are damp, the floor cold stone. In one corner straw is scattered. A long gnarled wooden table, soft and rotten, riddled with woodworm is in front of me. At the room's far end a small set of stone steps lead up to a large strong oak door, locked and bolted, the only opening being covered with a square of solid steel.

I feel incredibly hungry, incredibly thirsty and incredibly weak. There is no strength in my arms and legs as I drag myself up from the damp stones. On the table is a large plate, dressed with salad, upon which a large, prime quality steak lies. It is still steaming, its succulent smell and deep brown colouration causing me to salivate wildly, only increasing my thirst. A large pitcher full of water stands next to the food, light from a torch on the far wall dancing through the glass that stands on the table by the pitcher.

I almost run to the table, grabbing the pitcher and drinking from it eagerly. I vomit violently, water tainted with digestive juices and enzymes splashing over the damp stones of the floor.

Realising my error, I take a tiny sip of the water. But this is to no avail. Instantly, I vomit again, bringing the water back up from my empty stomach.

With a low groan, I tear a tiny portion of the steak with my teeth and cautiously swallow it, but within seconds it too joins the water on the floor, my guts not accepting what they cry out for...

With a cry of resignation, I crawl to the straw bedding in the corner, curl up in a foetal ball, and sleep...

... I wake to see a fresh, steaming steak on the table, the pitcher of water topped up to the brim. My hunger and thirst overwhelm me with their strength, I scrabble towards the table and bite then immediately swallow some of the steak, its odour tormenting my appetite. As before, the steak is propelled vigorously from my stomach, and as I look up, bent forwards by the force of my expurgation, I see my captor's eyes looking through the view-hole in the door.

"Look to the right of the door, Jeremiah - and make your choice. To eat, or to die."

Confusion wracked my mind as I looked where he had told me to. In the corner of room a bundled figure lay. I rolled it gently over.

To my horror, I found that it was my beloved, Kathryn. She lay unconscious on the floor before me, battered, bruised and broken. Anger filled my mind at what had happened; I shouted, a long primal scream of rage, "WHY???". Alexander's eyes looked on from the doorway.

"As I said, my dear friend, you must choose. To live or to die. To eat and survive, or to die from your hunger."

"What do you MEAN?" I screamed to him, but the panel in the door had been closed and bolted. Hunger overwhelms my anger and pity for my ravaged lover. I bite a chunk out of the steak on the table, sucking the juices from it in a vague hope of satiating my hungered, wanting stomach. Spitting the drained meat out, I lie next to Kathryn, hugging her gently, crying over her battered state.

Within a minute, I heave. The few drops of fluid fly from my body, flung with the sharp, crippling motion of my unrelenting body. Whimpering, hungry, thirsty, almost deadly weak I hold Kathryn in my arms, rocking her gently in self pity.

. .. .... .......... thud...... thud .......thudd ... thuddd... THUD.... THUDDD... THUD .... THUD......

The sensation, the noise permeates my body. The warmth of my lover's body in my arms, the relentless pressure of her heart, the sonorous ring of the blood running through her arteries and veins, her very life force that coarses through her body... The noise stifles me, paralyses my being. I bend down, lying her head in my lap, her neck across my thigh.

THUD...THUD...THUD...THUD...

Her neck twitches in time with the sound, the movement exaggerated by my mind and imagination... My hunger overwhelms me, the sound of her heart taunting me with its pounding relentless attack.

My mind detaches its control from my body, my very consciousness looking on in terror, confusion and disgust as my body moves and bites deep into the neck of my Kathryn, of the golden hair, the perverse raping and defiling of her body by my own, the destruction of the one I love the most by myself horrifying me... Yet still I bite, drawing blood...

The coppery taste of the warm, thick fluid overwhelms my tongue. I drink deep, the fluid sickening me as it flows down my throat into my stomach, stealing the life from my poor, dear Kathryn... More I drink, drawing the crimson liquid from her neck, satisfying my stomach as my mind reels, uncomprehending,
horrified at what it is that I am partaking in.

I drink deep, until my stomach is satisfied, and then, somehow knowing that I should stop, I release Kathryn, her body dropping to the stone with a thud.

I lick my lips, and wipe my mouth with the back of my hand.

Conscious action returns, and I weep. Uncontrollably I cry, not knowing why or what I have done, only that I have destroyed the only thing that I love. Then, mercifully, I sleep.

I awake, and Alexander is beside me.

"You chose rightly," he said slowly, "and she will probably recover, with the medical help I have provided for her. Probably."

“What have you DONE TO ME?" I shout.

"You are, as I am. A beast you are, lest a beast you become." He sighs. "It is an ancient riddle, yet it is probably the truest thing you will ever hear. And I am sorry to have caused you so much pain, so much agony, so much... well, it is over now and you shall never be the same again.

"I have known you and your family for a long time. I met your father in Africa - you will not remember me, you were too young. We made... an agreement. Anyway, come with me to the fire place. We have much to discuss, and no doubt you are cold and shocked from your ordeal."

He left the dungeon, and I followed him, my head in my hands.

* * *

(more...)

subscribe via RSS