Tower defense games on the computer automatically determine the shortest path the monsters can travel using any number of mathematical methods. One of those methods is called Dijkstra's algorithm. The problem with computer pathing methods is that often times, they are testing lots and lots of potential paths, to find the one that is the shortest. The computer has lots of computational capability so this happens in an instant. However, humans are not so talented. In optimization speak: as the solution space increases (due to the game map getting larger), the number of possible paths to check increases, which increases the time it takes for people to calculate the shortest path the monsters could take. The more time spent calculating the monster path, the less fun the game is.
We spent two days trying all sorts of different pathing methods: Shortest path required lots of computation. In this variant you'd place walls to block the path and then you would have to recalculate the shortest path. Numbers on tiles, basically monsters have to go from a high number to a low number, when given a choice of where to move. So you would have to have preset maps and then place numbers Catan style, on top of those tiles to (optimization speak: form a gradient) make the monsters walk "downhill". Dials that point the way, these would be spinning dials twister style, that pointed which way the monsters could walk from each tile. I'm sure there were more methods. Eventually we were so engrossed in this adventure that my older sister KN, told us we had to stop and spend time with family. So much for fun holidays! After months of testing, Asya and I finally settled on arrows, which is a variant of the Dials from above. The arrows would be printed on the tiles. This proved to be the most computationally efficient method for humans to solve while still providing some ability to change the monster path. So while Dijkstra's algorithm might provide a computationally efficient way of finding the shortest path for computers, we had developed a computationally efficient pathing method for human computers. We'll call it the AHN method (Aretskin-Hariton Norris). AHN doesn't need a targeted end point that typical algorithms require. End points in tower defense games are usually "your base" which is at some fixed location and the monsters are trying to run there. We initially had a castle tile that the monsters were trying to get to, but when we left behind shortest path, we didn't need castle anymore. The side effect of getting rid of the castle is that we had to change the loose conditions: It doesn't matter where the monsters run as long as they don't run off the map or into a mountain or in a circle. The picture below is from about three months in. We have laser cut our first board (more on that later) and just figured out that we want pathing by arrows. Notice, there is not castle tile so there is not specific endpoint the monsters must walk to. We have a 4x6 map which can be resized to 6x6 based on the number of players. We are playing with blue monsters instead of purple monsters.
0 Comments
Leave a Reply. |
AH Games
Tiny Independent Game Design and Publishers Archives
August 2022
Categories |