Tech Report — Efficient Laser Bolt Collision Checks

I’m going to depart from my usual style of blog post and exercise my right to describe some technical stuff. This week’s topic is going to be about collision detection. It’s a massive topic, but for the purposes of today’s post, I’m going to focus on a very specific portion of Gateway’s collision detection system: how it handles laser bolts colliding with other objects.

Collision detection is potentially very costly, and the amount of collision checks between objects doesn’t scale linearly. The real trick is to discard potential collisions with as many objects as quickly as possible. In my attempts to reduce how often these checks had to take place in Gateway, I focused my efforts upon the most prevalent collision-enabled objects in the game world: the laser bolts.

In my game, lasers move very fast. We can’t rely on simple distance checks to determine if a bolt hits a fighter; the ordnance may very well simply ‘jump’ over the fighter and miss it entirely.

Simple distance checks will not suffice because the bolt moves so fast that it may skip over a potential victim

Simple distance checks will not suffice because the bolt moves so fast that it may skip over a potential victim, missing it

So, instead, we cast a ray between the old and new positions of the laser bolt.

As the laser bolt moves forward, our collision system performs a ray cast between its old position and its new one to see if it hit anything in between

As the laser bolt moves forward, our collision system performs a ray cast between its old position and its new one to see if it hit anything in between

This works fine, but we’re unnecessarily testing the ray cast against objects that fall behind the bolt. So, we discard any objects from the ray cast test that aren’t in its path. This can be done with a fast vector dot-product calculation and discards half of the objects we have to test against, on average.

Ray casting is expensive, so we should only test the objects that fall in front of the laser bolt's path

Ray casting is expensive, so we should only test the objects that fall in front of the laser bolt’s path

But, we can still do better than this.

Now, we’re performing these collision checks every frame. Even though we’re discarding a good chunk of the objects in our scene fairly quickly, that can still be costly in terms of pure iteration. These checks for discarding objects also consume resources.

Let’s think about this: laser bolts move really fast. Over the life of a single bolt (about one second or two), no ship is likely to change it’s position much. In other words, the set of potential colliders for any single laser bolt is fairly static throughout its entire life. So, why not just pre-compute a list of potential colliders at the beginning of the bolt’s life? This is likely to be a very short (or empty) list, and we can re-use it for every frame of the bolt’s life until it dies. In other words, we’re only computing the list of possible collision candidates once.

This page has some great code for a fast check to see if a point lies within a cylinder in 3D space. By specifying a radius wide enough to account for the fact that certain ships may cross the path of the laser bolt, we can use this to build a list of potential colliders that will remain valid until the laser dies. This list might only ever contain just a handful of ships out of hundreds, and will save our collision engine from tons of unnecessary iteration.

When a laser bolt is first spawned, compute a small list of candidates which we may collide against, and re-use it continually throughout the laser's life

When a laser bolt is first spawned, compute a small list of candidates which we may collide against, and re-use it continually throughout the laser’s life

In the image above, we can see that only two ships are within this cylinder. For that particular laser bolt, those are the only objects we have to check for collisions against. Pretty neat.

Of course, we’ve made a number of assumptions. We assume that the laser bolt is fairly short-lived and travels very fast. Slower or long-lived ordnance would necessitate the use of a wider cylinder, if we could still use this technique at all. Additionally, weapons that don’t move in a straight line (such as heat-seeking missiles) would present a problem. But for standard laser bolts, this works just fine.


May 18 — Where I’m At

Voice recording has begun! This is a very exciting step, as the voices for the characters I’ve imagined can finally come alive.

Now, the script is still awaiting some final editing from another source, so there may be the possibility of having to do re-takes to accommodate the changes. The reason I’m starting voice recording already is because I’m getting eager to move this game along!

Since the story is now more or less finished (barring some final editing), a lot of final decisions regarding Gateway‘s gameplay have been made. The campaign itself spans 11 complete missions, and there will also be the option of playing customized instant action games. During these missions, the player will face off against several types of one-manned fighters, a few varieties of cruisers, and even newly-added space mines.

