Change Log (1.1):
- Integrated Unity Navigation for unit pathing
- Modified Grid System to be independent of models/shaders
- Added fast rectangle marquee selection system (No Ray-tracing)
- Added temporary artwork (So my eyes stop bleeding)
- Created R-Tree system (WIP)
And here's a video demonstrating the selection system and Navigation integration:
A note on the Navigation. The building is also a NavMesh, since they will be dynamically added. Currently NavMeshes apparently can push each other around. This is a bug I am going to fix, not a strange design choice.
First thing that came to mind is unprojecting the unit's position from world-space to screen-space. Then simply checking whether the new point was within my rectangle would determine if it is selected. This only works for the single point of the unit's pivot, meaning my rectangle could intersect with most of the model without selecting it. So I simply added a radius and made it a circle. The circle is then tested for intersection with the selection rectangle and more accurate, if still approximate, selection is determined.
There are a few shortcomings with my system, however. Firstly, circles by no means accurately express all models' shapes. Also, my method [currently] doesn't take into account perspective. That is, the circles don't scale with distance from the camera. I have a solution to this but I am unsure if it is necessary or fast enough to be worth it, since my RTS camera may not create much perspective anyways. I'll just save that for another update.
This will be used to sub-group units and items into proximity based bounding rectangles (R for Rectangle). The R-Tree will allow for fast look-up of units based on position. So, for instance, when calculating precise line-of-sight, I only want to check units close to a given unit for efficiency. This allows me to quickly obtain these units.
I am not quite happy with the amount of overlap in the tree at the moment, so I will be working to minimize overlap and area of rectangle groups when I integrate it into the Grid system.
I'd be happy to go into more depth in any of the techniques mentioned or unmentioned, so feel free to post a question in the comments below!A note on the Navigation. The building is also a NavMesh, since they will be dynamically added. Currently NavMeshes apparently can push each other around. This is a bug I am going to fix, not a strange design choice.
Selection {
The most accurate way to select an object is to trace rays from the camera's mouse position, into world-space and check for collisions with objects. For rectangular selection, the amount of rays needed increase dramatically. Since I want this system to be able to run on mobile platforms, I needed a faster method.First thing that came to mind is unprojecting the unit's position from world-space to screen-space. Then simply checking whether the new point was within my rectangle would determine if it is selected. This only works for the single point of the unit's pivot, meaning my rectangle could intersect with most of the model without selecting it. So I simply added a radius and made it a circle. The circle is then tested for intersection with the selection rectangle and more accurate, if still approximate, selection is determined.
There are a few shortcomings with my system, however. Firstly, circles by no means accurately express all models' shapes. Also, my method [currently] doesn't take into account perspective. That is, the circles don't scale with distance from the camera. I have a solution to this but I am unsure if it is necessary or fast enough to be worth it, since my RTS camera may not create much perspective anyways. I'll just save that for another update.
}
R-Tree {
And for those interested in some technical background, here's a video demonstrating the current progress of my R-Tree spacial data structure.This will be used to sub-group units and items into proximity based bounding rectangles (R for Rectangle). The R-Tree will allow for fast look-up of units based on position. So, for instance, when calculating precise line-of-sight, I only want to check units close to a given unit for efficiency. This allows me to quickly obtain these units.
I am not quite happy with the amount of overlap in the tree at the moment, so I will be working to minimize overlap and area of rectangle groups when I integrate it into the Grid system.
}
-K
Interesting concepts. I'm currently trying to program some detection AI in Unity, and I'm wondering how you implement your R-tree data structure? How would you code for proximity based bounding rectangles?
ReplyDeleteI'm currently using the physics.overlapsphere function on all of my agents (I have 300 total, and want to double that if I can). The problem being when all the agents are in close proximity, the cpu processing involved in physics.overlapsphere causes sharp noticeable framerate chugging.
Anyways, I'd be very interested as to how to sub-group units, so I don't have to have ai checks on every unit in my game. Or to make array building less intensive, and iterations much quicker.
Hey Anonymous,
ReplyDeleteYeah your problem's pretty understandable. Physics calculations, albeit simple ones, computed in n^2 time is not ideal. So spatial data structures could help you out, R-tree's being one of them.
First off, I'll admit I actually ended up not using my R-Tree and replacing it with a Quad-Tree. My reasoning is R-Tree's insertions and deletions are expensive, and any object that moves has to be deleted and re-inserted every update. And my units move often. Quad-Trees have slower query times than R-Trees though, so if your objects don't move very often (or at all), that might be better.
Quad-Trees separate a given region into 4 sub-regions and each of those into more sub-regions, etc. Each leaf node holds all the objects inside it's region. So in order to find a given object, you only need to compute O(4d + m) queries to find your object, where d = depth and m = maxAmountPerRegion, a quality setting. You can read more about them here: http://en.wikipedia.org/wiki/Quadtree
With my solution, I needed inserts and deletes fast, so I pre-expanded my Quad-Tree until it reached a given depth, and then allowed for the leafs to hold zero up to a max amount. Then it splits if it surpasses the max, and on deletions joins back to the initial depth. In its use, I simply give it a Rect or a Circle, and it returns the objects inside the given query region.
Does any of that make sense? I might post about my quad-tree solution soon when I get a chance. Then I can go into more detail and post some actual code snippets or maybe my entire solution.
Hey Katlan, thank you very much for the reply.
ReplyDeleteMy objects will be moving a lot, just as you said yours will be as well. So taking into consideration what you said, a Quad-Tree would most likely be better for my game. It is good to know insertions and deletions are expensive in R-Trees before I actually spend time constructing one, only later to find out it does me little good.
I understand what you are saying in theory and in concept (I ran into quad-trees while I was researching R-trees after coming across your blog), however I have no idea how to begin actually coding one. Could you maybe point me to some online examples or intructions on how to actually code a quad-tree? Even a short "this is how you create the first set of sub-regions" in actual code would be great.
I am relatively new to game programming, but far enough along that I want to see what a quad-tree solution can do for my game. I'm currently coding in Unityscript (Javascript), however I can usually convert from C# pretty well. If you do end up posting your quad-tree solution when it's finished, and especially some code snippets, I would definitely appreciate it.
Best of luck, and I really like how you implemented your selection process. There is so much more I want to learn, but I will just leave it at that. Thank you.