ara at May 10th, 2014 07:36 — #1
There is a problem with canon movement. Well actually several problems :
- the movement restriction is coupled with the firing restriction.
This forces long movements when short ones are available, one have to make a complete rotation while it's not necessary here:
It can also completly prevent acces to some firing zones
A solution would be to create two maps, a firing one and a movement one : (well map is a big word for a list of segment identified by their limit angles) the movement is restricted to the movement one and when one tries to fire it checks if you are in a firing interval.
- there is only one level of the canon that is checked for movement (and firing):
So this kinda work :
But this doesn't:
A solution would be to create several maps at different angles of the canon along with their transitions and use a shortest path algorithm + smoothing for the angle.
I could find references / algorithm if you'd like to implement but don't want to spend too much time thinking about the details.
nition at May 10th, 2014 17:28 — #2
Excellent post. Getting this system perfect is a challenge. There's a reason why Robocraft doesn't even try - you can't even place weapons if they don't have full range available to move and fire in that game.
As you've noticed, it only does simple angle limits at the moment - min/max horizontal and min/max vertical. Even now, there isn't always only one solution. If there are multiple solutions, the current system will try to choose the one that leaves the largest total movement area available. It also requires the 0,0 angle to be available and it always works from there, to preserve my sanity as a programmer.
What sucks is that as a human, it's easy to see straight away where the weapon should be able to go, but man is it hard to calculate mathematically. I actually wasn't able to find any existing algorithms or papers on this problem myself, so if you do find something relevant I would be interested. Maybe every time you place a part, it should hand off the calculation to Amazon's Mechanical Turk...
One of the benefits of the current system is that it doesn't have to path-find constantly - it only has the recalculate the min/max range if vehicle parts change.That does mean it has to ignore moving parts (you'll notice that the range calc ignores weapon barrels). But the ideal system which I think you're describing is something like:
- Create a map of everywhere that the weapon can reach (one for movement, and another for firing), starting from its zero position
- If there are multiple available movement areas that don't connect, select the largest one (or let the user select)
- In-game, path find from the weapon's current position towards the closest position on the map to where the user is aiming, and the weapon can fire (movement-only areas are just for passing through)
- Bonus: Also make this run fast enough to recalculate weapon ranges on-the-fly when parts are destroyed in-game
Two challenges there:
- How to create an accurate angle map of where the weapon can move to
- How to path-find through that map always in the best possible way
It took me two attempts to get the current system to reliably give the "best" result. I'm not keen to tackle it again just yet because I can see it being a huge job. If someone else had already solved this exact problem it'd be a different story, but so far I've had to solve it myself.
You make a very good point about movement vs firing range which I hadn't really thought about. That part of it I might be able to do something about.
ara at May 12th, 2014 19:13 — #3
I'm really sorry I don't have more time to dwell on that right now but, in short, this is a well studied robotics problem known as the motion planning problem. There exists many algorithms (and libraries but mostly in C++ and Java) that address this kind of problem but basically the idea is always the same, consider the set of acceptable positions of your robots (based on obstacles, self intersection and joint limits) aka, the free space, and move through this set from your current position to the position you want to go to. The most simple technique invoke a simple sampling and collision check to represent the free space as a grid (in your case you have 2 variables: the angles of the canon to the horizontal and to the vertical so a 2D grid with holes where you have obstacles).
nition at May 12th, 2014 19:52 — #4
Thanks, that's a starting point anyway.
I've tried two different systems for calculating the available range (as I said I couldn't find any real existing literature on this, so I made these up):
First I found blocked areas by raycasting. I'd cast rays e.g. 2 degrees apart in a spherical grid around the weapon's available range and reduce the range when something was hit. I assume that's what you mean by "sampling and collision check"?.
The major problem with that was that due to the margin of error between raycasts, there was always some edge case part arrangement that wouldn't reduce correctly, and there had to be some error as a trade-off to performance.
The current system checks against the bounds of all colliders on the vehicle directly. It looks at what parts of the weapon's range need to be off-limits based on the collider locations and tries to select a "best" option where the most weapon range is left available.
It now works with no errors, but as you've seen its functionality is limited to simple min/max angle reduction. It also makes moving the weapons around in-game easy (the only slightly difficult part is making a gun go the long around around if it needs to to get somewhere).
I can't really afford to dedicate more time to it now, unless there's actually an easy drop-in solution, but it'd be great if it allowed more advanced movement.
ara at May 16th, 2014 14:51 — #5
Yes, definetly something along those lines.
I can't promise anything in term of deadlines right now but if you give the general strucutre of how to check the bounds or the colliders in your code I'll try to write some code for that.
nition at May 18th, 2014 17:08 — #6
No pressure, but here's some info:
Weapons have a MinX, MaxX, MinY and MaxY angle. A weapon pointing straight forward is at angle 0, 0. Values are currently in degrees, where the min is a negative and max is positive angle. X is up (min) and down (max). Y is left (min) and right (max).
Imagine that == is a cannon facing to the right on the page
Weapons also have a bool flag for whether Y-axis rotation is limited at all. The large cannon has unlimited Y rotation (Y min/max are just ignored) unless it's blocked by something.
X-axis (up/down) rotation is currently limited to not more than 90 degrees each way (180 total). Y-axis (left/right) rotation can also be assumed to be <= 180 each way. This might make calculations simpler.
Y is up in Unity. Z is forward.
The weapon's range needs to be checked against colliders on the vehicle.
They're all un-rotated boxes (they're actually rotated in multiples of 90 degrees, but a box rotated 90 degrees is still an un-rotated box). So they can be checked with a simple AABB collision check or a raycast can check for a collision with them.
Note that although parts are generally snapping to a grid, colliders aren't in any sort of grid pattern - they're just located wherever they're needed to cover the part models. In practice I found that a raycast method was never accurate enough to get things right every time (unless the raycasts were made very closely-spaced, but performance is important here too).
Each part has a collider that just covers the whole part, on top of the more specific colliders that cover it more accurately. This can be used as an early check: If the encapsulating collider isn't hit, none of the inner ones will be. If it is hit, we can look more closely.
Part colliders are also inside an octree, so you can so fast collision checks on a specific area if necessary. Currently it accepts AABB bounds and returns all colliders that intersect those bounds. Alternatively if you need to check every collider, you can just run through an array of them all.
ara at May 19th, 2014 16:37 — #7
Thanks, that's pretty clear. As soon as I've got some time I'll write you something.
nition at May 19th, 2014 17:35 — #8
A few more things I forgot:
- The system also needs to understand weapons having zero range on one axis. e.g. the small machine gun can move up and down a bit, but Y axis movement min/max are 0/0.
- Weapons have a "barrel size" which is just a number that's the diameter of the barrel. It's useful especially if raycasting, since the thickness of the weapon barrel needs to be taken into account.
- To calculate weapon available movement range (as distinct from firing range), barrel length will be needed as well. You can assume that's available.
- There's a "can't fire" bool flag that can be set if the weapon has no available range at all (currently that happens if the straight forward firing angle is covered)