Pathfinding for Tower Defense

https://www.redblobgames.com/pathfinding/tower-defense/

by ingve • 8 years ago

264 63 8 years ago

Just an FYI: The Dijkstra map algorithms mentioned in the article can be used for a lot more than just pathfinding.

I’ve used them in a hobby game I’ve been developing with a lot of insight from http://www.roguebasin.com/index.php?title=Dijkstra_Maps_Visu... To implement things like determining if resources are connected to an in game road network. I’ve also used them extensively for the game’s AI for all sorts of different purposes.

Truly a handy tool to have in a game maker’s belt.

Waterluvian• 8 years ago

This kind of thing gets me eager to play around with game systems but the art gets in my way. I need to find a kit of generic assets that I can use to experiment with game systems development. Maybe that's why roguelikes are so attractive for this kind of thing?

kris-s• 8 years ago

A few collections of free assets you can use:

https://www.kenney.nl

https://opengameart.org

http://www.pixelprospector.com/graphics/

blackbrokkoli• 8 years ago

Try Unity3D! The Asset store has more art than you will ever need, especially if graphical consistency is no priority

Impossible• 8 years ago

Sketchfab (https://sketchfab.com/store/3d-models) and itch.io (https://itch.io/game-assets) both have healthy asset marketplaces as well. Unreal also has a decent asset store and Epic has released high quality assets for free (https://www.unrealengine.com/en-US/paragon, https://www.unrealengine.com/marketplace/open-world-demo-col..., https://www.unrealengine.com/marketplace/infiltrator-demo) and Unity has done the same for some of their high-end demos. Unity asset store also has small prototyping kits for cheap. I like https://www.oryxdesignlab.com tilesets for small roguelikes and RPGs as well.

rpeden• 8 years ago

Roguelikes are one way to solve the art problem.

As someone else mentioned, the Unity asset store has plenty of assets too - some are free, and many others are reasonably priced. There are plenty of 2D assets available, as well as 3D if that's what you're looking for.

Last time I checked, the TOS/EULA says you can use Unity purchased assets outside of Unity games, too - as long as you download them through the Unity editor. So you could potentially use the art assets you buy there even if you want to write your own game engine from scratch.

You might be able to find what you need here, too:

https://opengameart.org/

fenomas• 8 years ago

One thing I do in my game is use pathfinding to find suitable places for doors connecting rooms.

The process is, I randomly place some adjacent rooms, completely surrounded by walls. Then I set up a pathfinder (A*) where the cost of moving through walls is large but finite, and the cost elsewhere is tuned so that long detours can cost more than going through a wall. Then I run the pathfinder between various rooms, and place a door wherever the resulting path went through a wall.

This results in doors situated on "desire paths", so they look more or less like they were intelligently placed. It's also tuneable; you can tweak the costs to either get lots of doors and very convenient paths, or minimal doors while still having every room be reachable.

billfruit2• 8 years ago

I do like how the enemy swarms move in Dungeon Warfare, some randomness is present so that all of the minions don't follow the same beeline, rather moves organically like a crowd moving through a corridor.

hopfog• 8 years ago

Dungeon Warfare is a really refreshing take on Tower Defense. I can highly recommend it. Works good on mobile as well.

onychomys2• 8 years ago

The article is from 2014. We should put that year in the title.

dkersten• 8 years ago

Why does the year matter? Its not time-sensitive news or information.

lainga• 8 years ago

It's just an HN custom

kibwen• 8 years ago

Upvoting before I even read the article, and if you browse the other articles on the site you'll see why. Red Blob Games is a fantastic resource, check it out.

wycy2• 8 years ago

This would’ve been a handy article to have read before/during Advent of Code 2018. There were multiple path finding problems I struggled through.

teacpde3• 8 years ago

Oh man, day 15 is almost a party pooper to me, not because of the algorithm, but the edge cases. Took me ages to debug. It gives me perspectives to game development.

masklinn• 8 years ago

I don't know that it's quite similar though: advent's day 15 is about replicating exactly the algorithm used by the system designer, except using a somewhat hand-wavy description. Because of the testing methodology/system, it adds a lot of complexity to the task of aggro/pathfinding.

wycy2• 8 years ago

Yeah, my day 15 part 2 is still somewhat bugged. At termination, I print out 6 possible answers, each of which represents an off-by-one error. My correct answer is fortunately one of these: its the round * (elves HP + 3), which indicates that my elves sustain one too many attacks before the game ends. I still have no idea where this extra attack is coming in, but I’ve basically given up on perfecting my day 15 code. It was incredibly frustrating.

pouta3• 8 years ago

I love tower defense games but I could never find one that is either complete or not filled with ads/paytowin

slantyyz• 8 years ago

I miss the old model for games where you simply pay one (albeit higher) price and get everything.

maccard• 8 years ago

There are still plenty of games coming out at 15-20 dollars/euro where you get full access to the game, and ongoing development (which you did not have in the "old model"). Plenty of these games have additional content more akin to an expansion pack or even standalone game for reasonable prices.

You can also now find many games where you experience the full game for free, and you can spend a small sum on cosmetics. Again, going back to the old model, those games didn't have 7/8/9/10 different skins available for each player.

As much as the battlefront/fallout 76 style games are getting bad press, in my opinion it's never been a better time to be a gamer.

meroes• 8 years ago

Honestly the best tower defense games are still Warcraft 3 custom maps, which is getting a refresh with Reforged. I'd recommend YouTD personally.

imtringued• 8 years ago

There are custom game modes for Dota 2 and some of those are pretty good tower defense games.

tnecniv• 8 years ago

I spent so many hours playing Wintermaul back in the day.

billfruit2• 8 years ago

You can try Dungeons of the Endless, Amplitude Studio's refreshing mashup of dungeon crawling and tower defense.

pouta3• 8 years ago

Thank you, it looks amazing and it's on sale in Steam

onychomys2• 8 years ago

On Android, I play a lot of infinitode, which is totally ad free and has the best upgrade tree I've seen in any game ever. It's wonderful.

sigstoat• 8 years ago

defense grid 1 and 2

DamnInteresting• 8 years ago

Seconded! I love those games. The dialog is cheesy, but in a deliberate and non-obnoxious way. I just wish there was an easy way to wipe away all of my progress in those games and start anew, so I can play another clean play through. I've read some tutorials about how to wipe game data, but it always comes back via Steam cloud (unless I disable cloud sync for that game, but then I cannot play it across PCs). Frowny face.

AndrewDucker• 8 years ago

Definitely. I played the first one to death. And it had a plot!

Jach2• 8 years ago

What do you mean complete? Like you thought it ended too early or what?

One of my favorite tower defenses is Sanctum, on the PC. It's a tower defense with casual FPS elements. (Its sequel I didn't like as much, it's more the other way around as an FPS with casual tower defense elements.)

pouta3• 8 years ago

They felt like an unfinished product, don't remember why.

Is Sanctum fun to play with friends? I'm thorn between buying a single key (3 euros) or four keys (7 euros) on steam.

Reedx• 8 years ago

Check out Dungeon Warfare: https://store.steampowered.com/app/355980/Dungeon_Warfare/

pxndx• 8 years ago

I downloaded dungeon warfare (a suggestion from another comment chain) and it doesn't have ads or p2w elements. It was 3 eur in the Android play store.

munificent• 8 years ago

I really love Radiant Defense, by Hexage [1]. Great gameplay, good art, charming storyline, and you can pay for a full version and there are zero ads.

[1] http://www.hexage.net/defense/index.html

Riverheart• 8 years ago

Checkout Gemcraft on Steam.

awirth• 8 years ago

This reminds me of the documentation for how the game Liquid War did their pathfinding. The interesting relevance is that it does not use a uniform grid when calculating the gradients, but instead coalesces squares into power-of-two squares to "cheat"

https://ufoot.org/liquidwar/v5/techinfo/algorithm

Cyphase• 8 years ago

Oh man, Liquid War. That brings back memories. I'll have to give Liquid War 6 a try. Thanks for the nostalgia.

tonetheman• 8 years ago

I looked that game up Liquid Wars 6 is a GNU game. Who knew.

https://www.gnu.org/software/liquidwar6/manual/liquidwar6.ht...

It is funny... the manual tells you a lot about the game ... just not how to actually play. Sigh.

foxhop• 8 years ago

Woah very cool post. I've been planning to learn enough graph theory and the astar algorithm for pathfinding to make the non-player agents in my game have enough intelligence to find a target, whether that is a point on the map or the player itself.

Here is a link to a blog post about my game.

https://russell.ballestrini.net/yuletide-trains-and-homegrow...

aisofteng• 8 years ago

A* is very simple.

Ecolog• 8 years ago

It's crazy how often this website gets posted on HN for it's pathfinding tutorials.

Dzugaru• 8 years ago

I’ve always wanted to find a blog post somewhere about SC2-style swarm pathfinding. Dijkstra part is simple and there are many resources about it, whats hard is avoidance - units shouldn’t walk through each other. Achieving that smooth and correct wave-like motion of zerglings isn’t easy - I’ve tried but the results were ugly.

MaulingMonkey• 8 years ago

https://www.gamedev.net/forums/topic/597457-pathfinding-in-a... discusses some of the stuff StarCraft 2 uses, http://www.gameaipro.com/ has some stuff including for the other SC2, Supreme Commander 2 ( http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd... ) that solves similar issues.

egeozcan• 8 years ago

This could be a hard problem as many games fail to solve it. There's also the problem of idle units giving way to the ones on the move and formations and stances and many other stuff. In the end, you get some sort of compromise.

minimaxir• 8 years ago

A common tactic in the build-your-own-path TD genre is yo-yoing; that is, blocking a path to force the creeps to go the long way, then sell the created block and immediately block the long way, forcing them to go back the long way. Rinse and repeat.

It always feels like cheating the system, although harder game difficulties are typically balanced around that mechanic.

toxik• 8 years ago

Most tds I play don’t allow changing your maze during rounds

drsopp• 8 years ago

I remember fondly analyzing the old facebook game Maze Defence, and proving that the optimal ratio between area dedicated to towers and area for paths is .5

Moru2• 8 years ago

GemCraft TD's solves this by making it more and more expensive to build each block.

sowbug• 8 years ago

I don't know why I love tower-defense games so much, but I think it might be because playing feels like programming. Nearly every TD game I've played is deterministic; in fact, I think random gameplay elements would ruin the appeal. That means the challenge of the game is not being lucky or twitchy, but rather figuring out the rules and how to optimally apply them. That's also what I like about programming.

loosetypes• 8 years ago

Kind of depends on at what level your thinking about though.

In most games some towers can have a random aspects in deciding where/ what to attack. This can lead to variation of outcomes when replaying a given wave but amortized over an entire game the results are more-or-less static on a percentage basis.

Which is amusingly similar to probabilistic algorithms, so maybe that just reinforces your point.

izend• 8 years ago

I created a flash version of Gem Tower Defense 11 years ago because I was attracted to the randomness of the gameplay. I recently release a free iOS version.

http://gemtowerdefense.com/

diziet• 8 years ago

If this interests you, check out https://www.pathery.com/, a long standing project where the goal is to use a limited number of blocks to make the longest path possible.

Const-me• 8 years ago

I did the same a decade ago: http://const.me/articles/robocalypse-pathfinding/

Source code is available but I'm not sure it'll work with modern compilers. Unlike that article, I did not use dynamic memory while updating the vector field.

redcodenl2• 8 years ago

Given the maze on the website, what is the highest number you can get on a square when creating a maze?

This is a fun puzzle, I got up to 124:

https://imgur.com/a/L3OcJpA

redcodenl2• 8 years ago

Ah, just now noticed this: https://news.ycombinator.com/item?id=18802763

Pathfinding for Tower Defense

Related Stories