Post by Adam Schmelzle on Jun 24, 2008 8:40:50 GMT -5
After finding other things to do for nearly a week, I'm back at this again...
I am currently trying to find a way to determine if building a tower will permanently block the baddie path. It's not hard to figure out, but I want to do it in O(c) constant time, instead of O(n^2) or whatever. I want to detect it before the user tries to build, so there is an indication on screen that the user is not allowed to build the tower at the current location. I don't want it to slow the game down though, which is why I'm requiring O(c) time of whatever solution I come up with.
I currently just build the tower, re-calculate all the paths, and then if the path is blocked, I can un-build it. This works fine, but waits for the user to try to build. I can do the path blocking detection in O(c) time if the start and end of each path segment is touching a contiguous section of wall, but not when the end points are in separate disconnected parts of the level.
If I simply do a depth-first search, with tweaks and modifications, I can eliminate 99% of the work load, but that's not a very elegant solution.
This problem may force me to keep the paths attached to contiguous wall sections. Not like it's a deal breaker, since that's how most maps end up being anyway. This would only effect one of my current test maps.
Any suggestions?
I am currently trying to find a way to determine if building a tower will permanently block the baddie path. It's not hard to figure out, but I want to do it in O(c) constant time, instead of O(n^2) or whatever. I want to detect it before the user tries to build, so there is an indication on screen that the user is not allowed to build the tower at the current location. I don't want it to slow the game down though, which is why I'm requiring O(c) time of whatever solution I come up with.
I currently just build the tower, re-calculate all the paths, and then if the path is blocked, I can un-build it. This works fine, but waits for the user to try to build. I can do the path blocking detection in O(c) time if the start and end of each path segment is touching a contiguous section of wall, but not when the end points are in separate disconnected parts of the level.
If I simply do a depth-first search, with tweaks and modifications, I can eliminate 99% of the work load, but that's not a very elegant solution.
This problem may force me to keep the paths attached to contiguous wall sections. Not like it's a deal breaker, since that's how most maps end up being anyway. This would only effect one of my current test maps.
Any suggestions?
