I'm making a Tower Defense game in Flash with no predefined path.
Although my grid is 40x40 (small?), A* is struggling when recalculating every time. So I made my own modification to ease the recalculation and the touched cell count dropped to around 900 (when modifying near the root). It still freezes for a very short, but detectable, amount of time when a new tower is placed.
Is this an implementation problem, or is 40x40 just too much?
The structure of my code:
- All the data is saved in 2d array of cells.
- Each cell contains its parent in path direction (1-8 clockwise) and bitwise encoded array of its children in path (every bit represents a child).
- The search is performed by A* with the estimate of euclidian distance.