What do you suggest would be the best algorithm for a tower-defense game? It's a 2D based tile game, where there is walls and towers blocking the way, between spawnpoints and their destination points.
Constantly, as the player places a new tower to block the way, or to help shoot spawning units before they reach their destination, a new path for the affected spawnpoint's path will have to be recalculated, and the units must be re-routed to that new path.
Therefore, I need performance.
I tried the A* algorithm, but everytime the player places a new tower, and path has to be recalculated, the existing units who haven't gone past the tower yet, get lost, and stand still, since they were a part of the old path that has now lost its pathing information.
Answer
A* should be plenty fast enough. Each time a tower is placed you should calculate a new path for each spawn point, and assign that path to each unit that is spawned there. You should also calculate a new path for the units "in the field". Units in the field can have their paths calculated as the shortest path to get back on track, as in a path to the new path. Or the units can have their path calculated from their current position to the destination.
You can likely save calculations by grouping units in the field and calculate a common path for them all. For example if you have a group of units in tile (4,7), they can all use the same path, so you just have to calculate it once.
Additionally (depending on what your rules are) you should consider doing these calculations as a check before the tower is placed. This will disallow the player from placing towers that block all paths. Or as some tower defense games work, if the play blocks all paths, the units just ignore towers when path finding.
No comments:
Post a Comment