The HK Sentry

This project arose when, for various reasons, I decided to revisit the single player mode on Garry’s Mod. I hadn’t done this in many months due to some mod or another breaking it. But when I cleared out my unnecessary mods, it spontaneously started working again.
In any case, I chose to load up a map I hadn’t played on in many years, gm_zombieforest. The basic premise of this map is that you are a survivor of sorts who has ventured into a box-canyon full of trees, mud, leeches and zombies.
You must survive the resultant battle using anything available. The map is intended to be played on Garry’s mod, but players are expected to limit themselves to the map resources rather than using the tools and spawn-lists available. Needless to say I’ve never bothered with that way of playing.
My goal when I replayed it was to build some form of contraption specifically to protect me while I built more interesting things. Soon this project got a great deal more interesting than my “more interesting” projects were.
Initially, I chose to build a floating sentry turret, essentially an NPC tracking gun turret which would fly through the air, this was the core concept behind the drone. But rather than being free-flying per-say, I wanted it to stay close to me (but out of my way) so I made it keep at a set distance from me. The drone was effective, but because it had such a limited circle of operation, it couldn’t adequately protect me from the large numbers of zombies and head-crabs. So I chose to cut it loose and let it do its own thing. This rapidly expanded the requirements of the drone. I now had to develop a rudimentary Agent program to let it handle the various problems in its path. Its features would include:

  • Target Acquisition – it had to be able to find the targets nearest to me and terminate them before they got too close
  • Turret Aiming and Fire control – obviously it had to be able to aim at a target and decide that it was appropriate to fire, this would entail knowing the appropriate direction to point, working out the rotational math (done with Quaternions) and rotating to face that direction. Also it would need a system to know it was going to hit its target, I chose to use range.
  • Movement and obstacle avoidance – the most complex single part of the program, I had to find a way to navigate through the dense forest environment without getting hung up on trees.
  • It had to be efficiently programmed – else it wouldn’t be suitable for online play, and I just can’t abide not being able to show something off for the lag it produces.

Obviously a fair few challenges, some more complex than others.
As is normal for my drone projects, I started out with the basic mobility and expanded from there. I made it using a ray-trace directed at the ground beneath it so that it would be able to tell where the ground was (and how high above it the drone was) from there I was able to make it use applied forces to maintain a set altitude. I messed with the altitude controls a fair bit looking for an optimum solution and eventually settled on approximately two meters off the ground. This way it wouldn’t collide with smaller obstacles, but wouldn’t be caught in the branches of the trees.
The branches of trees would make a much more difficult obstacle than the trunks. Even with this altitude, there were still trees in the environment which had lower branches, the drone still had to encounter these however the obstacle avoidance mechanisms generally allowed it to bypass this.
Generalised movement was accomplished by a velocity feedback system. The drone would increase or decrease forces based on its velocity vector in comparison to a desired vector. This system was intended to provide a smooth and controlled movement rather than making the drone zip around the map at high speed, bouncing off everything in its path. I experimented with the ideal velocity a fair bit to find one which maintained that sense of menace and kept the speed necessary to intercept fast zombies and fast head-crabs (which, as their name suggests, are quite sprightly)
Obstacle Avoidance
Very complex problem, the environment as has been noted was studded with trees and similar obstacles, the drone had to be able to avoid getting hung up on them as it tracked targets, this was a huge irritation early on as I spent a great deal of time running after the stranded drone through the crowds of zombies in order to dislodge it from a bush so it could do its job.
There were a number of ways I could have done this.

  • I could have fitted a ray trace system to identify obstacles in its path and apply a force directly away from them, allowing differences in vectors to make the drone slide-around the tree. Advantages would mean that the drone reliably doesn’t bump into anything; disadvantage is that the vectors would cancel one another out partially and the drone would slow dramatically down. This meaning that any collisions would act as a speed-bump for the drone.
  • I could have created a digital map of the level which the drone would reference, using for example, A* Pathfinding Algorithms to navigate, this would be the most technically challenging for me as I am not very familiar with Pathfinding in general. This would entail my learning A* Pathfinding algorithms, figuring out how to apply them to this drone, and constructing an accurate map of the level for the drone to use.
  • What I actually did, I allowed the drone to collide with trees, but watched the velocity vectors, if the difference between desired and actual velocities was too great, the drone would apply a sine-wavoid lateral force which would in virtually all cases, dislodge the drone. This oscillating force typically meant that the drone’s collision was almost immediately followed by a lateral movement around the obstacle rather than getting stuck or spending any time at reduced speed, it was more efficient in code than either of the other options as well. I am justifiably proud of this method. Its key disadvantage is that it doesn’t allow for obstacles trapping the drone in such a way that the only way out is back the way it came. In these cases the drone would rely on its target getting into a position where the drone attempts to go back the way it came. This is quite likely to happen under most scenarios but on this level, there were no such areas, only rough cylindrical obstacles (trees) studding the area at wide intervals.

