I’m making a TD game in HTML5. For some reason, however, it bogs down when placing towers on the creeps path. From what I see on the profiler, the A* isn’t the problem. The problem is creating the navmesh. So far it’s a simple grid, with gcost computed by looking up the collision detection quadtree. The path also feels blocky. (I am also about to remove the quadtree and use prune and sweep with kd-trees).
What I want to do is:
1. Create a vertex array of the graph by pushing vertices of the staticCollisionObject array (without redundant vertices).
2. Do rays between them. Bruteforcing, it’s O(n^3), extremely slow. However, I think there is some way of doig it in O(n^2) without cheating using some kind of tree structures Better, but still probably slow. (also pruning for head-on edges)
3. Perform A* for the resulting graph consisting of the vertex array and the edges.
However, I feel that the step 2 will be too slow, so I will probably do some cheating. The question is, what kind of chating?