Hi All,
I am working on an RTS where the player can place roads in straight lines (no splines) and I want the AI to find the way from building A to B autonomously without the need of a NavMesh.
Whenever a road is placed (or “drawn”), I only collect the “corner points” or crossings with other roads in a way point array. Resembling a standard A* algorithm, I would need to iterate through the entire array of viable way points to determine the adjacent ones and then calculate the distance between them. Furthermore, I would need to store the calculations of every sub-step in case a followed path turns out to be a dead-end (which could be possible in the setup of the game).
So my question relates to improvements of efficiency of this computations as it scales up quite badly.
I should pre-sort the entries of the array somehow (by adjacency?) to exclude the irrelevant way points. There won’t be any chunks of roads in the game, each road must be connected to the initial center point leaving me with one giant array that I would have to iterate over.
If I sort the entries based on distance to the center point and evaluate the distance of (start → center) and (end → center), will it reduce the number of overall calculations needed? Can’t think of a way to achieve that…
Any thoughts on this topic are highly appreciated, even if you recommend following a completely different approach (as long as it doesn’t involve a NavMesh, it would need to reach over the entire map)