8 ms·
Pathfinding for Tower Defense
- benjaminjackman 8y agoJust 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_Visualized 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 8y agoThis 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 8y agoA few collections of free assets you can use: https://www.kenney.nl https://www.kenney.nl https://opengameart.org https://opengameart.org http://www.pixelprospector.com/graphics/ http://www.pixelprospector.com/graphics/
- blackbrokkoli 8y agoTry Unity3D! The Asset store has more art than you will ever need, especially if graphical consistency is no priority
- tokyodude 8y agoagreed 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 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=templates/packs https://assetstore.unity.com/search?q=category%3A90&sc=templ...
- rpeden 8y agoRoguelikes 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/ https://opengameart.org/
- Impossible 8y agoSketchfab (https://sketchfab.com/store/3d-models https://sketchfab.com/store/3d-models) and itch.io (https://itch.io/game-assets 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/en-US/paragon, https://www.unrealengine.com/marketplace/open-world-demo-collection https://www.unrealengine.com/marketplace/open-world-demo-col..., https://www.unrealengine.com/marketplace/infiltrator-demo 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 https://www.oryxdesignlab.com tilesets for small roguelikes and RPGs as well.
- fenomas 8y agoOne 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.
- onychomys 8y agoThe article is from 2014. We should put that year in the title.
- kibwen 8y agoUpvoting 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.
- wycy 8y agoThis would’ve been a handy article to have read before/during Advent of Code 2018. There were multiple path finding problems I struggled through.
- teacpde 8y agoOh 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 8y agoI 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.
- teacpde 8y agoYeah, 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.
- wycy 8y agoYeah, 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.
- teacpde 8y agoThat 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.
- pouta 8y agoI love tower defense games but I could never find one that is either complete or not filled with ads/paytowin
- slantyyz 8y agoI miss the old model for games where you simply pay one (albeit higher) price and get everything.
- maccard 8y agoThere 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 8y agoHonestly the best tower defense games are still Warcraft 3 custom maps, which is getting a refresh with Reforged. I'd recommend YouTD personally.
- imtringued 8y agoThere are custom game modes for Dota 2 and some of those are pretty good tower defense games.
- samstave 8y agoHow can I find these?
- 8y ago
- awirth 8y agoThis 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
- Cyphase 8y agoOh man, Liquid War. That brings back memories. I'll have to give Liquid War 6 a try. Thanks for the nostalgia.
- tonetheman 8y agoI looked that game up Liquid Wars 6 is a GNU game. Who knew. https://www.gnu.org/software/liquidwar6/manual/liquidwar6.html#In-a-nutshell 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.
- kbenson 8y ago> 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.
- foxhop 8y agoWoah 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-homegrown-video-games/ https://russell.ballestrini.net/yuletide-trains-and-homegrow...
- aisofteng 8y agoA* is very simple.
- Ecolog 8y agoIt's crazy how often this website gets posted on HN for it's pathfinding tutorials.
- Dzugaru 8y agoI’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 8y agohttps://www.gamedev.net/forums/topic/597457-pathfinding-in-a-space-based-rts-game/ https://www.gamedev.net/forums/topic/597457-pathfinding-in-a... discusses some of the stuff StarCraft 2 uses, http://www.gameaipro.com/ http://www.gameaipro.com/ has some stuff including for the other SC2, Supreme Commander 2 ( http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd... ) that solves similar issues.
- egeozcan 8y agoThis 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 8y agoA 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 8y agoMost tds I play don’t allow changing your maze during rounds
- deleted 8y ago[deleted]
- drsopp 8y agoI 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
- Moru 8y agoGemCraft TD's solves this by making it more and more expensive to build each block.
- billfruit 8y agoI 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 8y agoDungeon Warfare is a really refreshing take on Tower Defense. I can highly recommend it. Works good on mobile as well.
- sowbug 8y agoI 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 8y agoKind 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 8y agoI 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/
- diziet 8y agoIf this interests you, check out https://www.pathery.com/ 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 8y agoI did the same a decade ago: http://const.me/articles/robocalypse-pathfinding/ 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.
- redcodenl 8y agoGiven 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 https://imgur.com/a/L3OcJpA
- redcodenl 8y agoAh, just now noticed this: https://news.ycombinator.com/item?id=18802763 https://news.ycombinator.com/item?id=18802763