There have also been a number of performance optimizations. Space battles can now be larger, and I feel that this is important when it comes to making the player feel immersed.

Don’t let all this talk bore you! Here are some screenshots to show you what to expect after a few more months of development.


Three outmaneuvered alien vessels face destruction from opposing sides.


The volcanic planet Grappley is visible behind the chaos.

The next while will be spent fine-tuning the game mechanics, eliminating obvious bugs, and integrating voices into the missions.


Some Case Studies

Game programming is something I’ve been interested in since I was about 11 years old. I started by making simple programs and games in Visual Basic. Shortly afterwards, I made my bumbling way into the world of 3D game development, and I completed many projects using DarkBASIC. All of my games were very simple, but this is the reason I finished them: they were small and built on well-established mechanics such as jumping, collecting treasure, shooting, or racing against time.

Featured below are a few of my favourite completed game projects from way back when. They were all made for my own amusement, and are all from a time when I could barely program to save my life. Or make game art. Or anything.

Goblin Stoppers


Jump from platform to platform as you try to escape the lava-filled cave. Home to baby dragons hungry for their first taste of goblin flesh, the cave is also rumoured to hold treasure that renders the finder completely invulnerable…

I consider this to be my very first fully-playable computer game. Its simple mechanics, combined with a small map size, made this project a reasonable first.

Space Havoc 1, 2, and 3


Fight for your life in open space against skilled pilots determined to prove their worth.

The first version of this space-based combat game was incredibly simple, and started to grow in complexity as the project matured. It spawned a total of three titles. There were a few attempts to make a much more complex fourth title, but these designs eventually became part of Gateway.

Cavin’ In


Fight against time to collect all the treasure in a maze from which no one has ever returned. Lava flows around every corner, while fire goblins lie in wait for their next meal.

The idea here was to navigate through a dark cave in search of treasure, avoiding lava and catching glimpses of scary fire goblins while a lightning storm raged outdoors. Again, this was a very simple game with a simple goal: run through a large maze collecting items as you go, before time runs out and the cave collapses.

Space Fire


Use an assortment of weapons in a deep-space duel to the death. Only one of you will survive.

This was a two-player game, where each player had an assortment of weapons (laser bolts, laser charges, and missiles) with which to kill each other. Players could also take cover behind the asteroids (which could be destroyed, too). Unfortunately, no one ever played it with me more than once, because I was too good at it.



A twist on a classic sport, Shufflespace puts a 23rd-century spin on a well-known game.

The goal of this game was to aim and shoot a laser from the far end of a shuffleboard, and take down all of the miniature aliens at the other end. The alien formations could be customized, and the game even supported something called “live mode”, where the aliens would walk around at random, making them more difficult to hit.



Lost in a frozen maze, you find yourself attacked by vicious monsters that have made the cavern their home. Armed with only your wits and an ice-spewing gun that freezes everything it hits, only tenacity will ensure your survival.

This game didn’t have any time limits, but there was one important constraint: your gun had limited energy and depleted quickly as you fired. Energy crystals found within the cave would help to replenish its reserves, but most of them were guarded by the locals.

Water World


While not technically a game, this partially-submerged cavern was a good way to test various environmental effects and AI behaviours. Rumour has it that deep within the depths of the stone fort inside, mysterious life advice lies scrawled upon the ruins.


Mar. 29 – Where I’m At

This will be a quick update*, but an exciting one — the story for almost all of the 11 in-game missions has been written! All that’s remaining before final script editing and voice recording is just to finish up the dialogue for the last few. I expect I’ll have the last missions fully scripted by next week.

I have to admit, I’m incredibly excited about moving forwards to the recording stage. Several folks I know have generously offered their acting abilities, and I think that they’ll all fit their roles well. Here are some short descriptions of the main characters in the game, who will often be flying and fighting alongside the player.

Col. Warren Matthews
An uncomplicated, straightforward commander. A serious man with very little sense of humour. His people come first, and the mission comes second.

Lt. Andrew “Rig” Nash
Usually second-in-command during missions. Younger and more energetic than Matthews. Primary concern is for his wingmates and subordinates. Terse and forward, one gets the impression that he’s suffered a few scars, both literally and figuratively, over the course of his career.

