Pathfinding for Tower Defense(redblobgames.com)
redblobgames.com
Pathfinding for Tower Defense
https://www.redblobgames.com/pathfinding/tower-defense/
64 comments
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
This is a fun puzzle, I got up to 124:
https://imgur.com/a/L3OcJpA
Ah, just now noticed this:
https://news.ycombinator.com/item?id=18802763
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.
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.
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.
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.
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?
A few collections of free assets you can use:
https://www.kenney.nl
https://opengameart.org
http://www.pixelprospector.com/graphics/
https://www.kenney.nl
https://opengameart.org
http://www.pixelprospector.com/graphics/
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.
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/
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/
Try Unity3D! The Asset store has more art than you will ever need, especially if graphical consistency is no priority
agreed
I've been to several game jams where I see amazing prototypes come up in 24-48 hours where people use free or really cheap $5-$40 asset store assets
https://www.google.com/search?q=unity+assets+for+prototyping
It's arguably one reason why there are a glut of games. Not only do engines like Unity and Unreal make it easy to get started but their asset stores have starter kits for almost any type of game. FPS, 3rd person platformer, racing, tower defense game, 2D platformer, etc there's a kit that you download and just start skinning.
https://assetstore.unity.com/search?q=category%3A90&sc=templ...
I've been to several game jams where I see amazing prototypes come up in 24-48 hours where people use free or really cheap $5-$40 asset store assets
https://www.google.com/search?q=unity+assets+for+prototyping
It's arguably one reason why there are a glut of games. Not only do engines like Unity and Unreal make it easy to get started but their asset stores have starter kits for almost any type of game. FPS, 3rd person platformer, racing, tower defense game, 2D platformer, etc there's a kit that you download and just start skinning.
https://assetstore.unity.com/search?q=category%3A90&sc=templ...
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.
Dungeon Warfare is a really refreshing take on Tower Defense. I can highly recommend it. Works good on mobile as well.
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.
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.
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.
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.
Yeah, you are right, it just happens to remind me day 15. The description is surely not the best, but I don’t think it’s hand wavy, it went great length to explain what happens which I appreciate. What frustrates me is it does not help me to discover certain edge cases. But it reflects reality, there are bugs you can never imagine until you run into.
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.
That sounds very similar to what I experienced, my bug was that a player A plays twice in a round because it steps into a spot yielded by player B which died in the same round. My mistake was bookkeeping in an incorrect (which is only so for a few cases) way. Hope that helps.
I love tower defense games but I could never find one that is either complete or not filled with ads/paytowin
Honestly the best tower defense games are still Warcraft 3 custom maps, which is getting a refresh with Reforged. I'd recommend YouTD personally.
There are custom game modes for Dota 2 and some of those are pretty good tower defense games.
I spent so many hours playing Wintermaul back in the day.
I miss the old model for games where you simply pay one (albeit higher) price and get everything.
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.
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.
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.
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.)
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.)
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.
Is Sanctum fun to play with friends? I'm thorn between buying a single key (3 euros) or four keys (7 euros) on steam.
Sanctum wasn't much fun after a few levels. We ended up playing Dungeon Defenders instead. Still do now and then, great fun with the whole family. Just don't buy Dungeon Defenders 2, it's not as good and very buggy.
If you've got friends I think it's worthwhile, I played most maps either solo or with one friend, occasionally we got a full group too.
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.
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
[1]: http://www.hexage.net/defense/index.html
Check out Dungeon Warfare: https://store.steampowered.com/app/355980/Dungeon_Warfare/
defense grid 1 and 2
Definitely. I played the first one to death. And it had a plot!
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.
Checkout Gemcraft on Steam.
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
https://ufoot.org/liquidwar/v5/techinfo/algorithm
Oh man, Liquid War. That brings back memories. I'll have to give Liquid War 6 a try. Thanks for the nostalgia.
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.
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.
> It is funny... the manual tells you a lot about the game ... just not how to actually play.
That feels fitting for a GNU project. Copious amounts of information, little of it immediately useful for your current question.
That feels fitting for a GNU project. Copious amounts of information, little of it immediately useful for your current question.
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...
Here is a link to a blog post about my game.
https://russell.ballestrini.net/yuletide-trains-and-homegrow...
A* is very simple.
It's crazy how often this website gets posted on HN for it's pathfinding tutorials.
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.
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.
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.
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.
It always feels like cheating the system, although harder game difficulties are typically balanced around that mechanic.
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
GemCraft TD's solves this by making it more and more expensive to build each block.
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.
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.
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.
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/
http://gemtowerdefense.com/
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.
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.