Logic behind path finding... Sort of
Ok so I'm in the process of developing a 2D tower defense. There will be a set path for the enemies to travel on, though I'm not sure on how to go about implementing this movement. There will be turns and what not, and I don't know how to go about doing that. I was thinking maybe a bitboard kind of structure? I would need something that would be relatively efficient in checking often
EDIT:
I know of a few algorithm's that I could use, but I'm not sure if it would be neccesary/how to do it. I have depth first, breadth first, and dijkstra's in mind. Though the latter would be the last choice, I'd say, since there is only path and weight is irrelevant
EDIT:
I know of a few algorithm's that I could use, but I'm not sure if it would be neccesary/how to do it. I have depth first, breadth first, and dijkstra's in mind. Though the latter would be the last choice, I'd say, since there is only path and weight is irrelevant
Last edited on
When I started a tower defense game way back when I approached this differently.
If the map is based on a rigid "grid", you can assign each tile on that grid a value which represents the direction towards the exit.
Wipe the map clean, then start at the exit, and recursively set all surrounding tiles to point to the current tile. You can also give them a "weight" which determines how many tiles away they are from the exit (that way you don't start going in circles, or having suboptimal paths).
I might still have the source for this at home.....
EDIT: anyway, the idea was that the monsters will typically need to know their path a lot more often than the path actually changes. So by having the path sort of built into the map like this, they just follow whatever direction the tile they're currently on points to. When the user places a new tower and potentially changes the shortest path, you rebuild the whole map and all enemies will instantly shift directions to the new shortest path.
EDIT2: Yeah I totally did have the source, but it's really ugly. I didn't realize how old this was:
http://www.filefactory.com/file/7lh6o6mp7vlj/n/towerlogictest.zip
Source and binary included. Forgive the crappy upload site.
Here's a pic of how the program looks:
http://i47.tinypic.com/202rmv.png
If the map is based on a rigid "grid", you can assign each tile on that grid a value which represents the direction towards the exit.
Wipe the map clean, then start at the exit, and recursively set all surrounding tiles to point to the current tile. You can also give them a "weight" which determines how many tiles away they are from the exit (that way you don't start going in circles, or having suboptimal paths).
I might still have the source for this at home.....
EDIT: anyway, the idea was that the monsters will typically need to know their path a lot more often than the path actually changes. So by having the path sort of built into the map like this, they just follow whatever direction the tile they're currently on points to. When the user places a new tower and potentially changes the shortest path, you rebuild the whole map and all enemies will instantly shift directions to the new shortest path.
EDIT2: Yeah I totally did have the source, but it's really ugly. I didn't realize how old this was:
http://www.filefactory.com/file/7lh6o6mp7vlj/n/towerlogictest.zip
Source and binary included. Forgive the crappy upload site.
Here's a pic of how the program looks:
http://i47.tinypic.com/202rmv.png
Last edited on
This seems like a lot of extra calculations for what I'm doing. Imagine a game like Bloons TD. The path in there is completely static, the player can do nothing to alter it. This is the approach I'm going at this with.
| If the map is based on a rigid "grid", you can assign each tile on that grid a value which represents the direction towards the exit. |
I think this is still a good solution to the problem. Your path never change so you can hardcode the grid values if you want.
Last edited on
After giving some thought to this, I think I'm gonna give it a try both ways and see how it works out.
Have a question though, how would be able to check to make sure there is a path still? It would be possible for a player to be able to just make an impassible wall.
Sorry, I'm quite new to pathfinding :/
Have a question though, how would be able to check to make sure there is a path still? It would be possible for a player to be able to just make an impassible wall.
Sorry, I'm quite new to pathfinding :/
You can see that in my picture I uploaded. There is an enclosed section where the tiles are marked with '?' because they have no path to the exit.
With my approach these areas are found because I wipe the entire map to that '?' state. I then move over the entire map starting from the goal -- so if a tile has no connection to the goal, it will never be iterated over, and therefore remains a '?'.
With my approach these areas are found because I wipe the entire map to that '?' state. I then move over the entire map starting from the goal -- so if a tile has no connection to the goal, it will never be iterated over, and therefore remains a '?'.
Let's say I draw a line from the top to the bottom, this makes no path available from the entrance to the exit. Wouldn't this cause an issue?
Yes.
You can catch that, though. When the user tries to build a tower, you recalc the map to see how the path has changed. "no path" tiles will be marked as such. If the enterance or any of the tiles that enemies are currently standing are are "no path" tiles in the new map, you simply disallow the tower to be built where it was.
You can catch that, though. When the user tries to build a tower, you recalc the map to see how the path has changed. "no path" tiles will be marked as such. If the enterance or any of the tiles that enemies are currently standing are are "no path" tiles in the new map, you simply disallow the tower to be built where it was.
Topic archived. No new replies allowed.