Starting a tower defense game (and Dijkstra)

One of the other topics I’ve been learning about recently has been XNA and MonoGame. With these two technologies, you can develop a game for Windows, Win8, Windows Phone, iOS, and Android – all with the same codebase! If you want to learn about these, you MUST check out the courses on Pluralsight – they are top-notch!

If I were going to create a game, what kind would I make? Well, the kind of games I typically like are “tower defense” games. That is where you have an enemy (or enemies) coming in on one side of the screen, and you have to built up defenses to stop them from getting to your homebase on the other side. Plants vs Zombies is a popular example of this.

One of my favorite games to play on iOS, and Windows is Radiant Defense. In fact, I’d probably want to model a game after this concept, but I’d change quite a few things. What I DO like is that the game shows you the “path” that the enemy will take. You can build up walls and install guns along that path obviously.

Whenever you put up a “module” which stops the path of the enemy, the path diverts:

image[7]

image[14]

This is probably the biggest obstacle for me. How do you actually figure out what the shortest path is? Well, we discussed this today at the tail-end of staff and we ended up re-remembering the Dijkstra algorithm. We did a code challenge about just this topic in an internal user group meeting last year.

Dijkstra’s Algorithm finds the shortest path between two nodes. It weighs the “weight” of the connections between each node to do this.

So, I pieced together some code I found on the ‘net and got this working! The idea is that the game screen would be a grid. In each grid square you can build things. Once built, I figure out the optimal path for the enemy to take and then the level starts.

For a simple 3×3, it worked every time and runs sub-second. As I made the grid bigger, it started taking MUCH longer. If my game is similar to the one above, we’re talking about an 11×21 grid (and some maps go much larger!)

In my code, just to create a proof of concept, I tried to create this small 9×3 grid. The line represents the path I would LIKE this algorithm to find:

Untitled 

I create all my vertexes and edges, run it – and whammo:

Path=A1 – A2 – A3 – B3 – C3 – C2 – C1 – D1 – E1 – E2 – F2 – G2 – G3 – H3 – I3

Untitled2

Wait a minute, that’s not quite right at the end. I double, triple, and quadruple checked to make sure I have everything set up correctly – and I do, but the solution is not coming out correct for these larger grids. Specifically, towards the end of figuring out a larger grid it starts getting messed up.

Worse, MUCH worse, is how long it took to run:

Algorithm time: 00:00:25.5250502

It took 25 seconds on my desktop computer – so how long would this take on a tablet? Even it was still 25 seconds, this is obviously not even approximately acceptable!

I fear I might be at a dead-end. I could certainly run the algorithm through the profiler, and try to make it more efficient – but will I be able to make it 25x as efficient? Probably not. I guess I have a few options… I could just only allow certain paths for each map. I could also use the Plants vs Zombies approach simply have columns of enemies that always attack in a straight line. Lastly, I could also pre-calculate all the possible permutations. This doesn’t seem reasonable because even for my 3×9 grid, there are 60,480 possible combinations (if I did my math right). And if my math is right, a 10×20 grid would be 2,432,902,000,000,000,000 possible permutations!!

Those are alternatives, but I’d really, ideally like to do it this way where I figure out the path in code. I’ll see if I can refine the algorithm and get it running any faster. Meanwhile I’ll see if there are alternative algorithms that might do this faster!

Posted in Uncategorized, XNA and MonoGame

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
Categories

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 5 other followers

%d bloggers like this: