LOS for patfinding in a TD?

3 posts

Flag Post

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?

 
Flag Post

Isn’t it too complicated for a TD? I didn’t understand what do you want from monsters to do with towers – reading about all this maths, I assume you want towers to be obstacles with cost, right?

 
Flag Post

How are you calculating the safety/danger cost from being within range of turrets?

What’s questionable is whether or not the use of navmeshes is appropriate