Target Acquisition
A fairly straightforward system, using the inbuilt functions, I was able to run a find function on all entities matching certain parameters on the map. This produced a list of NPCs in the form of an array. Using another function I was able to reorder the array by distance; the first entry therefore being the nearest NPC to myself.
The main hurdle of this system was that in its raw form, it also tracked the NPC_TEMPLATE entities studding the map. These entities serve as spawn-points for zombies and other NPCs, but are themselves totally intangible and effectively non-existent. The problem being that the drone had no awareness of this, and would attack the templates and become stuck attacking them until a live NPC got closer to me than the template. This problem was remedied with a simple exclusion parameter on the Find. Excluding specifically objects of that class.
For efficiencies sake, since the Find functions are quite Operations intensive (querying every entity on the map for its Class) I limited the Find functions to use a timer system to update every couple seconds. This had the minor issue that the drone would continue to attack dead NPCs thinking they were still viable targets for at most a couple seconds, but would immediately switch targets once updated or another target got closer. This was partially remedied by tracking the isAlive() function on all targets, should any die, they would be removed from the list and the next lowest target would move up. This sped the drone’s target swapping up greatly however one problem remained.
The drone’s behaviour from my perspective was that it was cruising through the trees, silhouetted against the skybox due to the draw-distance. I was aware that it was doing a lot of travelling in between kills as the kills would appear in the top-right of my screen like any other Source based FPS.
It wasn’t until I built my holomap that I realised the behaviour problem the drone had.
It was tracking the nearest target to myself; however NPCs were coming at me from multiple directions. This meant that the drone had to criss-cross the area I was in on almost every kill, early on at least, I was occasionally killed by my own rapidly moving drone as it flew across my path at high speeds. Using myself as a center for tracking had the advantage that few if any NPCs ever got near me, but meant the drone was ignoring clusters of enemies in favour of killing one of them and moving back across to another group, this instead of killing the entire group to minimise travel.
My best effort at improving this system was a partial success; I simply moved its tracking center to itself. So the drone would attack the nearest enemies to itself at all times. This instantly solved the issue of destroying groups of zombies, but meant that very often the drone would ignore zombies that were attacking me in favour of clearing the opposite end of the map. The drone was more efficient at killing, but not so good at protecting me, which was its primary purpose anyway.
I haven’t worked more on the drone since, but my theory is that if I program it to switch modes, tracking independently when there are no targets within a certain range of myself, and tracking relative to myself otherwise, the system may prove more effective.


Turret control
Turret control has been something I have been completely at home with for the past five years of playing Gmod. My turrets have become so accurate and quick-tracking that I have pretty much stopped working with them as turrets. I still use the same code in building mechanisms due to the precise angular-movements however. Consequently, this was the single easiest part of the entire drone. Both parts of the drone, its body and its turret are actually turret code. The body has to be stabilised so it remains upright, and it yaws to face whatever it’s tracking. Essentially a limited turret,
The actual turret assembly simply hovers relative to the body, maintaining the correct angles to hit whatever it’s aiming at.
In other projects, I might make more sophisticated systems, accounting for things like target-leading and bullet drop, however in this case, the ranges and the hit-scan behaviour of the guns means that if it’s pointing at the target, firing will cause a hit no matter what. Ideal circumstances.
The drone’s accuracy in combat is not actually very good due to a combination of factors, mostly the relative motions. The turret is moving at high speed, as is the zombie it’s attacking (being a fast zombie) so the turret has some trouble accurately striking. This is compounded as the target list actually consists of three different kinds of enemies; Fast Headcrabs, Fast Zombies and Combine soldiers.
The target acquisition system is tied directly into the target-position system, my elegant solution was to check for the center of mass of the NPC, but apparently NPCs center of mass is actually between their feet anyway. I tried using the hit-box dimensions, but NPCs again are awkward. My eventual solution was to simply offset up from the default position by varying amounts depending on target type. In inches, Headcrabs took 5, Zombies took 50, and Combine took 60.
In each case this equated to a shot aimed roughly between the shoulders, more than large enough a target to compensate for the movement inaccuracies. I did some experimentation with rapid-fire vs. single-shot weapons for the drone, and found that rapid-fire afforded it some more efficiency overall, the inaccuracy of the drone was enough that I couldn’t rely on it striking its target with every shot. So I generally use full-auto. It means that a switch of targets results in very rapid termination of the targets in a given area. The most I have seen to date was five targets in under a second and a half. This is also due to the target acquisition system being geared to switch targets extremely quickly. In cases where the targets are all close together, they are all the top targets on the Target list. Meaning that as each one dies it is deleted from the records and immediately replaced by the next target, resulting in extremely quick changeover.
This is a clear advantage over the Target Finder devices available to standard Wiremod, these devices are known to take anywhere up to half a second to update once a target is lost.
As far as fire-control is concerned, I chose to simply use the range to target. In nearly all cases, the drone would almost certainly have a clear line of sight to its target at mid-ranges, in the event that a tree was in the way, either the NPC would move, or the drone would. The drone was set to circle its target when in a certain range, simply maintaining distance and applying a lateral movement. This meant that in nearly all cases, any obstacles would be bypassed quickly. To that end, the firing stayed range-based. When in range, the gun would fire, regardless of whether it actually pointed at its target. This indiscriminate fire would often claim several nearby zombies as collateral so I felt no need to limit it. It did however kill me a couple times when in close-quarters with the zombies. Particularly when I hadn’t managed to tune the target-positional offsets for head crabs and a swarm of them attacked me, chased and rarely killed by the drone which was shooting over the top of them. As alternative methods, I could have run a ray-trace from the gun to ID whatever it was aiming at to ensure it didn’t shoot at me. This would have advantages as I could tune it to shoot only at targets on its hit-list, or I could make it shoot only its specific current target. This second one would be of minimal advantage in this scenario, however it might be practical in role-play scenarios for an assassination robot.

Other Behaviour and Features
When the drone has no targets, it takes its fire-control and targeting offline, moves to station-keeping at a set distance from me, and uses my own aim-position as a target to track. For fun, I fitted the drone with a search-light mounted to its turret. It just looked cool that way. The result is that the drone will follow me around and move to engage any NPCs that spawn before returning to help provide a spotlight. I may experiment with using the drone during the HL2 single player levels. Though I would have to adapt the design a little; the base-station for the drone currently is static, though there is no reason not to attach those parts to the drone itself beyond adaptability. It is easier to update an E2 when it isn’t attached to a fast moving HK.