Sorry your browser is not supported!

The game concept is simple - stop enemies from reaching the right side of the playing area using the selection of towers available. Destroying enemies gives you coins which you can use to buy more turrets (or unlock more powerful turrets). For a twist there's also a "drop" system where enemies sometimes drop "gems" or "diamonds" which need to be collected with special collection towers. The gems and diamonds are used to upgrade towers which often adds more projectiles per volley and increases damage and range, etc.

One of the challenges for this game was the collision detection system. In my previous games I always checked every possible collider once every frame, however I discovered that wasn't going to work in this case due to the sheer volume of projectiles on screen when things get busy. I was seeing a big slow down in performance on my relatively beefy hardware when the game started checking 2500+ collisions PER FRAME. Every projectile on the playing area was checking for collision against every enemy on the playing area. What a waste, so I knew I had to implement a system to cull the sheer number of collision checks.

The answer was "spatial partitioning" where I basically divided the playing area into a 10x10 grid of "cells". Each enemy "keeps track" of what cell it's in after updating it's position, and the projectiles only check collision against enemies in the same cell.

The result? 86 times fewer collision checks and ultra smooth performance even on mediocre hardware and even with huge numbers of agents active in the game!

Nice

Optimizing the collisions is nice too.

i dig TD games and haven't played one in awhile so, whenever a demo's ready, so am i

For sure and it will be soon. I am still working on a handful of graphics/particle effects and tons of "polish" on the UI end still needs to be done.

The most interesting development involves balancing & tuning the waves of enemies which is really the hardest part and would normally take the most time. It needs to be challenging enough but still possible to beat, so I would need to go through lots of playtesting to tweak how hard the waves are and how much coins & gems you get, and the cost of towers (unlock / buy / upgrade) etc.

It gave me an interesting idea that I have now been working on the last couple of days involving a pseudo-machine learning system. I don't know if you are familiar at all with machine learning but here is the basic idea:

The program runs dozens of "instances" of the logic portion of the game code instead of just one. The game is actually really simple in terms of data, there are just three arrays of objects - the turrets, projectiles and enemies. The logic portion of the game code moves enemies across the playing area, causes turrets to fire at enemies in range (create a projectile object), and makes the projectiles move according to their properties etc. Instead of using AppGameKit pixel perfect collision checking, the "logic only" threads use a simpler distance calculation and considers a collision to be when the projectile gets "close enough" to the enemy.

AGK is still used to render any one of the threads you want to watch. You basically "tune in" to any one of the instances currently playing out and the AppGameKit engine will render objects from that thread to the screen. That way I can see what the AI agents are actually up to.

With machine learning you don't actually tell the AI anything about playing the game besides the possible input controls and defining some conditions for what should be considered "progress" or "good". In this case the input controls are very simple, all the human player can do is build, unlock, upgrade, or move towers (might introduce sell tower as well).

So the AI gets the same ability, it can build any towers that are currently unlocked, or it can unlock any tower it can afford to, or it can upgrade a tower it previously placed on the map, or it can move a tower it previously placed on the map. The code also limit AI to one action per second so that it's similar to a human rate of play.

In terms of what the AI actually chooses to do, machine learning involves using "feedback" from previous threads of the game. The basic idea is that you want to repeat (closely but not exactly) previous threads actions that led to "progress" signals. In this case progress is defined as destroying more enemies, earning more coins and gems, and of course reaching higher waves. Negative signals are introduced when enemies "leak" and "lives" are lost.

So at first when the program starts there is no "feedback" at all because there are no previous threads. In the very first threads the code will simply attempt anything - completely randomly. Each AI thread "records" it's actions and the timestamps of those actions in an array. The more "progress" a thread makes the higher "weighting" it's given in the feedback system. The next threads to start the game will use "weighting" from the most successful previous threads thus far to make it's decisions. So now each thread will approximate what has already led to progress previously, BUT allow for small changes so as to possibly discover an even better solution. If a thread achieves a better "progress" at an earlier time stamp then it takes the "lead" in the weighting system.

The result? The AI constantly improves by "brute force" towards the point that it eventually plays the game with 100% perfect efficiency.

The point of the whole thing though? I can use this system to actually tune and balance the game very tightly between "challenging" and "impossible" which will make it that much more fun and more interesting to keep playing and try to get further.

I am not quite there yet however. The heart of this idea of course is the "progress" and "feedback" system that influences the AI actions in future threads and the algorithms are turning out to be quite challenging. I think I am getting there though, and we'll find out soon if there's any merit to the whole endeavour.

re: "spatial partitioning", i always imaged using SetSpritePhysicsIsSensor would be ideal? i've used the command but not with near as many moving parts.

I'm not sure, what's your specific idea for using it in this case?

Lovely when you see massive performance increases with some extra code!

If sprite sensors were set up based on your "partitions" u could know what sprites were in each, as u are already doing but without "each enemy" keeping track of anything. I dont know if there are predictors in box2d (our version) that help (further) efficiency. This is theory. If i get time, i'll try to write a demo. But Im sure your method is working great. It just stirred the theory back up for me and am curious about your thoughts on it/if u'd tried it

back with a quick demo:

(continually setting Velocity = 30 just to show that you can change that anytime - ie, follow a path)

it works but not quite like i expected it to where anything passing through the shape of the sensor HAS to be under Box2d control. IE, i thought i could march the enemies thru with normal SetSpritePosition but the sensor does not sense Contact or Collision when i do. Hence why i gave the enemies Velocity to march.

i know its not quite the same implementation of your spatial partitions but the functionality is? IE, "what's within" or "what's around" (this defined shape). and since Box2d already has some "magic" under the hood, along with being multi-threaded, i figure it SHOULD be max efficiency/performance?

Ok yes I understand your idea now. My implementation for the partitioning is actually very simple. First I declare an array of [10][10] of type "list" (a list in c++ is basically an array with some built in functions).

To "figure out" what cell an enemy is in is actually exceedingly simple in my case. The playing area size is 4000 x 2000 so I just divide the enemy X position by 400 and Y position by 200 to get a number between 1 and 10 for each dimension!

Here's a snippet of the actual code from the Enemy::update() function in my game:

I should also mention something else. In the snippet above I was using the "center position" of the enemy sprites (position by offset) and putting them in the appropriate cells based on that point alone. That doesn't account for when part of the sprite is in one cell and part of the sprite is in another cell. There was the rare occasion that a projectile "slipped" through a piece of sprite without "colliding". I realized that in fact one enemy sprite can technically be "straddling" the borders between up to 4 different "cells", but it's only reporting presence in the cell where its center pixel is located.

I've since switched the function to check 4 points (the four corners of the sprite) and figure which cell for each of those points. Now when an enemy is not wholly contained in a single cell it can report presence in up to 4 different "cells lists" at the same time.