Ensign Kesha Orr
Fresh out of the training program, Orr’s level of experience is similar to the player’s. Usually the first one to point out new things or ask questions.

Ensign Adam “Belt” Brennan
Second in experience only to Nash. Likes to tell jokes and stories from his past. His ill-timed bantering often attracts negative attention from his superiors.

These descriptions might change slightly throughout the editing process. A lot has changed from the original story already, but I wouldn’t want to spoil anything yet…you’ll get to play it yourself when I’m finished.


* Sorry, no screenshots this time. I’ve recently suffered a hard drive failure and have yet to re-install the libraries needed to run Gateway on my (now fixed) machine to take some new screen grabs. Fortunately, I didn’t lose anything. Cloud storage is your friend.

Finish or Fail

I have a list of unfinished projects as long as my arm. It’s taken me a while to develop the discipline necessary to see my goals through to the end. So, this week’s post will be all about the various causes of project failure that used to plague me, years ago.

Of course, this list is not exhaustive, nor are these categories mutually exclusive. Readers are more than welcome to contribute their own insights.

  • Feature creep. This one hardly needs explanation, and has been the bane of my existence more than once. Too many times have I been unable to resist the pull of flashy features that only served to broaden the scope of my project to such a degree that I could not possibly finish it.
  • Massive changes to the system. A particular game called Wing comes to mind. (This was, in fact, yet another precursor to Gateway.) I had a nearly-finished game engine, support for exciting environments and missions, and a story ready to go. My younger brain thought that it would be a wise idea to upgrade the core graphics engine I had written to something more modern. Instead, all that ever became of Wing was a whole lot of shader bugs and rendering issues. While I could have easily reverted to previous, working versions, I had become so disenchanted with the problems I was having that I ultimately dropped the project. (Fortunately, a lot of the AI and flight mechanics code now reside in Gateway, which has saved me a lot of duplicated effort. So, it wasn’t a waste.)
  • Lack of design. This was an important lesson to learn. Many of my failed game projects began with visions of flashy graphics, advanced particle or rendering effects, or even a single unique gameplay mechanic. Having not given any thought into these projects other than, “this feature is going to be really cool”, they were, of course, doomed to disappear, not having a drop of substance. Since then, I’ve learned that quick, graphical demos are a great way to showcase flashy effects, and that you should have a solid plan in mind before touching a single line of code.
  • Lack of commitment. Being a game dev hobbyist means you’re free to work on whatever you want. I’m constantly being harassed by new and exciting ideas, even as I work on Gateway. Even a well-planned-out game isn’t guaranteed to be completed if you can’t pick your projects wisely. The trick is to choose something that you know you can complete. Initially, this should be something simple, and as you gain experience, you can take on the big ones.
  • Too much commitment. Or, in other words, learn how to take breaks. Your game isn’t going anywhere. Contrary to popular belief, your passion for your project will not dissolve if you set it aside for a week. In fact, you’re likely to return to it refreshed and excited as ever. Constantly pressuring yourself to work on it without disengaging for a while is a sure way to get sick of your project real fast, in favour of some other shiny jewel.

Originally, my failed project, Wing, was about a group of young anarchists trying to buck the system and disrupt a benign, powerful empire simply for fun, when things get out of hand and they find themselves being actively hunted for their increasingly risky crimes. For your viewing pleasure, here are two screenshots. The resemblance to Gateway is fairly apparent if you look closely.

Three established friends test the player's ability to face intense combat odds.

Three established friends test the player’s ability to face intense combat odds.

The player dives low to avoid being caught on radar.

The player dives low to avoid being caught on radar.


Deliver the Difference

Several years ago, I began work on a project called Space Havoc 4, but never completed it.* During SH4‘s development, I had a relevatory experience.

You see, around that time, Bungie had just released Halo Reach. Being (somewhat of) a Halo fan, I checked out the reviews and screenshots to see whether the game was worth my time. It looked good, but my heart sank when I saw screenshots of Reach‘s space-based missions.

