I made a quick velocity obstacle prototype last night. Above is video shows of some example scenarios.
I used similar velocity sampling and side bias in HRVO. It is cool how some test cases result almost symmetrical results. The last bit in the video uses more random start locations and parameters which makes the movement more random too.
I'll release the sources once I get it a bit more cleaned up.
In order to get smooth results, the prototype clamps the max acceleration (which is the reason why the agents sometimes collide) and also slightly smooths out the perceived velocity which is used to calculate the VOs.
The test cases do not exhibit too much flickering in the velocity selection, but I think it is a problem. I will do a couple of other protos to see if there could be simple way to make more coherent velocity selection with some simple extra logic.
Looks good!
ReplyDeleteOf course the problem with obstacle avoidance is that it works differently if the objects are, for example, cars, people or airplanes.
Each having different properties on how they would turn and accelerate/decelerate.
A person, for example, could also step sideways (strafe) more easily.
It might look better if you have a turning velocity as well, that accelerates/decelerates.
(it certainly wouldn't make it easier though)
Keep up the good work!
That's true.
ReplyDeleteI'm making an "action game enemy" assumption here :) Ideally I would like to be able to get something working which could be used with different steering implementations. Still assuming that they are roughly humanoidish. That is, they can be represented as discs and have reasonable velocity and some sort of acceleration deceleration. But I dont want to constrain too much how the actual movement code is implemented. We'll see :)
Impressive amount of work for one night, I wish I was as productive!
ReplyDeleteCouple of questions if you've got time.
1) Your implementation of VOs, how do they differ from opensteer?
2) Are you planning integrating this stuff into detour or as an added layer on top of detour, or not at all?
3) Animation speed is a problem with VOs as they speed up/slow down. How I handled this was to pre process/analayse the model animation and calc the distance travelled by looking at the bones. Each frame I calc the distance travelled by the VO and play the correct amount of animation for the distance.
1) I could find implementation of VOs in opensteer. It has a couple of methods to avoid obtacles and neighbours, but it does not try to solve the problem with same accuracy as VOs try to.
ReplyDeleteA really naive implementation of VOs could basically do the sample time-of-impact test as opensteer does for obstacles in many directions around the agent and choose the one that has highest score. The score could be determined by how far you can move into that direction and how close the new velocity is from the requested velocity. This is pretty much what RVO library does: http://www.cs.unc.edu/~geom/RVO/Library/
Steering behaviors in turn are trying to solve the problem by soft pushing things away. This works in many cases and creates pleasing results, but IMHO the results are much much harder to correct once things go wacky (in games, they always do).
So from my point of view, steering behaviors solve the local steering problem 80% of the cases, and I hope that I can increase that percentage beyond 95% with VOs.
2) Yes, that's the long term plan. For the time being, I try to find a local path planning method that satisfies me.
3) NPC locomotion animation is indeed a beast on its own. My hope is that I can get the steering code to be as robust as possible to that the path animation code will have easier time to cope with it . I have no plans at this point to dive into this, though.
Great work Mikko. Thanks to RVO and your work here, I think "solving" dynamic obstacles in the near future is very possible!
ReplyDeleteHowever, the catch is I don't think we should be looking to solve these things mathematically. All the samples I've seen so far, including yours, are very mechanical and almost robotic in their perfection. It's very good, but a crowd of people wouldn't be have like that at all.
I'm curious what it'll take to go beyond such a technical solution, and find a social solution that works as a crowd would. For example, people get to their positions eventually, but some stop and get confused, some move around, some run, some replan, etc.
We're possibly not far from that working either, but I've not seen anyone address this yet.
Alex
Alex, I agree. After fiddling around a bit with different time steps yesterday, I was a little less impressed with VOs (again) :)
ReplyDeleteAt the speed of movement you see in the vidoes you need to update the VOs at least 15 times per second, or else they move really bad.
The thing I was after with that experiment is that when dealing with animation it is important to try guess the future a bit in order to get good looking animation out.
Also, I like that the movement is robotic. If I can make the robotic movement 99% robust and predictable, I think I have greater change to dress it and make it more smooth.
I think I have to go through the animation stuff you (Alex) have done and see if I can meet somewhere it the middle.
Also, I think that simulating a crowd has different goals than simulating an individual. It is different level of detail that is important.
In a crowd it does not matter if one person is sliding against a wall and moonwalking like crazy, but if you look at an individual to do that it is unacceptable.
There's a recent paper on crowd modeling, where they concentrate on crowd movement and it looks totally awesome until you start to follow individuals.
Aggregate Dynamics for Dense Crowd Simulation
http://gamma.cs.unc.edu/DenseCrowds/
Your comment was really good, because it made me to refine my goal :) I think my goal now is to have rock solid (no collision, no sliding, good avoidance) movement which is easy to dress with animation.
I think I'd rather handle confusion ans such a bit higher level. For example it the agent is deviation too much from the expected path, etc. But I'd like the movement to be as robust as possible at first, even if it means that it is slightly robotic and cold.
Yeah, I agree with that approach, we need to have solved the avoidance problem before moving on I think...
ReplyDeleteLooking forward to seeing your results!
Alex
P.S. My approach to the animation stuff has shifted a bit recently, in the same way. I think we need animation to be able to follow specified paths exactly (as good looking as the assets allow), then we can start giving more freedom to the animation afterwards.