It took a little bit of introspection to figure out why. It was a silly thing: what I felt was a bit of jealousy combined with the disheartening feeling that whatever SH4 would turn out to be, it would not compare to what a major game company could produce.

In any case, I got a copy of the game. When I finally got to the space combat missions, I was pretty excited to see if they would live up to my expectations. To be perfectly honest, they didn’t. While the graphics and mechanics of play were polished (as always), it wasn’t terribly fun for me. This is probably because I was expecting epic space battles with tons of battle cruisers and hundreds of ships — while I have no doubt that Bungie could have delivered on that front if they had wanted, they chose not to.

So, in a way, hope still remained. I felt that I could produce something more fun, mostly only because the gameplay of Reach‘s space combat didn’t blow me away. In other words, there was room for improvement, and I didn’t feel “threatened” the way I had before. To be honest, I suspect that this will always be the case: the unique visions I’ve had for any of my games (either completed or not) have never been duplicated in any commercial games I’ve ever played. Is this just dumb luck, or is it because no two games, even with the same genre and similar appearance, are ever the same?

While I can’t speak to how many hobbyist game developers might have given up on a project because they feel they’ve been “scooped”, I’m sure many have experienced the same feelings I have regarding this issue.** I’ve since realized that these emotions are entirely uncalled-for, if only for the simple reason that no one — big-time company or not — can make the exact vision of what you want to see come true except for yourself.

Don’t put existing games up on a pedestal. Don’t be intimidated like I was. Challenge existing games and find ways to make them better. This should be a constant exercise. Nothing is above criticism. Everything can be improved. Your vision is unique, and the world needs to see it come to life.


*  Fun fact: little did I know that this failed project would become the precursor to Gateway.

** For the record, Space Havoc 4 was never completed not because of the Halo Reach incident, but simply because I couldn’t figure out the mechanics of various aspects of gameplay, namely the space gates, how they work, and how to destroy them — a problem I’ve resolved in Gateway.

Feb. 16 — Where I’m At

If it seems like it’s been a while since my last post…it’s probably because it has. Mostly, this has been because I’ve been busy actually working on Gateway instead of writing about it. There’s been tons of progress, but it can all be summed up in a single phrase:

The first mission is now complete.

Okay, it’s only the training mission, but that’s hardly important, since getting to this point required pretty much everything to be complete enough to support a mission with dialogue, basic enemies, props, etc. Scripting out the mission has uncovered a lot of bugs and “features” that have appeared since I last tested various aspects of gameplay. Thus, the list of things I’ve completed has mostly consisted of: “fixed a bug here, corrected a segfault there, etc.”

A few non-technical items have been addressed, as well. Several models and textures have been improved, for a better look and feel. While I recognize that I’m not an artist, I’m always open to improving something if I think that I can.

Right now, I’m at a very important stage in Gateway’s development: developing the story. I’ve always had a rough outline in my head at any given time, but the real work now involves scripting out every mission and piece of dialogue, in order to figure out how many voice actors are required. Several family and friends who I think would fit some parts well have already volunteered their time, which is going to be immensely helpful. I also have a few play testers lined up. (Not to mention that a couple of folks have already tested the tutorial mission and have given some very useful advice.) Thanks, everyone!

I’m incredibly excited about what’s going to come next. Seeing my game finally come to life in this way is rewarding and, at the same time, very nerve-wracking. What if some vital features are missing that could make the game more fun? What if it’s just no fun at all? I suppose these are normal fears. Whenever they happen to pop up, I usually just think something like, “Shut up. It’s either a half-complete game with loads of features, or something more minimal that’s actually finished. You can’t do it all.” Sound advice, if I do say so myself.

The other issue to consider is that of play-testers. If my game sucks in any way, I’ll just have to trust them to be honest. Then it falls on me to find a way to improve things. The only thing I can do now is just carry on forward.

Before we part ways, here is a screenshot from the tutorial mission. It shows some space stations, colossal gates, cruisers, fighters, and a little dialogue from the (later ill-fated) Col. Matthews.

The player is greeted by Col. Matthews as they enter the training sector.

The player is greeted by Col. Matthews as they enter the training sector.